John Scholes' Conway's Game of Life: Difference between revisions

Latest revision as of 11:49, 1 November 2023

John Scholes' Conway's Game of Life video is perhaps the most famous APL video. In it, John Scholes explains his own implementation of Conway's Game of Life in Dyalog APL, where he, one step at a time, develops the following dfn:

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

Scholes also published notes^[1] on the Game of Life, including alternate implementations, in his dfns workspace. The workspace includes a function which differs in a few small details.

      Life←{↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}

In this page we will break down the function Life to see how each part operates. If you're completely new to APL, you probably won't understand all of it right away—consider also reading some Simple examples or APL introductions. However, you should be able to follow the general ideas. Bear in mind that APL evaluates expressions from right to left unless you use parentheses.

The code here is written for Dyalog APL. It also works in ngn/apl, and other nested array languages allow similar implementations: see #Translations.

In 2021, Conor Hoekstra remade the video with additional explanations.^[2]

The Glider

One interesting pattern that occurs in Life is a Glider:

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

To see how the Glider evolves over the generations, we need to give it some space to move around. The Game of Life takes place on an infinite two-dimensional grid, but that might be a bit large for our computer! Let's start the Glider off in the bottom right-hand corner of a 10 x 10 grid:

      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

After one generation the pattern becomes:

      Life 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 1 0
0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 0

The Glider has slightly changed shape and also moved up and to the left.

Visualising it

To make the pattern easier to see, we can use indexing to place a ⌺ symbol where there's a cell and a · otherwise, for example (note that ⎕IO is Index Origin):

      Show←{'·⌺'[⎕IO+⍵]}
      Show grid
··········
··········
··········
··········
··········
··········
··········
·······⌺⌺⌺
·······⌺··
········⌺·

Here's how the Glider evolves over the first ten generations, computed using the Power operator for iteration:

      Show¨{Life⍣⍵⊢grid}¨0,⍳9
┌──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┐
│··········│··········│··········│··········│··········│··········│··········│··········│··········│··········│
│··········│··········│··········│··········│··········│··········│··········│··········│··········│··········│
│··········│··········│··········│··········│··········│··········│··········│··········│··········│··········│
│··········│··········│··········│··········│··········│··········│··········│··········│··········│··········│
│··········│··········│··········│··········│··········│··········│··········│··········│··········│······⌺···│
│··········│··········│··········│··········│··········│·······⌺··│······⌺⌺··│······⌺⌺··│·····⌺⌺⌺··│·····⌺⌺···│
│··········│········⌺·│·······⌺⌺·│·······⌺⌺·│······⌺⌺⌺·│······⌺⌺··│······⌺·⌺·│·····⌺⌺···│·····⌺····│·····⌺·⌺··│
│·······⌺⌺⌺│·······⌺⌺·│·······⌺·⌺│······⌺⌺··│······⌺···│······⌺·⌺·│······⌺···│·······⌺··│······⌺···│··········│
│·······⌺··│·······⌺·⌺│·······⌺··│········⌺·│·······⌺··│··········│··········│··········│··········│··········│
│········⌺·│··········│··········│··········│··········│··········│··········│··········│··········│··········│
└──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┘

How it works

To compute a new generation in the Game of Life we first need to find out how many neighbours each live cell has. To keep things simple let's consider the following 5-by-5 grid:

      currentGeneration←5 5⍴0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 1 0 0
      currentGeneration
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

Rotation

If we rotate each row of the grid one place left by using APL's Rotate function ⌽, each element is replaced by its right-hand neighbour. In other words, the new grid will have a 1 for all cells whose right-hand neighbour was 1:

      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 to find the left-hand neighbour by using ¯1⌽currentGeneration. By using APL's Outer Product operator ∘. together with the Rotate function we can get a set of three grids containing the left-hand neighbour, the original grid, and the right-hand neighbour:

      ¯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│
└─────────┴─────────┴─────────┘

Here currentGeneration must be enclosed before applying the outer product so that it is treated as a single element rather than rotating each of its Boolean elements (which would have no effect).

Extending to two dimensions

Now we can use a similar trick but rotate up and down by using APL's First Axis Rotate function ⊖. Used with an Outer Product this gives us a series of 9 grids:

     ¯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 grid in the centre is our original grid, and the others give the neighbours above, below, left, right and diagonally.

Summing it up

