Lab 8: The Reference Interpreter (Milestone 5)

Background

No new language features. This lab turns what you have into a specification: a golden test corpus, a backend-agnostic harness, a benchmark baseline, a written architecture document, and ADR-003.

Then you freeze it. Everything in Section 3 is a second implementation of what this lab defines.

This is the least glamorous lab in the curriculum and the one with the highest return. Skipping it means Section 3's bugs are found by reading code instead of by running tests.

Why This Lab Matters

  • The harness must be backend-agnostic before there is a second backend. Written afterwards, it bakes in the first backend's assumptions, and you will special-case something.
  • The corpus is the specification. Every semantic decision from Labs 1–7 — evaluation order, local x = x, truthiness, floor-division signs, arity padding, break absorption, the for overflow rule — must be in the corpus, or Section 3 is free to get it wrong.
  • The baseline is the only honest way to talk about Section 3's speedup. A number measured afterwards is a number you chose.

Prerequisites

Predict First

  1. How many golden programs do you think you need to pin the semantics of Labs 1–7? Write a number. You will count at the end.
  2. Which of your Section-2 decisions is least likely to be reproduced correctly by a compiler + VM? (Write it down. In Lab 12 you will find out.)
  3. If you deleted the tree walker after Lab 11 and a VM bug appeared in Lab 17, how would you find it? Describe the actual debugging session.
  4. fib(25) under the tree walker takes T. Predict the VM's time as a fraction of T.

Step 1: The Golden Corpus

tests/golden/
├── arith/            integer-float rules, floor division signs, overflow, div-by-zero
├── values/           truthiness, equality across subtypes, concat, length
├── scope/            shadowing, local x = x, block scoping, globals
├── control/          if chains, while, for (incl. maxinteger), break nesting, and/or
├── functions/        the three definition forms, arity, recursion, mutual recursion
├── errors/           every runtime error, with its expected message and kind
└── programs/         fizzbuzz, ackermann(2,3), gcd, primes, a small state machine

Each case is a pair:

tests/golden/scope/shadowing.ember
tests/golden/scope/shadowing.expected

-- tests/golden/scope/shadowing.ember
-- RULE: Lua 5.4 §3.5 — an inner block shadows; the initializer is evaluated
-- in the ENCLOSING scope before the new binding exists.
local x = 1
print(x)
do
  local x = 2
  print(x)
  local x = x + 1        -- reads the INNER x (2)
  print(x)
end
print(x)

1
2
3
1

Four rules for corpus cases, and each of them is load-bearing:

  1. Every case names the rule it pins, in a comment, with a manual reference where one exists. Six months from now, a failing test whose comment says "Lua 5.4 §3.5" is a five-minute investigation; one that says nothing is an hour.
  2. Assert on printed output only. Not internal state, not timings, not addresses. Printed output is the only contract both backends share.
  3. Deterministic output only. No clock, no randomness, no iteration over anything unordered. A flaky golden test poisons the whole strategy, because people start ignoring failures.
  4. Small. One rule per file. A 200-line program that fails tells you nothing.

Note: print is a library function and Section 5 builds the real one. For now, add a minimal print native that writes its arguments tab-separated with a newline, exactly as Lua does. It is fifteen lines and it unblocks the entire corpus. Write it in stdlib/base.rs so Lab 21 extends rather than replaces it.

Error cases need their own shape, because you are asserting on a failure:

-- tests/golden/errors/idiv-zero.ember
-- RULE: Lua 5.4 §3.4.1 — integer //0 and %0 are ERRORS; float /0 is infinity.
return 1 // 0

!error kind=Runtime
!message-contains n//0

Assert on kind and a substring of the message — never the full rendered text. The rendered text contains file names and line numbers, and the VM's message will legitimately differ from the tree walker's. This is the same distinction Section 5 makes for hosts: kind is the contract, the message is presentation.

Step 2: The Backend-Agnostic Harness

