Compiling Expressions to Bytecode

Writing a Compiler/Interpreter: Advanced

Chapter 3 · Compiling Expressions to Bytecode

Every chunk so far has been hand-assembled — a real, correct instruction format (Chapter 2), but built by literally writing emit_constant and chunk.write calls in the right order, by hand, every time. That doesn't scale to a real Wisp program. This chapter builds the actual bridge: a compiler that walks the exact same AST Course 1's lexer and parser already produce, and emits a chunk automatically — replacing hand-assembly for good, everywhere from here on.

Reusing Course 1's Own AST — With One Naming Correction

Chapters 1 and 2 of this course used small, standalone Literal/Binary classes for isolated experiments, with a shorthand op field. Course 1's own real AST — the one the actual lexer and parser build, and the one this compiler has to work against for real Wisp programs — uses a different field name, operator, and includes two more node types this course hasn't touched yet: Grouping (a parenthesized sub-expression) and Unary (the - prefix operator). This chapter switches to the real classes, field name and all.

# Course 1, Chapter 3 -- the real AST node classes this compiler compiles
@dataclass
class Binary(Expr):
    left: Expr
    operator: str     # not 'op' -- this is the real field name
    right: Expr
    line: int
    

The Compiler as a Visitor

The shape is deliberately familiar — the same accept()/visit_*() double dispatch Course 1's own Evaluator used. The difference is what each visit_* method does. The Evaluator computed and returned a Python value. The Compiler computes nothing — it emits instructions into a Chunk as a side effect, and returns nothing meaningful at all.

BINARY_OPS = {'+': OP_ADD, '-': OP_SUBTRACT, '*': OP_MULTIPLY, '/': OP_DIVIDE}

class Compiler:
    def __init__(self):
        self.chunk = Chunk()

    def compile(self, expr):
        self.visit(expr)
        self.chunk.write(OP_RETURN, expr.line)
        return self.chunk

    def visit(self, node):
        node.accept(self)

    def visit_literal(self, node):
        idx = self.chunk.add_constant(node.value)
        self.chunk.write(OP_CONSTANT, node.line)
        self.chunk.write(idx, node.line)

    def visit_grouping(self, node):
        self.visit(node.expression)   # no instruction of its own -- see below

    def visit_unary(self, node):
        self.visit(node.right)
        self.chunk.write(OP_NEGATE, node.line)

    def visit_binary(self, node):
        self.visit(node.left)
        self.visit(node.right)
        self.chunk.write(BINARY_OPS[node.operator], node.line)
    

The pattern in every branch is the same: compile the children first, then emit this node's own instruction last. That's not a stylistic choice — it's what makes a stack machine work at all. By the time visit_binary emits OP_ADD, both operands are already sitting on the VM's own stack, pushed there by the two self.visit(...) calls that ran before it. The tree's own shape — which the parser already built correctly, honoring every precedence rule from Course 1, Chapter 2 — becomes the instruction order for free, just by visiting children before parents.

Verified Against Three Independently-Built Trees

Verified directly — Course 1, Chapter 3's own published example tree, compiled and run for the first time

Course 1's own Chapter 3 printed this exact tree for "2 + 3 * 4": Binary(left=Literal(2.0), operator='+', right=Binary(left=Literal(3.0), operator='*', right=Literal(4.0))), and verified it evaluates to 14.0. Compiling that same tree object with this chapter's own Compiler, then running the resulting chunk through Chapter 2's run_vm: 14.0 — a second course, a different execution strategy, the exact same already-published tree, the same answer.

Verified directly — this course's own larger 17-node expression, rebuilt as a real AST and compiled

The expression from Chapters 1-2 (((1+2)*3-4)/5 + ((6-1)*2+3)), this time built with real Binary/Literal nodes instead of hand-assembled bytecode, compiled through Compiler, and run: 14.0 — matching every prior verification of this same expression, on its fourth independently-built representation now (tree-walk, hand-assembled bytecode, and now compiler-generated bytecode from a real tree).

Verified directly — Unary compiles and runs correctly, matching Chapter 2's own hand-assembled result

-(2 + 3) * 4, built as Binary(Unary('-', Binary(Literal(2.0), '+', Literal(3.0))), '*', Literal(4.0)) and compiled: -20.0 — exactly what Chapter 2's Exercise 1 got from hand-assembling the same expression directly.

Grouping Disappears at Compile Time

Grouping exists in the AST because (2 + 3) needs to be a distinct node from a bare 2 + 3 during parsing — without it, the parser has no way to represent "this sub-expression was explicitly parenthesized." But by the time the tree reaches the compiler, that information has already done its job.

Verified directly — a Grouping-wrapped expression compiles to byte-identical bytecode as the unwrapped version

Grouping(Binary(Literal(2.0), '+', Literal(3.0))) and the bare Binary(Literal(2.0), '+', Literal(3.0)) — same expression, one explicitly parenthesized, one not — both compile to exactly 6 code bytes, and those 6 bytes are byte-for-byte identical. visit_grouping emits nothing at all; it just visits the inner expression and returns.

