Compilation

Lesson 21 lowered the evaluator onto real hardware — pairs in finite vectors, a garbage collector, and the eval/apply cycle running as a controller that saves exactly the registers it needs. And it exposed the last waste: to run a loop a thousand times, that machine re-examines the same fixed syntax, re-takes the same branches, and re-walks the same environment frames a thousand times over. This is the capstone. We stop interpreting. Instead of traversing an expression's syntax every time it runs, a compiler traverses it once, ahead of time, and emits a sequence of register-machine instructions that, when run, produce the same value — with all the dispatching already decided. We will build that compiler, see how it computes register saves at compile time and resolves variables by their lexical position, and then close the entire 22-lesson loop: what survives unchanged from the substitution model of lesson 01, and what gets precomputed away.

1 · The thesis: do the dispatch once

The explicit-control evaluator of lesson 21 is a single fixed machine that, fed any expression, walks its syntax at run time: eval-dispatch tests "is this a literal? a name? a conditional? an application?" on every visit. For a loop body that runs a thousand times, that test is taken a thousand times — yet the answer never changes, because the program text never changes. Lesson 15's analyzing evaluator made the first cut: split the analysis (done once) from the execution (done many times), returning an execution function. Compilation is the same idea taken to the metal. Where the analyzer returned a JavaScript closure, the compiler returns register-machine instructions — concrete assign, save, restore, branch, goto — specialized to this exact expression. The dispatch happened at compile time and left no trace in the running code.

2 · An instruction sequence as a value: needs and modifies

The compiler is a function compile(exp, target, linkage) returning an instruction sequence: a list of register-machine instructions, but annotated with two register sets that let sequences be combined safely. target is the register where the value should land; linkage is where to go when done (§5).

// an instruction sequence is a value: which regs it reads, writes, and its instructions
const seq = (needs, modifies, statements) => ({ needs, modifies, statements });
const EMPTY = seq([], [], []);

// append two sequences whose register interactions are already safe
function appendSeqs(a, b) {
  return seq(
    union(a.needs, difference(b.needs, a.modifies)), // b needs what a didn't already set
    union(a.modifies, b.modifies),
    [...a.statements, ...b.statements]);
}

The needs/modifies annotation is the whole reason a compiler can decide save/restore without running the program — it is a static summary of the dynamic register effects that the lesson-21 evaluator only discovered at run time.

3 · Compiling the easy cases: literals, names, returns

The simplest expressions compile to a single assign. A self-evaluating literal just loads its constant into the target; a name loads the result of looking it up. Both then attach the linkage code that sends control onward (§5).

// 42  -->  put the constant 42 into the target register
function compileLiteral(exp, target, linkage) {
  return endWithLinkage(linkage,
    seq([], [target], [["assign", target, ["const", exp]]]));
}
// x   -->  look up x in env, put result in target
function compileName(exp, target, linkage) {
  return endWithLinkage(linkage,
    seq(["env"], [target],                       // reads env, writes target
        [["assign", target, ["lookup", exp, ["reg", "env"]]]]));
}

Notice compileName declares needs = ["env"]: it cannot run until env holds the right environment. That single annotation is what will let the compiler protect env across a subexpression that would otherwise overwrite it.

4 · Compiling an application — and preservation, computed at compile time

An application f(a, b) is the hard, central case, and it is where the lesson-21 stack discipline reappears — but moved from run time to compile time. To run it the machine must: evaluate f into fun; evaluate a and b into argl; then apply. The danger is the same one the explicit-control evaluator faced: evaluating the arguments uses and overwrites env and fun, but the operator needs env and the apply step needs fun. In lesson 21 the controller blindly saved those registers every run. The compiler does better: it asks, statically, does the argument code actually modify a register the later code needs? — and emits a save/restore pair only if so. This is register preservation.

// wrap `seq` so that `reg` is preserved across it ONLY if seq modifies it
// and the surrounding code needs it. The decision is made now, at compile time.
function preserving(regs, before, after) {
  if (regs.length === 0) return appendSeqs(before, after);
  const r = regs[0], rest = regs.slice(1);
  const mustSave = before.modifies.includes(r) && after.needs.includes(r);
  if (mustSave) {
    return preserving(rest,
      seq(union(before.needs, [r]), difference(before.modifies, [r]),
          [["save", r], ...before.statements, ["restore", r]]),
      after);
  }
  return preserving(rest, before, after);   // no clash -> emit NO save/restore
}

compile  f(x)   target=val   linkage=next

  ; operator f -- needs env, modifies fun
  assign fun  <- lookup(f, env)

  ; PRESERVE env across the operand code, because:
  ;   operand code MODIFIES env? no (just a lookup) ... and fun across operands?
  ;   operand 'x' is a name: needs env, modifies argl -- it does NOT modify fun,
  ;   so the compiler emits NO save/restore around fun. Contrast lesson 21,
  ;   which saved fun unconditionally on every single call.
  assign argl <- list(lookup(x, env))

  ; apply: branch on primitive vs compound (decided here once)
  test    primitive?(fun)
  branch  prim-branch
compiled-branch:
  assign val <- compound-apply(fun, argl)   ; (set up env, jump to body)
  goto    (after-call)
prim-branch:
  assign val <- apply-primitive(fun, argl)
after-call:

5 · Linkage: where a compiled fragment goes when it is done

Every compiled sequence must end by transferring control somewhere. The linkage descriptor says where, and there are exactly three kinds:

Linkage is the compile-time counterpart of the continue register the explicit-control evaluator managed at run time. A function body compiled with "return" linkage ends in goto (reg continue) — and because that is a tail position with nothing left to do, a tail call compiles to a plain goto with no stack growth, exactly mirroring lesson 21's constant-space tail recursion, now baked into the emitted code rather than discovered each run.

