The Reference Implementation

This chapter is short and it contains the best idea in the curriculum.

When the bytecode VM works in Lab 11, the tree-walking interpreter you just spent four weeks building will look like dead weight. It is slower by a large factor, it duplicates every semantic decision, and deleting it would remove a thousand lines. Do not delete it. It is your oracle, and Lab 12 turns it into a permanent, automatic correctness guarantee for everything you build afterwards.

This is ADR-003, and you write it before the VM exists — so that it is a prediction, not a rationalization.

Concept 1: An Oracle

1. Concept

A test oracle is the thing that knows the right answer. For assert_eq!(add(2,2), 4), the oracle is you, at the moment you wrote 4. That works for arithmetic and does not scale to "does this 400-line policy script produce the same result under both backends?"

A reference implementation is an oracle you can execute: a second, independent implementation of the same specification, written for clarity rather than speed, whose output defines correctness.

2. Problem

Section 3 replaces the entire execution engine. Every semantic decision made in Section 2 — operand evaluation order, shadowing, the local x = x rule, truthiness, short-circuit, arity padding, the floor-division sign, break absorption — must be reproduced exactly by a completely different mechanism.

Hand-written tests cannot cover that. You would need a test per decision per construct per combination, you would forget most of them, and the ones you wrote would be the ones you already understood — which are not the ones with bugs.

3. Mental model

You are about to write the same program twice, in two very different ways. Two independent implementations of the same specification almost never have the same bug. So run both on everything and compare: a disagreement is a bug, located to one of two places, found automatically, on inputs nobody thought to write a test for.

                     ┌──────────────────────┐
             ┌──────▶│ TREE INTERPRETER     │──── output A ────┐
             │       │ slow, obvious        │                  │
   program ──┤       └──────────────────────┘                  ├──▶ A == B ?
             │       ┌──────────────────────┐                  │      │
             └──────▶│ COMPILER + VM        │──── output B ────┘      │
                     │ fast, intricate      │                    mismatch = BUG
                     └──────────────────────┘                    (in one of two places)

4. Implementation

The mechanism is small. What makes it work is a discipline established now, in Lab 8: the test harness never names a backend.

#![allow(unused)]
fn main() {
// tests/harness.rs — written in Lab 8, BEFORE the VM exists.
pub trait Backend {
    fn name(&self) -> &'static str;
    /// Run a program, returning everything it printed. Output ONLY — never
    /// internal state, because internal state is exactly what differs.
    fn run(&mut self, src: &str) -> Result<String, EmberError>;
}

pub fn run_corpus(backend: &mut dyn Backend) -> Vec<Failure> { /* ... */ }
}

#![allow(unused)]
fn main() {
// tests/differential.rs — written in Lab 12, and never touched again.
#[test]
fn backends_agree_on_the_whole_corpus() {
    for case in golden_corpus() {
        let a = TreeInterp::new().run(&case.src);
        let b = VmBackend::new().run(&case.src);
        match (a, b) {
            (Ok(x), Ok(y)) => assert_eq!(x, y, "output differs in {}", case.name),
            (Err(x), Err(y)) => assert_eq!(x.kind, y.kind,
                                           "error KIND differs in {}", case.name),
            (a, b) => panic!("one backend succeeded and the other failed in {}:\n\
                              interp: {a:?}\nvm: {b:?}", case.name),
        }
    }
}
}

Three details that decide whether this works.

1. Compare printed output, not internal state. The backends' internals are supposed to differ. The only shared contract is observable behavior.
2. Compare error kinds, not error messages. Message text will differ (the VM knows the instruction pointer; the tree walker knows the AST node) and forcing them identical would be pointless churn. ErrorKind is the contract; the message is presentation. This is the same distinction Section 5 makes for hosts.
3. Every ordinary test becomes a differential test for free. You never sit down to "write differential tests". You write a golden program because you added a feature, and the harness runs it under both backends from then on, forever. That is why the harness must exist before the second backend does — retrofit it and you will special-case something.

5. Alternatives

6. Decision

