Fear and Loathing with APL

Hav­ing heard so much about APL from Phil Trelford (who is one of the lead­ers in the F# com­mu­ni­ty) I decid­ed to try it out too. For the unini­ti­at­ed, APL code looks every bit as mind-bend­ing and unbe­liev­able as scenes from John­ny Depp’s Fear and Loathing in Las Vegas.

For exam­ple, the life func­tion below imple­ments Conway’s game of life:

life\gets\{\uparrow1 \ \omega\lor.\land3 \ 4=+/,^-1 \ \emptyset \ 1\circ.\ominus^-1 \ \emptyset \ 1\circ.\phi\subset\omega\}

I know, right? WTF and mind blow­ing in equal mea­sures…

 

As I was learn­ing through Mas­ter­ing Dya­log APL, I took down plen­ty of notes which I hope will help get you up to speed with the basics quick­ly.

You can try out the exam­ples at TryAPL, just click on the “APL Key­board” but­ton and use the vir­tu­al key­board to enter the sym­bols you need.

apl-try-1

apl-try-2

Learn APL in 10 Minutes

+ and - does what you’d expect but mul­ti­pli­ca­tion and divi­sion becomes \times and \div (just like in maths).

* in APL is pow­er, i.e. 7 * 3 = 7 \times 7 \times 7

/ in APL also means some­thing else, which we’ll come to lat­er.

Also note the dif­fer­ence between neg­a­tive sign ^- and sub­trac­tion -, e.g. 1 - ^-1 = 2

 

Use \gets to assign a val­ue (either scalar or array) to a name, e.g.

X \gets 17.5

Years \gets 1942 \ 1958 \ 2007

and remem­ber, vari­able names are case sen­si­tive.

Vari­ables are muta­ble, and you can assign mul­ti­ple vari­able at once:

X \ Y \ Z \gets 1 \ 2 \ 3

but only if the length match, oth­er­wise you’ll get an error

X \ Y \gets 1 \ 2 \ 3

=> LENGTH \ ERROR

 

You can per­form arith­metic oper­a­tions between two arrays with the same shape:

1 \ 3 \ 5 \ - \ 3 \ 2 \ 1

=> ^-2 \ 1 \ 4

Price \gets 5.2 \ 11.5 \ 3.6 \ 4.8 \ 4.5 \\*    Qty \gets 2 \ 1 \ 3 \ 6 \ 2 \\*    Price \times Qty

=> 10.4 \ 11.5 \ 10.8 \ 28.8 \ 9

look ma, no loops 

If the shape doesn’t match, then you get an error:

1 \ 3 \ 5 - 3 \ 2

=> LENGTH \ ERROR

 

But, if one of the vari­ables is a scalar then the oth­er vari­able can be any shape:

1 \ 3 \ 5 - 3

=> ^-2 \ 0 \ 2

3 \times 1 \ 3 \ 5

=> 3 \ 9 \ 15

The same rule applies to oth­er oper­a­tions, e.g. max \lceil and min \lfloor.

75.6 \ \lceil \ 87.3

=> 87.3

11 \ 28 \ 52 \ 14 \ \lceil \ 30 \ 10 \ 50 \ 20

=> 30 \ 28 \ 52 \ 20

11 \ 28 \ 52 \ 14 \ \lceil \ 30

=> 30 \ 30 \ 52 \ 30

 

Most sym­bols in APL have dou­ble mean­ing, just like they do in alge­bra, e.g.

a = x - y where — means sub­trac­tion, a dyadic use of the sym­bol

a = -y where — means neg­a­tive, a monadic use of the same sym­bol

(before you freak out, monadic here is of the Math­e­mat­ics def­i­n­i­tion, and not the Haskell vari­ant )

apl-monadic

To find the length of an array, you can use Rho \rho monad­i­cal­ly:

Price \gets 1 \ 2 \ 3 \ 4 \ 5 \\*    \rho Price

=> 5

 

You can also Rho  \rho dyad­i­cal­ly to orga­nize items into spec­i­fied shapes, i.e.

Tab \gets 4 \ 2 \ \rho \ 25 \ 60 \ 33 \ 47 \ 11 \ 44 \ 53 \ 28 \\*    Tab

=>


25 \ 60 \\*    33 \ 47 \\*    11 \ 44 \\*    53 \ 28

where 4 2 describes the shape — 4 rows, 2 columns, fol­lowed by Rho \rho and the array of items to be orga­nized.

If the num­ber of items in the array doesn’t match the num­ber of slots in the shape we’re try­ing to orga­nize into, then the array is repeat­ed, e.g.

3 \ 2 \ \rho \ 1 \ 2 \ 3 \ 4

=>

1 \ 2 \\*    3 \ 4 \\*    1 \ 2

3 \ 2 \ \rho \ 1 \ 2

=>

1 \ 2 \\*    1 \ 2 \\*    1 \ 2

If there are too many items then extra items are ignored:

2 \ 2 \ \rho \ 1 \ 2 \ 3 \ 4 \ 5 \ 6

=>

1 \ 2 \\*    3 \ 4

Uti­liz­ing the way items are repeat­ed, there’s a neat trick you can do, e.g.

3 \ 3 \ \rho \ 1 \ 0 \ 0 \ 0

=>

1 \ 0 \ 0 \\*    0 \ 1 \ 0 \\*    0 \ 0 \ 1

 

In gen­er­al, APL has spe­cial names for data depend­ing on its shape:

scalar — sin­gle val­ue

vec­tor — list of val­ues

matrix — array with 2 dimen­sions

array — gener­ic term for any set of val­ues, regard­less of no. of dimen­sions

table — com­mon term for matrix

cube — com­mon term for array with 3 dimen­sions

Ok, now that we’ve intro­duced the notion of dimen­sions, it’s time to con­fess that I slight­ly mis­led you ear­li­er — Rho \rho actu­al­ly returns the shape of an array (not just its length, which only applies to a vec­tor), so it works with mul­ti-dimen­sion­al data too.

\rho (2 \ 2 \ \rho \ 1 \ 2 \ 3\ 4)

=> 2 2

Fur­ther­more, since the result of Rho \rho is itself a vec­tor, apply­ing Rho \rho again will give us the num­ber of dimen­sions an array has — oth­er­wise known as its Rank.

\rho \rho (2 \ 2 \ \rho \ 1 \ 2 \ 3 \ 4)

=> 2

i.e. scalars have 0 rank, vec­tors have 1 rank, and so on…

 

You can also reduce over a set of val­ues using / e.g. a plus reduc­tion to sum up all the num­bers in an array can be writ­ten as

+/ \ 21 \ 45 \ 18 \ 27 \ 11

=> 122

sim­i­lar­ly, fac­to­r­i­al can be writ­ten using mul­ti­ply reduc­tion:

\times/ \ 1 \ 2 \ 3 \ 4 \ 5

=> 120

The / sym­bol is an oper­a­tor, where­as + \ - \ \times \ \lceil etc. are func­tions. / can accept any of these func­tions and uses it to reduce over an array.

\lceil/ \ 1 \ 3 \ 5 \ 7 \ 9 \ 6 \ 4 \ 2

=> 9

\lfloor/ \ 1 \ 3 \ 5 \ 7 \ 9 \ 6 \ 4 \ 2

=> 1

 

APL calls pro­grams defined func­tions, and you can cre­ate a defined func­tion like this:

Average \gets \{ (+/ \ \omega) \div \rho \omega \}\\*    Average \ 1 \ 2 \ 3 \ 4 \ 5

=> 3

where:

Average — pro­gram name

\omega — gener­ic sym­bol for array passed on the right

\alpha — gener­ic sym­bol for array passed on the left

for exam­ple, if we have a func­tion f such that

f \gets \{ (+/ \ \omega) - (+/ \ \alpha) \}\\*    1 \ 2 \ 3 \ f \ 4 \ 5 \ 6 \ 7

=> 16

what we’ve done here is to sum the array on the right of f — 4 5 6 7 — and sub­tract it with the sum of the array on the left — 1 2 3.

Sim­ple, right? Let’s try a few more.

Plus \gets \{ \omega + \alpha \}\\*    Times \gets \{ \omega \times \alpha \}\\*    (3 \ Plus \ 6) \ Times \ (2 \ Plus \ 5)

=> 63

and you can use your cus­tom func­tions with reduc­tion:

Plus/ \ 1 \ 2 \ 3 \ 4 \ 5

=> 15

 

To index into an array, you can use the stan­dard [ ] nota­tion:

Val \gets 1 \ 2 \ 3 \ 4 \ 5\\*    Val[4]

=> 4

noticed that? APL is one-indexed!

What’s more, just like every­thing else, you can index into array with either a scalar or an array:

Val[1 \ 3 \ 4]

=> 1 3 4

Val[1 \ 3 \ 4 \ 1]

=> 1 3 4 1

This also works when it comes to updat­ing val­ues in an array:

Val[1 \ 3 \ 5] \gets 42\\*    Val

=> 42 2 42 4 42

Val[1 \ 3 \ 5] \gets 1 \ 3 \ 5\\*    Val

=> 1 2 3 4 5

Val[2 \ 2 \ \rho \ 1 \ 2 \ 3 \ 4]

=>

1 \ 2 \\*    3 \ 4

Note that it fol­lows the same rule as func­tions with regards to the input being either a scalar or a same-shaped array.

If the shape of the array doesn’t match, then it’ll error:

Val[1 \ 3 \ 5] \gets 2 \ 4\\*    Val

=> LENGTH \ ERROR

Equal­ly, if you use an invalid index, you’ll also get an error:

Val[6]

=> INDEX \ ERROR

 

You can use Iota \iota to gen­er­ate an array of inte­gers from 1 to N, e.g.

\iota 4

=> 1 2 3 4

Val[\iota 4]

=> 1 2 3 4

 

Booleans are rep­re­sent­ed as 1 and 0, and you can use any one of these rela­tion­al func­tions: < = =/ > \leq \geq

1 \ 3 \ 5 \ > \ 6 \ 2 \ 4

=> 0 1 1

1 \ 3 \ 5 \ < \ 6 \ 2 \ 4

=> 1 0 0

AND and OR seman­tics are rep­re­sent­ed by \land and \lor respec­tive­ly.

(1 \ 3 \ 5 > 6 \ 2 \ 4) \land (1 \ 3 \ 5 = 6 \ 3 \ 1)

=> 1 0 1

(1 \ 3 \ 5 > 6 \ 2 \ 4) \lor (1 \ 3 \ 5 = 6 \ 3 \ 1)

=> 0 1 1

you can use them to count no. of employ­ees based on salary for instance:

Salaries \gets 1000 \ 1500 \ 2750 \ 3000 \ 2000\\*    +/ (Salaries > 2500)

=> 2

 

You can also use an array of boolean val­ues as masks too:

1 \ 0 \ 1 \ / \ 1 \ 2 \ 3

=> 1 3

1 \ 0 \ 1 \ / \ 'iou'

=> iu

this is called com­pres­sion, and is use­ful for select­ing items con­form­ing to some cri­te­ria, e.g.

Val \gets 11 \ 13 \ 1 \ 8 \ 9 \ 15 \ 7\\*    Val > 10

=> 1 1 0 0 0 1 0

\rho Val

=> 7

\iota \rho\ Val

=> 1 2 3 4 5 6 7

there­fore, to find the indices of val­ues that’s greater than 10

(Val > 10) \ / \ \iota \rho Val

=> 1 2 6

and to get the cor­re­spond­ing val­ues, just use com­pres­sion:

(Val > 10) \ / \ Val

=> 11 13 15

 

Giv­en two arrays, A and B, you can return a new array with all the ele­ments of A minus all the ele­ments of B using the with­out oper­a­tor ~

A \gets 1 \ 2 \ 3\\*    B \gets 3 \ 4 \ 5\\*    A \sim B

=> 1 2

this doesn’t mod­i­fy A or B though.

A

=> 1 2 3

B

=> 3 4 5

 

mem­ber­ships

To find items from an array that exists in anoth­er array, you can use the mem­ber­ship oper­a­tor \epsilon

(\iota 5) \ \epsilon \ 1 \ 3 \ 5

=> 1 0 1 0 1

it also works with strings

Phrase \gets \ 'Panama \ is \ a \ canal \ between \ Atlantic \ and \ Pacific'\\*    Phrase \ \epsilon \ 'aeiouy'

=> 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0

you can (like before) get the indices of match­es using com­pres­sion:

(Phrase \ \epsilon \ 'aeiouy') \ / \ \iota \rho Phrase

=> 2 4 6 8 11 14 16 20 23 24 30 33 36 41 43 45

or find the match­ing char­ac­ters using com­pres­sion:

(Phrase \ \epsilon \ 'aeiouy') \ / \ Phrase

=> aaa­iaaaeeea­iaaii

inspect­ing the result tells us that those are indeed the char­ac­ters we’re look­ing for!

 

search

We saw how we can com­bine mem­ber­ships and iota-rho \iota \rho to find the indices in Phrase that cor­re­sponds to a mem­ber in ‘aeiouy’.

What if we want to find the first index each char­ac­ter in ‘aeiouy’ appears in Phrase, i.e. “aeiouy”.Select(char -> Phrase.IndexOf(char)) if you’re com­ing from a .Net back­ground.

We can use the dyadic form of Iota \iota:

Phrase \ \iota \ 'aeiouy'

=> 2 20 8 47 47 47

note that the length of Phrase is 46

\rho Phrase

=> 46

so the result 47 is essen­tial­ly say­ing that ‘o’, ‘u’, ‘y’ nev­er appeared in Phrase.

 

You can mod­el an ‘else’ seman­tic using two arrays whose lengths are off by 1. For instance:

Area \gets \ 17 \ 50 \ 59 \ 84 \ 89\\*    Discount \gets \ 9 \ 8 \ 6 \ 5 \ 4 \ 2

based on the way search works (not found = length + 1), we can map the spec­i­fied Area codes to cor­re­spond­ing dis­count rates: 17 -> 9, 50 -> 8, … 89 -> 4, and all oth­ers to 2.

D \gets \ 24 \ 75 \ 89 \ 60 \ 92 \ 50 \ 51 \ 50 \ 84 \ 66 \ 17 \ 89\\*    Area \ \iota \ D

=> 6 6 5 6 6 2 6 2 4 6 1 5

so where D does not exist in Area, you’ll get index 6 which does not exist in Area, BUT exists in Dis­count — i.e. the ‘oth­er’ case we’re try­ing to mod­el.

So if we use the result of Area \ \iota \ D as indices in Dis­count we’ll find the cor­re­spond­ing dis­count rate for the val­ues in D:

Discount[Area \ \iota \ D]

=> 2 2 4 2 2 8 2 8 5 2 9 4

this is an algo­rithm for chang­ing the frame of ref­er­ence, i.e. chang­ing a list of area codes into a list of dis­count val­ues, a gen­er­al form can be described as:

FinalSet[InitialSet \ \iota \ Values]

where \rho FinalSet = \rho InitialSet + 1

 

take and drop

You can use the Take \uparrow and Drop \downarrow func­tions like you do with Enumerable.Take and Enumerable.Drop in LINQ:

L \gets \iota 10\\*    4 \ \uparrow \ L

=> 1 2 3 4

4 \ \downarrow \ L

=> 5 6 7 8 9 10

if the count is neg­a­tive then you take from the end of the list, e.g. take last 3 items or drop last 7 items:

^-3 \ \uparrow \ L

=> 8 9 10

^-7 \ \downarrow \ L

=> 1 2 3

 

Giv­en a list of val­ues

L \gets 3 \ 8 \ 5 \ 14 \ 34 \ 5 \ 17 \ 21 \ 18

sup­pose you want to find the change from one num­ber to the next, i.e. 3 (+5) 8 (-3) 5 (+9) 14…

con­sid­er­ing that

1 \ \downarrow \ L

=> 8 5 14 34 5 17 21 18

^-1 \ \downarrow \ L

=> 3 8 5 14 34 5 17 21

so now you can sub­tract the two arrays (of equal length) to get the answer:

(1 \ \downarrow \ L) - (^-1 \ \downarrow \ L)

=> 5 \ ^-3 \ 9 \ 20 \ ^-29 \ 12 \ 4 \ ^-3

clever, right? It’s rem­i­nis­cent of the RX approach to track­ing mouse moves.

rx-mouse-move

 

mir­rors and trans­po­si­tion

You can also piv­ot data about any direc­tion eas­i­ly:

apl-mirrors-transpose

(screen­shot tak­en from Mas­ter­ing Dya­log APL)

 

out­er prod­ucts

You can use the out­er prod­uct oper­a­tor \circ. to cal­cu­late the carte­sian prod­ucts of two lists:

1 \ 2 \ 3 \ \circ.\times \ 3 \ 4 \ 5

=>

3 \ 4 \ \ 5\\*    6 \ 8 \ \ 10\\*    9 \ 12 \ 15

using the small cir­cle + dot \circ. + an oper­a­tion to apply, in this case mul­ti­ply \times, but could eas­i­ly be any­thing else:

1 \ 2 \ 3 \ \circ.+ \ 3 \ 4 \ 5

=>

4 \ 5 \ 6\\*    5 \ 6 \ 7\\*    6 \ 7 \ 8

here’s even more exam­ples tak­en from Mas­ter­ing Dya­log APL:

apl-outer-products

Unlike some of the oper­a­tions we’ve seen so far, the out­er prod­uct oper­a­tor works across dif­fer­ent sized arrays too:

1 \ 2 \ 3 \ \circ.+ \ 3 \ 4 \ 5 \ 6

=>

4 \ 5 \ 6 \ 7\\*    5 \ 6 \ 7 \ 8\\*    6 \ 7 \ 8 \ 9

 

Final­ly, there are some com­mon pat­terns (or idioms) you’ll see in APL.

  • find indices in A that exists in B

(A \ \epsilon \ B) \ / \ \iota \rho A

  • find the mem­bers (not indices) of A that exists in B

(A \ \epsilon \ B) \ / \ A

  • find indices in A where B first appeared in (i.e. Index­Of)

A \ \iota \ B

  • change the frame of ref­er­ence

FinalSet[InitialSet \ \iota \ Values]

  • gen­er­ate indices with incre­ment­ing steps

Start + Step \times (\iota Length) - 1

 

So that’s it, I hope this post has giv­en you a flavour of APL and help you learn the basics quick­ly. I find the array pro­gram­ming par­a­digm absolute­ly mind blow­ing and a com­plete­ly dif­fer­ent way to think about prob­lems.

Also I find it has a sim­i­lar trans­for­ma­tive effect in chang­ing the way I think about vari­ables — as a point-in-time snap­shot of some scalar val­ue — to FRP (e.g. sig­nals in Elm or observ­ables in RX).

 

In the next post, let’s see how we can use APL to solve some sim­ple prob­lems (that’s all I’m able to man­age for now!).

 

Links