Stencil: Difference between revisions

Jump to navigation Jump to search

Stencil (view source)

Revision as of 21:11, 28 January 2024

2,364 bytes added ,  28 January
Rationalized APL defined the stencil case of Cut earlier and in slightly more detail
m (Remove closing pre HTML tags that were within the source tags and displaying, which looks unintended.)
(Rationalized APL defined the stencil case of Cut earlier and in slightly more detail)
 
(5 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 defined in [[Rationalized APL]].


== 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...10775’

Navigation menu