2b:null 2c:["$","title",null,{"children":"3D λ reductions | Kelley van Evert | Observable"}] 31:T84c,viewof state = { const state = { rotx: .85, roty: -1.5, blur: false, scale: .7 }; const root = html`← This cell contains the code responsible for handling touch/mouse input. By using the viewof operator, it can transfer these canvas UI input events to a reactive variable containing the rotation/scale view state.`; const update = () => { root.value = state; root.dispatchEvent(new CustomEvent('input')); }; const pos = (e) => { const mouseX = e.pageX; const mouseY = e.pageY; const canvasX = c.canvas.offsetLeft; const canvasY = c.canvas.offsetTop; const canvasWidth = c.canvas.offsetWidth; const canvasHeight = c.canvas.offsetHeight; const x = ((mouseX - canvasX) / canvasWidth); const y = ((mouseY - canvasY) / canvasHeight); return { x, y }; }; var p0 = null; const move = (e) => { e.preventDefault(); const p = pos(e); if (p0) { const dx = p.x - p0.x; const dy = p.y - p0.y; state.rotx += dx * Math.PI; state.roty -= dy * Math.PI; p0 = p; update(); } return false; }; c.canvas.addEventListener('mousemove', move); c.canvas.addEventListener('touchmove', move); const mdown = (e) => { e.preventDefault(); state.blur = false; p0 = pos(e); return false; }; c.canvas.addEventListener('mousedown', mdown); c.canvas.addEventListener('touchdown', mdown); const mup = (e) => { e.preventDefault(); state.blur = true; p0 = null; update(); return false; }; c.canvas.addEventListener('mouseup', mup); c.canvas.addEventListener('touchup', mup); const mwheel = (e) => { e.preventDefault(); state.scale = _.clamp(state.scale + e.deltaY/20, .2, 4); state.e = e; update(); return false; }; c.canvas.addEventListener('wheel', mwheel); c.canvas.addEventListener('onwheel', mwheel); c.canvas.addEventListener('mousewheel', mwheel); c.canvas.addEventListener('DOMMouseScroll', mwheel); update(); return root; }32:T79a,render = c.render = function render (deblur) { if (deblur) state.blur = true; // ^ hack c.setTransform(1, 0, 0, 1, 0, 0); c.translate(width/2, height/2); const scale = () => (.00025 * width * state.scale); c.fillStyle = '#fafafa'; c.fillRect(-width/2, -height/2, width, height); var transform = Mat3.rotationY(state.rotx) .multiply(Mat3.rotationZ(state.roty)); g.nodes.forEach(n => n.p = Vertex.transform(n, transform)); const extent = d3.extent(g.nodes.map(n => n.p.z)); const step = 400; const layers = []; for (var i = 0, z; (z = extent[0] + i*step) < extent[1]; i++) { layers.push({ nodes: g.nodes.filter(n => n.p.z >= z && n.p.z < z + step), links: g.links.filter(l => l.source.p.z >= z && l.source.p.z < z + step), }); } if (layers.length > 2) { const last = layers.pop(); layers[layers.length - 2] = { nodes: layers[layers.length - 2].nodes.concat(last.nodes), links: layers[layers.length - 2].links.concat(last.links), }; } layers.forEach((layer, i) => { var a = (i+1) / layers.length; // 1/N --> 1 if (strategy == 'no') { c.lineWidth = (a + .5); // 1 --> 2 c.strokeStyle = d3.interpolateGreys(.2 + a*.8); // .4 --> 1 } c.fillStyle = d3.interpolateGreys(.2 + a*.8); // .4 --> 1 if (state.blur) StackBlur.canvasRGB(c.canvas, 0, 0, width, height, 2*(1.1-a)); layer.nodes.map(n => { c.beginPath(); c.ellipse(n.p.x * scale(), n.p.y * scale(), 1, 1, Math.PI*2, 0, Math.PI*2); c.fill(); }); layer.links.map(l => { if (strategy != 'no') { c.lineWidth = l[strategy] ? 2 : .5; c.strokeStyle = l[strategy] ? interpolators[strategy](.2 + a*.8) : d3.interpolateGreys(.2 + a*.4); } c.beginPath(); c.moveTo(l.source.p.x * scale(), l.source.p.y * scale()); c.lineTo(l.target.p.x * scale(), l.target.p.y * scale()); c.stroke(); }); }); }33:T418,function graph (term) { const MAX = 600; var it = 0; const cache = {}; const nodes = []; const links = []; var cut = false; const t0 = normalizeb(term); t0.by_name = t0.by_value = true; const todo = [t0]; while (todo.length > 0) { if (it++ >= MAX) { cut = true; break; } var t = todo.pop(); var d = dispb(t); var u = blcb(t); if (cache[u]) continue; nodes.push(cache[u] = { by_name: t.by_name, by_value: t.by_value, term: d, }); var R = reductionsb(t).map(normalizeb); R.forEach((t2, i) => { const link = { source: d, target: dispb(t2), by_name_all: (i == R.length - 1), by_value_all: (i == 0), }; link.by_name = t.by_name && link.by_name_all; link.by_value = t.by_value && link.by_value_all; if (link.by_name) t2.by_name = true; if (link.by_value) t2.by_value = true; links.push(link); todo.push(t2); }); } return { nodes, links, cut }; }34:[] 2f:{"id":"a7e4c99b371f8bf6","slug":"3d-reductions","title":"3D λ reductions","thumbnail":"1457de49ed0b4e8c850325ffabd320aa6c39c1907ec30ba8b5583db1d9382283","access_level":"public","create_time":"$D2018-02-22T18:53:50.670Z","update_time":"$D2020-09-03T16:54:45.994Z","view_time":null,"first_public_time":"$D2018-02-23T22:26:01.043Z","fork":false,"stars":6,"starred":false,"owner":{"type":"team","id":"cdda271b76654961","login":"kelleyvanevert","name":"Kelley van Evert","avatar_url":"https://avatars-next.observableusercontent.com/86df2bc54dd099fad6826dfcf7ae3dd97c5e0cdcf0cf3e0ac85ecd13e1938db2","tier":"starter_2024"},"version":1308,"publish_version":1308,"role":null,"authored":false,"authors":[{"type":"individual","id":"a35690ff73833989","login":"kelleyvanevert","name":"Kelley van Evert","avatar_url":"https://avatars-next.observableusercontent.com/86df2bc54dd099fad6826dfcf7ae3dd97c5e0cdcf0cf3e0ac85ecd13e1938db2","tier":null}],"members":[{"type":"individual","id":"a35690ff73833989","login":"kelleyvanevert","name":"Kelley van Evert","avatar_url":"https://avatars-next.observableusercontent.com/86df2bc54dd099fad6826dfcf7ae3dd97c5e0cdcf0cf3e0ac85ecd13e1938db2","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":3,"collection":null,"type":"notebook","body":{"title":"3D λ reductions","cells":[{"id":0,"value":"md`# 3D λ reductions`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":821,"value":"md`(*This one's just a static render, to please the Observable thumbnailer.*)\n\n![sdf](https://i.imgur.com/S8BwB0k.png)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":788,"value":"md`## What's this?\n\nWhat you see below is a 3D layout of the reduction graph of the lambda term:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":802,"value":"tex.block`\\left((λxy. x^{15} yy x)(λxy. x^{15} yy x)(λx.x)\\right)^2`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":813,"value":"texmd`Where $t^n$ is just concatenation, i.e. $t^n = \\\\overbrace{t\\\\,t \\\\dots t}^n$.\n\nThe example is due to:\n\n> Niels Bjørn Bugge Grathwohl, Jeroen Ketema, Jens Duelund Pallesen, and Jakob Grue Simonsen (2011) **“Anagopos: A Reduction Graph Visualizer for Term Rewriting and Lambda Calculus”** ([pdf](http://www.diku.dk/~bugge/pubs/files/grathwohl2011-0-paper.pdf))\n\nSee [my earlier notebook](https://beta.observablehq.com/@kelleyvanevert/lambda-reductions) for the code on lambda term reductions, etc.\n\nBTW, the DOF blur will kick in after the force simulation is completed.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1014,"value":"viewof term_i = radio({\n title: 'Lambda term',\n options: [\n { label: `SKK`, value: 'SKK' },\n { label: `N`, value: 'N' },\n { label: `line`, value: 's1' },\n { label: `square`, value: 's2' },\n { label: `cube`, value: 's3' },\n { label: `4D hypercube`, value: 's4' },\n { label: `5D hypercube`, value: 's5' },\n ],\n value: 'N',\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":904,"value":"viewof strategy = radio({\n title: 'Highlight computation or reduction strategy?',\n options: [\n { label: 'No', value: 'no' },\n { label: `Yes, call-by-name computation`, value: 'by_name' },\n { label: `Yes, all call-by-name paths`, value: 'by_name_all' },\n { label: `Yes, call-by-value computation`, value: 'by_value' },\n { label: `Yes, all call-by-value paths`, value: 'by_value_all' },\n ],\n value: 'by_name_all'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1130,"value":"md`You can choose to highlight the call-by-name or call-by-value reductions, and whether to highlight all such paths, or just the computation starting with the term of the graph.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":579,"value":"viewof c = {\n var c = DOM.context2d(width, height);\n c.canvas.value = c;\n return c.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1090,"value":"md`Finally, actually running the renderer:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1086,"value":"run = render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1034,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1056,"value":"md`The code that draws the graph. The reason for separating the render logic and the canvas into two cells in this way, by the way, is in order to reuse the canvas.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1119,"value":"interpolators = ({\n by_name: d3.interpolateBlues,\n by_name_all: d3.interpolateGreens,\n by_value: d3.interpolateReds,\n by_value_all: d3.interpolateOranges,\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":315,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":996,"value":"md`The 3D force-layout simulation.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":468,"value":"simulation = d3_force.forceSimulation(g.nodes, 3)\n .force(\"link\", d3_force.forceLink(g.links).id(d => d.term).distance(60))\n .force(\"charge\", d3_force.forceManyBody().strength(-1500))\n .force(\"center\", d3_force.forceCenter(0, 0, 0))\n// The calling of `c.render` instead of `render`, is a hack to avoid circularity in the cell definitions.\n// (It simply seems the best/nicest thing to do, to add these event handlers here.)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1276,"value":"{\n term;\n simulation\n .on('end', null)\n .on('tick', null)\n .on('end', () => render(true))\n .on('tick', render)\n \n return html`This cell restarts the simulation when a new term is chosen.`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":992,"value":"md`The reduction graph of the term in question:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1279,"value":"term = terms[term_i]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":462,"value":"g = graph(term)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":990,"value":"md`A function to collect the reduction graph of a term:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":61,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":988,"value":"md`The term to be displayed:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"N = {\n const t = '(λxy.yyyyy yyyyy yyyyy xxy)';\n const I = '(λx.x)';\n return bruijnify(parse(`(${t}${t}${I})(${t}${t}${I})`));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1148,"value":"terms = ({\n N,\n SKK: parseb(`(λλλ31(21))(λλ2)(λλ2)`),\n s0: s(0),\n s1: s(1),\n s2: s(2),\n s3: s(3),\n s4: s(4),\n s5: s(5),\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":994,"value":"md`Some fixed settings:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":584,"value":"width = 800","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":587,"value":"height = 400","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":979,"value":"md`## Dependencies`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"import { s, reductionsb, normalizeb, blcb, bruijnify, parse, parseb, dispb } from '@kelleyvanevert/lambda-reductions'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":45,"value":"d3 = {\n const d3 = await require('https://d3js.org/d3.v5.min.js');\n //const o = await require('https://unpkg.com/d3-3d@0.0.7/build/d3-3d.min.js');\n //d3._3d = o._3d;\n return d3;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":379,"value":"md`This little lib monkey-patches 3D into d3's force layout:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":139,"value":"d3_force = require('https://unpkg.com/d3-force-3d@1.1.0/build/d3-force-3d.js')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":168,"value":"_ = require('lodash')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":271,"value":"import { Mat3, Vertex } from '@kelleyvanevert/projection-of-3d-models-using-javascript-and-html5-canvas'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":715,"value":"StackBlur = require(\"https://cdnjs.cloudflare.com/ajax/libs/stackblur-canvas/1.4.1/stackblur.js\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":830,"value":"import { texmd } from '@kelleyvanevert/katex-within-markdown'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":873,"value":"import { text, radio } from '@jashkenas/inputs'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1","titling":"auto"}} 30:"$2f:body"