This is exactly why Grouping existed in the first place

Grouping's entire job was already finished once the parser used it to force the correct nesting shape — wrapping 2 + 3 so that a surrounding * 4 multiplies the sum, not just the 3. Once that shape is baked into the tree, the parentheses themselves carry no further information the compiler needs. This is a small, concrete instance of a bigger idea: different stages of a pipeline need different information, and it's fine — expected, even — for something essential at one stage to vanish completely by the next.

The Compiler Trusts the Tree It's Given

One thing the compiler deliberately does not do: check whether the tree's own shape is correct. It has no way to know that. It just walks whatever Binary/Unary/Literal/Grouping structure it's handed and emits matching instructions.

Verified directly — a deliberately mis-shaped tree compiles without a single complaint, and produces a confidently wrong answer

Hand-building a tree for "2 + 3 * 4" as if the parser had gotten precedence wrong — Binary(Binary(Literal(2.0), '+', Literal(3.0)), '*', Literal(4.0)), grouping the + first instead of the * — compiles with zero errors, zero warnings, into perfectly well-formed bytecode. Running it: 20.0, not 14.0. Nothing in this chapter's own machinery detected anything wrong, because nothing was wrong from the compiler's own point of view — it faithfully translated the tree it was given.

This is a real, working division of responsibility, not a gap

Precedence correctness is entirely Course 1, Chapter 2's own job — the parser is where * binds tighter than + gets encoded, once, into how the tree gets built. The compiler's only job is a faithful, mechanical translation of whatever tree it receives. Keeping those two concerns separate means a bug in one is easy to isolate: if a compiled program gives the wrong answer, the very first question is "is the tree shaped correctly?" — checkable independently of anything in this chapter — before ever suspecting the compiler itself.

Where This Connects

This chapter's finding	What it connects to
The compiler reuses Course 1's own lexer and parser, unchanged	The full pipeline is now: Course 1's lexer & parser (unchanged) → this chapter's `Compiler` → Chapter 2's `Chunk` → Chapter 2's `run_vm` — hand-assembly is retired for good
"Compile children before emitting this node's own instruction"	Chapter 5's own jump instructions will break this simple rule on purpose for `if`/`while` — a first hint that control flow needs a genuinely different compilation strategy than pure expressions
The compiler trusts the tree; correctness is the parser's job	Chapter 2's own unknown-opcode guard — that guard catches a structurally invalid chunk; this chapter's finding shows a structurally valid chunk can still be semantically wrong, a different failure mode entirely
Constants are added via `chunk.add_constant`, one per `Literal` node	Chapter 2's own 256-constant ceiling now applies to real Wisp programs automatically — any expression with more than 256 distinct literals will hit it, not just a hand-built stress test

Hands-On Exercises

Exercise 1

Build a tree for the Wisp expression -(-(5)) — a Unary node wrapping a Grouping-wrapped Unary node — using this chapter's own Compiler and Chapter 2's run_vm. Verify the result, and explain in terms of the compiler's own visit_unary method why two negations correctly cancel out rather than, say, doubling the value.

📄 View solution

Exercise 2

Build a flat chain of 256 additions (256 distinct Literal values, chained left-to-right through nested Binary nodes), compile it with this chapter's own Compiler, and confirm it compiles successfully. Then build the same shape with 300 distinct literals instead, and determine whether compiling it through the real Compiler — not a hand-built stress test like Chapter 2's own — hits the exact same 256-constant ceiling, and with the exact same error.

📄 View solution

Exercise 3

Deliberately introduce a bug into BINARY_OPS by mapping '+' to OP_SUBTRACT instead of OP_ADD, then compile and run 2 + 3. Determine the result, and explain why Chapter 2's own unknown-opcode guard (the else: raise RuntimeError(...) added to run_vm) does nothing to catch this specific kind of bug, even though the guard is still present and working exactly as it did in Chapter 2.

📄 View solution

Chapter 3 Quick Reference

Field name correction: Course 1's real AST uses Binary.operator, not the shorthand op Chapters 1-2's own toy examples used
The pattern: compile every child first, then emit this node's own instruction last — the tree's shape becomes the instruction order for free
Verified: Course 1, Chapter 3's own published "2 + 3 * 4" tree compiles and runs to 14.0, matching that chapter's own tree-walking result exactly
Verified: this course's own 17-node expression, rebuilt as a real AST, still compiles to 14.0 — its fourth independently-verified representation
Verified: a Grouping-wrapped expression compiles to byte-identical bytecode as the unwrapped version — parentheses carry no information the compiler still needs
Verified: a deliberately mis-shaped (precedence-broken) tree compiles with zero errors and produces a confidently wrong answer (20.0 instead of 14.0) — the compiler trusts the tree; correctness of shape is the parser's job alone
Next chapter: Global and Local Variables in Bytecode — giving compiled programs somewhere to actually store values between instructions