Stencil: Difference between revisions

Jump to navigation Jump to search

Stencil (view source)

Revision as of 10:38, 11 September 2022

2,519 bytes added ,  10:38, 11 September 2022
m
Text replacement - "<source" to "<syntaxhighlight"
m (Remove closing pre HTML tags that were within the source tags and displaying, which looks unintended.)
m (Text replacement - "<source" to "<syntaxhighlight")
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
{{Built-in|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, [[wikipedia:stencil code|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 [[wikipedia:convolution (computer science)|convolution]]), artificial [[neural networks]] and, most famously, [[wikipedia:cellular automaton|cellular automata]]. The operator derives from a subset (specifically, case 3) of the functionality of [[J]]'s [[Cut]] operator (<source lang=j inline>;.3</source>),<ref>[[Eugene McDonnell]]: [https://www.jsoftware.com/papers/eem/life1.htm Life: Nasty, Brutish, and Short]. [[APL88]]. </ref> which in turn originates in the 3-cut mentioned in [[A Dictionary of APL]]<ref>[[Ken Iverson]]: [https://www.jsoftware.com/papers/APLDictionary.htm A Dictionary of APL]. [[APL Quote Quad]], Volume 18, Number 1, 1987-09.</ref>
{{Built-in|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, [[wikipedia:stencil code|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 [[wikipedia:convolution (computer science)|convolution]]), artificial [[neural networks]] and, most famously, [[wikipedia:cellular automaton|cellular automata]]. The operator derives from a subset (specifically, case 3) of the functionality of [[J]]'s [[Cut]] operator (<syntaxhighlight lang=j inline>;.3</syntaxhighlight>),<ref>[[Eugene McDonnell]]: [https://www.jsoftware.com/papers/eem/life1.htm Life: Nasty, Brutish, and Short]. [[APL88]]. </ref> which in turn originates in the 3-cut mentioned in [[A Dictionary of APL]]<ref>[[Ken Iverson]]: [https://www.jsoftware.com/papers/APLDictionary.htm A Dictionary of APL]. [[APL Quote Quad]], Volume 18, Number 1, 1987-09.</ref>


== Description ==
== Description ==


For a call <source lang=apl inline>f⌺s</source> the right operand <source lang=apl inline>s</source> 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</source> and the second row describes the movement along the different [[axis|axes]]. When using stencil <source lang=apl inline>(f⌺s)Y</source> the right operand <source lang=apl inline>s</source> in general has <source lang=apl inline>≢⍴Y</source> columns. If it has fewer, the rectangles are cut out of the [[major cell]]s of the <source lang=apl inline>(≢⍴Y) - ≢1⌷s</source> axis of <source lang=apl inline>Y</source>. If <source lang=apl inline>s</source> is a vector or scalar it describes only the size of the rectangles and the movement defaults to 1. Rectangles are centred on [[element]]s of <source lang=apl inline>Y</source> whose [[index|indices]] differ by the movements in <source lang=apl inline>s</source> (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 [[cell]]s. Along the edges of the [[argument]] array, the windows are thus subject to be padded with [[fill element]]s. 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</source> for the respective [[subarray]].
For a call <syntaxhighlight lang=apl inline>f⌺s</syntaxhighlight> the right operand <syntaxhighlight 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 <syntaxhighlight lang=apl inline>f</syntaxhighlight> and the second row describes the movement along the different [[axis|axes]]. When using stencil <syntaxhighlight lang=apl inline>(f⌺s)Y</syntaxhighlight> the right operand <syntaxhighlight lang=apl inline>s</syntaxhighlight> in general has <syntaxhighlight lang=apl inline>≢⍴Y</syntaxhighlight> columns. If it has fewer, the rectangles are cut out of the [[major cell]]s of the <syntaxhighlight lang=apl inline>(≢⍴Y) - ≢1⌷s</syntaxhighlight> axis of <syntaxhighlight lang=apl inline>Y</syntaxhighlight>. If <syntaxhighlight 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 [[element]]s of <syntaxhighlight lang=apl inline>Y</syntaxhighlight> whose [[index|indices]] differ by the movements in <syntaxhighlight 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 [[cell]]s. Along the edges of the [[argument]] array, the windows are thus subject to be padded with [[fill element]]s.
 
The number of fill elements in along each axis is given as a vector left argument on each call of <syntaxhighlight lang=apl inline>f</syntaxhighlight> for the respective [[subarray]]. This is designed such that [[Drop]] (<syntaxhighlight lang=apl inline>↓</syntaxhighlight>) can take the left and right arguments to remove padding:
<syntaxhighlight 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 ==
== 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:
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>
<syntaxhighlight lang=apl>
       {⊂⍵}⌺3 3⊢3 3⍴⍳9
       {⊂⍵}⌺3 3⊢3 3⍴⍳9
┌─────┬─────┬─────┐
┌─────┬─────┬─────┐
Line 23: Line 61:
│0 0 0│0 0 0│0 0 0│
│0 0 0│0 0 0│0 0 0│
└─────┴─────┴─────┘
└─────┴─────┴─────┘
</source>
</syntaxhighlight>
In the following example, each neighbourhood is immediately [[ravel]]led and [[sum]]med:
In the following example, each neighbourhood is immediately [[ravel]]led and [[sum]]med:
<source lang=apl>
<syntaxhighlight lang=apl>
       {+/,⍵}⌺3 3⊢3 3⍴⍳9
       {+/,⍵}⌺3 3⊢3 3⍴⍳9
12 21 16 27 45 33 24 39 28
12 21 16 27 45 33 24 39 28
</source>
</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:
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>
<syntaxhighlight lang=apl>
       {⊂⍵}⌺(⍪2 2)⊢10 6⍴⍳100
       {⊂⍵}⌺(⍪2 2)⊢10 6⍴⍳100
┌──────────────┬─────────────────┬─────────────────┬─────────────────┬─────────────────┐
┌──────────────┬─────────────────┬─────────────────┬─────────────────┬─────────────────┐
Line 36: Line 74:
│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│
│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│
└──────────────┴─────────────────┴─────────────────┴─────────────────┴─────────────────┘
└──────────────┴─────────────────┴─────────────────┴─────────────────┴─────────────────┘
</source>
</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:
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>
<syntaxhighlight lang=apl>
       ⎕IO←0
       ⎕IO←0
       life ← {3=s-⍵∧4=s←{+/,⍵}⌺3 3⊢⍵}
       life ← {3=s-⍵∧4=s←{+/,⍵}⌺3 3⊢⍵}
Line 50: Line 88:
│.....│.....│.....│.....│.....│.....│.....│...⍠.│
│.....│.....│.....│.....│.....│.....│.....│...⍠.│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
</source>
</syntaxhighlight>
== See also ==
== See also ==
* [[Windowed Reduce]]
* [[Windowed Reduce]]
Line 61: Line 99:
=== Publications ===
=== Publications ===
* [[Dyalog '16]] presentation by [[Roger Hui]]: [https://www.dyalog.com/user-meetings/dyalog16.htm#D06 New Primitive Functions and Operators]
* [[Dyalog '16]] presentation by [[Roger Hui]]: [https://www.dyalog.com/user-meetings/dyalog16.htm#D06 New Primitive Functions and Operators]
* [[Dyalog Ltd.|Dyalog]] blog post by Roger Hui: [https://www.dyalog.com/blog/2017/07/stencil-lives/ Stencil Lives]
* [[Dyalog Ltd.|Dyalog]] blog posts by Roger Hui: [https://www.dyalog.com/blog/2017/07/stencil-lives/ Stencil Lives], [https://www.dyalog.com/blog/2020/06/towards-improvements-to-stencil/ Towards Improvements to ''Stencil'']


== References ==
== References ==
<references/>
<references/>
{{APL built-ins}}[[Category:Primitive operators]]
{{APL built-ins}}[[Category:Primitive operators]]
Retrieved from ‘https://aplwiki.com/wiki/Special:MobileDiff/7024...9666’

Navigation menu