{"id":4045,"date":"2017-07-31T09:15:07","date_gmt":"2017-07-31T09:15:07","guid":{"rendered":"http:\/\/www.dyalog.com\/blog\/?p=4045"},"modified":"2017-07-31T09:15:07","modified_gmt":"2017-07-31T09:15:07","slug":"stencil-lives","status":"publish","type":"post","link":"https:\/\/www.dyalog.com\/blog\/2017\/07\/stencil-lives\/","title":{"rendered":"Stencil Lives"},"content":{"rendered":"<p><code class=\" language-apl\">\u2395io\u21900<\/code> throughout. <code class=\" language-apl\">\u2395io<\/code> <em>delenda est<\/em>.<\/p>\n<h2>Stencil<\/h2>\n<p>A stencil operator <code class=\" language-apl\">\u233a<\/code> is available with Dyalog version 16.0. In brief, <em>stencil<\/em> is a dyadic operator <code class=\" language-apl\">f\u233as<\/code> which applies <code class=\" language-apl\">f<\/code> to (possibly overlapping) rectangles. The size of the rectangle and its movement are controlled by <code class=\" language-apl\">s<\/code>. For example, enclosing 3-by-3 rectangles with default movements of 1:<\/p>\n<pre><code class=\" language-apl\">   \u22a2 a\u21904 5\u2374\u2395a\r\nABCDE\r\nFGHIJ\r\nKLMNO\r\nPQRST\r\n   {\u2282\u2375}\u233a3 3 \u22a2a\r\n\u250c\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2510\r\n\u2502   \u2502   \u2502   \u2502   \u2502   \u2502\r\n\u2502 AB\u2502ABC\u2502BCD\u2502CDE\u2502DE \u2502\r\n\u2502 FG\u2502FGH\u2502GHI\u2502HIJ\u2502IJ \u2502\r\n\u251c\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2524\r\n\u2502 AB\u2502ABC\u2502BCD\u2502CDE\u2502DE \u2502\r\n\u2502 FG\u2502FGH\u2502GHI\u2502HIJ\u2502IJ \u2502\r\n\u2502 KL\u2502KLM\u2502LMN\u2502MNO\u2502NO \u2502\r\n\u251c\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2524\r\n\u2502 FG\u2502FGH\u2502GHI\u2502HIJ\u2502IJ \u2502\r\n\u2502 KL\u2502KLM\u2502LMN\u2502MNO\u2502NO \u2502\r\n\u2502 PQ\u2502PQR\u2502QRS\u2502RST\u2502ST \u2502\r\n\u251c\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u253c\u2500\u2500\u2500\u2524\r\n\u2502 KL\u2502KLM\u2502LMN\u2502MNO\u2502NO \u2502\r\n\u2502 PQ\u2502PQR\u2502QRS\u2502RST\u2502ST \u2502\r\n\u2502   \u2502   \u2502   \u2502   \u2502   \u2502\r\n\u2514\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2518\r\n<\/code><\/pre>\n<p><em>Stencil<\/em> is also known as <em>stencil code<\/em>, <em>tile<\/em>, <em>tessellation<\/em>, and <em>cut<\/em>. It has applications in artificial neural networks, computational fluid dynamics, cellular automata, etc., and of course in <a href=\"http:\/\/en.wikipedia.org\/wiki\/Conway%27s_Game_of_Life\" target=\"_blank\">Conway&#8217;s Game of Life<\/a>.<\/p>\n<h2>The Rules of Life<\/h2>\n<p>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.<\/p>\n<p>(0) A 0-cell with 3 neighboring 1-cells becomes a 1.<\/p>\n<p>(1) A 1-cell with 2 or 3 neighboring 1-cells remains at 1.<\/p>\n<p>(2) All other cells remain or become a 0.<\/p>\n<p>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.<\/p>\n<p>There is an implementation of life in the <a href=\"http:\/\/dfns.dyalog.com\/c_life.htm\" target=\"_blank\">dfns workspace<\/a> and explained in a <a href=\"http:\/\/www.youtube.com\/watch?hl=en-GB&amp;gl=GB&amp;fmt=18&amp;v=a9xAKttWgP4\" target=\"_blank\">YouTube video<\/a>. It assumes a toroidal topology.<\/p>\n<pre><code class=\" language-apl\">   life\u2190{\u21911 \u2375\u2228.\u22273 4=+\/,\u00af1 0 1\u2218.\u2296\u00af1 0 1\u2218.\u233d\u2282\u2375}    \u235d John Scholes\r\n\r\n   \u22a2 glider\u21905 5\u23740 0 1 0 0 1 0 1 0 0 0 1 1,12\u23740\r\n0 0 1 0 0\r\n1 0 1 0 0\r\n0 1 1 0 0\r\n0 0 0 0 0\r\n0 0 0 0 0\r\n   life glider\r\n0 1 0 0 0\r\n0 0 1 1 0\r\n0 1 1 0 0\r\n0 0 0 0 0\r\n0 0 0 0 0\r\n\r\n   {'.\u235f'[\u2375]}\u00a8 (\u23738) {life\u2363\u237a\u22a2\u2375}\u00a8 \u2282glider\r\n\u250c\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u2510\r\n\u2502..\u235f..\u2502.\u235f...\u2502..\u235f..\u2502.....\u2502.....\u2502.....\u2502.....\u2502.....\u2502\r\n\u2502\u235f.\u235f..\u2502..\u235f\u235f.\u2502...\u235f.\u2502.\u235f.\u235f.\u2502...\u235f.\u2502..\u235f..\u2502...\u235f.\u2502.....\u2502\r\n\u2502.\u235f\u235f..\u2502.\u235f\u235f..\u2502.\u235f\u235f\u235f.\u2502..\u235f\u235f.\u2502.\u235f.\u235f.\u2502...\u235f\u235f\u2502....\u235f\u2502..\u235f.\u235f\u2502\r\n\u2502.....\u2502.....\u2502.....\u2502..\u235f..\u2502..\u235f\u235f.\u2502..\u235f\u235f.\u2502..\u235f\u235f\u235f\u2502...\u235f\u235f\u2502\r\n\u2502.....\u2502.....\u2502.....\u2502.....\u2502.....\u2502.....\u2502.....\u2502...\u235f.\u2502\r\n\u2514\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2518\r\n<\/code><\/pre>\n<h2>Stencil Lives<\/h2>\n<p>It has long been known that <em>stencil<\/em> facilitates Game of Life computations. Eugene McDonnell explored the question in the APL88 paper <a href=\"http:\/\/www.jsoftware.com\/papers\/eem\/life.htm\" target=\"_blank\"><em>Life: Nasty, Brutish, and Short<\/em> [Ho51]<\/a>. The shortest of the solutions derive as follows.<\/p>\n<p>By hook or by crook, find all the 3-by-3 boolean matrices <code class=\" language-apl\">U<\/code> which lead to a middle 1. A succinct Game of Life then obtains.<\/p>\n<pre><code class=\" language-apl\">   B \u2190 {1 1\u2337life 3 3\u2374(9\u23742)\u22a4\u2375}\u00a8 \u23732*9\r\n   U \u2190 {3 3\u2374(9\u23742)\u22a4\u2375}\u00a8 \u2378B  \u235d \u2378 \u2190\u2192 {\u2375\/\u2373\u2374\u2375}\r\n\r\n   life1 \u2190 {U \u220a\u2368 {\u2282\u2375}\u233a3 3\u22a2\u2375}    \u235d Eugene McDonnell\r\n<\/code><\/pre>\n<p>Comparing <code class=\" language-apl\">life<\/code> and <code class=\" language-apl\">life1<\/code>, and also illustrating that the toroidal and 0-border computations can be expressed one with the other.<\/p>\n<pre><code class=\" language-apl\">   b\u21901=?97 103\u23743\r\n\r\n   x\u21901 1\u2193\u00af1 \u00af1\u2193 life 0,0,\u23680\u236a0\u236a\u2368b\r\n   y\u2190life1 b\r\n   x\u2261y\r\n1\r\n\r\n   g\u2190{(\u00af1\u2191\u2375)\u236a\u2375\u236a1\u2191\u2375}\r\n   p\u2190life b\r\n   q\u21901 1\u2193\u00af1 \u00af1\u2193 life1 (g b[;102]),(g b),(g b[;0])\r\n   p\u2261q\r\n1\r\n<\/code><\/pre>\n<p>Ad\u00e1m Brudzewsky points out that life can be terser as a train (fork):<\/p>\n<pre><code class=\" language-apl\">   life1a \u2190 U \u220a\u2368 \u22a2\u2218\u2282\u233a3 3    \u235d Ad\u00e1m Brudzewsky\r\n   life1b \u2190 U \u220a\u2368 {\u2282\u2375}\u233a3 3\r\n\r\n   (life1 \u2261 life1a) b\r\n1\r\n   (life1 \u2261 life1b) b\r\n1\r\n<\/code><\/pre>\n<p><code class=\" language-apl\">life1<\/code> is an example of implementing a calculation by look-up rather than by a more conventional computation, discussed in a recent <a href=\"http:\/\/www.dyalog.com\/blog\/2017\/04\/calculation-v-look-up\/\">blog post<\/a>. There is a variation which is more efficient because the look-up is effected with integers rather than boolean matrices:<\/p>\n<pre><code class=\" language-apl\">   A\u21903 3\u23742*\u233d\u23739\r\n   life2 \u2190 {B[{+\/,A\u00d7\u2375}\u233a3 3\u22a2\u2375]}\r\n\r\n   (life1 \u2261 life1b) b\r\n1\r\n<\/code><\/pre>\n<p>Jay Foad offers another stencil life, translating an <a href=\"http:\/\/kparc.com\/z\/fun.k\" target=\"_blank\">algorithm in k<\/a> by Arthur Whitney:<\/p>\n<pre><code class=\" language-apl\">   life3 \u2190 {3=s-\u2375\u22274=s\u2190{+\/,\u2375}\u233a3 3\u22a2\u2375}    \u235d Jay Foad\r\n\r\n   (life1 \u2261 life3) b\r\n1\r\n<\/code><\/pre>\n<p>The algorithm combines the life rules into a single expression, wherein <code class=\" language-apl\">s\u2190{+\/,\u2375}\u233a3 3 \u22a2\u2375<\/code><\/p>\n<p>(0) for 0-cells <code class=\" language-apl\">s<\/code> is the number of neighbors; and<br \/>\n(1) for 1-cells <code class=\" language-apl\"> s<\/code> is the number of neighbors plus 1, and the plus 1 only matters if <code class=\" language-apl\">s<\/code> is 4.<\/p>\n<p>The same idea can be retrofit into the toroidal <code class=\" language-apl\">life<\/code>:<\/p>\n<pre><code class=\" language-apl\">   lifea\u2190{3=s-\u2375\u22274=s\u2190\u2283+\/,\u00af1 0 1\u2218.\u2296\u00af1 0 1\u2218.\u233d\u2282\u2375}\r\n\r\n   (life \u2261 lifea) b\r\n1\r\n\r\n<\/code><\/pre>\n<h2>Collected Definitions and Timings<\/h2>\n<pre><code class=\" language-apl\">life   \u2190 {\u21911 \u2375\u2228.\u22273 4=+\/,\u00af1 0 1\u2218.\u2296\u00af1 0 1\u2218.\u233d\u2282\u2375}\r\nlifea  \u2190 {3=s-\u2375\u22274=s\u2190\u2283+\/,\u00af1 0 1\u2218.\u2296\u00af1 0 1\u2218.\u233d\u2282\u2375}\r\n\r\n  B\u2190{1 1\u2337life 3 3\u2374(9\u23742)\u22a4\u2375}\u00a8 \u23732*9\r\n  U\u2190{3 3\u2374(9\u23742)\u22a4\u2375}\u00a8 \u2378 B\r\n  A\u21903 3\u23742*\u233d\u23739\r\n\r\nlife1  \u2190 {U \u220a\u2368 {\u2282\u2375}\u233a3 3\u22a2\u2375}\r\nlife1a \u2190 U \u220a\u2368 \u22a2\u2218\u2282\u233a3 3\r\nlife1b \u2190 U \u220a\u2368 {\u2282\u2375}\u233a3 3\r\nlife2  \u2190 {B[{+\/,A\u00d7\u2375}\u233a3 3\u22a2\u2375]}\r\nlife3  \u2190 {3=s-\u2375\u22274=s\u2190{+\/,\u2375}\u233a3 3\u22a2\u2375}\r\n\r\n   cmpx (\u2282'life') ,\u00a8 '1' '1a' '1b' '2' '3' '' 'a' ,\u00a8 \u2282' b'\r\n  life1 b  \u2192 2.98E\u00af3 |    0% \u2395\u2395\u2395\u2395\u2395\r\n  life1a b \u2192 1.97E\u00af2 | +561% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\r\n  life1b b \u2192 2.99E\u00af3 |    0% \u2395\u2395\u2395\u2395\u2395\r\n  life2 b  \u2192 2.71E\u00af4 |  -91%\r\n  life3 b  \u2192 6.05E\u00af5 |  -98%\r\n* life b   \u2192 1.50E\u00af4 |  -95%\r\n* lifea b  \u2192 1.41E\u00af4 |  -96%\r\n<\/code><\/pre>\n<p>The <code class=\" language-apl\">*<\/code> indicate that <code class=\" language-apl\">life<\/code> and <code class=\" language-apl\">lifea<\/code> give a different result (toroidal <em>v<\/em> 0-border).<\/p>\n<p><code class=\" language-apl\">life1a<\/code> is much slower than the others because <code class=\" language-apl\">\u22a2\u2218\u2282\u233a<\/code> is not implemented by special code.<\/p>\n<p><code class=\" language-apl\">{+\/,\u2375}\u233a<\/code> is the fastest of the special codes because the computation has mathematical properties absent from <code class=\" language-apl\">{\u2282\u2375}\u233a<\/code> and <code class=\" language-apl\">{+\/,A\u00d7\u2375}\u233a<\/code>.<\/p>\n<p>The effect of special code <em>v<\/em> not, can be observed (for example) by use of redundant parentheses:<\/p>\n<pre><code class=\" language-apl\">   cmpx '{+\/,\u2375}\u233a3 3\u22a2b' '{+\/,(\u2375)}\u233a3 3\u22a2b'\r\n  {+\/,\u2375}\u233a3 3\u22a2b   \u2192 3.13E\u00af5  |      0%\r\n  {+\/,(\u2375)}\u233a3 3\u22a2b \u2192 2.63E\u00af2  | +83900% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\r\n\r\n   cmpx '{+\/,A\u00d7\u2375}\u233a3 3\u22a2b' '{+\/,A\u00d7(\u2375)}\u233a3 3\u22a2b'\r\n  {+\/,A\u00d7\u2375}\u233a3 3\u22a2b   \u2192 2.42E\u00af4 |      0%\r\n  {+\/,A\u00d7(\u2375)}\u233a3 3\u22a2b \u2192 2.98E\u00af2 | +12216% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\r\n\r\n   \u235d no special code in either of the following expressions\r\n   cmpx '{+\/,2\u00d7\u2375}\u233a3 3\u22a2b' '{+\/,2\u00d7(\u2375)}\u233a3 3\u22a2b'\r\n  {+\/,2\u00d7\u2375}\u233a3 3\u22a2b   \u2192 2.92E\u00af2 |      0% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395 \r\n  {+\/,2\u00d7(\u2375)}\u233a3 3\u22a2b \u2192 3.03E\u00af2 |     +3% \u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\u2395\r\n<\/code><\/pre>\n<p>That <code class=\" language-apl\">life<\/code> and <code class=\" language-apl\">lifea<\/code> do not use <em>stencil<\/em> and yet are competitive, illustrates the efficacy of boolean operations and of letting primitives &#8220;see&#8221; large arguments.<\/p>\n<p>Finally, if you wish to play with <em>stencil<\/em> a description and a hi-fi model of it can be found <a href=\"http:\/\/www.dyalog.com\/uploads\/conference\/dyalog16\/presentations\/D06_New_Primitives_RH.zip\" target=\"_blank\">here<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u2395io\u21900 throughout. \u2395io delenda est. Stencil A stencil operator \u233a is available with Dyalog version 16.0. In brief, stencil is a dyadic operator f\u233as which applies f to (possibly overlapping) rectangles. The size of the rectangle and its movement are &hellip; <a href=\"https:\/\/www.dyalog.com\/blog\/2017\/07\/stencil-lives\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":13,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[],"class_list":["post-4045","post","type-post","status-publish","format-standard","hentry","category-apl-language"],"_links":{"self":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/4045","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/users\/13"}],"replies":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/comments?post=4045"}],"version-history":[{"count":6,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/4045\/revisions"}],"predecessor-version":[{"id":4952,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/4045\/revisions\/4952"}],"wp:attachment":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/media?parent=4045"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/categories?post=4045"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/tags?post=4045"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}