2,951
edits
Conway's Game of Life: Difference between revisions
Jump to navigation
Jump to search
m
More uniform references
m (→External links: WP link style) |
m (More uniform references) |
||
| (One intermediate revision by the same user 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. 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. | '''[[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. | ||
A famous video by [[John Scholes]]<ref name="scholes">[[John Scholes | 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). | ||
<source lang=apl> | <source lang=apl> | ||
life ← {⊃1 ⍵ ∨.∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵} | life ← {⊃1 ⍵ ∨.∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵} | ||
</source> | </source> | ||
This implementation is also explained [[John Scholes' Conway's Game of Life|in its own article]]. | This implementation is also explained [[John Scholes' Conway's Game of Life|in its own article]]. | ||
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> | |||
== Historical implementations == | == Historical implementations == | ||
First published in October 1970 by [[wikipedia:Martin Gardner|Martin Gardner]] in Scientific American<ref>Gardner | First published in October 1970 by [[wikipedia:Martin Gardner|Martin Gardner]] in Scientific American<ref>[[wikipedia: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. | ||
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 | 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> | <source lang=apl> | ||
⍝ SHARP APL | ⍝ SHARP APL | ||
| Line 20: | Line 22: | ||
McDonnell also described how future language features, such as the [[Commute]] operator and a tesselation operator related to [[Cut (operator)|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. | McDonnell also described how future language features, such as the [[Commute]] operator and a tesselation operator related to [[Cut (operator)|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"<ref>Cliff Reiter. [http://archive.vector.org.uk/art10007290 "Time(r) for the Game of Life"]. [[Vector | 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 (operator)|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 <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. | ||