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

Jump to navigation Jump to search
→‎Translations: Link to zverok's Ruby version
(Expand on introduction)
(→‎Translations: Link to zverok's Ruby version)
(8 intermediate revisions by the same user not shown)
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]].
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> In the video, Scholes develops the following [[dfn]] one step at a time:
<source lang=apl>
      life ← {⊃1 ⍵ ∨.∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵}
</source>


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>
<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>


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 <source lang=apl inline>Life</source> 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]].
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]].
Line 254: Line 257:


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 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).
== Translations ==
=== GNU APL ===
In [[GNU APL]] the [[Inner Product]] <source lang=apl inline>∨.∧</source> 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.
<source lang=apl>
      Life←{↑↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}
      Life←{↑∨/1 ⍵∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}
</source>
=== dzaima/APL ===
In [[dzaima/APL]] the [[Reduce|reduction]] <source lang=apl inline>+/</source> [[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.
<source lang=apl>
      Life←{↑1 ⍵∨.∧3 4=⊂+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}
</source>
The computation of our example <source lang=apl inline>grid</source> also fails, because dzaima's [[Take]] does not allow overtaking. Instead we can insert the glider into a matrix of zeros using [[structural Under]]:
<source lang=apl>
      grid ← ¯10 ¯10↑glider            ⍝ DomainError
      grid ← glider⍢(¯3 ¯3∘↑) 10 10⍴0  ⍝ This works
</source>
=== Ruby ===
Github user zverok has translated Scholes' dfn to [[wikipedia:Ruby (programming language)|Ruby]] by first creating an <source lang=ruby inline>apl</source> 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].
== 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 following code times how long it takes to perform 1000 iterations of the Game of Life on a shape <source lang=apl inline>1000 1000</source> array. This computation performs a billion cell updates, so the total time in seconds is equal to the time taken per update in nanoseconds.
<source lang=apl>
      )copy dfns cmpx
      b←1=?1e3 1e3⍴2
      1 cmpx 'Life⍣1000 ⊢b'
</source>
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 ==
<references />
<references />
[[Category:Examples]][[Category:Dyalog APL examples]]

Navigation menu