Storage allocation and the explicit-control evaluator

Lesson 20 built a working register-machine simulator — an assembler that turns controller text into executable instruction objects, with counters that finally let us measure the cost model of lesson 19. But the simulator still cheats in two places: it pretends memory is infinite (every pair() conjures a fresh cell forever) and it leans on JavaScript's own pairs and recursion to do the real work. This lesson removes both crutches. First we make memory finite: pairs live in fixed-size vectors, addressed by typed pointers, and reclaimed by a garbage collector. Then we lower the metacircular evaluator of lesson 14 all the way down into a register machine — the explicit-control evaluator — where eval and apply become controller labels, argument evaluation becomes a loop, and recursion runs on a stack we manage by hand, saving exactly the registers lesson 19 told us we must.

1 · The last lie: memory is not infinite

Through lessons 14–20 we built evaluators that allocate freely: pair(a, b) always succeeds, lists grow without bound, every function call gets a fresh environment frame. That convenience was borrowed from the host. A real machine has a fixed array of memory cells; when you ask for a new pair there must be a cell to give, and when you stop needing one it must be returned to the pool, or the pool empties and the machine halts. Lesson 19 made control explicit (an instruction stream, an explicit stack); this lesson makes storage explicit.

The unit of storage is a pointer: not a pair itself but the address of a pair, plus a type tag saying what kind of thing lives there. A pair occupies one slot of two parallel vectors — its head in one, its tail in the other — and the pointer is just the shared index. Everything you thought of as "a list" is, underneath, a chain of indices threading through two arrays.

2 · Pairs in two vectors, addressed by typed pointers

Here is the heap model directly. A pointer is a tagged record; the heap is two arrays of the same length; pair writes the head and tail into the next free slot and returns a pointer to it.

// a pointer is a tag + address into the heap vectors
const ptr = (type, addr) => ({ type, addr });   // type: "p" pair, "n" number, "e" empty
const NIL = ptr("e", 0);

const SIZE = 8;                 // FINITE memory: only 8 pair slots
const theCars = new Array(SIZE);
const theCdrs = new Array(SIZE);
let free = 0;                   // the "free pointer": next slot to hand out

function consPair(h, t) {       // allocate one pair
  if (free >= SIZE) gc();       // out of room? reclaim first (see §4)
  const a = free++;
  theCars[a] = h;               // store the head pointer
  theCdrs[a] = t;               // store the tail pointer
  return ptr("p", a);           // return a typed pointer to the new pair
}
const head = (p) => theCars[p.addr];   // dereference: index into theCars
const tail = (p) => theCdrs[p.addr];   //              index into theCdrs

The list [1, 2, 3] — really cons(1, cons(2, cons(3, nil))) — is now a layout in the vectors, not a tree of objects. Each slot's cdr is a pointer (an index) to the next slot:

consPair(n1, consPair(n2, consPair(n3, NIL)))  builds, innermost first:

index:        0          1          2        3..7
theCars:  [   3      |   2      |   1      |  --  ]   inline numbers
theCdrs:  [  e:0     |  p:0     |  p:1     |  --  ]   typed pointers
                |          |          |
              NIL      ->slot0     ->slot1
                                       ^
                              the list head = ptr("p", 2)

Reading the list:  start at p:2 -> car 1, cdr p:1
                                 -> car 2, cdr p:0
                                 -> car 3, cdr e:0 (NIL) -- stop.
free pointer now = 3 ; slots 3..7 still available.

3 · Allocation, and the day the free pointer hits the wall

Allocation is now a single increment: hand out free, then free++. Cheap — until free reaches SIZE. At that instant the machine has a choice: halt with "out of memory," or notice that most of those slots hold pairs nobody can reach anymore and reclaim them. The whole field of garbage collection exists to make the second choice automatic.

The key insight is a definition of "dead." A pair is live if the running computation could still reach it by following pointers starting from the machine's registers; it is garbage otherwise. The registers that anchor this search are the roots: the evaluator's working registers (the expression being evaluated, the current environment, the argument list, the value just produced) plus the explicit stack. Anything reachable from a root is live; everything else is unreachable forever — no future instruction can ever name it — so it is safe to reclaim. Liveness = reachability.

