`⎕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.