The APL Orchard

7:12 AM

@dzaima Disappointed to not see any of the BQN symbols there.

@EliasMårtenson I just copied my list of APL symbols from paste's APL formatter. BQN symbol counts would probably be low enough to not be nearly as meaningful

Elias Mårtenson

@Adám when I follow the link to the online documentation from here: dyalog.com/documentation_180.htm#CORE it send me to version 17 instead of 18.

I presume that the page hasn't been updated?

Adám

@EliasMårtenson Ah, yes, I'll have that fixed.

Elias Mårtenson

8:29 AM

@dzaima What if you do it for only BQN symbols?

xificurC

interesting debate about language design and a language's purpose during the weekend! I think people are building their languages with different reasons/goals, and that's fine :)

Elias Mårtenson

I'm only asking because I find BQN symbols to be quite refreshing. :-)

xificurC

there was a question whether R qualifies as an array language. What are the requirements for a language to be one?
E.g. in clojure there's a lot of work right now to enable high performance ML and statistics, which naturally means implementing an array processing core. See [here](https://github.com/techascent/tech.ml.dataset) or [here](https://github.com/cnuernber/dtype-next) where there's a direct reference to APL :)

ugh, what's the syntax for links

Razetime

@xificurC [name](URL)

Elias Mårtenson

@xificurC I don't think it has anything to with runtime performance. It has to do with how you express solutions to problems.

Razetime

8:36 AM

remember to add http://

@xificurC problem here is chat markdow doesn't work in multiline messages

Elias Mårtenson

There is much to dislike about markdown, but its URL syntax must be the worst.

Razetime

@EliasMårtenson what do you think would be better?

dzaima

@xificurC My 1 requirement is that 1+[1,2,3] must be [2,3,4] with whatever array syntax, but a single regular +. (my additional requirement for an "APLy" lang is the existence of reduce and each operators, plus-reduce being the idiomatic way of summing)

@EliasMårtenson another issue is that much of my BQN code is in paste links, which i can't look at currently

regardless, count of BQN chars (this time, actual count) in the messages after BQN was first mentioned:
https://dzaima.github.io/paste/#0VZLPbtNAEMbvforhCoLuer2OLQHiwTgEtWqdbRygjZVQNYTSf1RU4oJaJFqQ0mMOvIOfgEdgv5mJbG7fb3dn5tuZoS0ia8rSpgk9J6LcWZMl9LKTzyBNVviEXkTpnXfx9FWUtrBZDHsKaW1mEnoSJaXO24QeEb8wLqG2mjPYLMLqG2uDgqsv0FS6mLsNnwVsmdDDjHUxiPoxy9zH9K9F4kW7@57Bu0GEkcRmeP9wqxpJx/cCnkMOGVyZRxj@FsgBo08CaXz2d9FcKcF7fS2AVrRVYEhLQD0RGHCGE4E8xc1IIAUMxVtq4GcpP7alBVz1YFwJFHA62@9BOFXI2JxmKLixlwLyVzFnc6SrGwFuT63p2E@lCUyR0PpYNS7CD5IJFOhVo2C5qKQmWGjPN@BwNb3vqK1@CQyQIrztwehMAX6qjz2oDxRgO8hUKY8fX31XjfjlsUJ8tZIJ…

Elias Mårtenson

@Razetime What @dzaima said. It'd be a bit more general and say that if the “natural” way to solve certain problems is by performing array operations, even though other approaches may exist, it qualifies.

xificurC

9:01 AM

@dzaima that can't possibly work for a language that designs + as non-overloadable without having the support baked into the language. It seems like a rather arbitrary requirement. I mean you could rebind + in clojure but, like, you shouldn't :) That doesn't make a namespace-qualified + any different though.

(def test-data (dtype-fn/+ (range 10 0 -1) 5)) ; => (15 14 13 12 11 10 9 8 7 6)

Elias Mårtenson

@xificurC It doesn't have to be literally called +. It's more of a mindset, along with the actual technical capability of the language to perform certain oprtations succintly.

dzaima

@xificurC that's exactly my point - + must, at a minimum, map over an array, built into the language

xificurC

@dzaima so your definition is also that array capabilities must be built-in and not a library

dzaima

@xificurC well of course, the question is about an array language

@dzaima if it needs some mapping builtin or a for loop, as far as i'm considered, the array language aspect is gone and it's now just a language with map/loop builtins, which JS is one of

@xificurC any language can gen an "array library", assuming the language allows for libraries that define functions..

xificurC

@dzaima sure, I'm not arguing, just trying to understand the distinction you're making. I was lulled here by the ToT vision, not by the array processing capabilities though. As you said, you can get those from a library

@dzaima so what qualifies? APL, J, K, BQN, any other "well known"?

dzaima

9:14 AM

@xificurC also R

Elias Mårtenson

Q?

dzaima

@EliasMårtenson Q is pretty much just K as far as this is considered

interestingly enough, Julia doesn't pass, but allows adding two arrays

Elias Mårtenson

