Designing register machines

Through eighteen lessons every evaluator we built — metacircular, analyzing, lazy, nondeterministic, the logic engine — quietly borrowed three things from the host language: recursion, memory, and dispatch. When evaluate called itself to evaluate a subexpression, JavaScript's own call stack remembered where to resume. That was a loan, and the loan hid the true cost of control. This lesson stops borrowing. We describe computation as a register machine: a fixed set of registers, a set of primitive operations, tests and branches, labels, and — the part the host used to give us for free — an explicit stack we must push and pop by hand. The headline: recursion needs an explicit stack, because the stack you leaned on for eighteen lessons is now your own responsibility.

1 · The register-machine model

A register machine computes by repeatedly altering the contents of a fixed collection of named storage cells. The pieces are deliberately few:

That is the entire vocabulary. No function calls, no local variables, no implicit return path. Everything richer — recursion, subroutines, an evaluator — must be built from these atoms. This is the bottom of the abstraction ladder we have been descending: a model close enough to real hardware that nothing is free.

2 · The data-path / controller split

A register machine has two halves, and keeping them separate is the central design discipline. The data paths are the registers and the operation/test boxes wired between them — what can be computed and where values can flow. The controller is the sequence of instructions that decides when each operation fires and which branch is taken — the order of events in time. Data paths answer "what is possible"; the controller answers "what happens, and when."

       DATA PATHS (structure: what can flow where)
   +-----+        +---------+        +-----+
   |  a  |---+--->|  op: -  |------->|  t  |
   +-----+   |    +---------+        +-----+
   +-----+   +--->|  test:= |--(flag)
   |  b  |------->+---------+

       CONTROLLER (behavior: when each box fires)
   loop:  test (op =) (reg b) (const 0)
          branch (label done)
          assign t (op rem) (reg a) (reg b)
          assign a (reg b)
          assign b (reg t)
          goto (label loop)
   done:

The same data paths can serve many controllers, and the split is exactly the procedure/process distinction from lesson 02 made physical: the data paths are the static definition of what the machine is capable of; the controller is the process — the unfolding in time. Everything below is just controllers over small data paths.

3 · The controller as JavaScript data

We will write controllers as a plain JavaScript array of instruction objects. Each instruction is a tagged record; labels are bare strings that mark positions. This is not decoration — making the controller data is exactly what lets lesson 20 feed it to an assembler. The instruction set:

Note save/restore and the stack they touch. That stack is the new burden. For the next machine we will not need it at all — and seeing exactly why is the whole point.

4 · Iterative gcd — a machine with no stack

Euclid's algorithm from lesson 02 is a linear iterative process: its entire state lives in two registers, and each step overwrites them. Nothing needs to be remembered for later, so the machine needs no stack.

// gcd(a, b): keep replacing (a, b) with (b, a mod b) until b == 0.
const gcdMachine = [
  "gcd",
    { op:"test",   fn:"=",   args:[{reg:"b"}, {const:0}] },
    { op:"branch", label:"done" },
    { op:"assign", reg:"t", src:{ fn:"rem", args:[{reg:"a"}, {reg:"b"}] } },
    { op:"assign", reg:"a", src:{ reg:"b" } },
    { op:"assign", reg:"b", src:{ reg:"t" } },
    { op:"goto",   label:"gcd" },
  "done"
];

step   instruction          a     b     t    flag
init                        206   40    -     -
1      test b=0                                false
2      branch (not taken)
3      t = rem(a,b)         206   40    6
4-5    a=b, b=t              40    6     6
       goto gcd
6      test b=0                                false
       ...                  6     4     4
       ...                  4     2     2
       ...                  2     0     0
       test b=0                                true
       branch -> done       (a = 2 is the answer)

5 · Recursive factorial — the stack becomes mandatory

Now the contrast that defines the lesson. Recursive factorial — n! = n * (n-1)! — is a linear recursive process. To compute (n-1)! the machine must, for the moment, forget n and reuse the same n register for the subproblem; but it must get n back afterward to perform the pending multiplication. There is no second register to keep n in, because the subproblem is the same machine and wants the same registers. The pending multiplications are precisely the deferred-operation chain from lesson 02 — and that chain has to live somewhere. It lives on the stack.

