⎕io←0 throughout. ⎕io delenda est.
Stencil
A stencil operator ⌺ is available with Dyalog version 16.0. In brief, stencil is a dyadic operator f⌺s which applies f to (possibly overlapping) rectangles. The size of the rectangle and its movement are controlled by s. For example, enclosing 3-by-3 rectangles with default movements of 1:
⊢ a←4 5⍴⎕a
ABCDE
FGHIJ
KLMNO
PQRST
{⊂⍵}⌺3 3 ⊢a
┌───┬───┬───┬───┬───┐
│ │ │ │ │ │
│ AB│ABC│BCD│CDE│DE │
│ FG│FGH│GHI│HIJ│IJ │
├───┼───┼───┼───┼───┤
│ AB│ABC│BCD│CDE│DE │
│ FG│FGH│GHI│HIJ│IJ │
│ KL│KLM│LMN│MNO│NO │
├───┼───┼───┼───┼───┤
│ FG│FGH│GHI│HIJ│IJ │
│ KL│KLM│LMN│MNO│NO │
│ PQ│PQR│QRS│RST│ST │
├───┼───┼───┼───┼───┤
│ KL│KLM│LMN│MNO│NO │
│ PQ│PQR│QRS│RST│ST │
│ │ │ │ │ │
└───┴───┴───┴───┴───┘
Stencil is also known as stencil code, tile, tessellation, and cut. It has applications in artificial neural networks, computational fluid dynamics, cellular automata, etc., and of course in Conway’s Game of Life.
The Rules of Life
Each cell of a boolean matrix has 8 neighbors adjacent to it horizontally, vertically, or diagonally. The Game of Life concerns the computation of the next generation boolean matrix.
(0) A 0-cell with 3 neighboring 1-cells becomes a 1.
(1) A 1-cell with 2 or 3 neighboring 1-cells remains at 1.
(2) All other cells remain or become a 0.
There are two main variations on the treatment of cells on the edges of the matrix: (a) the matrix is surrounded by a border of 0s; or (b) cells on an edge are adjacent to cells on the opposite edge, as on a torus.
There is an implementation of life in the dfns workspace and explained in a YouTube video. It assumes a toroidal topology.
life←{↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵} ⍝ John Scholes
⊢ glider←5 5⍴0 0 1 0 0 1 0 1 0 0 0 1 1,12⍴0
0 0 1 0 0
1 0 1 0 0
0 1 1 0 0
0 0 0 0 0
0 0 0 0 0
life glider
0 1 0 0 0
0 0 1 1 0
0 1 1 0 0
0 0 0 0 0
0 0 0 0 0
{'.⍟'[⍵]}¨ (⍳8) {life⍣⍺⊢⍵}¨ ⊂glider
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│..⍟..│.⍟...│..⍟..│.....│.....│.....│.....│.....│
│⍟.⍟..│..⍟⍟.│...⍟.│.⍟.⍟.│...⍟.│..⍟..│...⍟.│.....│
│.⍟⍟..│.⍟⍟..│.⍟⍟⍟.│..⍟⍟.│.⍟.⍟.│...⍟⍟│....⍟│..⍟.⍟│
│.....│.....│.....│..⍟..│..⍟⍟.│..⍟⍟.│..⍟⍟⍟│...⍟⍟│
│.....│.....│.....│.....│.....│.....│.....│...⍟.│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
Stencil Lives
It has long been known that stencil facilitates Game of Life computations. Eugene McDonnell explored the question in the APL88 paper Life: Nasty, Brutish, and Short [Ho51]. The shortest of the solutions derive as follows.
By hook or by crook, find all the 3-by-3 boolean matrices U which lead to a middle 1. A succinct Game of Life then obtains.
B ← {1 1⌷life 3 3⍴(9⍴2)⊤⍵}¨ ⍳2*9
U ← {3 3⍴(9⍴2)⊤⍵}¨ ⍸B ⍝ ⍸ ←→ {⍵/⍳⍴⍵}
life1 ← {U ∊⍨ {⊂⍵}⌺3 3⊢⍵} ⍝ Eugene McDonnell
Comparing life and life1, and also illustrating that the toroidal and 0-border computations can be expressed one with the other.
b←1=?97 103⍴3
x←1 1↓¯1 ¯1↓ life 0,0,⍨0⍪0⍪⍨b
y←life1 b
x≡y
1
g←{(¯1↑⍵)⍪⍵⍪1↑⍵}
p←life b
q←1 1↓¯1 ¯1↓ life1 (g b[;102]),(g b),(g b[;0])
p≡q
1
Adám Brudzewsky points out that life can be terser as a train (fork):
life1a ← U ∊⍨ ⊢∘⊂⌺3 3 ⍝ Adám Brudzewsky
life1b ← U ∊⍨ {⊂⍵}⌺3 3
(life1 ≡ life1a) b
1
(life1 ≡ life1b) b
1
life1 is an example of implementing a calculation by look-up rather than by a more conventional computation, discussed in a recent blog post. There is a variation which is more efficient because the look-up is effected with integers rather than boolean matrices:
A←3 3⍴2*⌽⍳9
life2 ← {B[{+/,A×⍵}⌺3 3⊢⍵]}
(life1 ≡ life1b) b
1
Jay Foad offers another stencil life, translating an algorithm in k by Arthur Whitney:
life3 ← {3=s-⍵∧4=s←{+/,⍵}⌺3 3⊢⍵} ⍝ Jay Foad
(life1 ≡ life3) b
1
The algorithm combines the life rules into a single expression, wherein s←{+/,⍵}⌺3 3 ⊢⍵
(0) for 0-cells s is the number of neighbors; and
(1) for 1-cells s is the number of neighbors plus 1, and the plus 1 only matters if s is 4.
The same idea can be retrofit into the toroidal life:
lifea←{3=s-⍵∧4=s←⊃+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}
(life ≡ lifea) b
1
Collected Definitions and Timings
life ← {↑1 ⍵∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}
lifea ← {3=s-⍵∧4=s←⊃+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵}
B←{1 1⌷life 3 3⍴(9⍴2)⊤⍵}¨ ⍳2*9
U←{3 3⍴(9⍴2)⊤⍵}¨ ⍸ B
A←3 3⍴2*⌽⍳9
life1 ← {U ∊⍨ {⊂⍵}⌺3 3⊢⍵}
life1a ← U ∊⍨ ⊢∘⊂⌺3 3
life1b ← U ∊⍨ {⊂⍵}⌺3 3
life2 ← {B[{+/,A×⍵}⌺3 3⊢⍵]}
life3 ← {3=s-⍵∧4=s←{+/,⍵}⌺3 3⊢⍵}
cmpx (⊂'life') ,¨ '1' '1a' '1b' '2' '3' '' 'a' ,¨ ⊂' b'
life1 b → 2.98E¯3 | 0% ⎕⎕⎕⎕⎕
life1a b → 1.97E¯2 | +561% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
life1b b → 2.99E¯3 | 0% ⎕⎕⎕⎕⎕
life2 b → 2.71E¯4 | -91%
life3 b → 6.05E¯5 | -98%
* life b → 1.50E¯4 | -95%
* lifea b → 1.41E¯4 | -96%
The * indicate that life and lifea give a different result (toroidal v 0-border).
life1a is much slower than the others because ⊢∘⊂⌺ is not implemented by special code.
{+/,⍵}⌺ is the fastest of the special codes because the computation has mathematical properties absent from {⊂⍵}⌺ and {+/,A×⍵}⌺.
The effect of special code v not, can be observed (for example) by use of redundant parentheses:
cmpx '{+/,⍵}⌺3 3⊢b' '{+/,(⍵)}⌺3 3⊢b'
{+/,⍵}⌺3 3⊢b → 3.13E¯5 | 0%
{+/,(⍵)}⌺3 3⊢b → 2.63E¯2 | +83900% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
cmpx '{+/,A×⍵}⌺3 3⊢b' '{+/,A×(⍵)}⌺3 3⊢b'
{+/,A×⍵}⌺3 3⊢b → 2.42E¯4 | 0%
{+/,A×(⍵)}⌺3 3⊢b → 2.98E¯2 | +12216% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
⍝ no special code in either of the following expressions
cmpx '{+/,2×⍵}⌺3 3⊢b' '{+/,2×(⍵)}⌺3 3⊢b'
{+/,2×⍵}⌺3 3⊢b → 2.92E¯2 | 0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
{+/,2×(⍵)}⌺3 3⊢b → 3.03E¯2 | +3% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
That life and lifea do not use stencil and yet are competitive, illustrates the efficacy of boolean operations and of letting primitives “see” large arguments.
Finally, if you wish to play with stencil a description and a hi-fi model of it can be found here.
Follow