@dzaima Ok, good to know. I never used K nor Q.

There are letters left in the alphabet. Someone should make L.

dzaima

@dzaima ah, at 0.7 it's deprecated and before it's allowed. This works in 1.0. don't know how to feel about that

Elias Mårtenson

What single letter languages are there... B, C, D, S, R, Q, J, K?

rak1507

9:19 AM

A

dzaima

@EliasMårtenson iirc there's a lang for every letter. There's V, and surely an A

Dyalog APL

<moon-child> all of them: beza1e1.tuxen.de/one_letter_proglangs.html

<moon-child> (and there are 2 Bs; ken thompson's and arthur whitney's)

xificurC

@Moonchild that raises another meta question - when is something considered a language? I'm sure people have many As and Bs lying around on their hard drives unpublished. Also, is Arthur's b used by anyone?

Adám

@EliasMårtenson All of them.

@xificurC Shakti (K9) is written in B, I think.

rak1507

Wow cool

Dyalog APL

9:24 AM

<moon-child> @xificurC I expect the original b isn't any more popular, at least nowadays. If it has a compiler and you can write code in it, I'd call that a language

<moon-child> @Adám I think it's in c. At the least, it exposes a c interface, and I believe the header that you use to interface it is shared with its source code

dzaima

@DyalogAPL many of the languages there are rather non-practical, so there's definitely some space for more langs

Adám

moon-child: it is "isomorphic to c": kparc.com/b/readme.txt

rak1507

'not interesting right now since i already prefer b and there is no c code we care about' lol

Dyalog APL

<moon-child> yes, but it can't consume c headers. Also, k binary is linked to libc (where b uses its own kernel interface)

<moon-child> also the binary has tail-call optimizations, which probably (?) mean it was compiled by a mainstream c compiler, as those are probably pretty low-priority optimizations for a self-made compiler. (Though there could very well be a newer version of b, different from that one and not public, which invalidates both of these points)

Adám

Quite possible. AW tends to not publish stuff. E.g. kOS is nowhere to be found online (that I know of).

xificurC

9:38 AM

@RGS is there more to learn? :)

Adám

@xificurC How far did the two of you get? (My presentation is ready…)

xificurC

@Adám cool, good luck with it! You have some common curriculum? :)

RGS

@xificurC there is plenty more to learn, I just assumed you kept learning with the other folks when I left

I had a crazy busy weekend, sorry for that

Adám

@xificurC Well, RGS (speak of the…) has observed me teaching.

xificurC

I think we stopped at ⍴ RGS drawing in 3D how a rank 3 array will be filled from a list of values

RGS

9:48 AM

@xificurC I just watched Adám teach plenty of times :D

xificurC

⋄ 2 3 4 ⍴ ⍳100

Dyalog APL

@xificurC
 1  2  3  4
 5  6  7  8
 9 10 11 12

13 14 15 16
17 18 19 20
21 22 23 24

xificurC

@RGS I'm not around during the weekend, family and all that

Adám

@xificurC Pro-tip: use backticks around your APL code. Otherwise, one day, SE chat will think it is markdown…

RGS

(Adám I was at a point when I thought teaching dfns and have xificurC write some small functions would be interesting)

Adám

9:49 AM

Sounds right. Go right ahead. Your presentation is all set too.

RGS

Alrighty then

@xificurC you all set?

xificurC

sure

RGS

Here's a vector v ← 1 2 3 4 5 6. Can you get me the mean of the elements of the vector, please?

@Adám (if that was my only concern :) )

Adám

⍨

RGS

@xificurC should I tag you? Or maybe review some of the things we've seen last time?

xificurC

10:01 AM

@RGS I'm switching a bit back and forth between my work and this, sorry. I am writing something in my dyalog REPL, so far I got to (+/÷⍴)v, which is the average, not the mean

Adám

That's the mean. He didn't say "median".

xificurC

yeah, I'm just re-reading and re-processing

then I'm done!

RGS

@xificurC No problem, just wanted to align expectations. Taking some time is perfectly fine, I'm also doing something else :)

xificurC

mean is average, I keep mistaking it for median

RGS

(+/÷⍴)v is great!

xificurC

10:02 AM

now don't ask for median! :D

RGS

Now do the median!

:P

xificurC

why doesn't +/÷⍴v work?

RGS

First let's turn your (+/÷⍴)v into a function, so that we can reuse it later.

+/÷⍴v is interpreted as +/ ( ÷ ( ⍴v ) )

xificurC

mean ← +/÷⍴

RGS

Whereas (+/÷⍴)v tells the interpreter that (+/÷⍴) is a (tacit) function.

@xificurC Great!

So let's meet a couple of new functions, so that your mean can be used with an arbitrary array.

Razetime

10:05 AM

b-but median..

⋄ (+/÷⍴) 3 4⍴⍳12

@RGS LENGTH ERROR

Welcome @brgal

@xificurC clearly your mean doesn't work for arbitrary arrays :/ Let's fix it so that you can give it an arbitrary array and it'll find the mean over all elements of the array. Is the task clear?