ADR-003: keep the tree-walking interpreter permanently as the semantic reference, and run the entire test corpus through both backends. Supplement with C for the Lua-compatible subset (Section 6) and E in the property tests.

7. Tradeoffs

Is "implement everything twice" too expensive? Be honest about it, because it is the strongest objection. In practice the second implementation is the compiler, and by then the semantics are settled — you are translating a decision, not making one. The features where it genuinely costs double are multiple returns (Lab 17) and metatables (Lab 18), and those are precisely the two where the differential test earns its keep, because they are the two where the backends are most likely to diverge. The expense and the payoff are the same feature. That is not a coincidence.

8. Production concerns

The blind spot, stated plainly: differential testing cannot find a bug in code the two backends share.

Ember's backends share Value, raw_eq, the arithmetic helpers, the lexer, and the parser. If binary_op implements Lua's modulo wrongly, both backends are wrong in exactly the same way and the differential test passes. This is not a flaw in the technique; it is a boundary, and knowing where it lies is what makes the technique usable.

That table belongs in docs/learning/. It is the difference between "we have differential testing" and understanding what that sentence buys.

Other concerns:

• The reference must stay correct, which means it must stay simple. Every optimization you make to the tree walker degrades its value as an oracle. This is why the section index lists "optimizing the interpreter" as a mistake.
• Nondeterminism breaks the comparison. If table iteration order is unspecified, the two backends may print in different orders and the test fails spuriously. Ember's insertion-ordered tables (ADR-008) exist partly for the product and partly for this. Determinism is a testability property before it is a feature.
• Keep it in CI, and keep it fast. A corpus of 200 small programs run twice is a second or two. If it ever gets slow, sample in pre-commit and run the whole thing in CI — never delete cases.

9. References

• McKeeman, Differential Testing for Software (Digital Technical Journal, 1998) — the paper that named the technique.
• Csmith (Yang, Chen, Eide, Regehr, PLDI 2011) — generated random C programs, compiled them with every compiler, compared outputs, and found over 300 bugs in GCC and LLVM, many of them wrong-code bugs in released versions. The most persuasive case study in existence for this technique.
• The WebAssembly reference interpreter (WebAssembly/spec, written in OCaml) — a normative reference implementation that production engines are tested against. Exactly this pattern, standardized.
• SQLite's testing story (sqlite.org/testing.html) — read the sections on fuzzing and on cross-checking query results with and without indexes. That second one is metamorphic testing in production, and SQLite's reliability is the argument.
• RISC-V's Spike simulator, used as the golden model for hardware verification — the same idea, one layer down.
• Jepsen — differential testing against a model, for distributed systems. Worth knowing the shape even though it is a different domain.

Things to Notice

• Two implementations almost never share a bug — unless they share code. Both halves of that sentence are load-bearing, and the second half is the part people forget.
• The oracle must be the simple one. A fast reference implementation is a contradiction: the properties that make it fast are the properties that make it hard to trust.
• The harness must be backend-agnostic before there is a second backend. Written afterwards, it will have the first backend's assumptions baked in.
• Compare behavior, not internals; compare error kinds, not error text. Those two rules are what keep the test from becoming a maintenance burden.
• Determinism is a testability property first. Every source of nondeterminism you remove is a spurious failure you never have to investigate.
• The cost and the payoff land on the same features. Multiple returns and metatables are the expensive ones to implement twice and the ones the comparison actually catches.

Validation / Self-check

1. What is a test oracle, and why is a hand-written expected value insufficient for Section 3?
2. Why must ADR-003 be written before the VM exists?
3. Give the three rules that make the differential harness work, and what breaks if each is violated.
4. Name four bug locations differential testing catches and three it cannot. What catches the latter?
5. Why is optimizing the tree walker listed as a mistake?
6. How does determinism relate to differential testing? Give a concrete spurious failure it prevents.
7. Which two upcoming features are the most expensive to implement twice, and why is that the same answer as "which two does the comparison most need to check"?
8. Cite one real-world system that uses a normative reference implementation, and one that found hundreds of compiler bugs this way.

Next: Lab 5 — Variables and Scope.