#![allow(unused)]
fn main() {
// tests/harness.rs
pub trait Backend {
    fn name(&self) -> &'static str;
    /// Run a program; return everything it printed. Output ONLY.
    fn run(&mut self, src: &str, limits: &Limits) -> Result<String, EmberError>;
}

pub struct Case { pub name: String, pub src: String, pub expect: Expect }
pub enum Expect { Output(String), Failure { kind: ErrorKind, contains: String } }

pub fn corpus() -> Vec<Case> { /* walk tests/golden, parse the !error header */ }

pub fn check(backend: &mut dyn Backend, case: &Case) -> Option<String> {
    match (backend.run(&case.src, &Limits::test_defaults()), &case.expect) {
        (Ok(got), Expect::Output(want)) if &got == want => None,
        (Ok(got), Expect::Output(want)) =>
            Some(format!("[{}] {}: output differs\n--- want ---\n{want}\n--- got ---\n{got}",
                         backend.name(), case.name)),
        (Err(e), Expect::Failure { kind, contains })
            if e.kind == *kind && e.message.contains(contains) => None,
        (a, b) => Some(format!("[{}] {}: expected {b:?}, got {a:?}", backend.name(), case.name)),
    }
}
}
#![allow(unused)]
fn main() {
// tests/golden.rs — the only test file, today.
#[test]
fn tree_interpreter_matches_the_corpus() {
    let mut b = TreeBackend::new();
    let failures: Vec<_> = corpus().iter().filter_map(|c| check(&mut b, c)).collect();
    assert!(failures.is_empty(), "{} failures:\n{}", failures.len(), failures.join("\n\n"));
}
}

The design rule: nothing in harness.rs, Case, or the corpus files mentions "interp" or "vm". In Lab 12 you add eight lines — a second Backend impl and a comparison test — and every case you have ever written becomes a differential test. That is the whole architecture, and it only works if you build it in this order.

Step 3: Property Tests

Golden cases pin decisions you thought of. Property tests find the ones you did not.

#![allow(unused)]
fn main() {
// tests/property.rs
proptest! {
    /// Parsing a fully-parenthesized printout of a tree must reproduce the tree.
    /// This catches PRECEDENCE bugs automatically — the class of bug that
    /// hand-written tests miss because you tested what you believed.
    #[test]
    fn parse_print_roundtrip(e in arb_expr(6)) {
        let printed = print_fully_parenthesized(&e);
        let reparsed = parse_expr(&printed);
        prop_assert_eq!(strip_spans(&e), strip_spans(&reparsed), "source: {printed}");
    }

    /// No input, however malformed, may panic or hang.
    #[test]
    fn never_panics(src in ".{0,400}") {
        let _ = run_with_limits(&src, &Limits { instructions: 100_000, depth: 64, .. });
    }

    /// Metamorphic: adding a dead branch cannot change the result.
    #[test]
    fn dead_code_does_not_change_semantics(p in arb_program(4)) {
        let a = run(&p);
        let b = run(&format!("if false then error('unreachable') end\n{p}"));
        prop_assert_eq!(a, b);
    }
}
}

That third one is metamorphic testing — asserting a relationship between two runs without knowing either answer. It is the technique that complements differential testing where you have only one implementation, and SQLite uses it heavily (running a query with and without an index and requiring identical results).

Step 4: The Benchmark Baseline

#![allow(unused)]
fn main() {
// benches/calls.rs
fn bench_calls(c: &mut Criterion) {
    c.bench_function("fib_25_interp", |b| {
        let src = "local function fib(n) if n<2 then return n end
                   return fib(n-1)+fib(n-2) end return fib(25)";
        b.iter(|| TreeBackend::new().run(black_box(src), &Limits::none()));
    });
}
}

Four benchmarks, each isolating one cost, because "the VM is 20× faster" is useless and "local variable access is 40× faster, calls are 12× faster, and arithmetic is 3× faster" is a design document:

BenchmarkIsolatesWhy
fib_25call overhead~243k calls, trivial bodies
loop_10mdispatch + arithmeticfor i=1,10000000 do n=n+1 end
locals_deepname resolutionread a variable from 8 scopes out, in a loop
globalsthe global paththe same read, but as a global
cargo bench 2>&1 | tee docs/learning/baseline-interp.txt
git add docs/learning/baseline-interp.txt && git commit -m "lab-08: interpreter baseline"

Commit the file. A baseline you can git show is a baseline; one in a terminal you closed is a memory.