@Razetime We'll get there ;)

xificurC

@RGS it doesn't work because ⍴ isn't correct for rank>1, correct?

⋄ +/ 2 3 ⍴ ⍳10

RGS

10:08 AM

@xificurC That as well. So what do you mean by "⍴ isn't correct for rank>1"? (also, note that the bot doesn't pick up edits, so you have to send a new message)

xificurC

ah, neither +/ :(

RGS

@xificurC So, what seems to be the problem?

⋄ +/ 2 3 ⍴ ⍳6

Dyalog APL

@RGS 6 15

xificurC

@RGS for a list ⍴ returns the count of elements (atoms?)

and +/ returns a sum over a list. But for higher ranks ⍴ doesn't return count and +/ doesn't return a sum of all elements

Razetime

what does ⍴ stand for

xificurC

10:10 AM

@Razetime rho :p

no, in APL :P

shape?

yes, exactly

So what is the shape of 2 3⍴⍳10?

xificurC

2 3

RGS

10:11 AM

Yeah, exactly.

xificurC

I see the right side could change to *⍴ or something along that

RGS

We want to count all elements of the array, not the length of each axis

@xificurC If an array has shape 2 5 2 5 how many elements does it have?

xificurC

ok so the one half is fixed by mean ← (+/÷(×/⍴))

RGS

Yeah, but now we have the +/ problem... So let's understand what f/ really does and then we'll fix it in a simple way, yeah?

⋄ 2 3 4⍴⍳24

Dyalog APL

@RGS
 1  2  3  4
 5  6  7  8
 9 10 11 12

13 14 15 16
17 18 19 20
21 22 23 24

RGS

10:16 AM

⋄+/ 2 3 4⍴⍳24

Dyalog APL

@RGS
10 26 42
58 74 90

RGS

Can you see what happened? (hint, look at the initial shape and at the shape of the result)

⋄×/ 2 3 4⍴⍳24

Dyalog APL

@RGS
   24   1680  11880
43680 116280 255024

xificurC

/ is reduce. In this case +/ reduces (folds) over a "row" to produce a single value

RGS

Exactly, it reduces along the last axis of the array

xificurC

10:19 AM

⋄⍴+/2 3 4⍴⍳24

Dyalog APL

@xificurC 2 3

RGS

(Btw, ⌿ is "reduce first", as it reduces along the first axis of the array, ⌿ is APL + / in a US physical layout)

But we really want to sum over all elements of the array, right? Wouldn't it be nice if you could just turn your array into a vector?

xificurC

∊?

RGS

@xificurC That is a possibility, yes. ∊ is "enlist" and it will take an array and return a vector with all of its simple elements

xificurC

this seems to work mean ← (+/÷⍴)∊

RGS

10:22 AM

⋄ mean ← (+/÷⍴)∊ ⋄ mean 3 4⍴⍳12

Dyalog APL

@RGS 6.5

RGS

Good. Instead of ∊ one could've used , that stands for Ravel.

For simple arrays, they look like the same function:

⋄ , 2 3⍴⍳6

Dyalog APL

@RGS 1 2 3 4 5 6

RGS

Can you find out the difference between monadic ∊ and monadic , by yourself?

xificurC

⋄∊2 3⍳10

Dyalog APL

10:25 AM

@xificurC 3

RGS

I think you missed a ⍴

xificurC

⋄∊2 3⍴⍳10

yeah

Dyalog APL

@xificurC 1 2 3 4 5 6

xificurC

⋄,2 3⍴⍳10

Dyalog APL

@xificurC 1 2 3 4 5 6

xificurC

10:26 AM

⋄,1 2 (3 4) 5

Dyalog APL

@xificurC 1 2 3 4 5

xificurC

⋄∊1 2 (3 4) 5

Dyalog APL

@xificurC 1 2 3 4 5

RGS

Found the difference yet? ;)

Adám

moon-child: do you think we could enable boxing and function display for the bot?

xificurC

10:27 AM

ravel just unrolls the nested array

enlist unrolls the elements as well, if necessary

RGS

Yeah

Ravel gives you a vector with all the scalars, whereas Enlist will enlist all the simple scalars

xificurC

is this "production-grade" definition? I imagine , to create a new large array for a computation only to get discarded later

Adám

:56097413 leading space not allowed in backticks.

RGS

⋄ meanravel ← (+/÷⍴)∘, ⋄ meanravel 2 2⍴(1 0) (0 1) (0 0) (1 1)

Dyalog APL

@RGS 0.5 0.5

Adám

10:30 AM

@xificurC Well, it is rare to want the average of an entire multi-dimensional array.

RGS

@xificurC , is extremely efficient, afaik the data is internally stored as a "flat" array either way

so , does less work than one would expect

dzaima

@xificurC Dyalog does that, but it's just a single memcpy (so very fast), and a different implementation can choose to make it not even that

xificurC

@dzaima a different implementation that what, optimizes it away at compile time?

dzaima

@xificurC either that, or has a way to reference the old array in the new object. e.g. in dzaima/APL monadic , (along with any reshape that doesn't change item count) is always O(1)

Adám

      ]runtime -c 2⍴⍨3⍴1000 ,2⍴⍨3⍴1000

  2⍴⍨3⍴1000  → 5.4E¯2 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
* ,2⍴⍨3⍴1000 → 5.4E¯2 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

This ^ is a ravel of a 1 GB, 3D array compared with not ravelling it.

      ]runtime -c a←2⍴⍨4⍴100 ,a←2⍴⍨4⍴100

  a←2⍴⍨4⍴100  → 5.4E¯3 |    0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