4 · Stop-and-copy garbage collection

Stop-and-copy is the cleanest collector to understand. Split the heap into two halves: from-space (where allocation currently happens) and an idle to-space. When from-space fills, stop the computation and walk the live data: copy every reachable pair from from-space into to-space, fixing up pointers as you go, then swap the roles of the two spaces. Garbage is never touched — you copy the living and abandon the dead in one sweep.

BEFORE gc  (from-space full; ? = unreachable garbage)
  roots: env -> p:1 , val -> p:4
  from:  [ ?:0 | (a, p:3) | ?:2 | (b, e) | (c, e) | ?:5 ... ]   FULL
                   live=1 -> 3            live=4

WALK from the roots, copying each live pair into to-space, compacting:
  copy p:1 -> to[0] ; its cdr p:3 -> to[1] ; copy p:4 -> to[2]
  leave a "forwarding pointer" in the old slot so shared structure
  is copied ONCE, not duplicated.

AFTER gc  (swap: to-space becomes the new from-space)
  to:    [ (a, p:1) | (b, e) | (c, e) | -- free from here -- ]
  roots updated:  env -> p:0 , val -> p:2
  free = 3 ; the 5 dead slots are reclaimed, the live data compacted.

5 · The explicit-control evaluator: eval/apply as a controller

Now the second crutch. The lesson-14 evaluator was a JavaScript function, evaluate(expr, env), that recursed by calling itself and let the host's call stack remember where it was. To lower it onto a register machine we must take all of that into the open: the recursion becomes explicit save/restore on the machine stack, and the dispatch on expression type becomes a controller — a graph of labels and branches in the register-machine language of lessons 19–20.

The evaluator runs over a handful of registers. There is no hidden state left; every "variable" the metacircular evaluator used is now a named register:

Control flows between two hubs. eval-dispatch looks at the syntactic type of exp and branches — a literal goes one way, a name another, a conditional another, an application another — exactly the data-directed syntax dispatch of lesson 14, now expressed as machine branches. apply-dispatch takes a fun and an argl and either runs a primitive or, for a compound function, builds a new frame and re-enters eval-dispatch on the body.

                 +-------------------- eval-dispatch (look at exp) --------------------+
   literal --------> assign val <- the literal ; go to (continue)
   name -----------> assign val <- lookup(exp, env) ; go to (continue)
   conditional ----> save continue ; eval the predicate ; on return test val,
                     then eval ONLY the chosen branch
   application ----> save continue ; eval the function expr into fun ;
                     then run the ARGUMENT LOOP to fill argl ; then apply-dispatch
                 +---------------------------------------------------------------------+
   apply-dispatch:  primitive?  -> assign val <- apply-primitive(fun, argl) ; go (continue)
                    compound?   -> env <- extend(fun.params, argl, fun.env)
                                    exp <- fun.body ; go to eval-dispatch  (TAIL position)

The argument-evaluation loop is where the host recursion was most hidden, so look closely. To evaluate f(a, b, c) the machine must evaluate a, then b, then c, accumulating results into argl — but evaluating each argument itself re-enters eval-dispatch, which clobbers exp, env, and uses the stack. So before evaluating each operand the loop saves the registers it will still need afterward (argl, the rest of unev, env) and restores them when that operand's evaluation returns. This is precisely the save/restore discipline lesson 19 derived for recursion, now driven by data.

6 · Recursion and tail calls on the explicit stack

The metacircular evaluator recursed for free; here recursion is the stack, made visible. Let us connect one eval step from lesson 14 to its register-machine save/restore sequence, as the brief demands. Take a conditional whose predicate is itself a call — the evaluator must remember "I still owe a branch evaluation" while it goes off to evaluate the predicate.

// lesson 14 — the host stack silently remembers `expr` and where to return
function evalCond(expr, env) {
  if (isTruthy(evaluate(predicate(expr), env)))   // <- nested call; host saves the rest
    return evaluate(consequent(expr), env);
  else
    return evaluate(alternative(expr), env);
}

