A register-machine simulator

Lesson 19 left us with machines on paper — controllers we could trace by hand and claim a stack depth and instruction count for. A claim that precise deserves to be checked, and a machine too big to trace deserves to be run. This lesson builds the machine that runs the machines: a simulator. Its heart is an assembler that walks the instruction array from lesson 19 and turns each instruction into an execution function — a closure over the machine's registers and stack that, when called, does that instruction's work and returns where to go next. This is closures (lessons 03 and 10) cashed out: the machine's behavior is a list of closures wired to shared state. And because we own the loop that calls them, we drop in performance counters that make lesson 19's pencil cost model into numbers the machine reports itself.

1 · The machine as a data structure

Before we can run a controller we need the hardware as a live object. A machine is just a record bundling the mutable state — registers, the stack, a program counter — with the lookup tables the assembler needs:

function makeMachine(registerNames, ops) {
  const regs  = {};                       // name -> current value
  registerNames.forEach(n => regs[n] = null);
  const stack = [];                        // the explicit stack from lesson 19
  let   flag  = false;                     // set by tests, read by branch
  let   pc    = 0;                          // program counter: index into the thunk list
  const labels = {};                        // label name -> index in the instruction list
  let   thunks = [];                        // the ASSEMBLED execution functions
  let   stats  = { instr: 0, maxDepth: 0 }; // performance counters
  return { regs, stack, ops,
           getFlag:()=>flag, setFlag:b=>flag=b,
           getPc:()=>pc,    setPc:i=>pc=i,
           labels, thunks, stats };
}

Two fields deserve attention. ops is the operation table — a map from operation name ("+", "rem", "=") to an actual JavaScript function; it is how the abstract {fn:"rem"} of lesson 19 connects to real arithmetic. thunks is empty for now — it gets filled by the assembler, and it is where the controller-as-data becomes controller-as-behavior.

2 · The assembler and label resolution

The assembler reads the instruction array (the data from lesson 19) and produces the parallel thunks array. It must solve one ordering problem: an instruction can goto a label that appears later in the text, so we cannot resolve a label to an index until we have seen the whole program. The classic fix is two passes:

So a label is not a runtime search — it is resolved once at assembly time into a numeric index, then a jump is a single assignment to pc. This is the same "do the work once, not on every execution" idea the analyzing evaluator introduced in lesson 15, now applied to addresses.

3 · Each instruction becomes a closure over machine state

Here is the conceptual core of the whole simulator. The assembler does not interpret an instruction every time it runs. It interprets each instruction's shape exactly once and returns a thunk: a zero-argument function that closes over the machine and, when called, performs that instruction and returns the next pc. The kind of work an assign does is decided once, at assembly; only the actual value flows at run time.

This is why lessons 03 and 10 were prerequisites. A closure is a function plus the environment it captured. Every thunk captures the same machine object, so all thunks read and write one shared set of registers and one shared stack — exactly the wiring of a real machine's data paths. The controller text became a list of behaviors permanently bonded to the hardware. We build a small helper that compiles a source (a constant, a register, or an operation) into a closure that yields its value, then build per-instruction thunks on top of it:

// Compile a source expression into a () => value closure over the machine.
function makeValue(m, src) {
  if ("const" in src) return () => src.const;            // captured once
  if ("reg"   in src) return () => m.regs[src.reg];      // read shared register
  if ("label" in src) return () => m.labels[src.label];  // a return address
  if ("fn"    in src) {                                   // an operation
    const fn   = m.ops[src.fn];                           // resolved ONCE
    const args = src.args.map(a => makeValue(m, a));      // sub-closures
    return () => fn(...args.map(a => a()));                // apply at run time
  }
}

4 · Worked example — one instruction becomes a thunk

function asmAssign(m, ins) {
  const value = makeValue(m, ins.src);    // built ONCE at assembly
  return (pc) => {                          // the thunk: run MANY times
    m.regs[ins.reg] = value();             // read regs, op, write reg
    return pc + 1;                          // next pc = fall through
  };
}
function asmBranch(m, ins) {
  const target = m.labels[ins.label];      // label -> index, resolved ONCE
  return (pc) => m.getFlag() ? target : pc + 1;   // jump iff the flag is set
}

5 · The execution loop

With every instruction now a thunk that returns the next pc, running the machine is a tight loop: fetch the thunk at pc, run it, set pc to what it returns, repeat until pc runs off the end. save/restore are thunks that push/pop the shared stack:

