The Stencil operator: ⌺
Contents
The Stencil operator: ⌺#
Every time I see some piece of medical research saying that caffeine is good for you, I high-five myself. Because I’m going to live forever. –Linus Torvalds
Are you familiar with Conway’s Game of Life? If not, it’s a cellular automaton with a deceptively simple set of rules:
Any live cell with two or three live neighbours survives.
Any dead cell with three live neighbours becomes a live cell.
All other live cells die in the next generation.
yet Game of Life gives rise to extraordinary complex patterns. It’s fun to implement – try it in your favourite language! Some good ones can be found on Rosettacode.
⎕IO ← 0
]box on
]rows on
Was ON
Was OFF
Game of Life is a bit of an APL party trick, to the extent that it may be the only application of APL that people have heard of after seeing a famous video of John Scholes’.
Here’s the current champion, all 17 symbols of it:
gol ← {≢⍸⍵}⌺3 3∊¨3+0,¨⊢ ⍝ Generate the next generation
To run it, we first need an array with some live cells in it. Here’s an 8×8 petri dish containing a “glider”:
glider ← 3 3⍴0 0 1 1 0 1 0 1 1
dish ← 8 8⍴0
dish[(⊂3 3)+⍸glider] ← 1
dish
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
The glider pattern is called so because it glides across the dish. Here’s a full cycle:
1 4⍴(gol⍣1⊢dish)(gol⍣2⊢dish)(gol⍣3⊢dish)(gol⍣4⊢dish)
┌───────────────┬───────────────┬───────────────┬───────────────┐ │0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│ │0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│ │0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│ │0 0 0 0 1 0 0 0│0 0 0 0 0 1 0 0│0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│ │0 0 0 0 0 1 1 0│0 0 0 0 0 0 1 0│0 0 0 0 1 0 1 0│0 0 0 0 0 0 1 0│ │0 0 0 0 1 1 0 0│0 0 0 0 1 1 1 0│0 0 0 0 0 1 1 0│0 0 0 0 1 0 1 0│ │0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│0 0 0 0 0 1 0 0│0 0 0 0 0 1 1 0│ │0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│ └───────────────┴───────────────┴───────────────┴───────────────┘
If you’d like to have the above Game of Life implementation dissected in detail, head over to dyalog.tv.
Anyway – this APL Game of Life implementation is primarily a demonstration of the power and versatility of the Stencil operator, ⌺. In simple terms, the dyadic Stencil operator lets you specify a sliding window of a rank of your choice to the right and a function operating over this sliding window to the left. It makes it trivial to implement image processing filters or convolution. In essence, for the 2D case, it’s four nested for-loops, the outermost two moving the window, and the innermost two visiting every data point within the window.
This is obviously a good fit for Game of Life: the rules are defined within a 3×3 neighbourhood, so all we need to do is count the 1s in the windows that Stencil delivers:
{≢⍸⍵} glider
5
Let’s look at Stencil in a bit more detail. We can illustrate the sliding window using enclose as the left operand and a size 2 window over a vector:
⊂⍤⊢⌺2⊢⍳10
┌───┬───┬───┬───┬───┬───┬───┬───┬───┐ │0 1│1 2│2 3│3 4│4 5│5 6│6 7│7 8│8 9│ └───┴───┴───┴───┴───┴───┴───┴───┴───┘
But now look what happens if we increase the window size to 3:
⊂⍤⊢⌺3⊢⍳10
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐ │0 0 1│0 1 2│1 2 3│2 3 4│3 4 5│4 5 6│5 6 7│6 7 8│7 8 9│8 9 0│ └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
The first and last windows now “overhang” the edge, filling the overhang with zeros. The way to think of it is that each data point in the argument array must line up with the centre of the window.
Stencil has a few more tricks up its sleeve. The right operand can be an array, where the first row defines the shape of the window, and the second row defines the step size. Again, using the vector above, we can say that we want a size 3 window, but instead of moving it one step (the default), we want to shift it three steps each time:
⊂⍤⊢⌺(⍪3 3)⊢⍳10
┌─────┬─────┬─────┬─────┐ │0 0 1│2 3 4│5 6 7│8 9 0│ └─────┴─────┴─────┴─────┘
We still have an odd-size window, and the first is centered over the first item as before. The step size, 3, dictates how far the center of the window moves, so the next window is centered over item 3 etc.
With an even size we can create non-overlapping windows that don’t overhang,
⊂⍤⊢⌺(⍪2 2)⊢⍳10
┌───┬───┬───┬───┬───┐ │0 1│2 3│4 5│6 7│8 9│ └───┴───┴───┴───┴───┘
and, of course, even-sized, non-overlapping windows that do overhang, too, if that’s what we want:
⊂⍤⊢⌺(⍪4 4)⊢⍳10
┌───────┬───────┬───────┐ │0 0 1 2│3 4 5 6│7 8 9 0│ └───────┴───────┴───────┘
The left argument#
The left operand function is actually called with a left argument; a vector indicating the number of fill arguments per axis: positive for the “before”, and negative for the “after”.
{⊂⍺ ⍵}⌺3 3⊢3 5⍴⎕A ⍝ Show the left argument vector
┌──────────┬──────────┬──────────┬──────────┬───────────┐ │┌───┬───┐ │┌───┬───┐ │┌───┬───┐ │┌───┬───┐ │┌────┬───┐ │ ││1 1│ │ ││1 0│ │ ││1 0│ │ ││1 0│ │ ││1 ¯1│ │ │ ││ │ AB│ ││ │ABC│ ││ │BCD│ ││ │CDE│ ││ │DE │ │ ││ │ FG│ ││ │FGH│ ││ │GHI│ ││ │HIJ│ ││ │IJ │ │ │└───┴───┘ │└───┴───┘ │└───┴───┘ │└───┴───┘ │└────┴───┘ │ ├──────────┼──────────┼──────────┼──────────┼───────────┤ │┌───┬───┐ │┌───┬───┐ │┌───┬───┐ │┌───┬───┐ │┌────┬───┐ │ ││0 1│ AB│ ││0 0│ABC│ ││0 0│BCD│ ││0 0│CDE│ ││0 ¯1│DE │ │ ││ │ FG│ ││ │FGH│ ││ │GHI│ ││ │HIJ│ ││ │IJ │ │ ││ │ KL│ ││ │KLM│ ││ │LMN│ ││ │MNO│ ││ │NO │ │ │└───┴───┘ │└───┴───┘ │└───┴───┘ │└───┴───┘ │└────┴───┘ │ ├──────────┼──────────┼──────────┼──────────┼───────────┤ │┌────┬───┐│┌────┬───┐│┌────┬───┐│┌────┬───┐│┌─────┬───┐│ ││¯1 1│ FG│││¯1 0│FGH│││¯1 0│GHI│││¯1 0│HIJ│││¯1 ¯1│IJ ││ ││ │ KL│││ │KLM│││ │LMN│││ │MNO│││ │NO ││ ││ │ │││ │ │││ │ │││ │ │││ │ ││ │└────┴───┘│└────┴───┘│└────┴───┘│└────┴───┘│└─────┴───┘│ └──────────┴──────────┴──────────┴──────────┴───────────┘
Another way to think of it is as what you need to drop to get rid of all the fillers:
{⊂⍺↓⍵}⌺3 3⊢3 5⍴⎕A ⍝ Drop all fillers
┌──┬───┬───┬───┬──┐ │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│ └──┴───┴───┴───┴──┘