Compiling instead of interpreting

Step 9 left birch in good shape: a file mode, a REPL, one environment across a session, and errors that point before they explain. What it is not is fast. Every statement pays for the whole pipeline on every run — scan, parse, then an evaluator that re-walks the tree from the root, making the same decisions at the same nodes it made last time. This last article is not about adding a feature. It is about the step the language does not take, why every serious interpreter takes it, and what it would look like here: compiling the tree once into bytecode, and running the bytecode instead of the tree.

No new code ships with this step — birch at interpreter-ch09 is the finished language, unchanged. What follows is the map of the territory the track stops short of.

Where the tree walk spends its time

Run one statement — x * x; — and count what the evaluator does. execute matches the statement, calls evaluate on the expression, which matches Expr::Binary, recurses into both operands, follows two Box pointers into two more evaluate calls, matches those variants, and only then does the multiplication. Every one of those steps is a real cost: a function call per node, a match per node to decide what the node even is, and a pointer chase per child — the tree lives on the heap wherever the allocator put it, and walking it is a tour of unrelated addresses.

Now run the same statement a thousand times inside a while. Nothing changes. The variant tests come back the same every iteration, the boxes point to the same children, and the recursion enters and exits the same functions two thousand more times. The tree is a description of the program, and the evaluator reads the description from scratch each time it needs to act on it.

That is the tax every tree-walking interpreter pays, and it is the reason none of them stop there.

The other shape: compile once, then run

The alternative is to split deciding from doing. Walk the tree one last time — but instead of evaluating, emit instructions: a flat list of simple commands for a machine that does not exist yet. That list is bytecode, and the machine that runs it is a small loop with a program counter and a value stack.

2 + 3 * x; compiled to such a list looks like this — a listing in birch’s own vocabulary, written out rather than printed, because birch stops before this step:

0  PushConst   2.0
1  PushConst   3.0
2  PushLocal   x
3  Multiply
4  Add
5  Print

Running it needs no tree at all. The loop reads instruction 0, pushes 2.0 on the stack; instruction 1 pushes 3.0; instruction 2 pushes the value of x; instruction 3 pops two values and pushes their product; instruction 4 does the same for the sum; instruction 5 prints what is left. One loop, one integer index, one stack. The multiplication did not require deciding that a node was a Binary with a Star token — that decision was made once, at compile time, and turned into a single instruction.

Control flow is where the shape really pays. The tree-walking while re-enters evaluate for the condition and execute for the body on every iteration, re-walking the same subtrees. Compiled, the whole loop is a straight line with two jumps in it:

0  PushLocal    i
1  PushConst    3.0
2  Less
3  JumpIfFalse  9
4  PushLocal    i
5  PushConst    1.0
6  Add
7  StoreLocal   i
8  Jump         0
9  ...          // the code after the loop

The condition compiles to instructions 0–2, the body to 4–7. Less leaves a bool on the stack; JumpIfFalse pops it and, when it is false, moves the program counter to 9 — past everything. Otherwise the body runs and Jump sends the counter back to 0 to test the condition again. The loop became two instructions. Nothing is re-walked, because there is nothing left to walk: the compiler already turned the shape of the program into the order of the list.

The compiler is the evaluator, walking once

The pleasant surprise is how little of birch the change touches. The scanner and the parser are untouched — they already produce the tree, and the tree is the compiler’s input. The compiler itself walks that tree in the same order evaluate does, children first, but its match arms emit instead of computing:

// evaluate, per Binary node: run both sides, then apply the operator
// compile, per Binary node: compile both sides (they land in order),
// then append one instruction for the operator

The arms stop returning Result<Value, RuntimeError> — at compile time there are no runtime errors to have. What compiles to what is a decision the tree already encodes. Along the way, the compiler can pay for work once that the evaluator would otherwise pay per run: constant literals go into a pool that instructions reference by index, and — the bigger win in a real implementation — names can be resolved against known scopes and turned into slot numbers, so PushLocal i is an array index at run time instead of a walk down a chain of HashMap scopes asking each one for the key. birch’s environment does that walk on every variable read; a compiled birch would do the walk once, at compile time, and record the answer.

Runtime errors do not disappear — 1 / 0; fails when it runs, not when it compiles — but they keep their addresses: an instruction can carry the line and column of the token it came from, which is why the tree stored whole tokens in the first place.

Why it is faster

Every mechanism above removes work from the run-time path:

