Background for chapter 01.
Graph reduction and laziness
lambda-calculus-and-ski.md and
bracket-abstraction.md get you to a combinator
term with no Var/Lam left. This doc is about the other half:
ccb31388:eval.c, the ~540-line C program that actually runs that term.
The central idea is that a term isn't a tree that gets copied around β it's
a graph of mutable cells, and reduction rewrites cells in place. That one
design choice is where sharing and laziness both come from.
1. A cell is a tag plus two pointers (or a value)
ccb31388:eval.c (lines 23β33):
typedef struct node {
enum node_mark mark;
enum node_tag tag;
union {
value_t value;
struct {
struct node *fun;
struct node *arg;
} s;
} u;
} node;
and the tag enum (line 17):
enum node_tag { FREE, IND, AP, INT, S, K, I, B, C, T, Y, SS, BB, CC, ADD, SUB, MUL, DIV, MOD, SUBR, EQ, NE, LT, LE, GT, GE };
Every node in the heap is one of these. An AP node is a function
application: its fun/arg union fields (accessed via the FUN/ARG
macros) point at two other cells. A combinator like S or K is a node
that carries no payload at all β the tag alone is the value. INT nodes
use the value field instead of fun/arg. The whole compiled program is
one big tree of AP cells with combinator/INT/prim leaves β but as
section 3 shows, "tree" stops being accurate the moment reduction starts,
because cells get reused and cross-linked.
2. The spine stack and the S rewrite
eval's job is to find the leftmost-outermost redex. It does this by
walking down the left spine of applications β FUN, FUN, FUN, ... β
pushing every node it passes onto an explicit stack, until it hits
something that isn't an AP. The stack macros (ccb31388:eval.c, lines
99β101):
#define PUSH(x) stack[++stack_ptr] = (x)
#define TOP(n) stack[stack_ptr - (n)]
#define POP(n) stack_ptr -= (n)
and the loop that uses them (lines 364β377, the AP unwinding step only):
PUSH(n);
for(;;) {
num_reductions++;
switch (TAG(n)) {
ind:
case IND:
n = INDIR(n);
TOP(0) = n;
break;
ap:
case AP:
n = FUN(n);
PUSH(n);
break;
TOP(0) is the innermost node just found, TOP(1) the one one level out,
and so on β after unwinding k applications, TOP(k) is the outermost
node, the root of the redex. Once the switch lands on a combinator tag with
enough arguments pushed above it, it reads the arguments off the stack via
TOP/ARG and rewrites. Here is case S in full (lines 380β391):
case S:
CHECK(3);
GCCHECK(2);
f = ARG(TOP(1));
g = ARG(TOP(2));
x = ARG(TOP(3));
POP(3);
n = TOP(0);
FUN(n) = new_ap(f, x);
ARG(n) = new_ap(g, x);
GOTO ap;
break;
CHECK(3) bails out (returns without reducing) if fewer than three
arguments are on the stack β S is only a redex when fully applied.
Otherwise f, g, x are read off the spine, the three intermediate
nodes are popped, and n = TOP(0) recovers the outermost node of the
redex β the original ((S f) g) x application cell. That cell's FUN/
ARG fields are then overwritten to new_ap(f, x) and new_ap(g, x):
the node is turned, in place, into f x (g x), exactly the S rule from
lambda-calculus-and-ski.md. GOTO ap
restarts unwinding from this now-rewritten node β section 3 traces what
happens next.
3. Sharing: x is fetched once, not copied
Look again at case S: x = ARG(TOP(3)) reads one pointer, and that
same pointer value is used in both new_ap(f, x) and new_ap(g, x). The
two x-occurrences in f x (g x) are not two copies of a subterm β they
are two AP cells whose arg field happens to point at the identical
heap cell. That is the whole mechanism of sharing in one line of C.
Take the smallest term that exercises it, S f g x itself, as
(((S +) I) ((+ 2) 3)) β i.e. + x (I x) with x = 2 + 3. Before the
S-reduction, the term is three stacked AP cells (call them n_c, the
outermost, applied last) over a leaf S, plus the separate subgraph X
for ((+ 2) 3):
n_c ββfunβββΆ n_b ββfunβββΆ n_a ββfunβββΆ [S]
β β βββargβββΆ [+]
β βββargβββΆ [I]
βββargβββΆ X where X = AP(AP(+, 2), 3)
Tracing case S against this graph exactly as in section 2: f = ARG(n_a) = +, g = ARG(n_b) = I, x = ARG(n_c) = X, then n = TOP(0) = n_c β the
outermost cell, reused as the answer. After the rewrite:
n_c ββfunβββΆ n_d = AP(+, X)
βββargβββΆ n_e = AP(I, X)
β
both n_d.arg and n_e.arg point at the SAME cell X
n_c itself was never freed and reallocated β its fun/arg fields were
just overwritten, so any other pointer into n_c anywhere in the graph
sees the rewritten form for free. And n_d/n_e both point at the one
X cell, not at two copies of ((+ 2) 3).
Now the payoff. Unwinding restarts from n_c and lands on the ADD
prim, whose ARITH2 macro (line 476) forces both operands:
r = evalint(ARG(TOP(1))) op evalint(ARG(TOP(2))); with op = + β
here ARG(TOP(1)) = X and ARG(TOP(2)) = n_e = AP(I, X). One honest
caveat: C does not specify the evaluation order of +'s operands, so
which of the two evalint calls runs first is the compiler's choice β
and the sharing conclusion doesn't depend on it. Both operands lead to
the same cell X: the first directly, the second through n_e, which
case I turns into an indirection to X (section 4). Whichever side is
forced first fully reduces X β the inner addition's SETINT(n, r)
(line 475) overwrites X's own tag/value fields to INT 5, in place.
When the other side is then forced, it arrives at that same cell β
directly, or via evali's while (TAG(n) == IND) loop (lines 335β336)
through n_e's indirection β and finds tag INT already there: it
returns immediately, no re-addition. In either order, 2 + 3 runs
exactly once; the second consumer just follows a pointer to a cell
someone else already finished computing.
Verified by running the actual term (shared2.comb, the same idea with
a 20-deep addition chain in place of 2 + 3 to make the effect large
enough to see in the reduction counter, appears below). The small case:
$ ./eval shared.comb # (((S +) I) ((+ 2) 3))
(((S +) I) ((+ 2) 3))
10
node size=24, heap size=100000
16 reductions, 0 GCs
$ ./eval duplicated.comb # ((+ ((+ 2) 3)) ((+ 2) 3)) -- two independent copies of (+ 2 3)
((+ ((+ 2) 3)) ((+ 2) 3))
10
node size=24, heap size=100000
13 reductions, 0 GCs
Both give 10, as they must. But the shared version does more
reductions here (16 vs 13) β for a two-step addition, the constant
overhead of the extra S and I rewrites outweighs the one addition it
saves. Sharing isn't free; it costs an indirection and an extra
application node. To see sharing actually win, the shared subterm has to
be expensive enough that recomputing it costs more than the S/I
overhead. Replacing 2 + 3 with a 20-deep nested addition
(((...((+ 1) 1)...) 1), still x + x via the same S + I shape) makes
the saving obvious:
$ ./eval shared2.comb
42
node size=24, heap size=100000
92 reductions, 0 GCs
$ ./eval dup2.comb # x + x with x written out twice (no sharing)
42
node size=24, heap size=100000
165 reductions, 0 GCs
Same answer, 92 vs 165 reductions β the duplicated version pays for the 20-deep chain twice; the shared version pays once. That is "evaluate once," measured, not asserted.
4. Indirection nodes: yes, they exist at commit 1
It would be easy to guess that the first commit's evaluator is too crude
for indirection nodes β it is not. IND is tag 1 in the enum quoted in
section 1, and it is created and followed in several places.
Creation, via the SETIND macro (line 361):
#define SETIND(n, x) do { TAG((n)) = IND; INDIR((n)) = (x); } while(0)
used by case K, case T, case I (the identity rewrites β each turns
its redex cell into a pointer to its result rather than copying the
result in), and by the comparison primitives, whose shared macro (line
496) sets the result cell to indirect to the boolean combinators T/K:
#define CMP(op) do { CHECK(2); r = evalint(ARG(TOP(1))) op evalint(ARG(TOP(2))); n = TOP(2); SETIND(n, r ? combT : combK); POP(2); } while(0)
case I itself (lines 421β428):
case I:
CHECK(1);
x = ARG(TOP(1));
POP(1);
n = TOP(0);
SETIND(n, x);
GOTO ind;
break;
β I x doesn't allocate a fresh copy of x; it turns the I x
application cell itself into an indirection to x. This is the same
in-place-update trick as S (section 3), specialized to the case where
the "new graph" is just the existing argument.
Following happens in three places: inside eval's own loop (case IND,
quoted in section 2, n = INDIR(n); TOP(0) = n;), in evali (lines
327β338, while (TAG(n) == IND) n = INDIR(n); after eval returns β this
is what callers use to get a "real" answer, never an indirection cell),
and inside the garbage collector's mark (next section) β which also
compresses indirection chains as a side effect, rewriting the root
pointer past them (lines 165β171):
if (TAG(n) == IND) {
/* Skip indirections, and redirect start pointer */
while (TAG(n) == IND) {
n = INDIR(n);
}
*np = n;
}
5. Memory: allocation and a real mark-and-scan GC
Cells come from one fixed-size array, allocated once (lines 11, 46):
#define HEAP_CELLS 100000
#define ALLOC_HEAP(n) do { cells = malloc(n * sizeof(node)); memset(cells, 0x55, n * sizeof(node)); } while(0)
100,000 cells, malloc'd up front and never grown β there's no free()
of individual cells anywhere in the file; the only way a cell becomes
available again is via the collector. alloc_node (lines 108β120) just
pops the head of a free list:
NODEPTR
alloc_node(enum node_tag t)
{
NODEPTR n = next_free;
if (n == NIL) {
ERR("out of memory");
}
if (TAG(n) != FREE)
abort();
next_free = NEXT(n);
TAG(n) = t;
return n;
}
And commit 1 genuinely does have a collector β mark-and-scan, called
before allocation-heavy reductions via GCCHECK (e.g. case S, section
2: GCCHECK(2) before its two new_ap calls). gc_check only actually
collects if the free list looks short (lines 212β222); gc, mark, and
scan (lines 158β210) are a textbook stop-the-world mark/sweep: mark
walks from every live root β every cell currently on stack[0..stack_ptr]
β marking AP spines recursively (and compressing IND chains as shown
above); scan then does one linear pass over the whole heap, threading
every unmarked cell onto the free list and clearing marks on the rest
(lines 198β210, three commented-out fprintf debug lines elided, marked
...):
void
gc(void)
{
num_gc++;
num_marked = 0;
// ...
for (int i = 0; i <= stack_ptr; i++)
mark(&stack[i]);
// ...
scan();
// ...
}
This is exercised for real, not just present in principle: running
nfib 35 (see y-combinator-and-recursion.md)
reports 1944 GCs over a billion-odd reductions.
What commit 1 does not have: no compaction or copying (cells never
move β scan only relinks the free list, it doesn't shrink or defragment
the heap array), no generations, no reference counting, and no growable
heap (out of memory in alloc_node is a hard ERR/exit, not a
request for more memory). The NODE_SPLIT and NODE_64 representations
sketched in the #elif branches at the top of the file are unused
alternatives β NODE_NAIVE (line 9: #define NODE_NAIVE) is the one
#defined and compiled; struct node in section 1 is its representation.
6. Laziness falls out of this, it isn't added on top
Nothing above ever evaluates an argument before it's asked for. case S
builds new_ap(f, x) and new_ap(g, x) and immediately GOTO aps back
into the left spine β it never inspects x. x only gets forced when
some later reduction step needs it as an INT (via evalint, e.g. inside
ARITH2, line 476) or needs to pattern-match its outermost tag. An
argument that's never demanded is simply never touched β it stays an
unevaluated AP/combinator subgraph forever, at zero cost beyond the
memory it occupies. Combine that with section 3's sharing and you get
call-by-need for free: an argument is a graph, evaluated at most once,
exactly when (and if) something forces it.
Next: y-combinator-and-recursion.md β the same in-place-update trick, applied to build a genuinely cyclic graph for recursion.