This is Words and Buttons Online — a collection of interactive #tutorials, #demos, and #quizzes about #mathematics, #algorithms and #programming.
APL deserves its renaissance too
This is the Game of Life in APL.
life←{↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}
|
I know, I know. I should have started with the introduction. But doesn’t it introduce itself rather well? You can see for yourself that it’s ultimately concise, expressive and utterly alien to all the mainstream computer languages.
In fact, it didn’t originate as a computer language at all. It was proposed as a better notation for tensor algebra by Harvard mathematician Kenneth E. Iverson. It was meant to be written by hand on a blackboard to transfer mathematic ideas from one person to another.
But due to its formality, it turned up to be surprisingly good to transfer ideas from people to computers as well. It was made into a computer language in the early 60's, and these weird symbols like ↑ or ⌽ were not a problem at all, because every hardware manufacturer had its own keyboard at the time anyway. ASCII wasn’t yet even ratified.
Its popularity grew through the following years peaking in the 70's. Fun fact, the very first portable computer by IBM — IBM 5100 “a 50-lb package of interactive personal computing” — came 6 years before the famous IBM PC and with APL on board.
By Marcin Wichary from San Francisco, U.S.A.
([1]Uploaded by Partyzan_XXI) [CC BY 2.0], via Wikimedia Commons
The secret of APL’s popularity was simple: learning all the alien symbols is a one-time investment, and expressiveness — the leverage you as a programmer gain — is for life.
However, later on, with the rise of BASIC based personal computing and C powered UNIX platform, APL came off the scene. It is still used in some niches, such as in financial sector, so there are people who actually make good money using APL up to this day. But it is, of course, as far from the mainstream as it can get.
Still, it's a nice and powerful language. And it's simple too. You might not believe it, but it’s one of the simplest languages in existence. Here, let me show you how the Game of Life works.
By Kieff [GFDL or CC-BY-SA-3.0], from Wikimedia Commons
The left arrow is an assignment, and the brackets mark a function's body. So this: life←{...} is simply a function definition.
In APL function's arguments are tacit, meaning you don’t have to specify a name for every argument, you just know by convention, that the left argument is always ⍺ and the right is always ⍵. But doesn’t it mean that APL functions take only two arguments at most? Not really. When you want to call C-like function like this: foo(x, y, z), in APL terms you simply pass a tuple of 3 values as a single argument. It’s still one ⍵. And you can't do (a, b, c)foo(x, y, z) in C at all, so APL is actually more powerful than C in this regard.
Let’s run our life with some input. We’ll use a ⍴ function to form a 5x5 matrix out of a linear array.
1. Form the in variable as a 5x5 matrix in ← 5 5 ⍴ 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 |
In the Game of Life this figure is called Glider. Running the life function on in will result in this:
1. Show the in variable in 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 |
The Glider moves!
In APL what we would normally call operators are functions too. Things like +, -, × etc. The functions are executed from right to left one at the time. There is no precedence, all the functions are equal.
The first function of the life's body would be enclose: ⊂. What it does — it makes our 5x5 matrix input into a scalar containing 5x5 matrix.
1. Show the in variable in 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 |
The next thing, as we're going right to left, is a bit trickier. It is rotate: ⌽. It rotates an array at given index.
1. Rotate an array 1 position left 1 ⌽ 1 2 3 4 2 3 4 1 |
But in our example, it doesn’t go by itself. It is itself an argument for an outer product operator: ∘. (in APL functions that take other functions as arguments are called operators).
And together they do this:
1. Enclose the in variable ⊂ in ┌─────────┐ │0 0 0 0 0│ │0 0 1 0 0│ │0 0 0 1 0│ │0 1 1 1 0│ │0 0 0 0 0│ └─────────┘ |
The next function also goes with an operator. It’s rotate first: ⊖. It works pretty much like rotate, but it rotates a nested array around the first level of “nestedness”. Basically, it scrolls matrices.
1. Just show the in in 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 |
With the outer product operator and our previous result it goes like this:
1. Enclose the in variable ⊂ in ┌─────────┐ │0 0 0 0 0│ │0 0 1 0 0│ │0 0 0 1 0│ │0 1 1 1 0│ │0 0 0 0 0│ └─────────┘ |
The next function in called ravel: , and it looks like a comma. What it does, it makes a nested array 1-dimensional.
1. Form the x variable as a 2x3 matrix x ← 2 3 ⍴ 1 2 3 4 5 6 |
It doesn’t ravel scalars, so being applied to our 3x3 matrix of enclosed matrices, it would make a linear array of 9 enclosed matrices.
,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂in
┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
│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 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 0│0 0 1 0 0│0 1 0 0 0│0 0 0 0 1│0 0 0 1 0│0 0 1 0 0│
│0 0 0 1 0│0 0 1 0 0│0 1 0 0 0│0 0 0 0 1│0 0 0 1 0│0 0 1 0 0│0 0 1 1 1│0 1 1 1 0│1 1 1 0 0│
│0 0 0 0 1│0 0 0 1 0│0 0 1 0 0│0 0 1 1 1│0 1 1 1 0│1 1 1 0 0│0 0 0 0 0│0 0 0 0 0│0 0 0 0 0│
│0 0 1 1 1│0 1 1 1 0│1 1 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│
└─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘
|
The next piece of code is an operator and function pair. Operator reduce: /, and a function plus: +. As you might guess, it reduces, as in map-reduce, a summation of all the matrices in the linear array.
+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂in ┌─────────┐ │0 1 1 1 0│ │0 1 2 2 1│ │1 3 5 4 2│ │1 2 4 3 2│ │1 2 3 2 1│ └─────────┘ |
Operator compare: = produces matrices of 0 and 1 based on whether every element in the right argument equals a corresponding element in the left argument. In our case we would use it to filter out 3s and 4s:
1. Sum all the rotated matrices +/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂in ┌─────────┐ │0 1 1 1 0│ │0 1 2 2 1│ │1 3 5 4 2│ │1 2 4 3 2│ │1 2 3 2 1│ └─────────┘ |
Then there is the logical part. Functions or: ∨ and and: ∧ used with the . — the inner product operator. They form an operator that makes an and on every element pair and then an or on a result.
1. And function 1 0 1 0 ∧ 1 1 0 0 1 0 0 0 |
Remember, we didn't count the neighbors exactly, we counted them along with the value in each cell. This was the 0 0 rotation. Now we have to build our logic around this.
- If the sum is 3 and the cell had 0, then it has 3 neighbors
— it lives. - If the sum is 3 and the cell had 1, then it has 2 neighbors
— it still lives. - If the sum is 4 and the cell had 0, then it has 4 neighbors
— it doesn't repopulate. - If the sum is 4 and the cell had 1, then it has 3 neighbors
— it lives.
That's why when we want our and to work with 3s unconditionally, we supply it with identity matrix 1. And when we want to and 4s with the original input, we supply it with in. Then we only have to or the results so any condition produces a living cell. That's how 1 in ∨.∧ 3 4... works.
1 in ∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂in
┌─────────┐ ⍝ Identity Original in
│0 0 0 0 0│ ⍝ 1 1 1 1 1 0 0 0 0 0
│0 0 0 0 0│ ⍝ 1 1 1 1 1 0 0 1 0 0
│0 1 0 1 0│ ⍝ 1 1 1 1 1 0 0 0 1 0
│0 0 1 1 0│ ⍝ 1 1 1 1 1 0 1 1 1 0
│0 0 1 0 0│ ⍝ 1 1 1 1 1 0 0 0 0 0
└─────────┘
|
The last function mix ↑ here simply removes enclosure.
1. Enclosed 1 in ∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂in ┌─────────┐ │0 0 0 0 0│ │0 0 0 0 0│ │0 1 0 1 0│ │0 0 1 1 0│ │0 0 1 0 0│ └─────────┘ |
Not so alien now, is it?
By Nash Gordon [CC BY-SA 4.0], from Wikimedia Commons
If you got interested but not enough to get things installed, you can try an online APL interpreter: https://tryapl.org/.
But why does it deserve its renaissance after all?
The last decade was a renaissance for the Lisp being reborn in Clojure. Also Erlang, being a niche language for telecom, decided to waltz into the mainstream with a plethora of web frameworks. Even Haskell not only gained popularity on its own but deeply influenced F# and Scala. APL however, despite its tremendous power, didn't get too much acclaim.
My theory is, since it was designed to be written by hand, it didn't work out very well with an ASCII. Didn't survive the standardization. Of course, APL has its ASCII friendly descendants inherited its expressiveness but frankly, they are all ugly far beyond the possibility of public success. Roughly 86% of all the fun you get from APL programming comes from the mysterious symbols and the magic behind them. It’s not that APL is alien to computers, it’s just the computers were alien to APL for quite a while.
But now, with the development of touch interfaces and optical character recognition, it might just get its second chance. Since on a tablet or on a phone you do have to use a virtual keyboard anyway, why not choose APL for its tablet-friendly concision? Or you could even draw APL symbols with your fingers. Not being constrained with the keyboard, you could name your own functions with hand-written symbols as well. You could develop your own truly free-form language just like Iverson did.
I would love that! Wouldn't you?
| Index #programming #tutorials | ← there's more. |
+ Github & RSS |