Why Bytecode? From Tree-Walking to a Virtual Machine

Writing a Compiler/Interpreter: Advanced

Chapter 1 · Why Bytecode? From Tree-Walking to a Virtual Machine

Course 1 built a complete, working implementation of Wisp — the same toy language this course continues — as a tree-walking interpreter: source text becomes tokens, tokens become an abstract syntax tree, and running a program means recursively calling accept()/visit_*() on that tree, over and over, every single time a piece of code executes. It works. It's also not how any serious language implementation actually runs code — Python itself, Lua, the JVM, and V8 all compile to some form of bytecode first: a flat, linear sequence of simple instructions, executed by a small virtual machine instead of a recursive tree walk. This course rebuilds Wisp's own runtime that way. This chapter asks the obvious question first, honestly, instead of assuming the answer: is bytecode actually faster, and if so, why?

What Stays, What Changes

Nothing from Course 1's own front end is being thrown away. The lexer (Chapter 1) and the recursive descent parser (Chapters 2-3) already do their job correctly — they turn Wisp source text into an AST, and that part of the pipeline doesn't care what happens to the tree afterward. What changes is everything downstream of the AST.

Stage	Course 1 (Fundamentals)	Course 2 (this course)
Lexing & parsing	Unchanged — reused exactly as built in Course 1, Chapters 1-3
After the AST	The `Interpreter` walks the tree directly, recursively, every time the program runs	A compiler walks the tree once, producing a flat list of instructions
Execution	Python's own call stack, one frame per AST node visited	A small stack-based virtual machine: one flat loop, an explicit data stack, no recursion per instruction
Function calls	A new Python `Environment` per call, tied to Python's own recursive call stack (Course 1, Chapter 7)	Explicit call frames on the VM's own frame stack (Chapter 6)
Memory	Python's own garbage collector, invisibly	A real, hand-written mark-and-sweep collector (Chapter 8)

Measuring the Real Cost of Tree-Walking

Before assuming bytecode is faster, it's worth actually building the smallest honest version of both and timing them. Here's a tree-walking evaluator matching Course 1's own shape — dataclass nodes, double dispatch through accept()/visit_*() — next to a bytecode compiler and a minimal stack-based VM for the same arithmetic:

# Tree-walking (Course 1's own shape)
class TreeWalkEvaluator:
    def visit_binary(self, node):
        left = node.left.accept(self)
        right = node.right.accept(self)
        if node.op == '+': return left + right
        if node.op == '-': return left - right
        # ... '*' and '/' the same way

# Compile the SAME tree to a flat instruction list, once
def compile_expr(node, out):
    if isinstance(node, Literal):
        out.append(('PUSH', node.value))
    elif isinstance(node, Binary):
        compile_expr(node.left, out)
        compile_expr(node.right, out)
        out.append((op_name(node.op),))

# A minimal stack-based VM -- one flat loop, no recursion
def run_vm(code):
    stack = []
    for instr in code:
        op = instr[0]
        if op == 'PUSH': stack.append(instr[1])
        elif op == 'ADD': b=stack.pop(); a=stack.pop(); stack.append(a+b)
        # ... SUB, MUL, DIV the same way
    return stack.pop()
    

Both were run on the exact same expression — a 17-node tree computing ((1+2)*3-4)/5 + ((6-1)*2+3) — evaluated 300,000 times, timing the median of 9 runs to cancel out system noise.

Verified directly — at this scale, the tree-walker is actually faster than the bytecode VM

Tree-walking: 1.051 microseconds per evaluation. Bytecode VM: 1.374 microseconds per evaluation. The VM is roughly 24% slower, not faster — the opposite of what "bytecode is faster" would predict.

This isn't a bug in the VM — it's an honest, structural fact about running bytecode in Python