* ,a←2⍴⍨4⍴100 → 2.0E¯2 | +266% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

This ^ is a ravel of a 0.1 GB, 4D array compared with not ravelling it, when the array is referenced elsewhere.

dzaima

10:39 AM

@Adám weird. Either Dyalog is optimizing ,⍴ there, or the reshape is very inefficient (all it has to do is ask for the memory and fill with 2s though, which i'd expect to be about as fast as the move of everything)

xificurC

@Adám if the numbers after the right arrow are the times then in the second case that's an order of magnitude difference, am I reading that correctly?

Adám

@xificurC Yes, makes sense, as the top example is 1.0 GB and the bottom is 0.1 GB.

@dzaima I don't understand. , here does nothing but change the rank and shape vector. All the time is consumed by memory allocation.

dzaima

@Adám for some reason i thought the shape was stored before the main data in Dyalog and so needs moving all data (which now that i think about it, is stupid)

xificurC

is there a way to write mean that instead of transforming the data to conform to our algorithm would translate our algorithm to conform to the data?

@Adám no, I meant that in second comparison the non-ravel code runs in E-3 whereas ravel in E-2

RGS

@xificurC What do you mean?

dzaima

10:45 AM

@xificurC not efficiently at least. That'd need an operator equivalent to f/, but that doesn't exist

Adám

@xificurC No, look at the values, it is 5.4E¯3 vs 2.0E¯2 i.e. 5.4 vs 20.0

xificurC

@RGS reduce in +/ makes + operate on the list. It "changes" + to work that way. Ravel changes the data

Elias Mårtenson

Ravel and reshape are two operations where Dyalog could probably pretty efficiently implement optimisations for. There should be no need for it to copy the content, no?

It could just update the shape in-place.

Adám

@dzaima Right, it is stored before the main data, but we have MAXRANK so the data always begins in the same location relative to the pocket start.

xificurC

@EliasMårtenson only if the array isn't referenced elsewhere

Adám

10:46 AM

@EliasMårtenson Indeed, that's what I just showed.

dzaima

@Adám wouldn't that mean forced wastage of 120 bytes per (scalar) array?

Elias Mårtenson

@xificurC True, but that could be fixed by using some kind of copy-on-write mechanism. I implemented that for GNU APL once, but it wasn't entirely reliable so it was never merged.

RGS

@xificurC ah I see. Then I believe dzaima already answered your question.

Let's do median, now? :D

xificurC

@dzaima I'm not sure I understand what operator you're trying to describe

Adám

@dzaima 32 bytes, apparently, but yes.

@xificurC It'd be an operator just like / but which ignores the shape.

xificurC

10:49 AM

@RGS sure. I'm running back and forth at this moment from the PC so be patient with me

dzaima

@xificurC there's no better way to sum all numbers in a matrix X than +/,X. If you wanted one, you'd need to define a monadic operator like / that ignores the shape

xificurC

@Adám I thought " in J does this

RGS

@xificurC Of course. Just to be sure, the median is the value that sits in the middle of an ordered vector, or the average of the two middle elements if the vector has even length.

Do you have any particular way in which you'd like to implement the median? Or would you like to have me propose an algorithm, so that I can introduce some primitives along the way?

Adám

@xificurC No, it just specifies on which rank arguments the operand is applied, but doesn't ravel. Instead, it "chops" arguments and applies the operand multiple times (if needed). Also, APL spells that ⍤.

dzaima

@Adám so there's some fancy compression (or deferring of shape to another pocket) of rank 15 arrays? Seems like a strange (and very wasteful) solution, but i guess it works

Adám

11:05 AM

@dzaima This may interest you.

xificurC

@RGS I'd like to try and come up with something myself first, if that's ok. But I'm a bit preoccupied so it might take anything ranging from 5 minutes to 1 hour to post

RGS

@xificurC alright, was writing that I have to go for a while, so feel free to post when you have the headspace and I'll check back with you later

xificurC

@Adám I had an inuition ⍤ together with +/ could sum an arbitrarily shaped array without the need to ravel it. I guess I was wrong :)

@RGS ok thx

Adám

@xificurC There is a trick: +/⍣≡

dzaima