Step 5: Write It Down

Three documents, and they are deliverables:

docs/architecture.md — the specification. It must state, at minimum:

  • The grammar (from the grammar chapter).
  • The precedence and associativity table.
  • Operand evaluation order: left to right, always. (Lua does not guarantee this. Ember does.)
  • The integer/float rules per operator.
  • Truthiness, equality, and ordering rules.
  • Scope rules, including the local x = x ordering and the local function binding order.
  • The absorbs/forwards table for control flow.
  • The calling convention, including arity padding.
  • The limits and their defaults, and the fact that expression depth and call depth multiply.

docs/adr/ADR-003-keep-the-tree-walker.md — written now, before any VM code exists.

# ADR-003: Keep the tree-walking interpreter as a permanent semantic reference

## Context
Section 3 replaces the execution engine. Every semantic decision in Labs 1–7 must be
reproduced by a different mechanism. We cannot write enough hand-written tests to
cover that, because the tests we would write are the cases we already understand.

## Options
A. Delete the tree walker once the VM works. Saves ~1,000 lines; leaves the VM
   checked only by tests we thought of.
B. Keep it, run the corpus through both, require identical output. Costs ~1,000
   lines of maintenance and a second implementation of every future feature.
C. Test against real `lua` instead. Independent oracle, but only covers the
   Lua-compatible subset; every deliberate divergence is a false positive.

## Decision
B, supplemented by C for the compatible subset in Section 6.

## Consequences
Every feature is implemented twice — most expensively multiple returns (Lab 17)
and metatables (Lab 18), which are also the two where divergence is most likely.
The tree walker must stay simple: optimizing it degrades its value as an oracle.
`ember run --interp` becomes a user-facing debugging tool. We revisit this only if
maintaining the second backend measurably slows feature work — and if so, the
replacement is C plus a much larger corpus, not nothing.

docs/learning/04-interpreter.md and 07-call-frames.md — the journal entries, including your three written predictions for Section 3.

The Trace: the corpus, both ways

Today only one backend exists, so the harness runs once. Run it anyway, and look at the output — this is the shape Lab 12 doubles:

$ cargo test --test golden
running 1 test
test tree_interpreter_matches_the_corpus ... ok

$ ember run --interp tests/golden/control/break-nested.ember
3
$ ember run tests/golden/control/break-nested.ember
3            # ← today these are the same code path. In Lab 12 they will not be.

And the baseline:

$ cargo bench --bench calls 2>&1 | grep -A1 fib_25
fib_25_interp           time:   [<your number here>]

Write your number in docs/learning/07-call-frames.md next to your prediction for the VM. Do not look it up, do not estimate from someone else's blog post. The comparison is only meaningful against your own machine, your own build flags, your own code.

Expected Output

$ cargo test
   ...
test tree_interpreter_matches_the_corpus ... ok
test property::parse_print_roundtrip ... ok
test property::never_panics ... ok
test property::dead_code_does_not_change_semantics ... ok
test result: ok. NN passed; 0 failed

$ ls tests/golden/**/*.ember | wc -l
27

Debugging Steps

A golden case passes locally and fails in CI

Something is nondeterministic. Usual suspects: iteration over a HashMap, a path in an error message, or terminal color codes leaking into output. Run with --no-color in tests and check that nothing in the corpus iterates an unordered collection.

The property test finds a panic

Good — that is the test working. Fix the panic; do not add the input to a skip list. Then commit the shrunk input as a golden case so it is checked forever.

parse_print_roundtrip fails

Either your pretty-printer is not fully parenthesizing, or your binding powers are wrong. Print the failing case; proptest shrinks it to something tiny.

The benchmark numbers move 30% between runs

Close other applications, use cargo bench (not cargo test --release), and let criterion do its warmup. If it still moves, note the variance in the baseline file — a baseline with an honest error bar is worth more than a precise-looking one.

The corpus is 8 files and you feel done

You are not. Go through docs/architecture.md line by line and write a case for every rule in it. If a rule has no case, either the rule is not real or the corpus has a hole; both are worth finding now.

Experiment

CLAIM. The corpus you wrote from memory has holes, and reading your own specification finds them.

