6.20 Conway Game of Life in LispE

A Single Line of Code

Version française

Conway's Game of Life is played on an infinite grid and can be summarized by the following three rules:

1. A dead cell with exactly three live neighbors comes to life.
2. A live cell with two or three live neighbors survives.
3. In all other configurations, the cell dies.

A few years ago, an APL program made quite a stir. It implemented the Game of Life in... a single line of code:

life ← {⊃1 ⍵ ∨.∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵}

This code, with its cryptic and mysterious appearance, left many observers perplexed. APL belongs to a family of languages known as array languages, which are designed to replace the usual keywords of languages with a set of mathematical symbols that can manipulate scalar values, vectors, or matrices of varying sizes. Users of these languages assert that they are as readable, if not more so, than traditional languages, and they often enjoy discovering the most concise and efficient ways of combining these symbols to implement complex algorithms. The Game of Life is their latest victim, so to speak.

Now, we will show how LispE can shed light on the hidden workings of this "diabolical" code.

LispE

Why choose LispE?

For a simple reason: LispE is a Lisp dialect that is based on arrays rather than linked lists. Therefore, many APL operators can be implemented in LispE.

Unfortunately, as a true representative of the Lisp family, parentheses are abundant... in great number:

(sqrt (sum (maplist (λ(x) (* x 2)) '(1 2 3 4 5 6))))

What APL condenses into a few symbols:

√+/2ר1 2 3 4 5 6.

It is clear that no dialect of Lisp will ever achieve such conciseness. However, we may be able to draw inspiration from other existing languages to at least reduce the number of parentheses.

The Composition Operator

LispE has an operator that allows multiple function calls to be combined into a single integrated expression.

For example, a typical LispE expression that applies two functions, filter and map, to a list generated by iota 10 is usually written as follows:

(filter '(< 10) (map '(* 2) (iota 10)))

However, with the composition operator . , this expression can be simplified by composing these functions:

(filter '(< 10) . map '(* 2) (iota 10))

Furthermore, there is no limit to the number of functions that can be composed using this operator. For instance, you can calculate the square root of the sum of a sequence of numbers with:

(sqrt . sum . iota 10) ; 7.4162

Let's be honest: what this operator allows is to skip the parentheses of the last element in the list. But it has the good taste of existing and allowing a significant reduction in parentheses. We just need to be aware that in certain cases, it can lead to an error.

; Unfortunately, the compiler rewrites this expression as: (cons (car '(a b c) 'd))
(cons . car '(a b c) 'd) 

The ultimate one-liner

Let's revisit the famous APL program:

life ← {⊃1 ⍵ ∨.∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵}

First of all, it is important to understand that an APL program is interpreted from right to left. The ⍵ here is equivalent to a function argument. In APL, a distinction is made between monadic and dyadic operators:

• A monadic operator takes a single argument on its right.
• A dyadic operator takes two arguments, one on the left and one on the right.

If we take the rightmost part of the expression: ¯1 0 1 ⌽¨ ⊂⍵, we see that it consists of three operators: ⌽¨ ⊂. The first takes a matrix, which corresponds to the grid of Conway's Game of Life, and transforms it into a list of subsets; it is monadic. The ¨ operator then applies the ⌽ operator to each element of this list. ⌽ performs three rotations -1 0 1 on the columns of the initial matrix ⍵, resulting in three new matrices.

If we translate this code into LispE, we get:

; We will initialize ⍵ with a matrix of 1s and 0s
; Note that LispE allows the use of Unicode characters in variable names
(setq ⍵ (rho 5 5 . integers 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 ))

The initial matrix ⍵ has the following shape:

   (0 0 0 0 0)
   (0 0 0 1 0)
   (0 1 1 1 0)
   (0 0 0 0 0)
   (0 0 0 0 0)

We then apply three different rotations to ⍵:

(maplist (λ(x) (rotate ⍵ x)) '(-1 0 1))

; Note that rotate can also be written as: ⌽
(maplist (λ(x) (⌽ ⍵ x)) '(-1 0 1))

After applying maplist, we obtain a list of three matrices:

; rotation -1
      (0 0 0 0 0)
      (0 0 1 0 0)
      (1 1 1 0 0)
      (0 0 0 0 0)
      (0 0 0 0 0)

; rotation 0      
      (0 0 0 0 0)
      (0 0 0 1 0)
      (0 1 1 1 0)
      (0 0 0 0 0)
      (0 0 0 0 0)

; rotation 1
      (0 0 0 0 0)
      (0 0 0 0 1)
      (0 0 1 1 1)
      (0 0 0 0 0)
      (0 0 0 0 0)

"To fully understand the underlying idea, it is necessary to remember that what matters here is knowing the number of neighbors of a given cell. The rotations allow each iteration to bring the set of neighbors of each cell back to the grid position."

Therefore, we first perform two rotations of the columns, one to the left and one to the right. The rotation 0 simply preserves the initial grid.

Then, we apply to each of these 3 matrices a rotation of the rows. This will result in a total of 9 matrices.

In APL code, this is achieved using the outer product: °. and applying row rotation using the ⊖ operator:

¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵

In other words, we apply 3 row rotations to each of the matrices obtained by column rotation, resulting in 9 matrices.

In LispE, this becomes:

(outer (λ(x ⍺) . rotate  ⍺ x true) '(1 0 -1)  . maplist (λ(x) . rotate ⍵ x) '(1 0 -1))

; Note that the outer function can also be written as: °

; To maintain correspondence with APL, we define the following macro:
(defmacro ⊖(l n) (rotate l n true))

; We can then rewrite the line above as:
(° (λ(x ⍺) . ⊖ ⍺ x) '(1 0 -1)  . maplist (λ(x) . ⌽ ⍵ x) '(1 0 -1))

Obviously, we are far from the conciseness of the APL language, but nonetheless, we can see the same operators. rotate ⍺ x true performs a row rotation of the matrices resulting from maplist.

We then simply sum the columns and the rows:

+/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵

The first operator, +⌿, performs a column reduction, and the second performs a row reduction by summing the values together.

LispE offers the same operators:

(-// '+ . -// '+ . ° (λ(x ⍺) . ⊖ ⍺ x) '(1 0 -1) . maplist (λ(x) . ⌽ ⍵ x) '(1 0 -1))

This results in:

   (0 0 1 1 1)
   (1 2 4 3 2)
   (1 2 4 3 2)
   (1 2 3 2 1)
   (0 0 0 0 0)

The rule is as follows:

• If the value of the cell is 3, it will be alive in the next cycle.
• If the value of the cell is 4, if a cell was alive in the current cycle, it will survive in the next cycle.

3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵

The = operator tests the values on its left against the matrix on its right and generates two Boolean matrices, placing a 1 at positions corresponding to a 3 or a 4.

To satisfy the condition for cells with a value of 4, an intersection is made with the original matrix, followed by a union with the matrix of 3s:

1 ⍵ ∨.∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵

In LispE, this becomes our own implementation of the game of life:

; The final expression: it is also a one-liner

((λ(⍺) (| (& (== ⍺ 4) ⍵) (== ⍺ 3))) . -// '+ . -// '+ . ° (λ(x ⍺) . ⊖ ⍺ x) '(1 0 -1) . maplist (λ(x) . ⌽ ⍵ x) '(1 0 -1))

; or with parenthèses:
(
   (λ(⍺) 
      (| 
         (& (== ⍺ 4) ⍵) 
         (== ⍺ 3)
      )
   )
   (-// '+ (-// '+
      (° (λ(x ⍺) (⊖ ⍺ x)) 
         '(1 0 -1) 
         (maplist (λ(x) (⌽ ⍵ x)) '(1 0 -1))
      )
    ))
)```

The `==` operator performs a complete scan of the matrix to detect the presence of 3s or 4s.
Note that a lambda function is created that applies to the previous expression to share the variable `⍺` for finding the 3s and 4s.

The calculation for the 4s forces an intersection with the values of the initial matrix: `(& (== ⍺ 4) ⍵)`, followed by a union.

The result is:

```Lisp
; Next step
   (0 0 0 0 0)
   (0 0 0 1 0)
   (0 0 1 1 0)
   (0 0 1 0 0)
   (0 0 0 0 0)

Conclusion

Conway's Game of Life, implemented in a single line of code in APL, generated a lot of interest. The code uses mathematical operations to manipulate matrices and implement the rules of the game. APL is an array language, where operations are performed on vectors and matrices, which allows for remarkable conciseness and efficiency.

Thanks to the composition operator in LispE, we were able to reveal the hidden mechanisms behind this complex APL line of code. By using operations like column and row rotations, column and row reductions, and the application of specific rules, we were able to step-by-step understand how this implementation of the Game of Life works.

LispE is a Lisp-based programming language that uses arrays instead of linked lists. While it may not match the conciseness of APL, LispE offers enough features to translate and understand complex APL codes.

In conclusion, the implementation of Conway's Game of Life in a single line of code in APL is a striking example of the power of array languages. Although its conciseness is hard to match in other languages, the translation and step-by-step analysis in a language like LispE allow us to demystify this complex line of code and understand the underlying mathematical operations.