@xificurC +/ always decrements the rank of its argument (except on scalars, but let's ignore that), so +/⍤whatever will also always decrement the rank of its argument

xificurC

11:24 AM

@RGS 2÷⍨v[⍋v][⌊2÷⍨⍴v]+v[⍋v][⌈2÷⍨⍴v] is what I came up with. Hard to test in the dyalog REPL as shortcuts I expect to work just don't :) Also I don't know how to define a function yet

Adám

@xificurC What OS are you on?

xificurC

@Adám what's the trick? And is it a solution to the mean question? Is it better/worse wrt performance?

@Adám linux (ubuntu)

rak1507

Doesn't work for something with an odd number of items

Adám

@xificurC Using RIDE?

xificurC

@Adám using the dyalog executable

I tried running it with rlwrap to get basic readline abilities but that's not what happened :)

dzaima

11:26 AM

@xificurC i'd suggest getting RIDE even if you prefer commandline. it'll be easier :)

Adám

@xificurC ^ github.com/Dyalog/ride/releases/tag/v4.3.3463

dzaima

@xificurC dyalog has its own commandline REPL system (it allows editing multiline functions, etc), though i too would much prefer to be able to simply rlwrap

@dzaima (and then in edit→preferences→shortcuts set BK to something more sane (i use ctrl+D), which allows previously inserted lines)

xificurC

11:44 AM

@rak1507 right, so it should be 2÷⍨v[⍋v][⌊2÷⍨1+⍴v]+v[⍋v][⌈2÷⍨1+⍴v]. Not sure anymore, is APL 0 or 1 based?

rak1507

by default, 1, but you can change it with ⎕IO

You can make functions with {}, ⍵ is the right argument, and ⍺ is the left

1 {⍺ + ⍵} 2

xificurC

thanks @rak1507, this then seems to work mdn←{2÷⍨⍵[⍋⍵][⌈2÷⍨1+⍴⍵]+⍵[⍋⍵][⌊2÷⍨1+⍴⍵]}

rak1507

Yeah

I came up with {(+/÷≢) (⍵[⍋⍵]) [∪(⌊,⌈)2÷⍨1+≢⍵]}

xificurC

if I knew how to create locals I would have cached ⍵[⍋⍵] and 2÷⍨1+⍴⍵

rak1507

{2÷⍨+/⍵[⍋⍵][(⌊,⌈)2÷⍨1+≢⍵]} also works

You can do something like {var ← whatever ⋄ stuff}

xificurC

11:57 AM

@rak1507 thanks, so a bit shorter would be md←{a←⍵[⍋⍵]⋄n←2÷⍨1+⍴⍵⋄2÷⍨a[⌈n]+a[⌊n]}

rak1507

Yep

Rather than doing a[⌈n] and a[⌊n] you can do something like a[(⌈,⌊)n]

xificurC

@rak1507 how to read this? (something) (something) [something]

rak1507

Not sure if you've come across trains yet

Right to left

(f g h) x = (f x) g (h x), so (⌈,⌊) n = (⌈n) , (⌊n)

xificurC

[] I only know as array access

dzaima

@xificurC the first something is a function, and the second is an array, so just how you'd read (-) (3 1 4)[1 2 3]

rak1507

11:59 AM

Yeah maybe the whitespace there is a bit confusing

xificurC

@dzaima ah, that makes it middle-to-right-to-left in my brain :)

dzaima

@xificurC yeah, x[y] has lower precedence than function application :P

xificurC

then maybe if I knew what ≢ and ∪ did I might have a chance to read it

dyadic , is concat?

dzaima

@xificurC ≢ is the first element of the shape, and ∪ gets the unique elements of an array

@xificurC yep

xificurC

ah, so you used ∪ to deduplicate the indexes in the odd length case

dzaima

12:03 PM

(btw, unrelated, earlier on you wrote (+/÷⍴). Called on a vector, ⍴ will return a 1-item vector, so the whole result of (+/÷⍴)1 2 3 is a 1-item vector. You should use ≢ there instead (so (+/÷≢)1 2 3 (and if you want it to make sense for higher dimensions too (+⌿÷≢) is even more correct)))

xificurC

why is there a crossed version of every glyph, hurts my head. What is ⌿?

rak1507

Try out ,/ 4 4 ⍴ ⍳16 and ,⌿ 4 4 ⍴ ⍳16 to see the difference

dzaima

@xificurC it's / but it acts on a different axis. Compare +/2 3 4⍴⍳24 vs +⌿2 3 4⍴⍳24 (also look at the shapes). For now just don't worry about it :)

@xificurC x[y][z] is equal to x[y[z]], and should be more efficient (and lead more to the optimized form)

@dzaima i guess it's still not that easy to notice the joining of the two parts. {2÷⍨ ⍵[(⍋⍵)[⌈2÷⍨1+⍴⍵]] + ⍵[(⍋⍵)[⌊2÷⍨1+⍴⍵]]} → {2÷⍨+/⍵[(⍋⍵)[(⌈2÷⍨1+⍴⍵) , ⌊2÷⍨1+⍴⍵]]} is quite a jump for a lot of complexity

xificurC

