Stencil

From APL Wiki
Revision as of 10:36, 11 September 2022 by Adám Brudzewsky (talk | contribs) (Text replacement - "</source>" to "</syntaxhighlight>")
Jump to navigation Jump to search

Stencil (⌺) is a primitive dyadic operator that applies its left operand to (possibly overlapping) rectangular views of the right argument array. The shape and movement of the rectangular views are dictated by the right operand. It was introduced to Dyalog APL in version 16.0 and is also known as tessellation, moving window, stencil code or cut. The operator can be used for computations involving the immediate neighbours of items in an array and has applications in image processing (particularly convolution), artificial neural networks and, most famously, cellular automata. The operator derives from a subset (specifically, case 3) of the functionality of J's Cut operator (<source lang=j inline>;.3</syntaxhighlight>),[1] which in turn originates in the 3-cut mentioned in A Dictionary of APL[2]

Description

For a call <source lang=apl inline>f⌺s</syntaxhighlight> the right operand <source lang=apl inline>s</syntaxhighlight> can in general be a two-row matrix of strictly positive integers, where the first row describes the dimensions of the rectangles that will be passed to <source lang=apl inline>f</syntaxhighlight> and the second row describes the movement along the different axes. When using stencil <source lang=apl inline>(f⌺s)Y</syntaxhighlight> the right operand <source lang=apl inline>s</syntaxhighlight> in general has <source lang=apl inline>≢⍴Y</syntaxhighlight> columns. If it has fewer, the rectangles are cut out of the major cells of the <source lang=apl inline>(≢⍴Y) - ≢1⌷s</syntaxhighlight> axis of <source lang=apl inline>Y</syntaxhighlight>. If <source lang=apl inline>s</syntaxhighlight> is a vector or scalar it describes only the size of the rectangles and the movement defaults to 1. Rectangles are centred on elements of <source lang=apl inline>Y</syntaxhighlight> whose indices differ by the movements in <source lang=apl inline>s</syntaxhighlight> (defaulting to 1), starting with the first element in ravel order. For a matrix, this is the top left. For even window sizes, the centring is instead on the space between elements or cells. Along the edges of the argument array, the windows are thus subject to be padded with fill elements.

The number of fill elements in along each axis is given as a vector left argument on each call of <source lang=apl inline>f</syntaxhighlight> for the respective subarray. This is designed such that Drop (<source lang=apl inline>↓</syntaxhighlight>) can take the left and right arguments to remove padding: <source lang=apl> 

    ({⊂⍵}⌺3 3)3 4⍴⍳12

┌──────┬───────┬────────┬───────┐ │0 0 0 │0 0 0 │0 0 0 │0 0 0 │ │0 1 2 │1 2 3 │2 3 4 │3 4 0 │ │0 5 6 │5 6 7 │6 7 8 │7 8 0 │ ├──────┼───────┼────────┼───────┤ │0 1 2│1 2 3│ 2 3 4│ 3 4 0│ │0 5 6│5 6 7│ 6 7 8│ 7 8 0│ │0 9 10│9 10 11│10 11 12│11 12 0│ ├──────┼───────┼────────┼───────┤ │0 5 6│5 6 7│ 6 7 8│ 7 8 0│ │0 9 10│9 10 11│10 11 12│11 12 0│ │0 0 0│0 0 0│ 0 0 0│ 0 0 0│ └──────┴───────┴────────┴───────┘ 

    ({⊂⍺}⌺3 3)3 4⍴⍳12

┌────┬────┬────┬─────┐ │1 1 │1 0 │1 0 │1 ¯1 │ ├────┼────┼────┼─────┤ │0 1 │0 0 │0 0 │0 ¯1 │ ├────┼────┼────┼─────┤ │¯1 1│¯1 0│¯1 0│¯1 ¯1│ └────┴────┴────┴─────┘ 

    ({⊂⍺↓⍵}⌺3 3)3 4⍴⍳12

┌────┬───────┬────────┬─────┐ │1 2 │1 2 3 │2 3 4 │3 4 │ │5 6 │5 6 7 │6 7 8 │7 8 │ ├────┼───────┼────────┼─────┤ │1 2│1 2 3│ 2 3 4│ 3 4│ │5 6│5 6 7│ 6 7 8│ 7 8│ │9 10│9 10 11│10 11 12│11 12│ ├────┼───────┼────────┼─────┤ │5 6│5 6 7│ 6 7 8│ 7 8│ │9 10│9 10 11│10 11 12│11 12│ └────┴───────┴────────┴─────┘ </syntaxhighlight>

Examples

With a default movement in every direction of 1, the rectangles are centred on neighbouring elements of the array. Here, we simply enclose each neighbourhood: <source lang=apl> 

     {⊂⍵}⌺3 3⊢3 3⍴⍳9

┌─────┬─────┬─────┐ │0 0 0│0 0 0│0 0 0│ │0 1 2│1 2 3│2 3 0│ │0 4 5│4 5 6│5 6 0│ ├─────┼─────┼─────┤ │0 1 2│1 2 3│2 3 0│ │0 4 5│4 5 6│5 6 0│ │0 7 8│7 8 9│8 9 0│ ├─────┼─────┼─────┤ │0 4 5│4 5 6│5 6 0│ │0 7 8│7 8 9│8 9 0│ │0 0 0│0 0 0│0 0 0│ └─────┴─────┴─────┘ </syntaxhighlight> In the following example, each neighbourhood is immediately ravelled and summed: <source lang=apl> 

     {+/,⍵}⌺3 3⊢3 3⍴⍳9

