Every expression is a tree. (2 + 3) * x looks like this:
* In Python: ('*', ('+', 2, 3), 'x')
/ \
+ x First element = operator.
/ \ Rest = children.
2 3 Tuples all the way down.
A rewrite rule says: when you see this pattern, replace it with that. A handful of them, applied until nothing changes, can simplify or differentiate arbitrary expressions.
Here's the whole thing. 90 lines of Python. A complete symbolic differentiator:
class _W:
def __repr__(self): return '_'
_ = _W()
def rewrite(t, *rules):
while True:
for r in rules:
n = r(t)
if n != t: t = n; break
else: return t
def bottom_up(rule):
def go(t):
if isinstance(t, tuple) and t:
t = (t[0],) + tuple(go(c) for c in t[1:])
return rule(t)
return go
class when:
def __init__(self, *pat):
self.pat, self.fn = pat, None
def then(self, f):
self.fn = f if callable(f) else (lambda *_, v=f: v)
return self
def __call__(self, t):
b = self._m(self.pat, t)
if b is not None and self.fn:
return self.fn(*b.values())
return t
def _m(self, p, t, b=None):
if b is None: b = {}
if callable(p) and not isinstance(p, type):
if not p(t): return None
b[f'_{len(b)}'] = t; return b
if p is _:
b[f'_{len(b)}'] = t; return b
if isinstance(p, str) and p.startswith('$'):
if p in b: return b if b[p] == t else None
b[p] = t; return b
if p == t: return b
if isinstance(p, tuple) and isinstance(t, tuple) and len(p) == len(t):
for pe, te in zip(p, t):
if self._m(pe, te, b) is None: return None
return b
return None
is_lit = lambda x: isinstance(x, (int, float))
def const_wrt(var):
def check(e):
if e == var: return False
if isinstance(e, tuple): return all(check(s) for s in e[1:])
return True
return check
simplify = [
when('+', 0, _).then(lambda x: x), # 0 + x = x
when('+', _, 0).then(lambda x: x), # x + 0 = x
when('*', 0, _).then(0), # 0 * x = 0
when('*', _, 0).then(0), # x * 0 = 0
when('*', 1, _).then(lambda x: x), # 1 * x = x
when('*', _, 1).then(lambda x: x), # x * 1 = x
when('^', _, 0).then(1), # x^0 = 1
when('^', _, 1).then(lambda x: x), # x^1 = x
when('+', is_lit, is_lit).then(lambda a, b: a + b),
when('-', is_lit, is_lit).then(lambda a, b: a - b),
when('*', is_lit, is_lit).then(lambda a, b: a * b),
]
diff = [
when('d', const_wrt('x'), 'x').then(0), # constant
when('d', 'x', 'x').then(1), # variable
when('d', ('+', _, _), '$v').then(lambda u, w, v: ('+', ('d', u, v), ('d', w, v))), # sum
when('d', ('-', _, _), '$v').then(lambda u, w, v: ('-', ('d', u, v), ('d', w, v))), # difference
when('d', ('*', _, _), '$v').then( # product
lambda u, w, v: ('+', ('*', u, ('d', w, v)), ('*', w, ('d', u, v)))),
when('d', ('^', 'x', is_lit), 'x').then(lambda n: ('*', n, ('^', 'x', n - 1))), # power
when('d', ('^', _, is_lit), '$v').then( # chain+power
lambda u, n, v: ('*', ('*', n, ('^', u, n - 1)), ('d', u, v))),
when('d', ('sin', 'x'), 'x').then(('cos', 'x')), # sin
when('d', ('sin', _), '$v').then(lambda u, v: ('*', ('cos', u), ('d', u, v))), # chain+sin
when('d', ('cos', 'x'), 'x').then(('-', 0, ('sin', 'x'))), # cos
when('d', ('cos', _), '$v').then(lambda u, v: ('*', ('-', 0, ('sin', u)), ('d', u, v))), # chain+cos
when('d', ('exp', 'x'), 'x').then(('exp', 'x')), # exp
when('d', ('exp', _), '$v').then(lambda u, v: ('*', ('exp', u), ('d', u, v))), # chain+exp
when('d', ('ln', 'x'), 'x').then(('/', 1, 'x')), # ln
when('d', ('/', _, _), '$v').then( # quotient
lambda u, w, v: ('/', ('-', ('*', w, ('d', u, v)), ('*', u, ('d', w, v))), ('^', w, 2))),
]
rules = [bottom_up(r) for r in diff + simplify]
result = rewrite(('d', ('*', ('^', 'x', 2), ('sin', 'x')), 'x'), *rules)
# => ('+', ('*', ('^', 'x', 2), ('cos', 'x')), ('*', ('sin', 'x'), ('*', 2, 'x')))
That's it. rewrite applies rules until nothing changes. bottom_up walks the tree leaves-first. when does pattern matching: _ matches anything, $x captures a named variable, callables act as predicates. The rest is just calculus rules written as patterns.
The chain rule is not coded explicitly. When a rule like d/dx sin(u) produces cos(u) * d/dx u, that new d node gets rewritten by the same rules on the next pass. The recursion emerges from the fixed-point loop.
The widgets below run a JS reimplementation of the same logic. Step through each one to watch the engine think.
Bottom-up traversal
The key mechanism. Rules only match at the root of whatever they're given, so bottom_up recurses into children first, then tries the rule at the rebuilt node. Leaves light up first, then the engine works upward.
Bottom-Up Traversal
(+ 0 (+ 0 x)) with 0+x => x
(+ (* 2 3) (* 4 5)) with constant folding
(* (+ x 0) (- 5 5)) with arithmetic rules
Reset
Step
Play
Press Step or Play.
<span><span></span>visiting</span>
<span><span></span>rule fired</span>
<span><span></span>rewritten</span>
<span><span></span>fixed point</span>
Arithmetic simplification
More rules, same engine. Identity elements, absorbing elements, constant folding, cancellation:
Arithmetic Simplifier
<span>0+x → x</span>
<span>x*0 → 0</span>
<span>x*1 → x</span>
<span>x-x → 0</span>
<span>n+m → compute</span>
(+ (* 2 3) (* 4 5))
(* (+ x 0) (- 5 5))
(+ (+ 0 x) (- y y))
(/ (* 3 (+ 2 4)) (- 9 3))
Reset
Step
Play
Press Step or Play.
Symbolic differentiation
The same engine with the diff rules from above. Watch the product rule split $x^2 \cdot \sin(x)$ into two branches, then the power and chain rules reduce each piece, then simplification cleans up:
Symbolic Differentiation
d/dx x^3
d/dx (x^2 * sin(x))
d/dx sin(x^2)
d/dx e^(x^2)
d/dx (sin(x) / x)
Reset
Step
Play
Press Step or Play.
/* ── Container ────────────────────────────────── */
.tr-demo {
max-width: 680px;
margin: 2.5em auto;
font-family: -apple-system, BlinkMacSystemFont, 'Segoe UI', Roboto, sans-serif;
}
.tr-demo h3 {
font-size: 0.85em;
text-transform: uppercase;
letter-spacing: 0.08em;
color: #888;
margin: 0 0 10px;
}
/* ── Controls ─────────────────────────────────── */
.tr-bar {
display: flex;
align-items: center;
gap: 8px;
flex-wrap: wrap;
margin-bottom: 6px;
}
.tr-bar select {
font-family: 'SF Mono', 'Fira Code', 'Consolas', monospace;
font-size: 13px;
padding: 5px 8px;
border: 1px solid #d0d0d0;
border-radius: 4px;
background: #fafafa;
flex: 1;
min-width: 160px;
}
.tr-bar button {
font-size: 13px;
padding: 5px 14px;
border: 1px solid #d0d0d0;
border-radius: 4px;
background: #fff;
cursor: pointer;
transition: background 0.12s;
white-space: nowrap;
}
.tr-bar button:hover:not(:disabled) { background: #f0f0f0; }
.tr-bar button:disabled { opacity: 0.35; cursor: default; }
/* ── Canvas ───────────────────────────────────── */
.tr-canvas {
border: 1px solid #e4e4e4;
border-radius: 6px;
background: #fdfdfd;
overflow: hidden;
min-height: 200px;
}
.tr-canvas svg { display: block; width: 100%; }
/* ── Info line ────────────────────────────────── */
.tr-info {
font-size: 13px;
font-family: 'SF Mono', 'Fira Code', 'Consolas', monospace;
padding: 6px 10px;
margin-top: 6px;
background: #f7f7f7;
border-radius: 4px;
min-height: 1.8em;
color: #444;
}
.tr-iter {
font-size: 11px;
color: #999;
margin-top: 4px;
font-family: 'SF Mono', monospace;
}
/* ── Rules pills ──────────────────────────────── */
.tr-pills {
display: flex;
flex-wrap: wrap;
gap: 4px;
margin-bottom: 8px;
}
.tr-pill {
font-family: 'SF Mono', 'Fira Code', 'Consolas', monospace;
font-size: 11px;
padding: 2px 8px;
background: #f0f0f0;
border-radius: 3px;
color: #666;
}
/* ── SVG tree nodes ───────────────────────────── */
.tr-edge {
stroke: #bbb;
stroke-width: 1.5;
fill: none;
transition: stroke 0.25s;
}
.tr-node circle {
fill: #fff;
stroke: #555;
stroke-width: 2;
transition: fill 0.25s, stroke 0.25s;
}
.tr-node text {
font-family: 'SF Mono', 'Fira Code', 'Consolas', monospace;
font-size: 13px;
fill: #333;
text-anchor: middle;
dominant-baseline: central;
pointer-events: none;
}
/* States */
.tr-node.visiting circle {
fill: #dbeafe;
stroke: #3b82f6;
stroke-width: 2.5;
}
.tr-node.matched circle {
fill: #fef3c7;
stroke: #f59e0b;
stroke-width: 2.5;
}
.tr-node.rewritten circle {
fill: #d1fae5;
stroke: #10b981;
stroke-width: 2.5;
}
.tr-node.done circle {
fill: #ede9fe;
stroke: #8b5cf6;
stroke-width: 2;
}
/* ── Color legend (inline) ────────────────────── */
.tr-legend {
display: flex;
gap: 14px;
font-size: 11px;
color: #888;
margin-top: 8px;
}
.tr-legend-dot {
display: inline-block;
width: 10px;
height: 10px;
border-radius: 50%;
margin-right: 4px;
vertical-align: middle;
}
.tr-legend-dot.c-visit { background: #dbeafe; border: 1.5px solid #3b82f6; }
.tr-legend-dot.c-match { background: #fef3c7; border: 1.5px solid #f59e0b; }
.tr-legend-dot.c-rewrite { background: #d1fae5; border: 1.5px solid #10b981; }
.tr-legend-dot.c-done { background: #ede9fe; border: 1.5px solid #8b5cf6; }
"use strict";(()=>{function y(e){return!Array.isArray(e)}function H(e){return Array.isArray(e)?e[0]:e}function I(e,t){return y(e)&&y(t)?e===t:y(e)||y(t)||e.length!==t.length?!1:e.every((n,r)=>I(n,t[r]))}function v(e){return y(e)?e:e.map(v)}function R(e){return y(e)?String(e):"("+e.map(R).join(" ")+")"}function T(e){return typeof e=="number"}function k(e,t){if(e===t)return!1;if(y(e))return!0;for(let n=1;n<e.length;n++)if(!k(e[n],t))return!1;return!0}function B(e,t){let n=[],r=0;function s(u){let f=r++;if(y(u))return n.push({nodeIdx:f,type:"visit",label:String(u)}),u;let c=[u[0]];for(let a=1;a<u.length;a++)c.push(s(u[a]));n.push({nodeIdx:f,type:"visit",label:String(c[0])});for(let a of t)if(a.match(c))return n.push({nodeIdx:f,type:"match",label:a.name,rule:a.name}),a.apply(c);return c}return{result:s(e),events:n}}function O(e,t,n=50){let r=[];for(let s=0;s<n;s++){let{result:p,events:u}=B(e,t);if(r.push({before:v(e),after:v(p),events:u}),I(p,e))break;e=v(p)}return r}function F(e,t,n){let r=[],s=[],p=0;function u(o){let d=p++;if(y(o))return{width:1,tree:o,id:d,label:String(o),children:[]};let h=[];for(let b=1;b<o.length;b++)h.push(u(o[b]));let E=h.reduce((b,l)=>b+l.width,0);return{width:Math.max(E,1),tree:o,id:d,label:String(H(o)),children:h}}function f(o,d,h,E){let b=d+h/2,l={id:o.id,x:b,y:E,label:o.label};if(r.push(l),o.children.length>0){let w=o.children.reduce((S,A)=>S+A.width,0),x=d;for(let S of o.children){let A=S.width/w*h,P=f(S,x,A,E+60);s.push({from:l,to:P}),x+=A}}return l}let c=u(e),a=40;return f(c,a,t-a*2,36),{nodes:r,edges:s}}var C="http://www.w3.org/2000/svg";function j(e){for(;e.firstChild;)e.removeChild(e.firstChild)}function q(e,t){j(e);for(let r of t.edges){let s=document.createElementNS(C,"line");s.setAttribute("x1",String(r.from.x)),s.setAttribute("y1",String(r.from.y)),s.setAttribute("x2",String(r.to.x)),s.setAttribute("y2",String(r.to.y)),s.setAttribute("class","tr-edge"),e.appendChild(s)}for(let r of t.nodes){let s=document.createElementNS(C,"g");s.setAttribute("class","tr-node"),s.setAttribute("transform",translate(${r.x},${r.y})),s.dataset.nid=String(r.id);let p=Math.max(16,r.label.length*5+8),u=document.createElementNS(C,"circle");u.setAttribute("r",String(p)),s.appendChild(u);let f=document.createElementNS(C,"text");f.textContent=r.label,s.appendChild(f),e.appendChild(s)}let n=t.nodes.reduce((r,s)=>Math.max(r,s.y),0);e.setAttribute("height",String(n+56))}function M(e,t,n){let r=e.querySelector(g[data-nid="${t}"]);r&&r.setAttribute("class","tr-node"+(n?" "+n:""))}function X(e){e.querySelectorAll("g.tr-node").forEach(t=>t.setAttribute("class","tr-node"))}function i(e,t,n){return{name:e,match:t,apply:n}}function m(e,t){return Array.isArray(e)&&e[0]===t&&e.length===3}var N=[i("0 + x \u2192 x",e=>m(e,"+")&&e[1]===0,e=>e[2]),i("x + 0 \u2192 x",e=>m(e,"+")&&e[2]===0,e=>e[1]),i("0 \xD7 x \u2192 0",e=>m(e,"")&&e[1]===0,()=>0),i("x \xD7 0 \u2192 0",e=>m(e,"")&&e[2]===0,()=>0),i("1 \xD7 x \u2192 x",e=>m(e,"")&&e[1]===1,e=>e[2]),i("x \xD7 1 \u2192 x",e=>m(e,"")&&e[2]===1,e=>e[1]),i("x \u2212 x \u2192 0",e=>m(e,"-")&&I(e[1],e[2]),()=>0),i("n + m",e=>m(e,"+")&&T(e[1])&&T(e[2]),e=>e[1]+e[2]),i("n \xD7 m",e=>m(e,"")&&T(e[1])&&T(e[2]),e=>e[1]*e[2]),i("n \u2212 m",e=>m(e,"-")&&T(e[1])&&T(e[2]),e=>e[1]-e[2]),i("n / m",e=>m(e,"/")&&T(e[1])&&T(e[2])&&e[2]!==0,e=>{let t=e[1]/e[2];return Number.isInteger(t)?t:Math.round(t*1e3)/1e3})],U=[...N,i("x^0 \u2192 1",e=>m(e,"^")&&e[2]===0,()=>1),i("x^1 \u2192 x",e=>m(e,"^")&&e[2]===1,e=>e[1]),i("x/1 \u2192 x",e=>m(e,"/")&&e[2]===1,e=>e[1]),i("0 \u2212 n \u2192 \u2212n",e=>m(e,"-")&&e[1]===0&&T(e[2]),e=>-e[2])];function V(e){return Array.isArray(e)&&e[0]==="d"&&e.length===3}function g(e,t){return V(e)&&Array.isArray(e[1])&&e[1][0]===t}function D(e,t){return g(e,t)&&e[1][1]==="x"&&e[2]==="x"}var Y=[i("d/dx(const) = 0",e=>V(e)&&e[2]==="x"&&k(e[1],"x"),()=>0),i("d/dx(x) = 1",e=>V(e)&&e[1]==="x"&&e[2]==="x",()=>1),i("sum rule",e=>g(e,"+"),e=>{let[,[,t,n],r]=e;return["+",["d",t,r],["d",n,r]]}),i("difference rule",e=>g(e,"-")&&e[1].length===3,e=>{let[,[,t,n],r]=e;return["-",["d",t,r],["d",n,r]]}),i("product rule",e=>g(e,""),e=>{let[,[,t,n],r]=e;return["+",["",t,["d",n,r]],["",n,["d",t,r]]]}),i("power rule",e=>g(e,"^")&&e[1][1]==="x"&&T(e[1][2])&&e[2]==="x",e=>{let t=e[1][2];return["",t,["^","x",t-1]]}),i("chain (power)",e=>g(e,"^")&&T(e[1][2]),e=>{let[,[,t,n],r]=e;return["",["",n,["^",t,n-1]],["d",t,r]]}),i("d/dx sin(x) = cos(x)",e=>D(e,"sin"),()=>["cos","x"]),i("chain (sin)",e=>g(e,"sin"),e=>{let[,[,t],n]=e;return["",["cos",t],["d",t,n]]}),i("d/dx cos(x) = \u2212sin(x)",e=>D(e,"cos"),()=>["-",0,["sin","x"]]),i("chain (cos)",e=>g(e,"cos"),e=>{let[,[,t],n]=e;return["",["-",0,["sin",t]],["d",t,n]]}),i("d/dx e^x = e^x",e=>D(e,"exp"),()=>["exp","x"]),i("chain (exp)",e=>g(e,"exp"),e=>{let[,[,t],n]=e;return["",["exp",t],["d",t,n]]}),i("d/dx ln(x) = 1/x",e=>D(e,"ln"),()=>["/",1,"x"]),i("quotient rule",e=>g(e,"/"),e=>{let[,[,t,n],r]=e;return["/",["-",["",n,["d",t,r]],["",t,["d",n,r]]],["^",n,2]]})],W=[...Y,...U];var z={"add-zero":{tree:["+",0,["+",0,"x"]],rules:[N[0]]},"const-fold":{tree:["+",["",2,3],["",4,5]]},nested:{tree:["",["+","x",0],["-",5,5]]}},J={ex1:{tree:["+",["",2,3],["",4,5]]},ex2:{tree:["",["+","x",0],["-",5,5]]},ex3:{tree:["+",["+",0,"x"],["-","y","y"]]},ex4:{tree:["/",["",3,["+",2,4]],["-",9,3]]}},K={power:{tree:["d",["^","x",3],"x"]},product:{tree:["d",["",["^","x",2],["sin","x"]],"x"]},chain:{tree:["d",["sin",["^","x",2]],"x"]},"exp-chain":{tree:["d",["exp",["^","x",2]],"x"]},quotient:{tree:["d",["/",["sin","x"],"x"],"x"]}};function L(e){return document.getElementById(e)}function (e,t,n){let r=L(e+"-svg"),s=L(e+"-info"),p=L(e+"-example"),u=L(e+"-reset"),f=L(e+"-step"),c=L(e+"-play"),a=L(e+"-iter");if(!r||!p||!s||!u||!f||!c)return;let o=null,d=null;function h(){d&&(clearInterval(d),d=null);let l=t[p.value],w=l.rules??n,x=v(l.tree),S=O(x,w),A=r.parentElement?.clientWidth??600,P=parseInt(r.getAttribute("height")??"300"),G=F(x,A,P);o={iterations:S,iterIdx:0,evtIdx:0,tree:v(x),layout:G},q(r,G),s.textContent="Press Step or Play.",a&&(a.textContent=""),f.removeAttribute("disabled"),c.removeAttribute("disabled"),c.textContent="Play"}function E(){if(!o)return;let l=o.iterations[o.iterIdx];if(!l){b();return}let w=l.events;if(o.evtIdx<w.length){let x=w[o.evtIdx];X(r),x.nodeIdx<o.layout.nodes.length&&M(r,x.nodeIdx,x.type==="match"?"matched":"visiting"),s.textContent=x.type==="visit"?Visiting ${x.label}:\u2192 ${x.rule},o.evtIdx++}else if(I(l.before,l.after))b();else{o.tree=v(l.after),o.iterIdx++,o.evtIdx=0;let x=r.parentElement?.clientWidth??600,S=parseInt(r.getAttribute("height")??"300");o.layout=F(o.tree,x,S),q(r,o.layout);for(let A of o.layout.nodes)M(r,A.id,"rewritten");s.textContent=R(o.tree),a&&(a.textContent=Iteration ${o.iterIdx})}}function b(){if(o){for(let l of o.layout.nodes)M(r,l.id,"done");s.textContent="Done: "+R(o.tree),a&&(a.textContent=${o.iterIdx} iteration(s)),f.setAttribute("disabled",""),c.setAttribute("disabled",""),d&&(clearInterval(d),d=null)}}p.addEventListener("change",h),u.addEventListener("click",h),f.addEventListener("click",E),c.addEventListener("click",()=>{d?(clearInterval(d),d=null,c.textContent="Play"):(d=setInterval(E,450),c.textContent="Pause")}),h()}function $(){("bu",z,N),("ar",J,N),("df",K,W)}document.readyState==="loading"?document.addEventListener("DOMContentLoaded",$):$();})();
Top comments (0)