This program features in "Dr.Dobbs", Feb. 2007
There is also a Slovak translation.
...and a Serbo-Croatian translation.
...and a Czech translation.
...and a French translation.
...and a Slovenian translation
...and a Russian translation .
...and a Ukrainian translation.
...and a Polish translation.
...and a Belarussian translation.
...and an Italian translation (and another one).
If you are not familiar with Convey's Game of Life or APL programming language, I recommend to consult the very short description of APL and the description of Conway's Game of Life. Besides, on this page you will find IBM APL2 interpreter and several language references.
This detailed explanation of the APL program that prints out N generations of the initial configuration M of the Game of Life will also serve as a brief and very informal course in APL.
Before we start to decipher (this seems to be the correct word here) the Life program, let's try to work out
the strategy of how to write this program in one line, no matter how impossible it sounds.
Life is a cyclic game by its very nature and - surely - the algorithm implementing this game apparently should consist of several cycles. Thus, the main loop of this program is the flow of the generations. Another loop is the one that scans the matrix to calculate the cells that are dead, alive or newborn. Yet another loop calculates the number of neighbors of every given cell. Now, you think, that's it: we cannot use even a single loop inside one line, let alone three nested loops!
But wait a minute - APL allows us to overcome almost any, even the most desperate situation.
First of all, we don't need a loop to scan the matrix, since APL allows us to work with the whole matrix usually using a single function. The same applies to the number of neighbors. As for the main loop that govenrs the change of generations - there will be no such thing at all!
Let N be a number of generations we want to calculate. We can write down all the loops
(that is the subprograms that constitute the body of the loop) as one very long line. Now all we have to do
is to execute this line.
It's not good, - says the reader. - What if we need 1000 generations ? Shall we write down 1000 loops that are doing the same thing then ? Absolutely not! As we've said before, all these loops are doing the same thing, so we will just write down only one loop and then APL will help us to multiply it N times using the ρ (ro) function, for this is the function which creates arrays of any dimension. After this is done we will call an amazing APL function called Execute - . This function executes a string regarding it as a valid line of an APL program. (The almost equal operator in Lisp is called eval). This function will be responsible for execution of a "very long line" of concatenated loop bodies.
Finally, we will have to calculate all the neighbors of every given cell of our matrix.
And this will be the main trick of our program.
Let's represent the live cells of Life as 1 and the empty cells as 0. For our example we will take a 5x5 matrix and put in the middle a very simple yet interesting organism called semaphore:
This is how semaphore behaves:
What shall we do to find a sum of all the neighbors of every cell in the given matrix ?
The number of neighbors is equal to 8, so, if we will shift our matrix 8 times in every possible direction
and then add together all the 1s in the resulting cells - the sum will be equal to the number of 1s
(i.e. the neighbors) surrounding given cell.
In the following picture you can see all 8 matrices after such a shift:
Now, let's sum up all these matrices except the original one:
Here is the closer look at some of the cells that point to their neighbors in the original matrix:
We've got the matrix where every cell contains the number of neighbors of the live cells of the original matrix!
Now, according to the rules of Life those cells that have 2 or 3 neighbors will live in the next generation while all others will die. The empty cells that have exactly 3 neighbors will be born in the next generation.
Performing several simple logical operations over the matrix of neighbors we will get the next generaion of our semaphore.
Having this plan of actions we can start the detailed study of the program.
And here it is:
To decipher the program we will move from right to left because this is the way the APL interpreter
moves. For convenience (and only for convenience, since there is nothing in APL that dictates this)
we will divide our program into logical blocks in a way shown in the following picture:
This way it will be easier to follow the events unfolding.
Between the apostrophes there is a string that constitutes the "body" of our main loop (Block 1):
The first thing that happens here is the Enclose operation performed upon the initial matrix M:
⊂M. Function Enclose turns an array of any dimension into a scalar (that is, the array looses all its
dimensions while its internal content remains intact). This situation is rather peculiar, so a picture may come
The next function is called Rotate: . It rotates the matrix the given number of times relative to its horizontal axes (as seen from the shape of the function). In order to understand the meaning of this function and to explain the symbol '' on its right, let's first look into the left argument of Rotate, namely the expression: (V,V←1 -1).
Two actions are taking place here: the variable V gets assigned with the vector 1 -1 (this is represented as V←1 -1), and then this variable is immediately used (in fact this variable will be used many times in this program). Here we meet the new function - , (comma), which is called Catenate and serves to concatenate two elements into a single vector. Hence, the expression V,V←1 -1 evaluates to a vector consisting of four elements: 1 -1 1 -1. As we already said, a side effect of this expression is the initialization of the variable V.
So, we have the following (Block 2):
Operator '' (which is called Each) influences the function Rotate in such a way,
that each element of the left argument of Rotate will get a counterpart corresponding element of the
righ argument of Rotate and the rotation of the matrix M will happen pair by pair.
(One word about operators: whereas functions work on arrays or scalars, operators work on functions themselves, i.e. if the argument of a function is always an array or a scalar, the argument of an operator is always a function).
Of course, operator Each can be used with any other function of APL.
Note this: in case one of the arguments of the function is a scalar (and you remember that the original matrix M was turned into a scalar by Enclose), this scalar will become a vector with the number of equal elements corresponding to the number of elements of the vector which is another argument of the function. That means we can see our expression as:
Now it's easy to understand what's going on. Matrix M is rotated four times around its horizontal axes:
one row up, one row down, again one row up, and again one row down.
Here is the result:
What we've got here is an intermediate result, of course. Actually, we have to shift every one of these matrices
left and right to get the diagonal shifts after all. And since we already have all necessary knowledge,
we can do it with this expression:
Again, we use the function Rotate, however this time it will rotate the matrices around the vertical
axes (as the symbol implies). The operator Each will work on all four matrices according to the
left argument of Rotate: left, right, right, left. Besides, to gain the maximum profit of the variable V,
we will use it here as well, and instead of the vector 1 -1 -1 1 we'll write
(V,V). Here Rotate is used again and is applied to the V itself.
Maybe, this expression does not help to clarify things here, but it's so APL-like!
Now we know what the result of the expression
looks like. We will call it Block 3:
After the matrix M is shifted in all diagonal directions all is left is to shift it up, down, left and right.
Thus, the result of the expression
And the result of the expression
Finally, the matrix is moved in all 8 directions.
To find the number of neighbors of every cell we have to make a vector consisting of the matrices we've got so far
and sum up all the elements of the vector. In APL we can do it simply like this:
+/ (Block 5) , (Block 4) , (Block 3)
Here another operator is introduced. It is called Reduction and looks like slash: /
The Reduction operator inserts its function-argument (in this case the addition function)
between all elements of the given vector. Note also the Catenate function that creates the vector
of all the blocks.
Here's what we have:
(matrix 1 of block 5) + (matrix 2 of block 5) +
(matrix 1 of block 4) + (matrix 2 of block 4) +
(matrix 1 of block 3) + (matrix 2 of block 3) + (matrix 3 of block 3) + (matrix 4 of block 3).
And now we have the matrix of all neighbors. It is the result of the expression that we called Block 6.
(We should add here that there is one more function performed over the resulting matrix - Disclose: ⊃. It is the exact opposite of the Enclose function. This function turns a scalar containing a matrix back into the matrix with original dimensions).
The next step, as was said, is to find all cells with the number of neighbors equal to 2 or 3,
so that they will continue to live in the next generation, and to find empty cells with the number of neighbors
equal to 3, so that the new cells will be born there.
First, let's compare the matrix of neighbors with the matrix filled with 2s (Block 7), so as the result we'll get the matrix of zeros and ones in such a way, that the ones correspond to the cells having exactly two neighbors:
2=T←The matrix of all neighbors (Block 6)
Here again two actions are performed in parallel: the variable T gets the value of the matrix
of neighbors and at the same time it is compared with the matrix of 2s
(note, that the scalar "2" is expanded to the matrix of 2s whose dimensions are equal to the matrix
it is compared with - that's how APL works).
Here's how the comparison looks like in reality:
And the result of it is:
As you see, the resulting matrix contains in every cell the result of comparison of the corresponding cells of the argument matrices. 1 means that the cells are equal, 0 - otherwise.
If we will perform the logical operation AND (∧) over this and the original matrix M (Block 8),
that is the 1s will be left only in those places where both matrices have 1s, we will get the matrix
where the only live cells are those having exactly two neighbors:
Indeed, in the original matrix M only the central cell has exactly two neighbors.
In the same way we can find all cells who has exactly three neighbors. Note the trick here:
it is not important whether the original cell is empty or alive: we have to let the live cells to live
and fill the empty cells with the newly born 1s.
The result of the expression 3=T (Block 9), where T, as you remember, is the matrix of neighbors, will be:
These cells shall be born in the next generation.
Finally, we have to logically add (using the OR (∨) operation) both matrices from the last two expressions and - voila! - we've calculated the next generation of Life for the matrix M!
All together now:
Block 10 ← The matrix of all neighbors, that is
(3=T)∨M∧2=T ← The matrix of all neighbors
will give the result:
which is indeed the next generation of the semaphore.
Now we have to print out the resulting matrix and we'll do it using APL's output function called Quad: (It is enough to "assign" the matrix to this function).
However, we are not done yet.
Remember, that until now all we did was a calculation of a single generation. Besides, all the actions are still "frozen" between the apostrophes. So, what happens to this string ?
Look at the Block 11. The variable S is assigned with the string denoted Block 1. Note again: S is not equal to the meaning (or the value) of the string, S is equal to the string itself, i.e. to the sequence of characters between the apostrophes. This way we delay the execution of Block 1 until the moment when everything will be ready for calculation N generations of Life. (Remember that Block 1 calculates only one generation).
To turn S from a vector of characters into a scalar we'll use the Enclose function which is already well known to us. Moving left we will discover a new function - Reshape (ρ) with left argument N representing the number of generations we want to calculate. This function will turn a now scalar S into a vector of N equal elements, every one of which contains Block 1, that is the "subroutine" to calculate a single generation. So, in general, we've got a vector of scalars consisting of vectors of characters.
The final metamorphose - yet another function Enlist (∈) serves for making a simple vector out of array consisting of any number of nested elements. Thus, our "complex" vector of N nested elements will become one very long but straightforward vector of characters. Let's name it somehow exceptionally to stress the importance of this vector, say Á, like mathematicians often do.
Here is what to pay attention to: every one of the substrings (i.e. every Block 1) of the vector
begins with the symbol M (the original matrix) and ends with the assignment operator ←
(as usual, the beginning is on the right and the end is on the left).
That is the rightmost character of Á -
is the original matrix M, and the vector itself looks like this (inner contents skipped):
And here we are! Now it's clear what's going on: when the string Á is executed from right to left, every newly calculated value of the matrix M (i.e. every new generation of Life) will be assigned to the same variable M as the new original matrix to calculate the next generation! And the number of generations will be equal to N.
The only remaining problem now is what to do with the leftmost, hanging in the air assignment operator ←. Look at the whole program again - at the very end the arrow is going straight to the symbol - Quad - which is concatenated with the vector Á by comma (Catenate). But does not it mean to print everything out ? Exactly, that's what we need!
And finally in the end of this grandiose act we are meeting the function (Execute) - the one we are already familiar with. This function executes the symbolic string which is this function's argument. Of course, the string should containg syntactically correct expression of APL. So, what is this function ? This is the APL interpreter itself disguised as an innocent function.
Well, what will be the result of the execution of our vector par excellence Á ?
Right - N matrices printed on the screen that represent N generations of Life starting from the original matrix M.
© 2005 Michael Gertelman
Visit World History Timeline!