Conway's Game of Life: Difference between revisions

From APL Wiki
Jump to navigation Jump to search
Miraheze>Adám Brudzewsky
 
m (→‎Historical implementations: Link to Cut, not Cut (operator))
 
(29 intermediate revisions by 4 users not shown)
Line 1: Line 1:
'''[[wikipedia:Conway's Game of Life|Conway's Game of Life]]''' is a well-known cellular automaton in which each generation of a population 'evolves' from the previous one according to a set of predefined rules.
'''[[wikipedia:Conway's Game of Life|Conway's Game of Life]]''' is a well-known cellular automaton in which each generation of a population "evolves" from the previous one according to a set of predefined rules. The Game of Life is defined on an infinite [[Boolean]] grid, but usually only finite patterns, where all 1 values fit in a finite Boolean [[matrix]], are studied. Because it involves interactions between adjacent [[elements]] of the matrix, and can take advantage of APL's convenient and fast Boolean handling, implementing the Game of Life is a popular activity for APLers. APL implementations have appeared in the [[APL Quote-Quad]] since 1971, a year after the rules of the Game of Life were first published. More recently, it is sometimes seen as a use case for the [[Stencil]] operator, which provides a concise way to work on three-by-three neighborhoods as used by the Game of Life.


Here is [[John Scholes]]' famous one-line APL function takes a boolean [[matrix]] as argument and returns a boolean matrix with the new generation.  
A famous video by [[John Scholes]]<ref name="scholes">[[John Scholes]]. [https://www.youtube.com/watch?v=a9xAKttWgP4 "Conway's Game of Life in APL"]. 2009-01-26.</ref> explains the following [[Dyalog APL]] implementation step by step. The implementation takes advantage of [[nested]] arrays and the [[Outer Product]] to produce many copies of the argument array. It finds adjacent elements by [[Rotate|rotating]] the original array, causing elements at the edge to wrap around (giving a torus geometry).
<syntaxhighlight lang=apl>
      life ← {⊃1 ⍵ ∨.∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵}
</syntaxhighlight>
This implementation is also explained [[John Scholes' Conway's Game of Life|in its own article]].


<source lang=apl>
The Game of Life is often credited with introducing programmers to APL: [[Aaron Hsu]]<ref>[[Aaron Hsu]]. [https://www.dyalog.com/50-years-of-apl/recollections.htm#AH Dyalog - Recollections (section)]</ref> and [[Jay Foad]]<ref>[[Jay Foad]]. [https://www.dyalog.com/blog/2016/02/a-message-from-the-cto/ "A message from the CTO"].</ref> state that Scholes' video was their first introduction to APL, and Scholes himself says he became intrigued with the language in 1971 after hearing that a new language would allow the [[wikipedia:Xerox Sigma 9|Xerox Sigma 9]] to implement the Game of Life in a single line.<ref>[[John Scholes]]. [https://www.dyalog.com/50-years-of-apl/recollections.htm#JS Dyalog - Recollections (section)]</ref><ref>Stephen Taylor. [http://archive.vector.org.uk/art10013790 "How we got here"]. [[Vector journal]] Volume 23 special supplement "Dyalog at 25". 2008-09.</ref>
      Life←{↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}
</source>


== The Glider ==
== Historical implementations ==


One interesting pattern that occurs in Life is a [[wikipedia:Glider (Conway's Life)|Glider]]:
First published in October 1970 by [[wikipedia:Martin Gardner|Martin Gardner]] in Scientific American<ref>[[wikipedia:Martin Gardner|Martin Gardner]] "Mathematical Games – The fantastic combinations of John Conway's new solitaire game "life"". Scientific American. 223 (4): 120–123. 1970-10.</ref>, Conway's Game of Life quickly became a popular target of APL implementation. Jean Jacques Duby's 7-line interactive implementation appeared in [[APL Quote Quad]] exactly a year later.<ref>Jean Jacques Duby. "Conway's Game "Life"", [[APL Quote Quad]] Vol. III No. 2 & 3 p. 54. 1971-10-01. Reprinted ''SIGPLAN Notices'' [https://dl.acm.org/toc/sigplan/1971/6/10 Volume 6, Issue 10]; see [https://dl.acm.org/action/showFmPdf?doi=10.1145%2F1317448 Front matter] p. 120.</ref> Duby's [[tradfn]] takes as input a list of coordinates of live cells and displays subsequent states until no live cells remain or the user stops it; it was shown along with an pattern evolving into a [https://www.conwaylife.com/wiki/Beehive beehive]. The next state is computed one element at a time, so that the function makes little use of APL's array capabilities. The function was followed by a 9-line implementation in February 1972<ref>Bruce A. Beebe. "Life". [[APL Quote Quad]] Vol III No. 4 p. 37. 1972-02-10. Reprinted ''SIGPLAN Notices'' [https://dl.acm.org/toc/sigplan/1972/7/4 Volume 7, Issue 4]; in [https://dl.acm.org/doi/abs/10.1145/1115910.1115916 Algorithms].</ref>, both a 6-line and a 4-line implementation in June 1972<ref>W. J. Jones, "Game of Life" and D. A. Bonyun, "Game of Life". [[APL Quote Quad]] Vol III No. 5 p. 66-67. 1972-06-05</ref>, and an 8-line [[APL.SV]] implementation in 1974.<ref>Marc Sinykin and David Vorgang. [https://dl.acm.org/doi/abs/10.1145/585882.585901 Algorithm Number 124]. [[APL Quote Quad]] Vol 5 No. 4 p. 94. 1974-12.</ref> The last three implementations used more efficient strategies involving [[Rotate]], [[indexing]] with an array index, or [[Take]] to obtain the neighbors of every array element at once.
<source lang=apl>
      glider←3 3⍴1 1 1 1 0 0 0 1 0
      glider
1 1 1
1 0 0
0 1 0
</source>


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:
The tradition of [[one-liner]] Game of Life implementations was firmly established by [[Eugene McDonnell]]'s "Life: Nasty, Brutish, and Short", presented at [[APL88]].<ref>[[Eugene McDonnell]]. [https://dl.acm.org/doi/abs/10.1145/55626.55659 "Life: Nasty, Brutish, and Short"] ([https://www.jsoftware.com/papers/eem/life.htm web]). [[APL88]] Conference Proceedings, [[APL Quote-Quad]] Vol. 18 No. 2, 1987-12.</ref> In addition to a survey of the Quote-Quad implementations listed above, McDonnell cites a 1984 ''[[IBM]] PC Tech Journal'' article which compared the expressiveness of various programming languages using the Game of Life as a benchmark. While the article presented favorably, [[Donald McIntyre]] wrote to the journal to complain about its verbosity, and present some logical simplifications. Like previous implementations, McIntyre's solution computes each of the eight neighbor arrays for the original state separately. McDonnell instead used [[SHARP APL]]'s [[Rank operator]] to apply multiple rotations separately in a single step, and showed that the same could be done with [[APL2]]'s [[Each]] operator. He first presented versions using two eight-element rotations vectors, and then showed how [[wikipedia:Don Knuth|Don Knuth]]'s Metafont implementation decomposed the sum into horizontal and vertical components and transferred this idea to APL, resulting in two 23-token implementations:
<source lang=apl>
<syntaxhighlight lang=apl>
      grid←¯10 ¯10↑glider
⍝ SHARP APL
      grid
lf:((2×+⌿¯1 0 1⊖⍤0 2+⌿¯1 0 1⌽⍤0 2 ⍵)-⍵)∊5 6 7
0 0 0 0 0 0 0 0 0 0
⍝ APL2
0 0 0 0 0 0 0 0 0 0
lfe:((2×+⌿⊃¯1 0 1⊖¨+⌿¯1 0 1⌽¨⊂⍵)-⍵)∊5 6 7
0 0 0 0 0 0 0 0 0 0
</syntaxhighlight>
0 0 0 0 0 0 0 0 0 0
McDonnell also described how future language features, such as the [[Commute]] operator and a tesselation operator related to [[Cut]] and the much later [[Stencil]], might reduce this to as few as 11 tokens (one of which is a long list of integers), or to 9 tokens when using a pre-defined vector of matrices.
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
</source>


After one generation the pattern becomes:
Cliff Reiter's 2005 article "Time(r) for the Game of Life"<ref>Cliff Reiter. [http://archive.vector.org.uk/art10007290 "Time(r) for the Game of Life"]. [[Vector journal]] Volume 21 Number 3. 2005-05.</ref> studies the performance of several [[J]] implementations, including both methods based on [[Cut]] and one by Ewart Shaw more similar to McDonnell's Rotate-based strategies, finding the latter to be much faster. He also includes a survey of APL-family Life implementations since "Life: Nasty, Brutish, and Short".
<source lang=apl>
      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
</source>


The Glider has slightly changed shape and also moved up and to the left.
[[John Scholes]] published a video in which he explains his own implementation of Life, the same as the function <syntaxhighlight lang=apl inline>Life</syntaxhighlight> above, in 2009.<ref name="scholes"/> Scholes' function resembles McDonnell's APL2 implementation in its use of three-element vertical and horizontal rotation vectors, but uses [[Inner Product]] and [[Outer Product]] rather than [[Each]] as well as a different arithmetic scheme.


=== Visualising it ===
When introducing the [[Stencil]] operator in [[Dyalog APL 16.0]], [[Roger Hui]] presented several Game of Life implementations using the new primitive.<ref>[[Roger Hui]]. [https://www.dyalog.com/blog/2017/07/stencil-lives/ "Stencil Lives"]. 2017-07-31.</ref> These included [[Jay Foad]]'s function <syntaxhighlight lang=apl inline>{3=s-⍵∧4=s←{+/,⍵}⌺3 3⊢⍵}</syntaxhighlight>, translated from [[Arthur Whitney]]'s [[K]] implementation <syntaxhighlight lang=apl inline>{3=s-x&4=s:2(+-1+/':)/x}</syntaxhighlight>.<ref>[[Arthur Whitney]]. [https://web.archive.org/web/20220926225051/https://kparc.com/z/fun.k "fun.k"].</ref>


To make the pattern easier to see, we can print a <source lang=apl inline>⌺</source> symbol where there's a cell and a <source lang=apl inline>·</source> otherwise, for example:
Conway's Game of Life featured as one of the problems in the APL [[Code golf|Code Golf]] Autumn Tournament, an event jointly run by [[Dyalog Ltd.]] and Optima Systems Ltd. In a follow-up [[Dyalog webinar]], [[Adám Brudzewsky]] presented both the game and one of the winning 17-character solutions (<syntaxhighlight lang=apl inline>{≢⍸⍵}⌺3 3∊¨3+0,¨⊢</syntaxhighlight>) in detail.<ref>[[Gitte Christensen]] & [[Adám Brudzewsky]]. [https://dyalog.tv/Webinar/?v=3FjYly2G_QI "Dyalog Webinars: APL CodeGolf Autumn Tournament"]. 2017-10-26.</ref>
<source lang=apl>
      Show←{'·⌺'[⎕IO+⍵]}
      Show grid
··········
··········
··········
··········
··········
··········
··········
·······⌺⌺⌺
·······⌺··
········⌺·
</source>
 
Here's how the Glider evolves over the first ten generations:
<source lang=apl>
      Show¨{Life⍣⍵⊢grid}¨0,⍳9
┌──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┐
│··········│··········│··········│··········│··········│··········│··········│··········│··········│··········│
│··········│··········│··········│··········│··········│··········│··········│··········│··········│··········│
│··········│··········│··········│··········│··········│··········│··········│··········│··········│··········│
│··········│··········│··········│··········│··········│··········│··········│··········│··········│··········│
│··········│··········│··········│··········│··········│··········│··········│··········│··········│······⌺···│
│··········│··········│··········│··········│··········│·······⌺··│······⌺⌺··│······⌺⌺··│·····⌺⌺⌺··│·····⌺⌺···│
│··········│········⌺·│·······⌺⌺·│·······⌺⌺·│······⌺⌺⌺·│······⌺⌺··│······⌺·⌺·│·····⌺⌺···│·····⌺····│·····⌺·⌺··│
│·······⌺⌺⌺│·······⌺⌺·│·······⌺·⌺│······⌺⌺··│······⌺···│······⌺·⌺·│······⌺···│·······⌺··│······⌺···│··········│
│·······⌺··│·······⌺·⌺│·······⌺··│········⌺·│·······⌺··│··········│··········│··········│··········│··········│
│········⌺·│··········│··········│··········│··········│··········│··········│··········│··········│··········│
└──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┘
</source>
 
== How the APL code works ==
If you're completely new to APL, this explanation is probably not the place to start, rather check out our [[Tutorials#Introductions|introductions]]. However, you should be able to get some idea of what's happening even if the details are not yet clear. Just bear in mind that APL evaluates expressions from right to left unless you use parentheses.
 
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>
      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
</source>
=== 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:
 
<source lang=apl>
      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
</source>
 
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:
 
<source lang=apl>
      ¯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│
└─────────┴─────────┴─────────┘
</source>
=== 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:
 
<source lang=apl>
    ¯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│
└─────────┴─────────┴─────────┘
</source>
 
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 the corresponding elements in each of the 9 grids. For a live cell this will give us 1 more than the number of neighbours - e.g. 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>
      +/,¯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│
└─────────┘
</source>
 
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, which we can find as follows:
 
<source lang=apl>
    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│
└─────────┴─────────┘
</source>
 
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>
<source lang=apl>
    (⊂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│
└─────────┘
</source>
 
(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>
      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│
└─────────┘
</source>
 
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>
      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│
└─────────┘
</source>
 
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:
<source lang=apl>
    (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│
└─────────┘
</source>
=== 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:
 
<source lang=apl>
    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│
└─────────┘
</source>
 
The final expression ends with a bit of housekeeping using <source lang=apl inline>↑</source> to turn the result back into a simple array (it's currently nested).


== External links ==
== External links ==
* [[wikipedia:Conways_Game_of_Life|Wikipedia]]
* [[wikipedia:Conway's Game of Life|Conway's Game of Life]]
* [http://youtube.com/watch?v=a9xAKttWgP4 John Scholes' famous video] on YouTube
* [http://youtube.com/watch?v=a9xAKttWgP4 John Scholes' famous video] on YouTube
* [http://dfns.dyalog.com/n_life.htm John Scholes' notes], as part of the [[dfns workspace]], includes a more in-depth treatment
* [http://dfns.dyalog.com/n_life.htm John Scholes' notes], as part of the [[dfns workspace]], includes a more in-depth treatment
== References ==
<references />
{{APL community}}[[Category:Recreation]]

Latest revision as of 19:38, 31 January 2024

Conway's Game of Life is a well-known cellular automaton in which each generation of a population "evolves" from the previous one according to a set of predefined rules. The Game of Life is defined on an infinite Boolean grid, but usually only finite patterns, where all 1 values fit in a finite Boolean matrix, are studied. Because it involves interactions between adjacent elements of the matrix, and can take advantage of APL's convenient and fast Boolean handling, implementing the Game of Life is a popular activity for APLers. APL implementations have appeared in the APL Quote-Quad since 1971, a year after the rules of the Game of Life were first published. More recently, it is sometimes seen as a use case for the Stencil operator, which provides a concise way to work on three-by-three neighborhoods as used by the Game of Life.

A famous video by John Scholes[1] explains the following Dyalog APL implementation step by step. The implementation takes advantage of nested arrays and the Outer Product to produce many copies of the argument array. It finds adjacent elements by rotating the original array, causing elements at the edge to wrap around (giving a torus geometry).

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

This implementation is also explained in its own article.

The Game of Life is often credited with introducing programmers to APL: Aaron Hsu[2] and Jay Foad[3] state that Scholes' video was their first introduction to APL, and Scholes himself says he became intrigued with the language in 1971 after hearing that a new language would allow the Xerox Sigma 9 to implement the Game of Life in a single line.[4][5]

Historical implementations

First published in October 1970 by Martin Gardner in Scientific American[6], Conway's Game of Life quickly became a popular target of APL implementation. Jean Jacques Duby's 7-line interactive implementation appeared in APL Quote Quad exactly a year later.[7] Duby's tradfn takes as input a list of coordinates of live cells and displays subsequent states until no live cells remain or the user stops it; it was shown along with an pattern evolving into a beehive. The next state is computed one element at a time, so that the function makes little use of APL's array capabilities. The function was followed by a 9-line implementation in February 1972[8], both a 6-line and a 4-line implementation in June 1972[9], and an 8-line APL.SV implementation in 1974.[10] The last three implementations used more efficient strategies involving Rotate, indexing with an array index, or Take to obtain the neighbors of every array element at once.

The tradition of one-liner Game of Life implementations was firmly established by Eugene McDonnell's "Life: Nasty, Brutish, and Short", presented at APL88.[11] In addition to a survey of the Quote-Quad implementations listed above, McDonnell cites a 1984 IBM PC Tech Journal article which compared the expressiveness of various programming languages using the Game of Life as a benchmark. While the article presented favorably, Donald McIntyre wrote to the journal to complain about its verbosity, and present some logical simplifications. Like previous implementations, McIntyre's solution computes each of the eight neighbor arrays for the original state separately. McDonnell instead used SHARP APL's Rank operator to apply multiple rotations separately in a single step, and showed that the same could be done with APL2's Each operator. He first presented versions using two eight-element rotations vectors, and then showed how Don Knuth's Metafont implementation decomposed the sum into horizontal and vertical components and transferred this idea to APL, resulting in two 23-token implementations:

⍝ SHARP APL
lf:((2×+⌿¯1 0 1⊖⍤0 2+⌿¯1 0 1⌽⍤0 2 ⍵)-⍵)∊5 6 7
⍝ APL2
lfe:((2×+⌿⊃¯1 0 1⊖¨+⌿¯1 0 1⌽¨⊂⍵)-⍵)∊5 6 7

McDonnell also described how future language features, such as the Commute operator and a tesselation operator related to Cut and the much later Stencil, might reduce this to as few as 11 tokens (one of which is a long list of integers), or to 9 tokens when using a pre-defined vector of matrices.

Cliff Reiter's 2005 article "Time(r) for the Game of Life"[12] studies the performance of several J implementations, including both methods based on Cut and one by Ewart Shaw more similar to McDonnell's Rotate-based strategies, finding the latter to be much faster. He also includes a survey of APL-family Life implementations since "Life: Nasty, Brutish, and Short".

John Scholes published a video in which he explains his own implementation of Life, the same as the function Life above, in 2009.[1] Scholes' function resembles McDonnell's APL2 implementation in its use of three-element vertical and horizontal rotation vectors, but uses Inner Product and Outer Product rather than Each as well as a different arithmetic scheme.

When introducing the Stencil operator in Dyalog APL 16.0, Roger Hui presented several Game of Life implementations using the new primitive.[13] These included Jay Foad's function {3=s-⍵∧4=s←{+/,⍵}⌺3 3⊢⍵}, translated from Arthur Whitney's K implementation {3=s-x&4=s:2(+-1+/':)/x}.[14]

Conway's Game of Life featured as one of the problems in the APL Code Golf Autumn Tournament, an event jointly run by Dyalog Ltd. and Optima Systems Ltd. In a follow-up Dyalog webinar, Adám Brudzewsky presented both the game and one of the winning 17-character solutions ({≢⍸⍵}⌺3 3∊¨3+0,¨⊢) in detail.[15]

External links

References

  1. 1.0 1.1 John Scholes. "Conway's Game of Life in APL". 2009-01-26.
  2. Aaron Hsu. Dyalog - Recollections (section)
  3. Jay Foad. "A message from the CTO".
  4. John Scholes. Dyalog - Recollections (section)
  5. Stephen Taylor. "How we got here". Vector journal Volume 23 special supplement "Dyalog at 25". 2008-09.
  6. Martin Gardner "Mathematical Games – The fantastic combinations of John Conway's new solitaire game "life"". Scientific American. 223 (4): 120–123. 1970-10.
  7. Jean Jacques Duby. "Conway's Game "Life"", APL Quote Quad Vol. III No. 2 & 3 p. 54. 1971-10-01. Reprinted SIGPLAN Notices Volume 6, Issue 10; see Front matter p. 120.
  8. Bruce A. Beebe. "Life". APL Quote Quad Vol III No. 4 p. 37. 1972-02-10. Reprinted SIGPLAN Notices Volume 7, Issue 4; in Algorithms.
  9. W. J. Jones, "Game of Life" and D. A. Bonyun, "Game of Life". APL Quote Quad Vol III No. 5 p. 66-67. 1972-06-05
  10. Marc Sinykin and David Vorgang. Algorithm Number 124. APL Quote Quad Vol 5 No. 4 p. 94. 1974-12.
  11. Eugene McDonnell. "Life: Nasty, Brutish, and Short" (web). APL88 Conference Proceedings, APL Quote-Quad Vol. 18 No. 2, 1987-12.
  12. Cliff Reiter. "Time(r) for the Game of Life". Vector journal Volume 21 Number 3. 2005-05.
  13. Roger Hui. "Stencil Lives". 2017-07-31.
  14. Arthur Whitney. "fun.k".
  15. Gitte Christensen & Adám Brudzewsky. "Dyalog Webinars: APL CodeGolf Autumn Tournament". 2017-10-26.


APL community [edit]
Conferences and activities Advent of CodeAPL CampfireAPL CultivationAPL Meetup (Portuguese) ∙ APL ShowAPL Problem Solving CompetitionAPL ChallengeAPL QuestAPL SeedsArray CastBAA sessionsCode golfDyalog user meetingsDyalog webinarsIverson Award
Chat rooms and forums APL FarmAPL Orchard
User groups APL et J (France) ∙ APL Germany (terminology) ∙ APL ∊ BCN (Spain) ∙ BAA (UK) ∙ FinnAPL (Finland) ∙ SIGAPL (USA) ∙ Tokyo APL/J/K Meetup (Japan)
People Phil AbramsBrian BeckerBob BerneckyLarry BreedCharles BrennerJim BrownAdám BrudzewskyGitte ChristensenPeter DonnellyJohn EarnestAdin FalkoffGarth FosterLib GibsonAaron HsuRoger HuiKen IversonMorten KrombergDick LathwellMarshall LochbaumEugene McDonnellRoger MooreTrenchard MoreAlan PerlisHenry RichAl RoseJohn ScholesIan SharpBob SmithGeoff StreeterArthur Whitney
Other APL Quote QuadAPL WikiBlogsBooksCase studiesFamous APL usersHumourJobsMerchandisePapersPodcastsTryAPLTry It OnlineVideo channels