// n! using ONE register n and ONE result register val, plus the stack.
const factMachine = [
  "fact",
    { op:"test",   fn:"=", args:[{reg:"n"}, {const:1}] },
    { op:"branch", label:"base" },
    { op:"save",   reg:"n" },                         // remember n for the multiply
    { op:"assign", reg:"n", src:{ fn:"-", args:[{reg:"n"},{const:1}] } },
    { op:"save",   reg:"continue" },                  // remember where to return
    { op:"assign", reg:"continue", src:{ label:"after" } },
    { op:"goto",   label:"fact" },                    // recurse on n-1
  "after",
    { op:"restore", reg:"continue" },
    { op:"restore", reg:"n" },                        // get our n back
    { op:"assign",  reg:"val", src:{ fn:"*", args:[{reg:"n"},{reg:"val"}] } },
    { op:"goto",    label:{ reg:"continue" } },
  "base",
    { op:"assign", reg:"val", src:{ const:1 } },
    { op:"goto",   label:{ reg:"continue" } }
];

descending (push)                       stack (top = right)
  fact n=3:  save n=3 ----------------> [3]
  fact n=2:  save n=2 ----------------> [3, 2]
  fact n=1:  base case, val = 1 ------> [3, 2]   (no save at base)

ascending (pop) — pending multiplies fire in reverse
  restore n=2; val = 2 * 1 = 2 -------> [3]
  restore n=3; val = 3 * 2 = 6 -------> []
  done: val = 6

6 · Subroutines via a continue register

Notice the machine never "called" anything in the host sense — it only gotos the fact label. So how does it know where to come back to? It writes the return label into a register named continue before jumping, and the called code ends with goto (reg continue). That is the entire mechanism of a subroutine call: a jump plus a register holding the return address. Because the same continue register is reused at every level, each level must save its own continue before overwriting it — which is why the stack carries return addresses as well as data. A real machine's call/return, which the host language packaged invisibly into one nice f(), decomposes here into: set continue, push it, jump, and on return pop it and jump back.

Common mistakes / failure modes

Checkpoint exercise

iter:  test (= n 0) -> branch ans
       assign product = (* n product)
       assign n = (- n 1)
       goto iter
ans:   (product holds n!)

Where this points next

We can now describe any computation — iterative or recursive — as a register machine on paper, complete with an honest, hand-drawn account of its stack discipline and therefore its space cost. But a machine described on paper is just a claim. We asserted that fact(3) reaches stack depth 3 and runs a certain number of instructions; we have no way to check it, and no way to run a machine too large to trace by hand. A description that good should be executable, and a cost model that concrete should be measurable. Lesson 20 builds the bridge: a simulator — an assembler that turns these instruction arrays into runnable code, plus instrumentation (stack-depth and instruction counters) that turns lesson 19's pencil arithmetic into numbers the machine reports itself. The on-paper machine becomes an executable, measurable artifact.

Interview prompts

• What are the components of a register machine? (§1 — a fixed set of registers, primitive operations wired between them, tests that set a flag, branches/gotos, labels, and a controller instruction sequence; later an explicit stack.)
• Explain the data-path / controller split and why it matters. (§2 — data paths are the registers and operation/test boxes (what can be computed and where values flow); the controller sequences when each fires; it is the definition-vs-process distinction made physical, and one set of data paths serves many controllers.)
• Why does iterative gcd need no stack but recursive factorial does? (§4–5 — gcd's whole state lives in its registers and nothing is deferred (constant space); factorial defers a multiply whose operand n must survive the recursive subproblem, and the only place to keep depth-many such values is the stack.)
• Draw the stack discipline of fact(3). (§5 — save n at each descending level (depth grows to 3), hit the base case, then restore n and fire the pending multiplies on the way up (depth drains to 0); the stack mirrors the deferred-operation chain.)
• How is a subroutine call implemented without a host-language call? (§6 — write the return label into a continue register, goto the subroutine label, and end the subroutine with goto (reg continue); save continue first if the callee will overwrite it.)
• What invariant must save/restore obey, and what breaks if it is violated? (§5–6, mistakes — they must bracket like LIFO brackets (restore in reverse save order) around every register the callee clobbers and the caller still needs; violating it returns to the wrong place or swaps register values.)
• What did the host language hide that the register machine exposes? (§5 — the call stack, and therefore the real space cost of recursion; every prior evaluator borrowed the host's recursion/memory, hiding the cost of control that an explicit stack now makes visible.)