Conway's Game of Life: Difference between revisions

From APL Wiki
Jump to navigation Jump to search
(→‎Historical implementations: Reiter's J article)
m (fix source)
Line 24: Line 24:
[[John Scholes]] published a video in which he explains his own implementation of Life, the same as the function <source lang=apl inline>Life</source> 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.
[[John Scholes]] published a video in which he explains his own implementation of Life, the same as the function <source lang=apl inline>Life</source> 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.


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 <source lang=apl inline>{3=s-⍵∧4=s←{+/,⍵}⌺3 3⊢⍵}</source>, translated from [[Arthur Whitney]]'s [[K]] implementation <source inline>{3=s-x&4=s:2(+-1+/':)/x}</source>.<ref>[[Arthur Whitney]]. [http://kparc.com/z/fun.k "fun.k"].</ref>
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 <source lang=apl inline>{3=s-⍵∧4=s←{+/,⍵}⌺3 3⊢⍵}</source>, translated from [[Arthur Whitney]]'s [[K]] implementation <source lang=apl inline>{3=s-x&4=s:2(+-1+/':)/x}</source>.<ref>[[Arthur Whitney]]. [http://kparc.com/z/fun.k "fun.k"].</ref>


== External links ==
== External links ==

Revision as of 02:25, 14 April 2020

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.

Historical implementations

First published in October 1970 by Martin Gardner in Scientific American[2], 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.[3] 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[4], both a 6-line and a 4-line implementation in June 1972[5], and an 8-line APL.SV implementation in 1974.[6] 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.[7] 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"[8] 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.[9] 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}.[10]

External links

References

  1. 1.0 1.1 Scholes, John. "Conway's Game of Life in APL". 2009-01-26.
  2. Gardner, Martin (October 1970). "Mathematical Games – The fantastic combinations of John Conway's new solitaire game "life"". Scientific American. 223 (4): 120–123.
  3. 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.
  4. 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.
  5. 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
  6. Marc Sinykin and David Vorgang. Algorithm Number 124. APL Quote Quad Vol 5 No. 4 p. 94. 1974-12.
  7. McDonnell, Eugene. "Life: Nasty, Brutish, and Short" (web). APL88 Conference Proceedings, APL Quote-Quad Vol. 18 No. 2, 1987-12.
  8. Cliff Reiter. "Time(r) for the Game of Life". Vector Journal Volume 21 Number 3. 2005-05.
  9. Roger Hui. "Stencil Lives". 2017-07-31.
  10. Arthur Whitney. "fun.k".