Real bytecode VMs (CPython's own C-level interpreter, or a hand-written VM in C) are fast because their instruction dispatch loop compiles down to machine code — a tight, predictable loop with cheap branching. A VM written in Python, interpreting its own separate instruction format, is still running on top of Python's own interpreter the whole time. Both the tree-walker and this VM pay Python's own per-operation overhead; the VM just adds a second layer of interpretation on top, for a small 17-instruction program. Building a bytecode VM in the same host language as the tree-walker doesn't automatically buy a speedup — it has to earn it a different way.

The Same Comparison at Real Program Scale

A 17-node arithmetic expression isn't a realistic Wisp program, though — a real script has loops, function bodies, and expressions nested far deeper than one line. Repeating the exact same measurement on a much larger expression (a 201-node chain, then a 601-node one) tells a genuinely different story:

Expression size	Tree-walk (median)	Bytecode VM (median)	Ratio
17 nodes	1.051 µs/eval	1.374 µs/eval	0.765× — VM slower
201 nodes	27.382 µs/eval	16.318 µs/eval	1.678× — VM faster
601 nodes	84.893 µs/eval	49.620 µs/eval	1.711× — VM faster

Verified directly — the VM's advantage isn't fixed, it grows with program size, and eventually flips the result entirely

At 17 nodes the tree-walker wins. At 201 nodes and beyond, the VM wins by a consistent, repeatable ~1.7× — confirmed at two different larger sizes, not a one-off measurement.

Why size changes the answer

Every node the tree-walker visits costs a real Python function call — accept(), then visit_binary(), then two more recursive accept() calls for the children. Python function calls carry real, fixed per-call overhead (a new stack frame, argument binding, a return). The VM pays a similar per-instruction cost inside its loop — but only once per instruction, via plain iteration, never via a nested function call. As the program grows, the tree-walker's cost compounds with both the number of nodes and the cost of recursing through them, while the VM's cost grows only with instruction count. Small programs don't run long enough for that difference to matter; larger ones do.

The Other Cost: Recursion Depth Itself

There's a second, sharper problem with recursive evaluation that has nothing to do with speed: it can simply fail, on a program that's done nothing wrong except be deeply nested. Python's own call stack has a limit — sys.getrecursionlimit(), 1000 by default — and every accept()/visit_*() pair the tree-walker uses to evaluate one level of nesting consumes two of those frames, not one.

Verified directly — double dispatch costs almost exactly double the usable recursion depth

A left-deep chain of nested Binary nodes, evaluated via accept()/visit_binary(): the deepest chain that evaluates without crashing is 497 levels — depth 498 raises RecursionError. The same chain walked by one single plain recursive function (no accept()/visitor indirection, just a direct call) survives to 996 levels — almost exactly 2× as deep, because each tree level costs one Python stack frame instead of two.

A real Wisp program can absolutely produce nesting this deep — a long chain of string concatenation, a deeply recursive data structure literal, or (as Course 1's own Chapter 7 measured directly) a recursive Wisp function calling itself: exactly 163 levels at Python's default recursion limit, since each nested WispFunction call also rides Python's own call stack. That's a different code path than the expression-nesting case above, but the same underlying cause: recursive evaluation ties Wisp's own limits to the host language's stack, in a way a Wisp programmer has no way to reason about or predict.

Verified directly — a flat instruction loop is never at risk, at any depth, because it never recurses per node

A tree 5,000 levels deep is compiled once (using a temporarily raised recursion limit just for that one compile pass — the compiler itself is still recursive, but only runs a single time) into 10,001 flat instructions. Running that same precompiled bytecode through run_vm() 500 times in a row, at Python's completely normal, unraised default recursion limit, succeeds every single time. run_vm()'s own for loop never grows the Python call stack no matter how deep the original expression was — depth only affects how many instructions there are, not how deep any single execution needs to recurse.

Forward reference — this is exactly what Chapter 6 fixes for function calls

The 163-level ceiling Course 1 measured for recursive Wisp functions exists because each nested call allocates a new Python stack frame via Python's own visit_call recursion. Chapter 6 of this course ("Functions & Call Frames") gives the VM its own explicit call-frame stack — a Python list, not the interpreter's own call stack — so a deeply recursive Wisp function will no longer be bounded by Python's recursion limit at all. That's not a hypothetical benefit; it's the direct, structural fix for a real limitation this exact course already measured.

Where This Connects

This chapter's finding	What it connects to
A naive same-language VM is slower at small scale, faster at larger scale (~1.7×)	Sets realistic expectations for this course's own Chapter 10 capstone, which will benchmark tree-walking against the finished VM on a real, moderately complex program — not a toy expression
Double-dispatch tree-walking costs ~2× the usable recursion depth of a single recursive function	Explains, precisely, why Course 1's own Chapter 7 measured a 163-level function-call ceiling rather than something closer to Python's raw 1000-frame limit
A flat instruction loop never recurses per node, at any depth	Chapter 6's own call-frame stack, which removes the 163-level ceiling entirely by giving Wisp function calls an explicit frame stack instead of Python's own call stack
The lexer and parser are unchanged from Course 1	Chapter 3's compiler reuses the exact same AST node classes Course 1, Chapter 3 already built — nothing about the front end needs to be rewritten

The Road Ahead

Chapter	Builds
2	Chunks, opcodes, and a minimal fetch-decode-execute VM loop
3	A single-pass compiler emitting bytecode directly from Wisp source
4	Global and local variables — locals resolved to stack slots at compile time
5	Control flow via jump instructions and backpatching
6	Functions and call frames — the fix for this chapter's own 163-level finding
7	Closures and upvalues
8	A real mark-and-sweep garbage collector
9	Classes, instances, and method dispatch in bytecode
10	Capstone — benchmarking the finished VM against Course 1's own tree-walking interpreter, on the same program

Hands-On Exercises

Exercise 1

Using this chapter's own TreeWalkEvaluator and run_vm(), build a left-deep expression of depth 300 (601 nodes) and time both approaches evaluating it 20,000 times (median of several runs). Confirm whether the ratio found in this chapter (~1.7× in the VM's favor at 201 nodes) holds, grows, or shrinks at this larger size.

📄 View solution

Exercise 2

Write a single plain recursive Python function (no accept()/visitor split at all — just one function calling itself directly on node.left and node.right) that evaluates the same left-deep Binary chain this chapter used for its recursion-depth test. Find its own maximum working depth via binary search, and confirm it lands close to double the tree-walker's own 497-level limit.

📄 View solution

Exercise 3

Rewrite this chapter's own run_vm() to use small integer opcodes (e.g. 0 for PUSH, 1 for ADD) instead of string comparisons, and re-run the 17-node, 300,000-evaluation benchmark from this chapter. Determine whether removing the string comparisons closes the gap with tree-walking, narrows it, or has no real effect — and explain your result in terms of what the benchmark is actually measuring.

📄 View solution

Chapter 1 Quick Reference

Reused unchanged from Course 1: the lexer and the recursive descent parser — only what happens after the AST changes
Verified: at small scale (17 nodes), a naive same-language bytecode VM is ~24% slower than tree-walking, not faster
Verified: at larger scale (201-601 nodes), the same VM is consistently ~1.7× faster — the advantage grows with program size, not a fixed constant
Verified: double-dispatch tree-walking (accept()/visit_*()) survives to depth 497 before RecursionError; a single recursive function survives to depth 996 — ~2×, from one stack frame per level instead of two
Verified: a precompiled flat instruction list runs correctly at any depth, any number of times, at Python's normal recursion limit — the VM's own loop never recurses per node
Connects directly to: Course 1 Chapter 7's own 163-level recursive-function ceiling, resolved structurally by this course's own Chapter 6
Next chapter: Chunks, Opcodes & a Stack-Based VM — building the real instruction format and execution loop this chapter only sketched