• One dispatch loop instead of recursion per node. The evaluator pays a function call, a match, and pointer-chasing per node. The bytecode loop pays one match per instruction, and the instructions sit in a contiguous Vec — the next one is usually already in cache, where the next tree node is wherever the allocator left it.
• Decisions made once. The variant tests, the constant parsing, the scope-chain walks: the tree walker redoes all of it on every run. Compiled, they are baked into the instruction list, and a thousand executions of the same statement reuse the answers.
• Control flow is data. A loop or a branch moves an integer; nothing re-enters the evaluator, no subtree is revisited, and a function call is a saved program counter and a fresh frame — the same idea as the scopes call pushes today, but with a return address instead of unwinding by returning through recursion.
• The stack beats result plumbing. Operands meet on a Vec<Value>; there is no Result threading up through nine levels of recursion and no Flow enum carrying returns to the call site — Return becomes an instruction that jumps to the frame’s saved address.

How much faster depends on the implementation, and honest answers come from measuring, not from this page. But the direction is not in doubt in practice: it is the reason CPython, Lua, the JVM and every JavaScript engine keep their programs in this form rather than walking trees, and it is why the gap between a toy tree-walker and a real interpreter is roughly the gap this article has been describing.

Everyone does this

The move is not exotic — it is the standard next step, and most languages readers already use took it visibly.

CPython compiles every .py file to bytecode before running it, and does not hide the fact — the standard library’s dis module prints the listing, the same shape as the two above, for any function. When a Python file gains a .pyc beside it, that is the compiled form being cached so the next run skips the compile. Lua compiles every chunk to bytecode too, and its VM is register-based rather than stack-based — instructions name slots instead of pushing and popping — a refinement of the same idea. The JVM runs bytecode from any language that can compile to it, which is the whole reason Java, Kotlin and Scala can share a runtime. JavaScript engines start the same way: parse to bytecode, run it in a fast interpreter, and — for code that runs hot — compile the bytecode further, into machine code, while the program is running. WebAssembly is the same pattern once removed: a binary instruction format for a virtual machine, so any language that compiles to it runs anywhere the VM is installed.

Reading the list back, one pattern is hard to miss: the fastest way to run a program slowly many times is to interpret its source each time; the fastest way to run it once more is to compile it once and keep the compiled form. birch’s REPL is already halfway there — it keeps the environment across the session, so only the work of re-reading each line is repeated.

What birch would need

The full build is a track of its own, and this track has said its piece — but the skeleton fits on this page, because it is the same three enums the whole project has run on:

enum Instruction {
    PushConst(Value),
    PushLocal(usize),
    StoreLocal(usize),
    Add, Subtract, Multiply, Divide,
    Less, Equal,
    JumpIfFalse(usize),
    Jump(usize),
    Call { args: usize },
    Return,
    Print,
}

// the run loop, in full:
// let mut stack: Vec<Value> = Vec::new();
// let mut pc = 0;
// while let Some(instruction) = &code.get(pc) {
//     pc += 1;
//     match instruction { /* push, pop, jump: set pc instead of recurse */ }
// }

The scanner, parser and tree stay as they are; compile replaces evaluate as the thing that consumes the tree, and the REPL’s loop gains one stage — scan, parse, compile, run — with the compiled form of each declaration ready to run again without any of the earlier stages. Everything else the track built carries over: the tokens, the positions, the printer for debugging, the truthiness rule, the value type. That is the quiet payoff of building each stage as an enum with a match: the next stage is another match, not a rewrite.

Where this leaves the track

Ten steps, in the order they happened: a grammar and a promise; a scanner that knows where every character sits; a Pratt parser that gets precedence out of one binding-power table; a tree as Rust enums, with Box wherever recursion needed breaking; a tree-walking evaluator; environments as a chain of scopes; if, while, calls and returns; errors that point at the token that caused them; a REPL that can tell wrong from not finished yet; and this — the account of the step beyond.

The language at interpreter-ch09 runs real programs and fails honestly, and the track’s ledger of what it lacks is worth reading plainly. Functions see the caller’s variables, not the ones in scope where they were defined — there are no closures yet, and the step 7 article says so in exactly those words. Function values are kept alive by Rc, which is enough for these programs but is not a collector. Names are looked up by walking scope chains at run time. And programs run by walking the tree, for the reasons this article gave. None of those gaps is a secret; each one was named when it was left behind, and each is a project of its own.

The transferable part is the shape, not the language. Every stage of this track was the same move: model the possibilities as an enum, let match force every case to be handled, and add the next stage by writing another match. Scanning, parsing, evaluating, error reporting and — had the track gone one further — compiling are all that move at different depths. The track overview has the full itinerary, and structs, enums, and pattern matching is where the move itself is taught.