Life: Nasty, brutish, and short
Eugene E. McDonnell · ACM SIGAPL APL Quote Quad · 1987
This paper describes a series of functions for performing Conway's game of Life [Ga70] in APL, beginning with versions that go back to the early 1970's. The paper doesn't deal with the game itself, but rather with the expressive power of various approaches, and particularly with the increased expressiveness found in some of the new operator extensions to APL. Given a state of the game, which we can think of as a Boolean matrix, the object, from the point of view of this paper, is to produce the next state, or generation, of the game. The rules for providing the next Boolean matrix are: consider the eight cells surrounding a given cell in the current matrix (ignoring border cells); the corresponding cell in the next matrix will have the value 1 if the current value is 0 and exactly three of the surrounding cells are 1, or if the current value is 1 and either two or three of the surrounding cells are 1. Expressed this way, it is easy to see why many APL versions of Life have appeared since the game was first discussed in 1970, since APL is admirably suited to dealing with matrices in general and Boolean matrices in particular. Several APL versions of the game of Life appeared in the magazine APL Quote-Quad . The first of these was given by Duby [Du71]. I have taken the liberty of changing the display form of the function, in order to allow it to be studied more easily. In its original form, this was a seven-line function. I have broken it into many more lines by putting on separate lines all uses of assignment, and removing all uses of locutions such as .op. The function uses index origin 0. The part of this function that we are interested in begins at label Next , and goes to the end of the function. This is the part where the next state is computed. Unlike most of the other versions we will study, this one attends to the matter of growing and shrinking the size of the matrix in accordance with the location of the living cells in each state. The assignment to ƒ in Loopy is the actual development of the next state. Note that it treats the creation of the next state as a scalar operation, computing Loopy x times y times, where x is the number of rows in the matrix and y is the number of columns. For each cell, the values in the neighbor cells are computed, and used to determine the value of the corresponding cell in the next state. Thus, this first recorded attempt doesn't make much use of APL's ability to describe matrix operations “all at once”. The obvious inefficiencies of the approach of Algorithm 70 led to the appearance of two new versions in the following year. The first of these that I will discuss is due to Bonyun [BO72]. This function as it originally appeared had only four (very long) lines. I have performed the same untangling for it that I did for Algorithm 70. This function uses index origin 1. It also takes care of growing and shrinking the matrix mat according to the size of the living cell population. The five lines of the function that I have marked with a comment symbol determine the next state, using a strategy that will become familiar. In the line marked (*), eight terms enter into the formation of a sum; each of these terms gives one of the eight neighbors of each cell, and the sum gives the total number of living neighbors of each cell. Thus, the function makes good use of APL's matrix-handling abilities. The eight neighbors are found by appropriate rotations of the matrix, in various combinations. Thus, the neighbor cell to the upper left of the cell is found by - 1φ - 1θ (the term shown as ( - 1φ h )), and so forth. The function uses a global variable mat , and I shall stigmatize a function which uses a global variable as nasty . In the same issue as Bonyun's algorithm appeared the next solution to the problem. It was provided by W.J. Jones [Jo72]. It is in index-origin 1. It assumes a fixed sized state matrix of 20 rows by 20 columns. Jones determines the next state in the two lines marked with the comment symbol. Essential to his solution is the matrix r , which gives the indices of the state matrix in staggered form: 2 3 4 5 6 7 8 9 10…18 19 20 1 1 2 3 4 5 6 7 8 9…17 18 19 20 20 1 2 3 4 5 6 7 8…16 17 19 19 This is used to give all possible vertical and horizontal alignments of an element with adjacent elements. A solution which uses such a brute-force approach to a solution I shall call brutish . The first line marked with a comment symbol develops t by using r as both a row and a column index to the state matrix a , thereby giving a four-dimensional result, and summing this along the first and third dimensions; this is used in the next commented line to determine the living cells in the next state via a simple pair of tests. Jones displays the successive states followed by a separator line which includes the state number and the number of living elements. The next version of Life appeared in Apl Quote-Quad in 1974 [Si74]. The authors were high school students, who describe their version as follows: [The function] has the syntax: Increment Life Matrix where Increment is how often the pattern is to be printed (1 = every generation, 2 = every other generation, etc.) and Matrix is a binary matrix which has 1's for occupied cells and 0's for unoccupied cells. The function operates in either origin and prints the character 0 for occupied cells. It also prints a set of statistics with each generation printed, showing: population, births, deaths, and survivals. The program will stop and print an explanatory message if the pattern dies out or becomes stable. The program operates on the principle of creating eight identical matrices of the pattern and offsetting each one in a different direction. When these matrices are summed together the resulting matrix represents how many neighboring occupied cells each cell has. The matrix (called sum in the program) is then used to compute the succeeding generations. This program uses little CPU time because the only primitive functions used to compute the sum matrix are + and ↑ which are two of the fastest primitives. I've tried to make this function more readable by various means, but it does not seem to be a notational improvement over the ones we have already seen. Our next example comes from the year 1984. In that year one of the commercial PC publications contained an article [Wy84] which compared several programming languages in terms of their ability to describe the game of Life. One of the languages used was APL. The example in APL was nicely structured, and there were several functions, of which I shall show only two: the outermost function called LifeGame and the function which produces the next generation, called NextGen : The best comment on this comes from Donald McIntyre, who wrote: This is an excellent representation for the purpose of the beginning tutorial for which it was written. Its clarity is admirable. But it is not the final formulation that I would want my students to aim for. Long names for variables are no doubt necessary in programs such as Fortran and COBOL that commonly run to hundreds of lines, but just as long names are never used in formulas by mathematicians, physicists, or engineers, so they are unnecessary in short functions (often of a single line) defined in APL. Long names have a superficial appearance of good documentation, but in my opinion they tend to conceal rather than illuminate the operation of functions containing them. This quotation comes from an article submitted by McIntyre to the same journal, but which was never printed [McI84]. He shows how the logic of the NextGen function can be considerably simplified, by applying the rules of logic, and then presents a suite of functions of his own, embodying the principles he espouses. I found out about this unprinted