P11 — Programming Language, Interpreter, and Virtual Machine

Run it first. There is a companion page that builds this project's machinery as numbered, independently runnable blocks and then assembles them into one measured system: P11 hands-on — block by block (handson/h*.py). Every number on it was produced by running the code. Read it alongside the milestones below.

Large · 132 hours · split across two stages · Rust

• Phase I — Tree-walk interpreter: Small, 55 h, Weeks 16–20 (Stage 1)
• Phase II — Bytecode VM, types, GC: Medium, 77 h, Weeks 44–50 (Stage 2)

The split is deliberate. Phase I is scheduled early because it is the easiest project in the journey conceptually and the hardest linguistically — it is where you learn Rust, on a problem simple enough that the language is the only difficulty. Phase II returns when Rust is no longer the obstacle.

Table of Contents

• The Loop, Instantiated
• Why This Project Matters
• Prerequisites
• Duration and Size
• Central Technical Questions
• Phase I — Tree-Walk Interpreter (W16–W20)
• Phase II — Bytecode VM (W44–W50)
• Showcase — The Compiler Bug That Passes Every Test
• The Dispatch Measurement That Justifies Rust
• Concepts To Study
• Primary-Source Readings
• Experiments
• Benchmarks and Metrics
• Correctness Tests
• Failure Tests
• Expected Difficulties
• Scope Boundaries
• Deliverables
• Exit Criteria
• Extension Ideas
• Connections
• References

The Loop, Instantiated

Why This Project Matters

Every abstraction you use is, underneath, a dispatch loop, a stack frame, and a decision about who frees memory. This project makes all three concrete.

The specific payoff for your trajectory: after building a garbage collector you will never again reason vaguely about a latency spike in a JVM or Go service. After building a dispatch loop you will understand why PyTorch's Python overhead matters (P13), why a Python ANN index loses to C++ (P02), and what a JIT is actually doing. After implementing lexical scope with closures, you will know exactly what a closure costs.

There is also a professional-credibility dimension. "I built a language with a bytecode VM and a garbage collector, and here is the GC pause distribution" is a claim very few senior engineers can make, and it changes the kinds of conversations you can have.

Prerequisites

• Phase I: none. This is the entry point to Rust
• Phase II: Phase I complete; P04 (which gave you real Rust practice on a harder problem)
• From math.md: nothing. This project is math-free, which is part of why it is a good Rust on-ramp

Duration and Size

Large in total, 132 hours, split into two.

Central Technical Questions

1. What is a closure, physically? What is captured, where does it live, and what keeps it alive?
2. Where does a tree-walk interpreter spend its time? Predict the split between dispatch, environment lookup, and allocation. Then measure it.
3. Why is bytecode faster than an AST walk — and under what conditions is it not?
4. What does a garbage collector cost, in throughput and in pause distribution?
5. What does a type checker buy at runtime, if the language is dynamically typed anyway?
6. Which optimisations actually pay? Constant folding sounds valuable; measure whether it is.

Phase I — Tree-Walk Interpreter (W16–W20)

Small, 55 hours, 5 weeks. Language target: dynamically typed, C-like syntax, first-class functions, closures, lexical scope. Roughly Lox from Crafting Interpreters in scope — but write it before reading it, and use the book to check your design afterwards rather than to produce it.

Milestones

The closure test

fun makeCounter() {
  var i = 0;
  fun count() { i = i + 1; return i; }
  return count;
}
var c1 = makeCounter();
var c2 = makeCounter();
c1(); c1(); c2();     // expect 1, 2, 1

If c2() returns 3, your closures share an environment when they must not. If it returns 1 but c1() returned 1 twice, you copied the environment instead of capturing it. This eight-line program distinguishes three different implementations, which is why it is the canonical test.

Phase II — Bytecode VM (W44–W50)

Medium, 77 hours, 7 weeks.

Milestones

The bug you will write in milestone 9

When compiling a loop, it is easy to emit the body once per iteration — effectively unrolling at compile time. It produces correct results, so tests pass. Symptoms: compile time scales with the trip count, and bytecode size explodes.