ok, @RGS with the tips on how to create a function and locals I finished with md←{a←⍵[⍋⍵]⋄n←2÷⍨1+⍴⍵⋄2÷⍨a[⌈n]+a[⌊n]}. After another debate I now understand how that can be simplified to @rak1507's solution of {(+/÷≢) (⍵[⍋⍵]) [∪(⌊,⌈)2÷⍨1+≢⍵]}

RGS

Alright, cool!

Here is mine: {(+/÷≢)⍵/⍨1>|(2÷⍨1+≢⍵)-⍋⍋⍵}

I'm using a couple of primitives you may have not seen yet, namely monadic | and dyadic / as a function, not an operator.

Want to decipher mine or do you want me to walk you through it?

xificurC

12:14 PM

@RGS why ⍋⍋ instead of just ⍋? Or i that a diffferent glyph

no it's the same

@RGS you can tell me the meaning of those new functions and I can try to decipher

RGS

@xificurC It is the same glyph, except I'm using it twice (on purpose)

dzaima

huh, these aren't that different in performance. i expected quite a bit more difference

RGS

monadic | is the magnitude of the argument:

⋄ | ¯1 3 5.6 ¯4.5 1J1

Dyalog APL

@RGS 1 3 5.6 4.5 1.414213562

RGS

And dyadic function / is Replicate:

⋄ 1 0 2 0 3 / 'abcdef'

Dyalog APL

12:16 PM

@RGS LENGTH ERROR

RGS

What am I doing XD

⋄ 1 0 2 0 3 0 / 'abcdef'

Dyalog APL

@RGS acceee

xificurC

@RGS I tried different arguments but ⍋ and ⍋⍋ kept returning the same answer, so what's the catch?

dzaima

@xificurC try ⍋7 5 6 vs ⍋⍋7 5 6

⍋⍋X is an array such that the reordering needed for sorting it is the same as the one for X. Note that X≡⍋⍋X if X is an N-item vector of unique integers 1…N (aka a permutation of ⍳≢N)

xificurC

@dzaima I tried like 4 combinations and they all returned the same :) This one doesn't, although I can't quite grok what it means

RGS

12:23 PM

⍋v is a vector that tells you from where you should pick each element in v so that the result is ordered

so that ⍋v and v have the same length, but the first element of ⍋v isn't necessarily corresponding to the first in v, and etc

dzaima

another way to look at it - the n'th biggest item in X is at the same index in ⍋⍋X

RGS

⍋⍋v tells you where each corresponding item of v goes

And now I have to go again @xificurC :P lunch and then the Dyalog '20 user meeting... Feel free to ping me when you think you understood my sample implementation and we'll go over it as soon as I can

Adám

Announcement: One and a half hour until Dyalog ’20; online on Monday–Tuesday 9th–10th November 2020. It is free, but you must register.

xificurC

1:07 PM

@dzaima isn't that the same for ⍋X in that case though?

Marshall

1:20 PM

@dzaima To access the sorting algorithm you need to use one of the sorting idiom functions such as {⍵[⍋⍵]}. So replace (⍵[⍋⍵]) with ({⍵[⍋⍵]}⍵). But evenly-distributed arrays of 1e5-1e6 elements are sort of a pathologically good case for the radix sort used by grade, so for ?100000⍴1e7 it actually gets slower. For other arrays the sort-based method is usually faster. ?1e7⍴1e3 is somewhat striking.

Sorting is also faster for ?100000⍴8e5 and smaller ranges.

xificurC

1:50 PM

@RGS OK, ⍋⍋ returns the same list but each value gets replaced by its index in the sorted list, so 5 7 6 is 1 3 2 as in 5 is first, 7 is third and 6 is second, when the list is sorted. By combining that with 1>|(2÷⍨1+≢⍵) you get a bitmask of the elements that are needed for calculating the median (1 index for an even-numbered list and 2 for odd). I imagine it as distance-from-median-less-or-equal-to-1, if that makes sense. The rest is self-explanatory.

xificurC

2:09 PM

these are the kind of "weird" solutions only an array programmer comes up with. I'm still wondering if it's clearer or faster than a naive solution

dzaima

@xificurC it's the slowest of the 3 i compared

{(+/÷≢) ({⍵[⍋⍵]}⍵) [∪(⌊,⌈)2÷⍨1+≢⍵]} and {2÷⍨+/⍵[(⍋⍵)[(⌊,⌈)2÷⍨1+⍴⍵]]} are the better contenders, depending on the input specifics

Marshall

If you're really concerned about median's performance, you could probably write a decent quickselect algorithm for Dyalog, since comparison and compression (filtering) are both fast. But you'd miss some element-swapping tricks that really good quickselect algorithms use.

xificurC

2:27 PM

@Marshall I'm trying to get a general sense of the performance characteristics of idiomatic APL code

Marshall

@xificurC Disclaimer first: in any language, a general sense (even a well-developed one) will not get you far, and the way to write fast code is to measure things.

I've written some about performance here, although that page too detailed and incomplete at the same time.

