Conway's Game of Life: Difference between revisions

Jump to navigation Jump to search

Conway's Game of Life (view source)

Revision as of 22:16, 10 September 2022

108 bytes added ,  22:16, 10 September 2022
m
Text replacement - "<source" to "<syntaxhighlight"
m (Text replacement - "<source" to "<syntaxhighlight")
(One intermediate revision by the same user not shown)
Line 2: Line 2:


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).
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>
<syntaxhighlight lang=apl>
       life ← {⊃1 ⍵ ∨.∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵}
       life ← {⊃1 ⍵ ∨.∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵}
</source>
</syntaxhighlight>
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]].


Line 14: Line 14:


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:
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>
⍝ SHARP APL
⍝ SHARP APL
lf:((2×+⌿¯1 0 1⊖⍤0 2+⌿¯1 0 1⌽⍤0 2 ⍵)-⍵)∊5 6 7
lf:((2×+⌿¯1 0 1⊖⍤0 2+⌿¯1 0 1⌽⍤0 2 ⍵)-⍵)∊5 6 7
⍝ APL2
⍝ APL2
lfe:((2×+⌿⊃¯1 0 1⊖¨+⌿¯1 0 1⌽¨⊂⍵)-⍵)∊5 6 7
lfe:((2×+⌿⊃¯1 0 1⊖¨+⌿¯1 0 1⌽¨⊂⍵)-⍵)∊5 6 7
</source>
</syntaxhighlight>
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 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".
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 <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.


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>
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]]. [http://kparc.com/z/fun.k "fun.k"].</ref>


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 (<source lang=apl inline>{≢⍸⍵}⌺3 3∊¨3+0,¨⊢</source>) 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>
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>


== External links ==
== External links ==
Retrieved from ‘https://aplwiki.com/wiki/Special:MobileDiff/6028...9509’

Navigation menu