This is not hypothetical. Building the reference measurement for this page, the first compiler did exactly that: a 200,000-iteration loop with 2 statements produced 840,000 bytecode instructions and took 269 ms to compile, versus 16 instructions and 18 µs once a LOOP opcode with a backward jump was added. A 52,500× difference in code size, from one design mistake that all the correctness tests passed.

Test for it: assert that compiled bytecode length is independent of loop trip count.

Showcase — The Compiler Bug That Passes Every Test

Fifteen minutes. The single most likely defect in Phase II milestone 9, and the one-line assertion that catches it.

# P11 -- the compiler bug that passes every correctness test.
def compile_unrolled(trip, body_ops=3):
    """Emit the loop body once per iteration. Correct results, exploding code."""
    return [("OP", i) for _ in range(trip) for i in range(body_ops)]

def compile_looped(trip, body_ops=3):
    """Emit the body ONCE, with a counter and a backward jump."""
    return [("SETCTR", trip)] + [("OP", i) for i in range(body_ops)] + [("LOOP", 1)]

print(f"{'trip count':>12}{'unrolled':>12}{'looped':>9}{'ratio':>10}")
for trip in (10, 1_000, 100_000, 1_000_000):
    u, l = len(compile_unrolled(trip)), len(compile_looped(trip))
    print(f"{trip:>12,}{u:>12,}{l:>9}{u//l:>9,}x")

print("\\nBoth compilers produce IDENTICAL results, so every correctness test passes.")
print("The tell is that compile time and code size scale with the TRIP COUNT rather")
print("than the program size. The assertion that catches it is one line:")
print("    assert len(compile(prog)) is independent of the loop bound")
print("\\nThis is not hypothetical: the first bytecode compiler written for this track")
print("emitted 840,000 instructions and took 269 ms for a 200,000-iteration loop,")
print("against 16 instructions and 18 us once a LOOP opcode existed.")

  trip count    unrolled   looped     ratio
          10          30        5        6x
       1,000       3,000        5      600x
     100,000     300,000        5   60,000x
   1,000,000   3,000,000        5  600,000x
\nBoth compilers produce IDENTICAL results, so every correctness test passes.
The tell is that compile time and code size scale with the TRIP COUNT rather
than the program size. The assertion that catches it is one line:
    assert len(compile(prog)) is independent of the loop bound
\nThis is not hypothetical: the first bytecode compiler written for this track
emitted 840,000 instructions and took 269 ms for a 200,000-iteration loop,
against 16 instructions and 18 us once a LOOP opcode existed.

Write that assertion before you write the compiler. It costs nothing and it is the only thing standing between you and a week of wondering why compilation got slow.

The Dispatch Measurement That Justifies Rust

Phase II's premise is that bytecode beats AST walking. Here is that premise tested — in Python, with both interpreters written in the same host language, same semantics, verified to produce identical results:

program      : 200,000 iterations x 2 statements = 400,000 statements
bytecode     : 16 instructions total (loop body emitted ONCE)
tree-walk    :    217.46 ms      543.6 ns/statement
compile      :     17.63 us   (one-time, 16 instrs)
bytecode run :    328.50 ms      821.3 ns/statement
speedup      :      0.66x
correctness  : tree x=110702.539411685  bc x=110702.539411685  match=True

The bytecode VM is 1.5× slower. Both produce identical results to fifteen significant figures, so this is not a bug — it is the actual behaviour.

The reason is the thing worth learning. Each source statement compiles to ~7 bytecode instructions. In a host-interpreted VM, every one of those costs a full host-language dispatch: loop iteration, tuple unpack, comparison chain, stack push/pop. The tree-walk pays one type() check and a short comparison chain per AST node — fewer, larger steps. So the bytecode VM multiplies its work by the instruction count while paying the same per-step cost.

Bytecode's advantage was never "fewer operations". It is "cheaper operations", and that only materialises when the dispatch loop compiles to machine code, where a switch becomes a computed goto (a few ns) and the AST walk's pointer-chasing plus virtual dispatch plus cache misses becomes the expensive option.