function run(m) {
  while (m.getPc() < m.thunks.length) {
    const thunk = m.thunks[m.getPc()];
    m.stats.instr++;                         // count every instruction executed
    m.setPc(thunk(m.getPc()));               // run it; it returns the next pc
  }
  return m.regs["val"] ?? m.regs["a"];       // answer lives in a register
}
// save / restore thunks (assembled from {op:"save"/"restore"}):
const saveThunk    = (reg) => (pc) => {
  m.stack.push(m.regs[reg]);
  m.stats.maxDepth = Math.max(m.stats.maxDepth, m.stack.length);  // measure!
  return pc + 1;
};
const restoreThunk = (reg) => (pc) => { m.regs[reg] = m.stack.pop(); return pc + 1; };

Notice there is no recursion in the simulator's loop. The simulated machine recurses by goto-ing its own label and pushing the explicit stack — but the host loop is flat. We have finally stopped borrowing the host's call stack: the machine's recursion lives entirely in m.stack, an array we control, exactly as lesson 19 demanded.

6 · Instrumentation — measuring lesson 19

Because we own both the loop and the stack thunks, instrumentation is nearly free. Two counters already appear above: stats.instr increments once per executed instruction, and stats.maxDepth tracks the high-water mark of the stack inside save. A trace mode just prints the instruction before running its thunk. Now the claims of lesson 19 become checkable numbers:

trace                        stack         maxDepth   instr
fact n=3  test(=3,1) false                  0          1
          save n=3           [3]            1          ...
          n=2; save cont     [3, c]         2
fact n=2  save n=2           [3,c,2]        3
          n=1; save cont     [3,c,2,c]      4
fact n=1  test(=1,1) true -> base
          val=1                             4
after...  restore; val=2*1=2  drains
after...  restore; val=3*2=6  drains
RESULT  val = 6     stats.maxDepth = 4     stats.instr = 26

Common mistakes / failure modes

Checkpoint exercise

function asmGoto(m, ins) { /* ... */ }
function asmTest(m, ins) { /* ... */ }

Where this points next

We now have an executable, self-measuring register machine: feed it the instruction data from lesson 19 and it reports the exact stack depth and instruction count, for any input size. But the simulator still rests on two host-language conveniences we have not yet paid for. The stack is a JavaScript array that grows without limit, and whenever the simulated programs build pairs or lists, they lean on the host's heap and garbage collector — memory is still effectively infinite and free. Real hardware has neither: storage is a finite block of cells, allocation can run out, and reclaiming dead memory is a job someone must do explicitly. Lesson 21 confronts this head on — it represents pairs as indices into finite vectors, builds a garbage collector, and then turns the lesson-14 metacircular evaluator itself into a register machine (the explicit-control evaluator), with its stack saving exactly the registers lesson 19 said it must. The machine stops pretending memory is magic.

Interview prompts

• What does the assembler do, and why is two-pass assembly necessary? (§2 — it converts the instruction array into a parallel array of execution thunks; two passes are needed because a goto can target a label defined later, so pass 1 records every label's index before pass 2 can resolve jumps and build thunks.)
• Explain "each instruction becomes a closure over the machine state." (§3–4 — the assembler interprets an instruction's shape once and returns a zero-arg function that captures the shared machine (registers, stack, resolved op/label) and, when called, performs the instruction and returns the next pc.)
• What work happens once at assembly versus every time a thunk runs? (§4 — resolving the operation function and label-to-index happens once; reading live registers, applying the op, choosing the branch, and writing a register happen on every run — the analyze-once / execute-many split from lesson 15.)
• How do labels resolve to something a jump can use? (§2 — pass 1 maps each label name to the index of the next instruction slot; a goto/branch then compiles to a thunk that sets pc to that numeric index — no runtime search.)
• Why does the simulator's run loop contain no recursion despite running recursive factorial? (§5 — the simulated machine recurses by goto-ing its own label and pushing the explicit m.stack array; the host only needs a flat fetch-execute loop, so we no longer borrow the host's call stack.)
• How does the simulator make lesson 19's cost model measurable? (§6 — counters in the run loop and save thunk: stats.instr per executed instruction and stats.maxDepth as the stack high-water mark, plus optional tracing — confirming, e.g., fact(3) reaches maxDepth 4.)
• What two host conveniences does the simulator still rely on, motivating lesson 21? (§where-next — an unbounded stack array and the host heap/GC for pairs; memory is still effectively infinite and free, so lesson 21 makes it finite vectors with explicit allocation and garbage collection.)