Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

24. The tree-walking interpreter is kept as a differential-testing oracle

  • Status: Accepted
  • Date: 2026-09-04

Context

Milestone 3 gives Korrin a second way to run a program. The obvious thing to do with the first one is delete it: it is slower, it is now redundant, and two implementations of one language is twice the surface to maintain.

The problem is that the new engine is much harder to be sure about. The interpreter's correctness argument is "it does what the tree says". The VM's is "a compiler turned the tree into instructions that are equivalent, and a machine with three stacks runs them in the right order, keeping the right things alive". The failure modes are different in kind: a mis-emitted jump, a stack left one value deep, a capture closed a moment too late. None of those look like a crash. They look like a program quietly printing the wrong number.

Meanwhile there is an oracle sitting right there. The interpreter already runs every program the test suite has, it was written months before the VM and without reference to it, and its answers have been trusted through two milestones.

Decision

The tree-walking interpreter stays, permanently, as the oracle the VM is tested against. It is not deprecated, not feature-frozen relative to the language, and not an implementation detail scheduled for removal.

Both engines are reachable: korrin::run / run_file use the interpreter, korrin::run_vm / run_file_vm use the VM.

The agreement contract

Given the same program, the engines must agree that:

  1. Both succeeded, or both failed. Succeeding under one engine and failing under the other is a bug even when the failure looks reasonable.
  2. On success, stdout matches byte for byte.
  3. On failure, the primary diagnostic's ErrorCode matches.

Point 3 deliberately stops at the code. Messages and spans are not compared: the VM knows the exact instruction that faulted and often points at a better place than the interpreter's whole-expression span, and holding it to the worse position would make the oracle a ratchet against improvement. This mirrors what tests/programs.rs already does with its .err fixtures.

The one accepted disagreement

ADR 0022 narrows Korrin's scoping rule from a runtime search to a lexical one, which leaves exactly one program shape where the engines differ. It is pinned by a test that asserts the difference is still exactly that shape, so a future fuzz failure of that kind is recognised in seconds rather than investigated.

Where sharing is allowed

The engines share the value-level operations: arithmetic, comparison, indexing, attribute lookup, iteration (interpreter::ops). They do not share scoping, control flow, calls, or closures.

The line is drawn at "does an independent implementation of this tell us anything". Two implementations of 1 + 1 do not; two implementations of "which binding does this name refer to" very much do, and that is where the two engines were always going to differ.

Consequences

  • Every existing golden program and every runnable specification example becomes a VM test for free, which is a far broader corpus than anything written specifically for the VM.
  • Bugs surface as a disagreement with a known-good answer instead of as a mismatch with what someone thought the answer should be. Four real bugs in the VM were found this way on the first run of the suite.
  • Two engines are two things to update when the language grows. Every future feature has to be implemented twice or, where it is a value operation, once in the shared module. This is the price, and it is paid deliberately.
  • The interpreter is also the fallback if a VM bug is found in the field, and the reference when the specification and an implementation disagree.
  • The oracle only checks what it is run on. It is not a proof, and the proptest-style fuzzing it enables is only as good as the programs generated.

Alternatives considered

  • Delete the interpreter once the VM passes the existing tests. The existing tests were written to exercise the language, not a compiler, and passing them says little about jump patching or stack discipline. It also throws away the only independent implementation at exactly the moment one becomes valuable.
  • Keep it but freeze it. A frozen oracle drifts out of the language and stops being able to run new programs, which is precisely when the check is most needed.
  • Compare spans and messages too. Would catch more, and would fail every time the VM produced a better diagnostic, training everyone to paper over differences rather than look at them.
  • Trust a large test suite instead. A test suite encodes what someone thought to check. An oracle answers questions nobody thought to ask, which is the entire point.