Now we can find out how many neighbours each cell in the original grid has by summing (Plus Reduce) the corresponding elements in each of the 9 grids. We sum all the grids at once by ravelling the shape 3 3 matrix of grids to obtain a 9-element vector; otherwise Reduce would only allow us to sum rows or columns. Here APL's representation of Booleans as numbers is advantageous, since otherwise counting the number of true values would require converting them to numbers or using conditional logic. For a live cell the sum is 1 more than the number of neighbours—for example, a 4 in the result means a cell has three neighbours. For a dead cell the result is just the number of neighbours:

      +/,¯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:

Any live cell with two neighbours lives, unchanged, to the next generation
Any cell, live or dead, with exactly three neighbours is live in the next generation

This means that all cells which might be live in the next generation will have a sum of 3 (from the first rule) or 3 or 4 (from the second rule).

So we're interested in cells with a sum of 3 or 4. We can find these cells with a simple application of Equal to, relying on pervasion and scalar extension to distribute the data properly. The result of the last step was a scalar containing one grid; when paired with the vector 3 4 it is extended to give two grids. Within each grid 3 and 4 are compared with every element by scalar extension again. If the right argument were a flat array rather than being enclosed, we could obtain a similar, but flat, result using another Outer Product.

     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 next step is best understood by first considering the two scores 4 and 3 separately.

(a) A score of 4 corresponds either to a live cell with three neighbours or a dead cell with four neighbours. Only in the former case do we get a cell in the next generation - i.e. we get a cell if the score is 4 and the cell is currently live. Here we're using 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│
└─────────┘

(b) A score of three corresponds either to a live cell with two neighbours or a dead cell with three neighbours. In either case we get a cell in the next generation:

      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│
└─────────┘

We can write this slightly redundantly by and-ing with 1 (meaning "and the cell is alive or dead") for reasons which will become apparent shortly:

      1∧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│
└─────────┘

So the next step is to say that a cell is live if either test (a) or test (b) is met. We need to use APL's Or function, ∨. We could write this rather 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 1 1 1 0│
│0 1 0 0 0│
│0 1 1 0 0│
│0 0 0 0 0│
└─────────┘

Refactoring

But we can take advantage of APL's Inner Product operator to do the and operations of each test and then or the result - the ∨.∧ in the following:

     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│
└─────────┘

The final expression ends with a bit of housekeeping using Mix (↑) to turn the result back into a simple array (it's currently nested).

Translations

GNU APL

In GNU APL the Inner Product ∨.∧ results in a twice-enclosed matrix, rather than once-enclosed as in Dyalog APL. This can be fixed either by mixing twice, or by using a reduction instead of an inner product.

      Life←{↑↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}
      Life←{↑∨/1 ⍵∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}

dzaima/APL

In dzaima/APL the reduction +/ mixes its result, which defeats our use of scalar extension causing a LENGTH ERROR. Because the sum has only one (matrix) result, enclosing it corrects this issue.

      Life←{↑1 ⍵∨.∧3 4=⊂+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}

The computation of our example grid also fails, because dzaima's Take does not allow overtaking. Instead we can insert the glider into a matrix of zeros using structural Under:

      grid ← ¯10 ¯10↑glider            ⍝ DomainError
      grid ← glider⍢(¯3 ¯3∘↑) 10 10⍴0  ⍝ This works

Ruby

Github user zverok has translated Scholes' dfn to Ruby by first creating an apl module to implement parts of APL. The code is shown on Github and explained on zverok's blog.

LispE

Scholes' program is translated to LispE, an array-oriented Lisp, on this page.

Performance

Although it uses nested arrays to organize the computation, Scholes' Game of Life implementation can still be a fairly fast algorithm on medium and large matrices, competitive with straightforward C implementations. This is because the simple arrays stored in the outer nested array all have the same size as the argument. There are only nine of these arrays, so the overhead associated with nesting is constant and small. Until they are summed, these arrays are Boolean, allowing them to be stored in a packed representation and rotated quickly (Roger Hui states that the Game of Life motivated some improvements to Boolean functions in Dyalog 13.2 and 14.0^[3]). When adding them, recent versions of Dyalog APL use vector instructions, enabling many numbers to be added at once.

The following code times how long it takes to perform 1000 iterations of the Game of Life on a shape 1000 1000 array. This computation performs a billion cell updates, so the total time in seconds is equal to the time taken per update in nanoseconds.

      )copy dfns cmpx
      b←1=?1e3 1e3⍴2
      1 cmpx 'Life⍣1000 ⊢b'