This measurement is why Phase II is in Rust, and it is the first thing to reproduce in milestone 10: run your Rust bytecode VM against your Rust tree-walker and confirm the sign of the effect flips. Published results for compiled interpreters put the AST→ bytecode win at roughly 2–10× depending on workload; if you measure less than 1.5×, your dispatch loop has a problem (bounds checks, Box<dyn> indirection, or a non-inlined stack).

Report the Python result alongside the Rust one. "Bytecode is faster" is folklore. "Bytecode is 1.5× slower in Python and 4× faster in Rust, and here is the mechanism" is knowledge.

Concepts To Study

• Lexing: maximal munch, source positions, why lexer errors differ from parse errors
• Parsing: recursive descent; Pratt / precedence climbing (the technique that makes expression parsing pleasant); error recovery via synchronisation
• ASTs: representation, the visitor pattern, and why Rust enums make it natural
• Environments and scope: the chain, shadowing, and why lexical scope is resolvable statically
• Closures: capture by reference vs value; upvalues and the open/closed distinction; what keeps a captured variable alive
• Bytecode: stack vs register machines, instruction encoding, jumps and patching
• Dispatch: switch, computed goto, direct threading, subroutine threading
• Call frames: the frame stack, return addresses, argument passing
• Garbage collection: mark-sweep, tri-colour marking, root sets, precise vs conservative; generational hypothesis; pause distributions
• Reference counting and why cycles defeat it
• Type checking: unification, gradual typing, soundness vs completeness
• Optimisation: constant folding, DCE, inline caching, and why a JIT is the logical next step

Primary-Source Readings

Budget: 16 hours across both phases.

Experiments

E8 is the most professionally valuable experiment in the project. Plot the GC pause distribution — p50, p99, max — against heap size. That plot is the reason your Java service has a p99 problem, and once you have generated it yourself the whole class of production latency mystery becomes legible.

E11 and E12 must be measured separately. Bundling optimisations and reporting a combined speedup is the most common dishonesty in compiler benchmarking. You will probably find constant folding is worth almost nothing on realistic programs — report that.

Benchmarks and Metrics

Use a fixed benchmark set across both phases: fib(25) recursive, an n-body loop, string building, a closure-heavy functional benchmark, a dictionary/object-heavy benchmark, and an allocation-churn benchmark.

Correctness Tests

1. Program suite with expected outputs, run identically against both engines. This is the spine of the project — build it in Phase I milestone 3.
2. The counter-closure test above.
3. Parser precedence table: every operator pair, expected parse tree.
4. Parser round-trip: parse(print(parse(s))) == parse(s).
5. Scope and shadowing in nested blocks and functions.
6. Bytecode size independent of loop trip count.
7. Both engines agree on every program in the suite, bit-for-bit on float output.
8. GC correctness: no live object collected; no garbage retained after a full collection. Verify with an object census, not with "it didn't crash".
9. GC under stress: collect at every allocation. Slow, and it finds root-set bugs nothing else does.
10. Fuzz the parser: random byte strings must produce an error, never a panic or a hang.
11. Type checker soundness: every program it accepts runs without a type error.

Test 9 is the one that matters. A GC bug is a memory-corruption bug that manifests arbitrarily far from its cause; a "collect always" mode turns it into an immediate, reproducible failure.

Failure Tests

Expected Difficulties

1. Rust's ownership model vs an environment chain is Phase I's real difficulty. Environments reference parents and closures capture them, so you need Rc<RefCell<>> — and you should understand why rather than cargo-culting it. Budget the time; this is the intended learning.
2. Closures are harder than they look. Capture semantics are subtle and the difference between capturing a variable and copying its value is invisible until the counter test.
3. The unrolling bug in milestone 9 — see above. It passes every correctness test.
4. GC root sets are easy to get wrong. Anything on the VM stack, in call frames, in upvalues, or in a temporary during a native call is a root. Miss one and you free a live object. The stress mode is your defence.
5. Phase II may not be faster at first, and you now know that is a real possibility rather than a bug. Measure the dispatch loop before assuming.
6. Scope creep is severe here. Everyone wants to add a feature. The language is done when the test suite passes; new syntax is not progress.

