Write the program as a graph, not a tree: identical subexpressions become one shared node, reduced at most once and updated in place. That single trick — sharing plus in-place update — is the mechanism under every lazy functional language: let sq = 2+3 in sq*sq computes 2+3 a single time, where a tree would compute it twice.
THE TECHNIQUE share the node; reduce it once
sq * sq where sq = 2+3. As a tree, the two sq leaves are separate — 2+3 is evaluated twice. As a graph, both *-operands point at one2+3 node; reducing it once updates the shared node for both. Count the additions. live demo
HISTORY & CREDIT Wadsworth 1971, not Turner
“Turner invented graph reduction” — no; Wadsworth did (1971 thesis). Turner’s 1979 work is combinator graph reduction, standing on it. cited
1971 · Christopher Wadsworth — represent the term as a DAG so identical subterms are one shared node, reduced at most once via in-place update. The invention. 1976 · Henderson & Morris; Friedman & Wise — name and crystallise lazy evaluation as a strategy (“CONS should not evaluate its arguments”); infinite data structures become usable. 1979 / 1982 · David Turner — compile a lazy language to S,K,I,B,C combinators and reduce the combinator graph; Hughes replaces the fixed set with program-specific supercombinators + full laziness. 1984 / 1992 · Johnsson & Augustsson — the G-machine compiles the graph instead of interpreting it; Peyton Jones’s Spineless Tagless G-machine (GHC) — though GHC later re-added tags (2007) after measuring branch mispredicts.
Sharing is a mechanism, laziness a strategy; string reduction copies-and-re-reduces, graph reduction keeps one node — the efficiency lives in the difference. Wadsworth, 1971
RECOMMEND FOR I-13 a shared node = one evaluation, counted
Sharing shows as a lower reduction count — the same value, less work:
$ i13 run graph.i13 # sq*sq with sq = 2+3
tree reduction: sq computed TWICE -> result 25, 2 additions
graph reduction: sq shared, once -> result 25, 1 addition
Recommend:nothing new — a reduction that returns [value, count] threads the work count; the tree form evaluates 2+3 twice (2 adds), the graph form binds the shared node once and reuses it (1 add) — same result 25 (verified). The sharing is the value-semantic let binding: bind the sub-result once, use it twice. Note: a real reduction graph is a node arena with in-place update (PS-015) — and I-13’s value-semantic array update is the immutable form of exactly that (cf. the persistent segment tree, dart 124). It provides the sharing that turns the closureless combinators (dart 144) into a fast lazy language.