The timings below were taken with various versions of Dyalog APL on an Intel Kaby Lake i7. The largest change appears in 17.0, when Boolean-integer addition was implemented using vector instructions (on this processor, AVX2).

Version	Time (s)
15.0	14.0
16.0	13.5
17.0	1.32
17.1	1.31
18.0 (pre-release)	0.75

References

↑ Scholes, John. life in the dfns workspace.
↑ Hoekstra, Conor. APL + Game of Life = ❤️ in the code_report YouTube channel. 2021-04-25.
↑ Morten Kromberg and Roger Hui. D11: Primitive Performance at Dyalog '13 (script). 2013-10.

[1] Scholes, John. life in the dfns workspace.

[2] Hoekstra, Conor. APL + Game of Life = ❤️ in the code_report YouTube channel. 2021-04-25.

[3] Morten Kromberg and Roger Hui. D11: Primitive Performance at Dyalog '13 (script). 2013-10.

[1]

[2]

[3]

John Scholes' Conway's Game of Life: Difference between revisions

Latest revision as of 11:49, 1 November 2023

Contents

The Glider

Visualising it

How it works

Rotation

Extending to two dimensions

Summing it up

Refactoring

Translations

GNU APL

dzaima/APL

Ruby

LispE

Performance

References

Navigation menu