Basically, array languages (the ones that exist, not the ones we might want) get their performance by implementing primitives with fast algorithms. They can do combinations of primitives as well, but this is usually pretty limited. Dyalog recognizes many derived functions like +/, and has a few idioms like {⍵[⍋⍵]} that are fixed sequences of tokens.

Because these algorithms work on arrays, there are two factors that contribute to their cost (okay, that's not always exactly right, but it's very close). First, the primitive will do a fixed amount of processing per array, to check the array's type and size and decide on an algorithm to use. This takes 20-100ns usually. Second, it does the computation. This varies based on the primitive, but it's O(n) or O(n log(n)) in most cases because APL primitives are simple.

The maximum throughput if the whole array has to be processed is memory cache bandwidth, which is around 30GB/s, or a fraction of a nanosecond per element, depending on how many bytes per element are used. Arithmetic hits this boundary, and a lot of other operations come pretty close in Dyalog.

Comparing the fixed 20-100ns to the variable 0.03ns/byte, you can see we are looking at about 1000 elements before throughput becomes the dominant factor instead of fixed costs. If you have arrays of that size, and you can express your computation using fast primitives without blowing up the amount of work done in the process, performance tends to be C-like.

It can be faster than (normal, portable, sane) C if Dyalog's able to use vector instructions that C compilers don't use, or slower if the extra overhead of doing things in multiple passes is too much, or there's a better algorithm that can't be translated into array primitives.

When working with smaller arrays the 20-100ns cost dominates, and Dyalog can't beat compiled scalar languages. Because that overhead still gets spread out among many elements, it can still be very fast for an interpreted language. If you ever end up working primarily with scalars, well, 20ns is very slow for a single operation and Dyalog won't compete with any scalar interpreted languages.

xificurC

3:07 PM

@Marshall I understand that part. Anecdotal evidence suggests there's only a few hot spots that need careful performance tuning. At that point the question becomes just how fast can you go, or can you shell out to C/asm/etc if you can't make it. I tend to prefer languages where you can stay within it to get the necessary performance improvements. Of course many (most?) applications don't need to go as fast as C to achieve acceptable performance, it largely depends on the domain.

@Marshall thanks, that puts things into perspective. I think that correct abstractions, model and algorithms are usually the true bottlenecks of an application, which no C or vector instructions will solve. Still, knowing what performance to expect from your daily line of code can be a helpful metric.

@Marshall I wonder if it's slower than python, which, as crazy as it seems to me, noone minds being the slowest language on the planet

dzaima

@xificurC correct → incorrect?

xificurC

@dzaima indeed, that sentence got rewritten too many times

RGS

@xificurC Yes, that is exactly how I interpreted it as I wrote it

Razetime

3:29 PM

@dzaima is there a way to save an APLImg file?

dzaima

@Razetime i.save 'name' apparently

Razetime

oh perfect

dzaima

@dzaima quite surprised again that that's actually implemented. ¯\_(ツ)_/¯

Razetime

hahaaa

Marshall

@xificurC It's slower. I timed finding the 25th fibonacci number by naive recursion ({⍵≤1:⍵⋄(∇⍵-2)+(∇⍵-1)} in APL); Dyalog takes 0.1s while python takes 0.06s. Actually a smaller margin than I was expecting.

dzaima

3:40 PM

@Marshall i assume that's with cpython. pypy3 is quite a bit better (e.g. [2*x+3+5*x*x*x for x in range(1000)] is 226E¯6s vs 3.8E¯6s)

Marshall

Oh, Python actually jumps around between 0.03s and 0.07s (garbage collection?) so on average it's faster than I reported.

@dzaima Yes, CPython, as that's the one everyone complains about.

dzaima

@Marshall pypy appears to take 0.0085s

Razetime

4:21 PM

@dzaima would dzaima/APLP5 be considered a "standard library"?

dzaima

@Razetime well, it's not standard, nor is it a library

Razetime

2

Q: Crop an image to a square

In this challenge, you will take an input image and crop it to make a square, leaving only the central part of the input image. The answers must work with landscape, portrait, or square input images. The width of the output image should be equal to the shortest side of the input image e.g. the r...

I just wanna add a chat statement so I can post an answer here

@dzaima Aand this is what I wrote: Try it online!

soo is it alright

or do i scrap it and try with pbm

dzaima

@Razetime is that correct? shouldn't the left arg of P5.G.img be 0 0 if the image is square?

also there exists i.sz for getting both w and h in a vector, which should help a lot

Razetime

it draws the image at 0,a+-(smallest dimension)/4

with canvas size of smallest dim, smallest dim

which should center it correctly

dzaima

@Razetime a and smallest dimension are the same thing though?

Razetime

4:36 PM

ah ok

yes pretty much

this might be shorter with pbm

so

the center has to be a/2, a/2

wait is there a centered drawing mode for img

dzaima

i've got this at 62

@Razetime unfortunately not, even though processing has one

Razetime

any way to put P5.size in a function?

dzaima

@Razetime no

Razetime

alright