Scope Boundaries

In scope: one dynamically-typed language with optional annotations, tree-walk and bytecode engines, mark-sweep GC, three optimisations, a good error-message story.

Out of scope: a JIT; native code generation; LLVM; a standard library beyond a handful of builtins; modules and imports; a package manager; concurrency in the target language; exceptions (return-based errors only); a debugger; self-hosting.

Permitted-library line: no parser generators (lalrpop, pest), no GC crates. logos for lexing is borderline — prefer hand-writing it; the lexer is two days and teaches source-position handling.

Deliverables

1. lang/ — Rust workspace with both engines, sharing a test suite
2. LANGUAGE.md — a grammar and semantics specification. Writing a spec for your own language is a distinct and valuable skill
3. REPORT.md centred on E4 (with the sign-flip story) and E8 (GC pauses)
4. The disassembler and the GC pause histogram — the two most legible artifacts
5. Notebook entries for E4, E8, E11
6. A benchmark suite runnable against both engines

Exit Criteria

Phase I:

• Test suite passes: arithmetic, control flow, functions, closures, scoping
• Counter-closure test passes
• Parser precedence exhaustively tested; fuzzing produces no panics
• Errors carry line and column
• E1 complete: time by AST node type measured
• Phase I report written

Phase II:

• Bytecode VM passes Phase I's entire test suite, unchanged
• Bytecode size independent of loop trip count, asserted
• GC: no leaks under churn; stress mode passes
• E4 complete: AST vs bytecode measured in Rust, compared against the Python result, with the mechanism explained
• E8 complete: GC pause distribution plotted against heap size
• E11 and E12 measured separately
• Type checker catches a type error; overhead measured
• Phase II report written with a falsified prediction

Extension Ideas

• Inline caching for global and property lookup; measure the hit rate. The single highest-value real optimisation in dynamic-language runtimes.
• Generational GC with a measured pause comparison against mark-sweep. The generational hypothesis is testable: measure your own object lifetime distribution first and check whether it holds for your benchmarks.
• Register-based VM compared against the stack VM (the Lua design decision).
• A tracing JIT for hot loops. Large — treat as a separate project if you want it.

Connections

Backward (Phase I): none. Backward (Phase II): Phase I, and P04 for Rust fluency.

Forward:

• → P04: Phase I is your Rust on-ramp; P04 is the payoff
• → P12 (Kernel): dispatch loops become scheduler loops; the GC's root-set traversal and the kernel's page reclamation are the same shape of problem; stack frames become kernel stacks
• → P13 (Tensor): eager vs graph execution is exactly AST-walking vs bytecode, one level up. The dispatch-overhead lesson transfers directly
• → P14: instruction dispatch cost vs arithmetic cost is the same ratio question as kernel-launch overhead vs FLOPs

References

• Nystrom, R. Crafting Interpreters. Genever Benning, 2021. craftinginterpreters.com — free online.
• Pratt, V. R. Top Down Operator Precedence. POPL 1973.
• Aho, A. V., Lam, M. S., Sethi, R., Ullman, J. D. Compilers: Principles, Techniques, and Tools, 2nd ed. Addison-Wesley, 2006. Reference, not a read-through.
• Jones, R., Hosking, A., Moss, E. The Garbage Collection Handbook, 2nd ed. CRC Press, 2023.
• Wilson, P. R. Uniprocessor Garbage Collection Techniques. IWMM 1992.
• Ertl, M. A., Gregg, D. The Structure and Performance of Efficient Interpreters. Journal of Instruction-Level Parallelism 5, 2003.
• Ierusalimschy, R., de Figueiredo, L. H., Celes, W. The Implementation of Lua 5.0. Journal of Universal Computer Science 11(7), 2005. The register-VM argument.
• Deutsch, L. P., Schiffman, A. M. Efficient Implementation of the Smalltalk-80 System. POPL 1984. The origin of inline caching.
• Appel, A. W. Modern Compiler Implementation in ML. Cambridge, 1998.
• Pierce, B. C. Types and Programming Languages. MIT Press, 2002. Chapters 1–11 for the type checker.