@@ Line 1: / Line 1: @@
-Perhaps the most famous APL video is [[John Scholes]] explaining his own implementation of [[Conway's Game of Life]] in [[Dyalog APL]].<ref>[[John Scholes|Scholes, John]]. [https://www.youtube.com/watch?v=a9xAKttWgP4 "Conway's Game of Life in APL"]. 2009-01-26.</ref> Scholes also published notes<ref>[[John Scholes|Scholes, John]]. [http://dfns.dyalog.com/n_life.htm life] in the [[dfns workspace]].</ref> on the Game of Life, including alternate implementations, in his [[dfns workspace]].
+[https://www.youtube.com/watch?v=a9xAKttWgP4 '''John Scholes' Conway's Game of Life''' video] is perhaps the most famous APL video. In it, [[John Scholes]] explains his own implementation of [[Conway's Game of Life]] in [[Dyalog APL]], where he, one step at a time, develops the following [[dfn]]:
+<syntaxhighlight lang=apl>
+      life ← {⊃1 ⍵ ∨.∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵}
+</syntaxhighlight>
-Here is the full implementation:
+Scholes also published notes<ref>[[John Scholes|Scholes, John]]. [http://dfns.dyalog.com/n_life.htm life] in the [[dfns workspace]].</ref> on the Game of Life, including alternate implementations, in his [[dfns workspace]]. The workspace includes a function which differs in a few small details.
-<source lang=apl>
+<syntaxhighlight lang=apl>
        Life←{↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}
-</source>
+</syntaxhighlight>
-In this page we will break down the function to see how each part operates. If you're completely new to APL, you probably won't understand all of it right away—consider also reading some [[Simple examples]] or APL [[introductions]]. However, you should be able to follow the general ideas. Bear in mind that APL evaluates expressions from [[Evaluation order|right to left]] unless you use parentheses.
+In this page we will break down the function <syntaxhighlight lang=apl inline>Life</syntaxhighlight> to see how each part operates. If you're completely new to APL, you probably won't understand all of it right away—consider also reading some [[Simple examples]] or APL [[introductions]]. However, you should be able to follow the general ideas. Bear in mind that APL evaluates expressions from [[Evaluation order|right to left]] unless you use parentheses.
 The code here is written for [[Dyalog APL]]. It also works in [[ngn/apl]], and other [[Nested array theory|nested]] array languages allow similar implementations: see [[#Translations]].
+In 2021, Conor Hoekstra remade the video with additional explanations.<ref>Hoekstra, Conor. [https://www.youtube.com/watch?v=pMslgySQ8nc APL + Game of Life = ❤️] in the [https://www.youtube.com/channel/UC1kBxkk2bcG78YBX7LMl9pQ code_report YouTube channel]. 2021-04-25.</ref>
 == The Glider ==
 One interesting pattern that occurs in Life is a [[wikipedia:Glider (Conway's Life)|Glider]]:
-<source lang=apl>
+<syntaxhighlight lang=apl>
        glider←3 3⍴1 1 1 1 0 0 0 1 0
        glider
@@ Line 19: / Line 24: @@
 0 0
 1 0
-</source>
+</syntaxhighlight>
 To see how the Glider evolves over the generations, we need to give it some space to move around. The Game of Life takes place on an infinite two-dimensional grid, but that might be a bit large for our computer! Let's start the Glider off in the bottom right-hand corner of a 10 x 10 grid:
-<source lang=apl>
+<syntaxhighlight lang=apl>
        grid←¯10 ¯10↑glider
        grid
@@ Line 35: / Line 40: @@
 0 0 0 0 0 0 1 0 0
 0 0 0 0 0 0 0 1 0
-</source>
+</syntaxhighlight>
 After one generation the pattern becomes:
-<source lang=apl>
+<syntaxhighlight lang=apl>
        Life grid
 0 0 0 0 0 0 0 0 0
@@ Line 50: / Line 55: @@
 0 0 0 0 0 0 1 0 1
 0 0 0 0 0 0 0 0 0
-</source>
+</syntaxhighlight>
 The Glider has slightly changed shape and also moved up and to the left.
@@ Line 56: / Line 61: @@
 === Visualising it ===
-To make the pattern easier to see, we can use [[indexing]] to place a <source lang=apl inline>⌺</source> symbol where there's a cell and a <source lang=apl inline>·</source> otherwise, for example:
+To make the pattern easier to see, we can use [[Bracket indexing|indexing]] to place a <syntaxhighlight lang=apl inline>⌺</syntaxhighlight> symbol where there's a cell and a <syntaxhighlight lang=apl inline>·</syntaxhighlight> otherwise, for example (note that <syntaxhighlight lang=apl inline>⎕IO</syntaxhighlight> is [[Index Origin]]):
-<source lang=apl>
+<syntaxhighlight lang=apl>
        Show←{'·⌺'[⎕IO+⍵]}
        Show grid
@@ Line 70: / Line 75: @@
 ·······⌺··
 ········⌺·
-</source>
+</syntaxhighlight>
 Here's how the Glider evolves over the first ten generations, computed using the [[Power operator]] for iteration:
-<source lang=apl>
+<syntaxhighlight lang=apl>
        Show¨{Life⍣⍵⊢grid}¨0,⍳9
 ┌──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┐
@@ Line 87: / Line 92: @@
 │········⌺·│··········│··········│··········│··········│··········│··········│··········│··········│··········│
 └──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┘
-</source>
+</syntaxhighlight>
 == How it works ==
 To compute a new generation in the Game of Life we first need to find out how many neighbours each live cell has. To keep things simple let's consider the following 5-by-5 grid:
-<source lang=apl>
+<syntaxhighlight lang=apl>
        currentGeneration←5 5⍴0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 1 0 0
        currentGeneration
@@ Line 100: / Line 105: @@
 0 1 0 0
 0 0 0 0
-</source>
+</syntaxhighlight>
 === Rotation ===
-If we rotate each row of the grid one place left by using APL's [[Rotate]] function <source lang=apl inline>⌽</source>, each element is replaced by its right-hand neighbour. In other words, the new grid will have a 1 for all cells whose right-hand neighbour was 1:
+If we rotate each row of the grid one place left by using APL's [[Rotate]] function <syntaxhighlight lang=apl inline>⌽</syntaxhighlight>, each element is replaced by its right-hand neighbour. In other words, the new grid will have a 1 for all cells whose right-hand neighbour was 1:
-<source lang=apl>
+<syntaxhighlight lang=apl>
 ⌽currentGeneration
 0 0 0 0
@@ Line 111: / Line 116: @@
 1 0 0 0
 0 0 0 0
-</source>
+</syntaxhighlight>
-Similarly we can rotate right to find the left-hand neighbour by using <source lang=apl inline>¯1⌽currentGeneration</source>. By using APL's [[Outer Product]] operator <source lang=apl inline>∘.</source> together with the Rotate function we can get a set of three grids containing the left-hand neighbour, the original grid, and the right-hand neighbour:
+Similarly we can rotate right to find the left-hand neighbour by using <syntaxhighlight lang=apl inline>¯1⌽currentGeneration</syntaxhighlight>. By using APL's [[Outer Product]] operator <syntaxhighlight lang=apl inline>∘.</syntaxhighlight> together with the Rotate function we can get a set of three grids containing the left-hand neighbour, the original grid, and the right-hand neighbour:
-<source lang=apl>
+<syntaxhighlight lang=apl>
        ¯1 0 1∘.⌽⊂currentGeneration
 ┌─────────┬─────────┬─────────┐
@@ Line 124: / Line 129: @@
 │0 0 0 0 0│0 0 0 0 0│0 0 0 0 0│
 └─────────┴─────────┴─────────┘
-</source>
+</syntaxhighlight>
-Here <source lang=apl inline>currentGeneration</source> must be [[enclose]]d before applying the outer product so that it is treated as a single [[element]] rather than rotating each of its Boolean elements (which would have no effect).
+Here <syntaxhighlight lang=apl inline>currentGeneration</syntaxhighlight> must be [[enclose]]d before applying the outer product so that it is treated as a single [[element]] rather than rotating each of its Boolean elements (which would have no effect).
 === Extending to two dimensions ===
-Now we can use a similar trick but rotate up and down by using APL's First Axis Rotate function <source lang=apl inline>⊖</source>. Used with an Outer Product this gives us a series of 9 grids:
+Now we can use a similar trick but rotate up and down by using APL's First Axis Rotate function <syntaxhighlight lang=apl inline>⊖</syntaxhighlight>. Used with an Outer Product this gives us a series of 9 grids:
-<source lang=apl>
+<syntaxhighlight lang=apl>
       ¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
 ┌─────────┬─────────┬─────────┐
@@ Line 152: / Line 157: @@
 │0 0 0 0 0│0 0 0 0 0│0 0 0 0 0│
 └─────────┴─────────┴─────────┘
-</source>
+</syntaxhighlight>
 The grid in the centre is our original grid, and the others give the neighbours above, below, left, right and diagonally.
 === Summing it up ===
-Now we can find out how many neighbours each cell in the original grid has by summing ([[Plus]] [[Reduce]]) the corresponding elements in each of the 9 grids. We sum all the grids at once by [[ravel]]ling the [[shape]] <source lang=apl inline>3 3</source> [[matrix]] of grids to obtain a 9-element [[vector]]; otherwise [[Reduce]] would only allow us to sum rows or columns. Here APL's representation of [[Boolean]]s as numbers is advantageous, since otherwise counting the number of true values would require converting them to numbers or using conditional logic. For a live cell the sum is 1 more than the number of neighbours—for example, a 4 in the result means a cell has three neighbours. For a dead cell the result is just the number of neighbours:
+Now we can find out how many neighbours each cell in the original grid has by summing ([[Plus]] [[Reduce]]) the corresponding elements in each of the 9 grids. We sum all the grids at once by [[ravel]]ling the [[shape]] <syntaxhighlight lang=apl inline>3 3</syntaxhighlight> [[matrix]] of grids to obtain a 9-element [[vector]]; otherwise [[Reduce]] would only allow us to sum rows or columns. Here APL's representation of [[Boolean]]s as numbers is advantageous, since otherwise counting the number of true values would require converting them to numbers or using conditional logic. For a live cell the sum is 1 more than the number of neighbours—for example, a 4 in the result means a cell has three neighbours. For a dead cell the result is just the number of neighbours:
-<source lang=apl>
+<syntaxhighlight lang=apl>
        +/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
 ┌─────────┐
@@ Line 167: / Line 172: @@
 │0 1 1 1 0│
 └─────────┘
-</source>
+</syntaxhighlight>
 For a cell to exist in the next generation, one of two rules must be met:
@@ Line 176: / Line 181: @@
 This means that all cells which might be live in the next generation will have a sum of 3 (from the first rule) or 3 or 4 (from the second rule).
-So we're interested in cells with a sum of 3 or 4. We can find these cells with a simple application of [[Equal to]], relying on [[pervasion]] and [[scalar extension]] to distribute the data properly. The result of the last step was a [[scalar]] containing one grid; when paired with the [[vector]] <source lang=apl inline>3 4</source> it is extended to give two grids. Within each grid 3 and 4 are compared with every element by scalar extension again. If the right argument were a flat array rather than being [[enclose]]d, we could obtain a similar, but flat, result using another [[Outer Product]].
+So we're interested in cells with a sum of 3 or 4. We can find these cells with a simple application of [[Equal to]], relying on [[pervasion]] and [[scalar extension]] to distribute the data properly. The result of the last step was a [[scalar]] containing one grid; when paired with the [[vector]] <syntaxhighlight lang=apl inline>3 4</syntaxhighlight> it is extended to give two grids. Within each grid 3 and 4 are compared with every element by scalar extension again. If the right argument were a flat array rather than being [[enclose]]d, we could obtain a similar, but flat, result using another [[Outer Product]].
-<source lang=apl>
+<syntaxhighlight lang=apl>
 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
 ┌─────────┬─────────┐
@@ Line 187: / Line 192: @@
 │0 0 0 0 0│0 0 0 0 0│
 └─────────┴─────────┘
-</source>
+</syntaxhighlight>
 The next step is best understood by first considering the two scores 4 and 3 separately.
-(a) A score of 4 corresponds either to a live cell with three neighbours or a dead cell with four neighbours. Only in the former case do we get a cell in the next generation - i.e. we get a cell if the score is 4 ''and'' the cell is currently live. Here we're using APL's [[And]] function, <source lang=apl inline>∧</source>
+(a) A score of 4 corresponds either to a live cell with three neighbours or a dead cell with four neighbours. Only in the former case do we get a cell in the next generation - i.e. we get a cell if the score is 4 ''and'' the cell is currently live. Here we're using APL's [[And]] function, <syntaxhighlight lang=apl inline>∧</syntaxhighlight>
-<source lang=apl>
+<syntaxhighlight lang=apl>
      (⊂currentGeneration)∧4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
 ┌─────────┐
@@ Line 201: / Line 206: @@
 │0 0 0 0 0│
 └─────────┘
-</source>
+</syntaxhighlight>
 (b) A score of three corresponds either to a live cell with two neighbours or a dead cell with three neighbours. In either case we get a cell in the next generation:
-<source lang=apl>
+<syntaxhighlight lang=apl>
 =+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
 ┌─────────┐
@@ Line 213: / Line 218: @@
 │0 0 0 0 0│
 └─────────┘
-</source>
+</syntaxhighlight>
 We can write this slightly redundantly by ''and''-ing with 1 (meaning "''and'' the cell is alive or dead") for reasons which will become apparent shortly:
-<source lang=apl>
+<syntaxhighlight lang=apl>
 ∧3=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
 ┌─────────┐
@@ Line 225: / Line 230: @@
 │0 0 0 0 0│
 └─────────┘
-</source>
+</syntaxhighlight>
-So the next step is to say that a cell is live if either test (a) ''or'' test (b) is met. We need to use APL's [[Or]] function, <source lang=apl inline>∨</source>. We could write this rather long-windedly as:
+So the next step is to say that a cell is live if either test (a) ''or'' test (b) is met. We need to use APL's [[Or]] function, <syntaxhighlight lang=apl inline>∨</syntaxhighlight>. We could write this rather long-windedly as:
-<source lang=apl>
+<syntaxhighlight lang=apl>
       (1∧3=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration)∨(⊂currentGeneration)∧4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
 ┌─────────┐
@@ Line 237: / Line 242: @@
 │0 0 0 0 0│
 └─────────┘
-</source>
+</syntaxhighlight>
 === Refactoring ===
-But we can take advantage of APL's [[Inner Product]] operator to do the ''and'' operations of each test and then ''or'' the result - the <source lang=apl inline>∨.∧</source> in the following:
+But we can take advantage of APL's [[Inner Product]] operator to do the ''and'' operations of each test and then ''or'' the result - the <syntaxhighlight lang=apl inline>∨.∧</syntaxhighlight> in the following:
-<source lang=apl>
+<syntaxhighlight lang=apl>
 currentGeneration∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂currentGeneration
 ┌─────────┐
@@ Line 251: / Line 256: @@
 │0 0 0 0 0│
 └─────────┘
-</source>
+</syntaxhighlight>
+The final expression ends with a bit of housekeeping using [[Mix]] (<syntaxhighlight lang=apl inline>↑</syntaxhighlight>) to turn the result back into a simple array (it's currently nested).
+== Translations ==
+=== GNU APL ===
+In [[GNU APL]] the [[Inner Product]] <syntaxhighlight lang=apl inline>∨.∧</syntaxhighlight> results in a twice-[[enclose]]d matrix, rather than once-enclosed as in [[Dyalog APL]]. This can be fixed either by [[mix]]ing twice, or by using a [[Reduce|reduction]] instead of an inner product.
+<syntaxhighlight lang=apl>
+      Life←{↑↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}
+      Life←{↑∨/1 ⍵∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}
+</syntaxhighlight>
+=== dzaima/APL ===
+In [[dzaima/APL]] the [[Reduce|reduction]] <syntaxhighlight lang=apl inline>+/</syntaxhighlight> [[mix]]es its result, which defeats our use of [[scalar extension]] causing a [[LENGTH ERROR]]. Because the sum has only one (matrix) result, enclosing it corrects this issue.
+<syntaxhighlight lang=apl>
+      Life←{↑1 ⍵∨.∧3 4=⊂+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}
+</syntaxhighlight>
+The computation of our example <syntaxhighlight lang=apl inline>grid</syntaxhighlight> also fails, because dzaima's [[Take]] does not allow overtaking. Instead we can insert the glider into a matrix of zeros using [[structural Under]]:
+<syntaxhighlight lang=apl>
+      grid ← ¯10 ¯10↑glider            ⍝ DomainError
+      grid ← glider⍢(¯3 ¯3∘↑) 10 10⍴0  ⍝ This works
+</syntaxhighlight>
+=== Ruby ===
+Github user zverok has translated Scholes' dfn to [[wikipedia:Ruby (programming language)|Ruby]] by first creating an <syntaxhighlight lang=ruby inline>apl</syntaxhighlight> module to implement parts of APL. The code is shown [https://github.com/zverok/ruby_as_apl on Github] and explained [https://zverok.github.io/blog/2020-05-16-ruby-as-apl.html on zverok's blog].
+=== LispE ===
+Scholes' program is translated to LispE, an array-oriented Lisp, on [https://github.com/naver/lispe/wiki/6.20-Conway-Game-of-Life-in-LispE this page].
+== Performance ==
+Although it uses [[nested]] arrays to organize the computation, Scholes' Game of Life implementation can still be a fairly fast algorithm on medium and large matrices, competitive with straightforward C implementations. This is because the [[simple]] arrays stored in the outer nested array all have the same size as the argument. There are only nine of these arrays, so the overhead associated with nesting is constant and small. Until they are summed, these arrays are [[Boolean]], allowing them to be stored in a packed representation and [[rotate]]d quickly ([[Roger Hui]] states that the Game of Life motivated some improvements to Boolean functions in [[Dyalog APL 13.2|Dyalog 13.2]] and [[Dyalog APL 14.0|14.0]]<ref>[[Morten Kromberg]] and [[Roger Hui]]. D11: [https://dyalog.tv/Dyalog13/?v=84t87EO5ZEE Primitive Performance] at [[Dyalog '13]]  ([https://www.dyalog.com/uploads/conference/dyalog13/presentations/D11_Primitive_Performance/perfscript1.htm#2 script]). 2013-10.</ref>). When adding them, recent versions of Dyalog APL use [[vector instructions]], enabling many numbers to be added at once.
-The final expression ends with a bit of housekeeping using [[Mix]] (<source lang=apl inline>↑</source>) to turn the result back into a simple array (it's currently nested).
+The following code times how long it takes to perform 1000 iterations of the Game of Life on a shape <syntaxhighlight lang=apl inline>1000 1000</syntaxhighlight> array. This computation performs a billion cell updates, so the total time in seconds is equal to the time taken per update in nanoseconds.
+<syntaxhighlight lang=apl>
+      )copy dfns cmpx
+      b←1=?1e3 1e3⍴2
+cmpx 'Life⍣1000 ⊢b'
+</syntaxhighlight>
+The timings below were taken with various versions of [[Dyalog APL]] on an Intel Kaby Lake i7. The largest change appears in 17.0, when [[Boolean]]-integer [[addition]] was implemented using vector instructions (on this processor, AVX2).
+{|class=wikitable
+! Version                                !! Time (s)
+|-
+| [[Dyalog APL 15.0|15.0]]               || 14.0
+|-
+| [[Dyalog APL 16.0|16.0]]               || 13.5
+|-
+| [[Dyalog APL 17.0|17.0]]               ||  1.32
+|-
+| [[Dyalog APL 17.1|17.1]]               ||  1.31
+|-
+| [[Dyalog APL 18.0|18.0]] (pre-release) ||  0.75
+|}
 == References ==
 <references />
+[[Category:Examples]][[Category:Dyalog APL examples]]

John Scholes' Conway's Game of Life: Difference between revisions

Latest revision as of 11:49, 1 November 2023

The Glider

Visualising it

How it works

Rotation

Extending to two dimensions

Summing it up

Refactoring

Translations

GNU APL

dzaima/APL

Ruby

LispE

Performance

References

Navigation menu

Search