I guess mathematica 2 op

dzaima

another alternate method would be to get the pixel matrix, do a a↑(.5×s-a←⌊/s←i.sz)⌽ and create a new image or something

Razetime

4:49 PM

i.save still takes a few bytes

dzaima

true

Razetime

lets try RGB matrix

rak1507

5:31 PM

@RGS I felt ill and had a nap so I missed your talk :(( will it be recorded and put on youtube?

Adám

@rak1507 Yes, eventually. Feel better!

rak1507

Thanks!

ngn

6:26 PM

@Marshall your whole block of messages is an excellent explanation! i have a small request: could you remove the footnote about strides in ngn/apl from the wiki page or replace it with a reference to numpy? strides were an experiment that i later abandoned. i took the idea from numpy.

Marshall

6:47 PM

@ngn Is the current version all right? I wanted to keep the Vector reference, because it's a good explanation of how strides work, so I changed the sentence to say strides can be rather than are used, and added a note by the reference itself.

I think some early APLs like APL\3000 used strided representations in connection with Phil Abrams's "beating" concept. Further research is needed, but I'm not going to do it right now at least.

xpqz

@ngn I read your vector paper with interest. Is this no longer what you'd advocate?

ngn

7:03 PM

i realized a few things over the years: if you want them to respect you, beat them at their own game - write a fast apl (or apl-like) interpreter, don't change the game by escaping into expressivity or flashy ui-s. if you want it to be fast, you must write it in c. if you're developing solo, you must simplify. contrary to what many people believe, simplifying (i.e. making the code smaller) has the side effect of improving performance. these observations naturally lead to k.

@Marshall reading more carefully right now..

rak1507

How do you do string interpolation in APL?

RGS

What is string interpolation?

ngn

@Marshall yes, looks good

@RGS "replacing a ${variable} in a string with its value"

RGS

Ah I see, thanks ngn.

ngn

@rak1507 afaik there's no support for string interpolation but you can conjure up something with ⎕r and ⍎

rak1507

7:12 PM

That's what I feared

ngn

it shouldn't be that scary :) tell us what syntax you need and i bet someone here will be able to answer

rak1507

I'll just use ⍕ and ,

ngn

fair enough

Adám

@rak1507 This?

rak1507

Saw that, thought there might be a better way

Adám

7:16 PM

@rak1507 Advanced version.

ngn

@Marshall i'm not familiar with "beating"

@Marshall have you heard of tagged pointers (or tagged values)? i think that's a noteworthy optimisation

Marshall

@ngn Pretty sure I have, but I can't remember what it refers to now.

@ngn That's the name Phil Abrams used for manipulations in his subscript calculus; it's described in "An APL Machine" (which I haven't read fully).

ngn

@Marshall you store the "type" in the higher bits (typically bits 56..63) and the value in the lower bits (assuming it fits there, eg bits 0..31). this way the entire information about a scalar (or very small vector) can fit in a register and you can avoid touching ram

Marshall

@ngn Yes, I've seen that. You said ngn/k uses it earlier?

So it's a little different from NaN boxing because the "default" is a pointer, not a float.

ngn

@Marshall yes, it uses it for atoms (scalars) of 32bits or fewer

@Marshall i think it's different. you can use nan boxing for array items, right?

Marshall

7:29 PM

@ngn Yes, although presumably you'd want a flag/type to say the array just has normal floats.

ngn

@Marshall tagged pointers are great also because you don't have to refcount them

@Marshall needless to say, original k is even better

Marshall

@ngn Yes. I has a somewhat similar optimization in that it computes the type and value of a result separately. If the type is known (instead of a mix of possible types) and fits in a register then it passes the value by value without refcounting.

ngn

Tagged pointer

In computer science, a tagged pointer is a pointer (concretely a memory address) with additional data associated with it, such as an indirection bit or reference count. This additional data is often "folded" into the pointer, meaning stored inline in the data representing the address, taking advantage of certain properties of memory addressing. The name comes from "tagged architecture" systems, which reserved bits at the hardware level to indicate the significance of each word; the additional data is called a "tag" or "tags", though strictly speaking "tag" refers to data specifying a type, not...

^in case you haven't looked it up yet

xificurC

7:48 PM

@ngn why 32? Are you using all the other 32 bits? Typically only a few bits are used

@ngn what is used in original k? And which k :) If some of them are closed source did someone reverse engineer them?

ngn

@xificurC sure! type usually takes 8 because it's easier to fetch with *(char*) or similar

i used 32 as an example because many things (chars, short ints, 32-bit ints, primitive verbs, etc) can fit in 32 bits and are easy to get with just casting the tagged value to int

@xificurC it's a secret :)

@xificurC afaik more than one version of k differentiates between pointer types and value types, and pointer types are always tagged with type=0, so extracting the actual pointer is a no-op, and then the rest of the type information is in the header before the array's data. it's complicated.

xificurC

@ngn a secret you know? :)

ngn

@xificurC sometimes secrets are hidden in plain sight

Transcript for