[Sticky] Language of the Month: APL  

  RSS

1

APL (A Programming Language) is fantastically beautiful in it's conciseness. The language was created in the 60's by Ken Iverson and his colleagues at IBM. The language is quite unique in it's syntax as it uses predominantly non-ASCII characters including some Greek letters. APL was very much mathematically inspired and used a powerful notation for mathematical algorithms.

To give an idea of how this language looks, let's have a look at the infamous Conway's "Game of Life" written in APL.

   ∇ nextGeneration←Life currentGeneration 
[1] ⍝⍝ Take a matrix of Booleans and returns one
[2] nextGeneration←↑↑1 currentGeneration∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
   ∇

... you might be asking yourself: "Where's the rest of it?", but that is sincerely the entire APL function. How incredible!

I think it would be quite a waste not to learn how it all works, so why not?

To start let's see how we can declare a 5x5 grid of Boolean values.

currentGeneration←5 5

Alright, so far so simple. Let's declare the grid with some values already existing.

currentGeneration←5 5⍴0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 1

The ⍴ function is called Reshape or Dyadic Rho. To give an example of it in use A⍴B describes an array of shape A with data B.

So far our grid looks like:

0 0 0 0 0
0 0 1 1 0
0 1 1 0 0
0 0 1 0 0
0 0 0 0 0

Not bad. If we rotate each row to the left, using APL's Rotate function ⌽, our grid would look like this:

1⌽currentGeneration
0 0 0 0 0
0 1 1 0 0
1 1 0 0 0
0 1 0 0 0
0 0 0 0 0

Similarly we can rotate right by using the code:

¯1⌽currentGeneration

By using APL's Outer Product operator , together with the Rotate function we can get a set of three grids containing the 3 variants.

¯1 0 1∘.⌽⊂currentGeneration
0 0 0 0 0   0 0 0 0 0   0 0 0 0 0
0 0 0 1 1   0 0 1 1 0   0 1 1 0 0
0 0 1 1 0   0 1 1 0 0   1 1 0 0 0
0 0 0 1 0   0 0 1 0 0   0 1 0 0 0
0 0 0 0 0   0 0 0 0 0   0 0 0 0 0

By using APL's First Axis Rotate function . We can get 9 grids when used with the Outer Product.

 ¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
0 0 0 0 0   0 0 0 0 0   0 0 0 0 0
0 0 0 0 0   0 0 0 0 0   0 0 0 0 0
0 0 0 1 1   0 0 1 1 0   0 1 1 0 0
0 0 1 1 0   0 1 1 0 0   1 1 0 0 0
0 0 0 1 0   0 0 1 0 0   0 1 0 0 0

0 0 0 0 0   0 0 0 0 0   0 0 0 0 0
0 0 0 1 1   0 0 1 1 0   0 1 1 0 0
0 0 1 1 0   0 1 1 0 0   1 1 0 0 0
0 0 0 1 0   0 0 1 0 0   0 1 0 0 0
0 0 0 0 0   0 0 0 0 0   0 0 0 0 0

0 0 0 1 1   0 0 1 1 0   0 1 1 0 0
0 0 1 1 0   0 1 1 0 0   1 1 0 0 0
0 0 0 1 0   0 0 1 0 0   0 1 0 0 0
0 0 0 0 0   0 0 0 0 0   0 0 0 0 0
0 0 0 0 0   0 0 0 0 0   0 0 0 0 0

The centre grid is clearly our original grid.
Now we get into the Conway's Game of Life part of the programming. If you don't know what it is, I would suggest looking for a quick YouTube video explaining it. It is a very simple concept.

We can find out how many neighbours each cell in the original grid has by summing the corresponding elements in the 9 grids.

+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
0 1 2 2 1
1 3 4 3 1
1 4 5 4 1
1 3 3 2 0
0 1 1 1 0

For a cell to exist in the next generation, one of two rules must be met:
1. Any live cell with two neighbours lives to the next generation.
2. Any cell, live or dead, with exactly 3 neighbours is live in the next generation.

Therefore, the live cells will have a sum of 3 or 4. As two neighbours gives a sum of 3, and three neighbours gives a sum of 4.

So we're interested in cells with a sum of 3 or 4, which we can find as follows:

3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
0 0 0 0 0   0 0 0 0 0
0 1 0 1 0   0 0 1 0 0
0 0 0 0 0   0 1 0 1 0
0 1 1 0 0   0 0 0 0 0
0 0 0 0 0   0 0 0 0 0

The problem with the sum of 4 is that it could correspond to a dead cell with 4 neighbours.

0 1 0
1 0 1
0 1 0

or a live cell with four neighbours

0 1 1
1 1 0
0 0 0

we are only interested in the latter. So the cell will only live if the cell has a sum of 4 AND the cell is live. Here we use APL's AND function, ^.

(⊂currentGeneration)^4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
0 0 0 0 0
0 0 1 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0

The same problem can be said for the sum of 3, we need to ensure that we mean a live cell with two neighbours rather than a dead cell with 3 neighbours.

3=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 0 0
0 0 0 0 0

The next step is to say the cell is live if either of the two tests is met. We'll use APL's OR function, .

We can write this long-windedly as:

(1^3=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration)∨(⊂currentGeneration)^4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 0 1 0 0
0 0 0 0 0

Or we could take advantage of APL's Inner Product operator.

1 currentGeneration∨.^3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
0 0 0 0 0
0 1 1 1 0
0 1 0 0 0
0 1 1 0 0
0 0 0 0 0

Finally, we turn the result into an array by using ↑↑.

For the Game of Life fanatics out there, here's a glider.

glider←3 3⍴1 1 1 1 0 0 0 1 0
glider
1 1 1
1 0 0
0 1 0

grid←¯10 ¯10↑glider
grid
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0

Sources: http://aplwiki.com

"Computer science is no more about computers than astronomy is about telescopes."
~ Edsger W. Dijkstra

 
Share:
  
Working

Please Login or Register