12 21 16 27 45 33 24 39 28 </syntaxhighlight> If the number of columns in the right operand to stencil does not match the rank of the right argument, the windowing is applied on the major cells: <source lang=apl> 

     {⊂⍵}⌺(⍪2 2)⊢10 6⍴⍳100

┌──────────────┬─────────────────┬─────────────────┬─────────────────┬─────────────────┐ │1 2 3 4 5 6│13 14 15 16 17 18│25 26 27 28 29 30│37 38 39 40 41 42│49 50 51 52 53 54│ │7 8 9 10 11 12│19 20 21 22 23 24│31 32 33 34 35 36│43 44 45 46 47 48│55 56 57 58 59 60│ └──────────────┴─────────────────┴─────────────────┴─────────────────┴─────────────────┘ </syntaxhighlight> Stencil allows for a very succinct expression of a dfn that calculates the next iteration in Conway's Game of Life (on a rectangle bound by zeros). Inspired by an algorithm from Arthur Whitney written in K and adapted to APL by Jay Foad: <source lang=apl> 

     ⎕IO←0
     life ← {3=s-⍵∧4=s←{+/,⍵}⌺3 3⊢⍵}

     {'.⍠'[⍵]}¨ (⍳8) {life⍣⍺⊢⍵}¨ ⊂glider

┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐ │..⍠..│.⍠...│..⍠..│.....│.....│.....│.....│.....│ │⍠.⍠..│..⍠⍠.│...⍠.│.⍠.⍠.│...⍠.│..⍠..│...⍠.│.....│ │.⍠⍠..│.⍠⍠..│.⍠⍠⍠.│..⍠⍠.│.⍠.⍠.│...⍠⍠│....⍠│..⍠.⍠│ │.....│.....│.....│..⍠..│..⍠⍠.│..⍠⍠.│..⍠⍠⍠│...⍠⍠│ │.....│.....│.....│.....│.....│.....│.....│...⍠.│ └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘ </syntaxhighlight>

See also

External links

Documentation

Publications

References

  1. ↑ Eugene McDonnell: Life: Nasty, Brutish, and Short. APL88.
  2. ↑ Ken Iverson: A Dictionary of APL. APL Quote Quad, Volume 18, Number 1, 1987-09.
APL built-ins [edit]
Primitives (Timeline) Functions
Scalar
Monadic Conjugate ∙ Negate ∙ Signum ∙ Reciprocal ∙ Magnitude ∙ Exponential ∙ Natural Logarithm ∙ Floor ∙ Ceiling ∙ Factorial ∙ Not ∙ Pi Times ∙ Roll ∙ Type ∙ Imaginary ∙ Square Root ∙ Round
Dyadic Add ∙ Subtract ∙ Times ∙ Divide ∙ Residue ∙ Power ∙ Logarithm ∙ Minimum ∙ Maximum ∙ Binomial ∙ Comparison functions ∙ Boolean functions (And, Or, Nand, Nor) ∙ GCD ∙ LCM ∙ Circular ∙ Complex ∙ Root
Non-Scalar
Structural Shape ∙ Reshape ∙ Tally ∙ Depth ∙ Ravel ∙ Enlist ∙ Table ∙ Catenate ∙ Reverse ∙ Rotate ∙ Transpose ∙ Raze ∙ Mix ∙ Split ∙ Enclose ∙ Nest ∙ Cut (K) ∙ Pair ∙ Link ∙ Partitioned Enclose ∙ Partition
Selection First ∙ Pick ∙ Take ∙ Drop ∙ Unique ∙ Identity ∙ Stop ∙ Select ∙ Replicate ∙ Expand ∙ Set functions (Intersection ∙ Union ∙ Without) ∙ Bracket indexing ∙ Index ∙ Cartesian Product ∙ Sort
Selector Index generator ∙ Grade ∙ Index Of ∙ Interval Index ∙ Indices ∙ Deal ∙ Prefix and suffix vectors
Computational Match ∙ Not Match ∙ Membership ∙ Find ∙ Nub Sieve ∙ Encode ∙ Decode ∙ Matrix Inverse ∙ Matrix Divide ∙ Format ∙ Execute ∙ Materialise ∙ Range
Operators Monadic Each ∙ Commute ∙ Constant ∙ Replicate ∙ Expand ∙ Reduce ∙ Windowed Reduce ∙ Scan ∙ Outer Product ∙ Key ∙ I-Beam ∙ Spawn ∙ Function axis ∙ Identity (Null, Ident)
Dyadic Bind ∙ Compositions (Compose, Reverse Compose, Beside, Withe, Atop, Over) ∙ Inner Product ∙ Determinant ∙ Power ∙ At ∙ Under ∙ Rank ∙ Depth ∙ Variant ∙ Stencil ∙ Cut ∙ Direct definition (operator) ∙ Identity (Lev, Dex)
Quad names Index origin ∙ Comparison tolerance ∙ Migration level ∙ Atomic vector
Retrieved from ‘https://aplwiki.com/index.php?title=Stencil&oldid=9663’