ev-conditional:
  save  exp                 ; we will need the whole cond again to pick a branch
  save  env                 ; the predicate must run in THIS env
  save  continue            ; remember where the whole conditional returns to
  assign continue <- after-pred   ; predicate should return here, not to the caller
  assign exp <- predicate(exp)
  go to eval-dispatch       ; recurse: evaluate the predicate

after-pred:                 ; the predicate's value is now in val
  restore continue          ; bring back the caller's return label
  restore env               ; bring back the conditional's environment
  restore exp               ; bring back the whole conditional
  test  val                 ; truthy?
  branch  ev-consequent ; else fall through to ev-alternative
ev-alternative:
  assign exp <- alternative(exp) ; go to eval-dispatch
ev-consequent:
  assign exp <- consequent(exp)  ; go to eval-dispatch

The same machinery makes a deep idea fall out for free: tail-call iteration uses constant stack. Notice in §5 that apply-dispatch evaluates a compound function's body by reassigning exp and env and jumping to eval-dispatch without first saving anything — because nothing remains to be done after the body returns; its value is the call's value. So a function whose last act is to call another (or itself) re-enters eval-dispatch with the stack at the same depth it started. A loop written as tail recursion runs in O(1) stack. This is not an optimization bolted on; it is a direct consequence of which registers the controller does and does not save, and it is the explicit-stack analogue of the iterative-process shape we first met all the way back in lesson 02.

Common mistakes / failure modes

Checkpoint exercise

Where this points next

We now have an evaluator that runs on real, finite hardware: pairs in vectors, a collector that reclaims the dead, and the eval/apply cycle realized as a controller that saves precisely the registers it must. But look at what this machine spends its time doing. To run a loop a thousand times, eval-dispatch examines the same expression's syntax type a thousand times, re-decides which branch of the controller applies a thousand times, re-walks the environment frames to resolve the same variable a thousand times. All of that work is a function of the program's text, which never changes between iterations — yet the interpreter re-derives it on every pass. Lesson 15 already showed the cure in miniature: analyze the syntax once. The explicit-control evaluator makes the waste concrete and total, because now we can count every redundant dispatch as machine instructions. The forcing function is exact: if all this dispatching depends only on the fixed program text, do it once, ahead of time, and emit the register-machine instructions directly — stop interpreting and start compiling. That is lesson 22, the capstone, where human-readable language finally becomes machine code.

Interview prompts

• How are pairs represented once memory is finite? (§2 — as typed pointers (an address into two parallel vectors theCars/theCdrs); head/tail are index lookups, a list is a chain of cdr-indices, and sharing/mutation fall out of aliased indices.)
• Define when a heap cell is garbage. (§3–4 — it is garbage iff it is unreachable by following pointers from any root (the working registers plus the explicit stack); liveness equals reachability, so unreachable cells can never be named by a future instruction.)
• Explain stop-and-copy garbage collection and why it beats reference counting. (§4 — split into from/to-space, copy live data reachable from roots into to-space (forwarding pointers keep shared structure single-copy), swap; it collects cyclic garbage that reference counting leaks, but pauses the machine and uses half the space.)
• What registers does the explicit-control evaluator use, and what did each replace? (§5 — exp/env (the evaluate arguments), val (the return value), continue (the host return address), fun/argl/unev (the locals of apply and the argument loop); no hidden state remains.)
• Why must the argument-evaluation loop save and restore registers? (§5 — evaluating each operand re-enters eval-dispatch, which clobbers exp/env and uses the stack, so the loop saves argl, the remaining operands, and env before each operand and restores them after — the lesson-19 save/restore discipline driven by data.)
• Why do tail calls run in constant stack space? (§6 — apply-dispatch evaluates a compound body by reassigning exp/env and jumping to eval-dispatch without saving, because nothing remains after the body; not saving in tail position is exactly what keeps the stack flat.)
• Trace how a conditional's evaluation becomes save/restore. (§6 — save exp/env/continue, set continue to a return label, eval the predicate via eval-dispatch, then restore, test val, and eval only the chosen branch — each implicit host return becomes an explicit save/restore plus a continue register.)