METHOD. Write docs/architecture.md first, from memory. Then go through it rule by rule and ask "which corpus file pins this?" Add a case for every rule that has none. Count how many you added.

PREDICTION. Before starting: how many rules will have no case? (Most people guess 2–3. Most people find 8–15.)

RESULT. Record the count and, more usefully, which kinds of rule you forgot. There is usually a pattern — error cases, boundary values, or interactions between two features — and knowing your own pattern is a durable skill.

Test

The tests in this lab are the deliverable, so the "one test" is a meta-test:

#![allow(unused)]
fn main() {
#[test]
fn every_documented_rule_has_a_corpus_case() {
    // docs/architecture.md tags each normative rule with `[RULE:name]`.
    // Each corpus file names the rules it pins in a `-- RULE:` comment.
    // This test asserts the two sets match. It is the cheapest possible
    // defense against a specification and a test suite drifting apart.
    let documented = rules_in_architecture_doc();
    let covered = rules_named_in_corpus();
    let uncovered: Vec<_> = documented.difference(&covered).collect();
    let orphaned: Vec<_> = covered.difference(&documented).collect();
    assert!(uncovered.is_empty(), "documented but untested: {uncovered:?}");
    assert!(orphaned.is_empty(), "tested but undocumented: {orphaned:?}");
}
}

Tip: That test is worth writing even though it looks like bureaucracy. It converts "keep the docs up to date" from a good intention into a build failure, and it is the reason docs/architecture.md will still be accurate in week sixteen.

Challenge Extensions

  1. Compare against real Lua. For every corpus case that avoids Ember's documented divergences, run lua and require identical output. Gate it behind cargo test --features lua-compat so it is skippable when Lua is not installed. This is oracle C and it is genuinely independent.
  2. Coverage. Run cargo llvm-cov over the corpus. Which branches of binary_op are never taken? Those are the semantics you have not tested. Add cases until the arithmetic and comparison paths are fully covered.
  3. Corpus generator. Write a program generator that produces valid Ember programs and run it under both --interp and (later) the VM. Start with the arithmetic subset. This is a small Csmith, and it is how you find the bugs neither of you thought of.
  4. Shrink your own failures. When a property test fails, proptest shrinks it. Write down the shrunk case and the un-shrunk one. How much smaller? That ratio is why property testing is worth the setup.
  5. A second reference. Write a 200-line Python implementation of Ember's arithmetic and comparison rules and differential-test the rules against it. This covers exactly the blind spot from the concept chapter — the shared code that Rust-side differential testing cannot check.

Deliverables

  • tests/golden/ with 25+ cases across all seven categories, each naming the rule it pins.
  • Error cases assert kind and a message substring, never full rendered text.
  • tests/harness.rs defines a Backend trait, and nothing in the harness or the corpus names a backend.
  • tests/property.rs with round-trip, no-panic, and one metamorphic property.
  • benches/ with four benchmarks; docs/learning/baseline-interp.txt committed.
  • docs/architecture.md written, with every normative rule tagged.
  • The rules-vs-corpus meta-test passes.
  • docs/adr/ADR-003-keep-the-tree-walker.md written before any VM code exists.
  • Three written predictions for Section 3's speedup, in docs/learning/07-call-frames.md.
  • cargo clippy -- -D warnings clean; ./scripts/boundary-audit.sh passes.
  • Milestone 5 complete. The language is frozen as a reference.

Validation / Self-check

  1. Why must the harness be backend-agnostic before the second backend exists? Give a concrete thing that would go wrong otherwise.
  2. Why do error cases assert on kind plus a substring rather than the rendered message?
  3. Give the four rules for a corpus case and the failure each one prevents.
  4. What is metamorphic testing, and how does it differ from differential testing? Give an example of each from this lab.
  5. Why four benchmarks rather than one? What would "the VM is 20× faster" fail to tell you?
  6. State ADR-003's rejected options and their real costs. Why must the ADR be written now?
  7. What is the blind spot of differential testing, and which challenge extension addresses it?
  8. How many rules in your docs/architecture.md had no corpus case? What kind were they?

Next: Section 3 — Bytecode and the Virtual Machine. You now have a specification. Everything from here is a second implementation of it.