6 · Lexical addressing — the payoff that beats the interpreter

Here is the sharpest win, and the one that most directly answers lesson 21's complaint. In the explicit-control evaluator, lookup(x, env) searches the environment at run time: scan the current frame's names for x; if absent, follow the parent link and scan that frame; repeat. For a variable bound three frames out, that is three frame scans every single time the variable is read — pure re-derivation of something the program text fixes once and for all.

But the compiler knows the lexical structure — the nesting of scopes — at compile time, because scope is a property of the text, not of any run. So it can resolve each variable to a lexical address: a (frame-number, position-in-frame) pair telling exactly where the value will sit. The emitted code skips straight there — follow N parent links, take the Mth slot — with no name comparisons at all.

function outer(a, b) {        // frame depth 1: { a:0, b:1 }
  function inner(c) {         // frame depth 0 (innermost): { c:0 }
    return a + c;             // a is 1 frame out, position 0; c is here, position 0
  }
  return inner;
}

INTERPRETED (lesson 21) lookup of `a` inside inner, every call:
  scan inner's frame {c}   -- not found
  follow parent link
  scan outer's frame {a,b} -- found at position 0  -> return it
  (two frame scans + name comparisons, REPEATED on every read of `a`)

COMPILED: `a` resolves at COMPILE TIME to lexical address (1, 0):
  assign val <- lexical-ref(env, frame=1, pos=0)   ; follow 1 parent, take slot 0
  (zero name comparisons; the search was done ONCE by the compiler)

7 · Interoperating with the evaluator

Compiled code and the explicit-control evaluator are not rivals; they share the same machine, the same registers, and the same calling convention (a function is applied via fun/argl, returns through continue). So a compiled function can call an interpreted one and vice versa: apply-dispatch simply checks whether a function is primitive, interpreted-compound, or compiled, and dispatches accordingly. This is why a real system can compile hot code while still interpreting freshly typed expressions at a REPL — they meet at the shared register-machine interface. The compiler did not invent a new semantics; it produced a faster encoding of the same one.

Common mistakes / failure modes

Checkpoint exercise

Where this points next — the whole arc

There is no next lesson; there is the synthesis. Twenty-two lessons were a single forcing-chain, and every link was a model breaking under a named pressure. We began in lesson 01 with the substitution model — to run a program, replace expressions with their values — valid only while functions stayed pure. Lesson 09's assignment detonated it: a call now depended on history, so substitution lied, and the environment model (10) replaced it. To make that model executable we wrote it as the metacircular evaluator (14), which re-traversed syntax on every run; so the analyzing evaluator (15) split analysis from execution. Owning the evaluator let us change the rules — lazy (16), nondeterministic (17), logic (18) — but all of them silently borrowed the host's recursion and memory. To expose the true cost of control we descended to register machines (19), made them executable with a simulator (20), then made memory finite with storage and garbage collection and lowered the evaluator into the explicit-control machine (21). That machine re-dispatched the same fixed syntax forever — and that final waste forced this lesson. Now stand back and see what the compiler does to the ladder. It preserves the semantics every model up the chain agreed on — the same value the substitution model would have computed for a pure expression, the same environment-model meaning for variables, the same eval/apply structure of lesson 14. It precomputes everything that depends only on the fixed program text: which syntactic branch applies (the dispatch of 14), the analysis done once (15), which registers must be saved (the save/restore of 21), and where each variable lives (lexical addressing). Semantics is what stays; analysis is what moves to compile time. That single distinction — preserve meaning, precompute structure — is the bottom of the ladder. Human-readable language has become machine code, and the whole journey from "replace an expression with its value" to "emit an instruction that follows one parent link and takes slot zero" is one unbroken argument that programming is the control of complexity through abstraction — including, at the very end, abstraction over evaluation itself.

Interview prompts

• How does a compiler differ from the explicit-control evaluator, and what does it eliminate? (§1 — the evaluator re-traverses and re-dispatches the fixed syntax on every run; the compiler traverses and dispatches once, ahead of time, and emits register-machine instructions, so each run only executes — the redundant dispatch is gone.)
• What does compile return, and what are needs and modifies? (§2 — an instruction sequence: its statements plus the set of registers it reads (needs) and the set it changes (modifies); the annotation lets sequences be combined safely without running them.)
• Explain register preservation and how it is computed. (§4 — wrap a register's save/restore around a subexpression only if the subexpression modifies that register AND the following code needs it; the clash is decided statically from needs/modifies, unlike the interpreter's unconditional save.)
• What are the three linkage kinds and what does each emit? (§5 — "next" emits nothing (fall through); "return" emits goto (reg continue); a label emits goto (label L); linkage is the compile-time form of the continue register, and return-linkage in tail position is a plain goto.)
• What is lexical addressing and why does it make compiled code faster? (§6 — resolving a variable to a (frame, position) address at compile time because scope is fixed by the text; the emitted code follows N parent links and takes a slot directly, replacing the interpreter's repeated run-time frame-by-frame name search.)
• How do compiled code and the evaluator interoperate? (§7 — they share the same machine, registers, and calling convention (fun/argl/continue); apply-dispatch checks whether a function is primitive, interpreted-compound, or compiled and dispatches, so each can call the other — same semantics, faster encoding.)
• Across the whole series, what does the compiler preserve versus precompute? (synthesis — it preserves the semantics every model agreed on (the value substitution/environment/eval-apply would compute) and precomputes everything fixed by the program text: syntactic dispatch, analysis, register saves, and variable addresses — preserve meaning, precompute structure.)