31:T5be,md`# Sandpiles in the reactive runtime This notebook documents a little experiment with [reactive programming](https://en.wikipedia.org/wiki/Reactive_programming) using [Observable's runtime library](https://github.com/observablehq/runtime). In "ordinary use", the variables defined in a runtime correspond to cells in a notebook and they are "observed" by [the standard inspector](https://github.com/observablehq/inspector) which displays the cells as HTML elements. However, the runtime can be used more generally as an engine for reactive computation. Below, I explain how to simulate a few simple variants of the [abelian sandpile model](https://en.wikipedia.org/wiki/Abelian_sandpile_model) using the Observable runtime. **Note:** About all I know about reactive programming is what I've read on Wikipedia. I'd be happy to receive comments / suggestions from anyone who knows any more than I do! *Spoiler:* The implementations below aren't particularly efficient! If you're just interested in the sandpile model, ~~see [this WIP notebook](https://observablehq.com/d/807bb0225b7d4769) for a faster (but less "reactive") approach.~~ Scratch that, see [these](https://observablehq.com/@mbostock/abelian-sandpile) [two](https://observablehq.com/@mbostock/abelian-sandpile/2) amazing notebooks by [Mike Bostock](/@mbostock) for even faster implementations! (For reasons beyond my ken, the code below seems to run about 3 times faster in Chrome than in Firefox...) `32:T47b,md`## First approach The version of the sandpile model we'll consider first is as follows: Consider a *L* by *L* grid of squares. Each grid square can hold an integer number of grains of sand, subject to the following "toppling" rule. At each instant of time, if there are two or more grains of sand on a given square: - two grains are removed from that square, - one is placed on the square on the right, and - one is placed on the one below. To trigger the dynamics, we add grains of sand repeatedly to the square at the top left corner of the grid and then enforce the toppling rule whenever it applies. Now, how might we simulate this using a reactive programming approach? ### A tiny version using notebook cells A first idea is to represent each of the squares by variables which react to the squares that might pass them grains. (We'll see a better idea using \`mutable\` cells in the next section...) Let's mock this up using notebook cells. We want each cell to keep track of the number of grains on it as well as the number of grains falling to the right or to the left. The function \`topple\` will enforce the toppling rule. `33:T48f,{ const svg = d3.select(DOM.svg(450,300)); const data = [[0,0],[1,0],[0,1],[1,1],[2,0],[2,1],[0,2],[1,2],[2,2]]; const g = svg.selectAll('g').data(data).join('g') .attr('transform', d => `translate(${20+150*d[0]},${100*d[1]})`); g.append('ellipse') .attr('cx', 50) .attr('cy', 50) .attr('rx', 60) .attr('ry', 35) .attr('fill', 'none') .attr('stroke', 'black'); g.append('text') .text(d => `a${d[0]}${d[1]}`) .attr('x', 50) .attr('y', 50) .attr('fill', 'black') .attr('font-size', 25) .attr('text-anchor', "middle") .attr('dominant-baseline', "central"); const vert = g.filter(d => d[1]>0); vert.append('line') .attr('x1',50) .attr('y1',15) .attr('x2',50) .attr('y2',-15) .attr('stroke','black'); vert.append('polygon') .attr('points', '45,0 50,15 55,0') .attr('fill', 'black'); const horiz = g.filter(d => d[0]>0); horiz.append('line') .attr('x1',-10) .attr('y1',50) .attr('x2',-40) .attr('y2',50) .attr('stroke','black'); horiz.append('polygon') .attr('points', '-25,45 -10,50 -25,55') .attr('fill', 'black'); return svg.node(); }34:T634,md`---- ## Using Mutable The above approach doesn't scale too well unfortunately. When the variable corresponding to (0,0) is redefined, all ${Lx*Ly} cells have to be re-evaluated, even though 3/4 of the time the sand only shifts between the squares from (0,0) to (1,1). Furthermore, the fact that grain toppling is hard-coded into the dependencies of the variables is a bit constraining. You may have noticed that the sandpile model we considered above is rather asymmetric: the grains only ever topple down or to the right. In particular, grains can never topple backwards. In the usual sandpile model on a grid, 4 grains on a square topple to its neighbors in the four cardinal directions -- with the approach above, this leads to cyclic dependencies, since a square can both give and receive grains from each of its neighbors. In this section, we'll go through another implementation of the sandpile model using Observable's very cool [mutable](https://observablehq.com/@observablehq/introduction-to-mutable-state) keyword. The key idea is to use **multiple** reactive variables per grid square: - a \`mutable\` object (which actually consists of multiple variables "under the hood") containing the number of grains on a given square and - a toppling logic variable which can adjust the mutable variables corresponding to "downstream" squares. ### Mini-implementation in notebook cells As above, let's first prototype this in a 3 by 3 grid using notebook cells (feel free to skip down to [the button and visualization](#btrigger)). Here are the cells for the (0,0) square: `35:T410,function gridObserver2(ctx, x, y) { return { pending() { ctx.fillStyle = '#ddd'; ctx.fillRect(boxw2*x, boxh2*y, boxw2, boxh2); }, fulfilled(value) { switch (value) { case 0: { ctx.fillStyle = '#00f'; break; } case 1: { ctx.fillStyle = '#f00'; break; } case 2: { ctx.fillStyle = '#0f0'; break; } case 3: { ctx.fillStyle = '#ff0'; break; } case 4: { ctx.fillStyle = '#0ff'; break; } case 5: { ctx.fillStyle = '#f0f'; break; } case 6: { ctx.fillStyle = '#fff'; break; } case 7: { ctx.fillStyle = '#000'; break; } default: { ctx.fillStyle = '#555'; } } ctx.fillRect(boxw2*x, boxh2*y, boxw2, boxh2); }, rejected(error) { console.log(`error in cell ${x}, ${y}`); } } }36:[] 2f:{"title":"Sandpiles in the reactive runtime","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":536,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":182,"value":"// Given a raw value (number of grains on a square),\n// return an object with the new value and number of grains to send to the squares to the right and below\nfunction topple(value) {\n return value >= 2 ? {value:value-2, right:1, below:1} : {value, right:0, below:0};\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":614,"value":"md`The dependencies among the cells \\`a00, ..., a22\\` form the following directed 3 by 3 grid:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":690,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":688,"value":"md`Cell \\`a00\\` also takes as input a variable \\`atrigger\\` which is controlled by a button input below (not shown in the above diagram). The other cells use Observable's [\\`this\\`](https://beta.observablehq.com/@tmcw/untitled/5) to \"remember\" their last value. Feel free to inspect their source below. \n\nWhen you're ready, click on [the button](#atrigger) to drop grains on \\`a00\\`.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":554,"value":"// Square at (0,0)\na00 = {\n let value = (this && this.value) || 0,\n right = 0, below = 0;\n value += +atrigger;\n if (value >= 2) { value -= 2; right = 1; below = 1; }\n return {value, right, below};\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":569,"value":"// Square at (1,0)\na10 = {\n const value = (this && this.value) || 0;\n return topple(value + a00.right);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":573,"value":"// Square at (0,1)\na01 = {\n const value = (this && this.value) || 0;\n return topple(value + a00.below);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":578,"value":"// Square at (1,1)\na11 = {\n const value = (this && this.value) || 0;\n return topple(value + a10.below + a01.right);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":594,"value":"// Square at (2,0)\na20 = {\n const value = (this && this.value) || 0;\n return topple(value + a10.right);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":596,"value":"// Square at (2,1)\na21 = {\n const value = (this && this.value) || 0;\n return topple(value + a11.right + a20.below);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":601,"value":"// Square at (0,2)\na02 = {\n const value = (this && this.value) || 0;\n return topple(value + a01.below);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":602,"value":"// Square at (1,2)\na12 = {\n const value = (this && this.value) || 0;\n return topple(value + a02.right + a11.below);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":598,"value":"// Square at (2,2)\na22 = {\n const value = (this && this.value) || 0;\n return topple(value + a12.right + a21.below);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":631,"value":"viewof atrigger = {\n const div = html``;\n div.onclick = () => m.redefine(\"[0,0]\", () => ({value:0, right:1, below:1}));\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":16,"value":"canvas = DOM.canvas(Lx*boxw,Ly*boxh)","pinned":false,"hidden":false,"mode":"ojs"},{"id":783,"value":"md`Cool, huh?\n\nIn the rest of this section, let's have a look at the internals of our runtime module \\`m\\`, using a function I've adapted from [MDN](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Enumerability_and_ownership_of_properties#Obtaining_properties_by_enumerabilityownership) / [SO](https://stackoverflow.com/a/8024294/) which exposes all properties of a JS object and its parent:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":68,"value":"getAllPropertyNamesAsObj(m)","pinned":true,"hidden":false,"mode":"ojs"},{"id":787,"value":"md`The variables are stored in the \\`_scope\\` map:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":65,"value":"m._scope","pinned":true,"hidden":false,"mode":"ojs"},{"id":805,"value":"md`Here's how to check on one of the variables corresponding to a particular square:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":71,"value":"getAllPropertyNamesAsObj(m._scope.get(\"[1,0]\"))","pinned":true,"hidden":false,"mode":"ojs"},{"id":790,"value":"md`The \\`_runtime\\` object is not too interesting unless \\`m\\` is currently \"live\":`","pinned":false,"hidden":false,"mode":"ojs"},{"id":792,"value":"getAllPropertyNamesAsObj(m._runtime)","pinned":true,"hidden":false,"mode":"ojs"},{"id":416,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":214,"value":"// mutable (0,0)\nmutable b00 = 0","pinned":true,"hidden":false,"mode":"ojs"},{"id":222,"value":"{ // topple (0,0)\n b00;\n if (mutable b00 >= 2) {\n mutable b00 -= 2;\n mutable b01++;\n mutable b10++;\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":907,"value":"md`Note the lines:\n\\`\\`\\`js\n b00;\n if (mutable b00 >= 2) {\n\\`\\`\\`\nWhy this and not simply:\n\\`\\`\\`js\n if (b00 >= 2) {\n\\`\\`\\`\n? \n\nThe reason is that the latter code can result in weird race-condition glitches. This is because \\`b00\\` and \\`mutable b00\\` are slightly out-of-sync, as under the hood, \\`b00\\` is implemented from the values of \\`mutable b00\\` using \"[\\`Generators.observe\\`](https://github.com/observablehq/stdlib#Generators_observe)\".\n\nThe other 8 cells are similar:\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":224,"value":"// mutable (1,0)\nmutable b10 = 0","pinned":false,"hidden":false,"mode":"ojs"},{"id":239,"value":"{ // topple (1,0)\n b10;\n if (mutable b10 >= 2) {\n mutable b10 -= 2;\n mutable b20++;\n mutable b11++;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":851,"value":"// mutable (0,1)\nmutable b01 = 0","pinned":false,"hidden":false,"mode":"ojs"},{"id":854,"value":"{ // topple (0,1)\n b01;\n if (mutable b01 >= 2) {\n mutable b01 -= 2;\n mutable b02++;\n mutable b11++;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":231,"value":"// mutable (1,1)\nmutable b11 = 0","pinned":false,"hidden":false,"mode":"ojs"},{"id":247,"value":"{ // topple (1,1)\n b11;\n if (mutable b11 >= 2) {\n mutable b11 -= 2;\n mutable b21++;\n mutable b12++;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":834,"value":"// mutable (2,1)\nmutable b21 = 0","pinned":false,"hidden":false,"mode":"ojs"},{"id":866,"value":"{ // topple (2,1)\n b21;\n if (mutable b21 >= 2) {\n mutable b21 -= 2;\n mutable b22++;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":835,"value":"// mutable (1,2)\nmutable b12 = 0","pinned":false,"hidden":false,"mode":"ojs"},{"id":869,"value":"{ // topple (1,2)\n b12;\n if (mutable b12 >= 2) {\n mutable b12 -= 2;\n mutable b22++;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":845,"value":"// mutable (2,0)\nmutable b20 = 0","pinned":false,"hidden":false,"mode":"ojs"},{"id":872,"value":"{ // topple (2,0)\n b20;\n if (mutable b20 >= 2) {\n mutable b20 -= 2;\n mutable b21++;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":847,"value":"// mutable (0,2)\nmutable b02 = 0","pinned":false,"hidden":false,"mode":"ojs"},{"id":875,"value":"{ // topple (0,2)\n b02;\n if (mutable b02 >= 2) {\n mutable b02 -= 2;\n mutable b12++;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":849,"value":"// mutable (2,2)\nmutable b22 = 0","pinned":false,"hidden":false,"mode":"ojs"},{"id":878,"value":"{ // topple (2,2)\n b22;\n if (mutable b22 >= 2) {\n mutable b22 -= 2;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":217,"value":"btrigger = {\n const div = html``;\n div.onclick = () => m2.redefine(\"trigger\", [`mutable [${tag}]`],\n (m00) => {\n m00.value+= +object.size;\n });\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":264,"value":"canvas2 = {\n object;\n return DOM.canvas(Lx2*boxw2,Ly2*boxh2);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":997,"value":"viewof object = form(html``)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1031,"value":"md`Let me mention again that this approach to simulating the sandpile model is not particularly efficient and was chosen just to see what kinds of weird things could be done by (ab)using the Observable runtime. See ~~[this WIP notebook](https://observablehq.com/d/807bb0225b7d4769)~~ Mike Bostock's notebooks [[1]](https://observablehq.com/@mbostock/abelian-sandpile) [[2]](https://observablehq.com/@mbostock/abelian-sandpile/2) for much, much faster implementations!\n\nHere you can see that a **lot** more variables are defined in \\`m2\\` than in \\`m\\`:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1029,"value":"m2._scope","pinned":true,"hidden":false,"mode":"ojs"},{"id":326,"value":"getAllPropertyNamesAsObj(m2._scope.get(\"mutable [10,10]\"))","pinned":true,"hidden":false,"mode":"ojs"},{"id":418,"value":"boxh2 = 3","pinned":false,"hidden":false,"mode":"ojs"},{"id":419,"value":"boxw2 = 3","pinned":false,"hidden":false,"mode":"ojs"},{"id":982,"value":"md`The observer factory \\`gridObserver2\\` is similar to [\\`gridObserver\\`](#gridObserver) above except that it supports more colors (and uses \\`boxw2\\`, \\`boxh2\\`, \\`Lx2\\` and \\`Ly2\\`).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":275,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":1020,"value":"md`\\`noObs\\` is a \"do-nothing\" observer. This is needed to force the \"topple\" and \"trigger\" cells to run.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":396,"value":"noObs = ({\n pending() {\n },\n fulfilled(value) {\n },\n rejected(error) {\n }\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1017,"value":"md`### Imports`","pinned":false,"hidden":false,"mode":"ojs"},{"id":691,"value":"d3 = require('d3@5')","pinned":false,"hidden":false,"mode":"ojs"},{"id":61,"value":"import {getAllPropertyNamesAsObj} from '048035bf9a9c263e'","pinned":true,"hidden":false,"mode":"ojs"},{"id":998,"value":"import {form} from \"@mbostock/form-input\"","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W36","stdlib":"1","titling":"auto"}