Skip to content
Tutorials Center
My learning

Topics

Lesson 53 of 61 ยท Projects

Project: Compiler and VM for the Toy Language

Turn the Tiny interpreter into a compiler: generate stack bytecode with locals, globals and calls, add AST and peephole optimizers, a disassembler and a VM.

The previous project ran Tiny by walking its syntax tree. That is easy to write, but every pass over a loop re-examines the same nodes. In this project you will build the other kind of implementation: a compiler that translates a Tiny program once into a flat list of bytecode instructions, a virtual machine that executes them, two small optimizers that make the code shorter, and a disassembler that lets you read what the compiler produced.

The front end is exactly the lexer and parser from the toy language project, so the code below repeats it unchanged. To keep the focus on code generation, this project leaves out the static checker and trusts the program to be sensible. The compiler still reports the mistakes it cannot avoid noticing, such as an undeclared name or a function it cannot compile. The ideas used here come from bytecode and virtual machines and from local optimizations.

What the compiler supports

A bytecode VM wants fixed, predictable memory locations, and that shapes the language subset:

  • Functions are declared at the top level and called by name. A function nested inside another function would need closures (captured variables that outlive their function), which require a more elaborate design. The compiler rejects such programs with a clear message.
  • Top-level let variables are globals, stored by name in a table. Every function can read and assign them.
  • All other variables are locals. Parameters and every let inside a function or a block get a numbered slot in the frame of the running function, which is much faster than a name lookup.
  • Everything else in Tiny works: integers, booleans, strings (as constants), arithmetic, comparisons, and/or with short-circuiting, if/else, while, recursion and mutual recursion.

The instruction set

Every instruction is [opcode, operand, position]. The position is the source line and column, kept so that the VM can report run-time errors with a caret.

Instruction Operand Effect on the stack
CONST a value pushes the value
LOAD / STORE local slot push the slot / pop into the slot
GLOAD / GSTORE global name push the global / pop into the global
ADD SUB MUL DIV MOD none pop two, push the result
LT LE GT GE EQ NE none pop two, push a boolean
NEG NOT none pop one, push one
JUMP target index no stack change
JUMP_IF_FALSE target index pops a condition; jumps if it is false
CALL function number pops the arguments, starts a new frame
RET none ends the frame; the return value stays on the stack
PRINT / POP none pop one value (print it / discard it)
HALT none stops the machine

The compiler produces one code object per function: its name, the number of parameters, the number of local slots, and its instruction list. Code object 0 is always <main>, the top-level program.

flowchart LR
    S["Source"] --> P["Parse (AST)"]
    P --> F["Fold constants<br/>and dead branches"]
    F --> G["Generate bytecode<br/>(one code object per function)"]
    G --> H["Peephole pass<br/>(clean up the code)"]
    H --> V["VM runs it"]
    H --> D["Disassembler prints it"]

The pipeline of this project. The optimizers sit on both sides of code generation: one works on the tree, one on the instructions.

Step 1: the virtual machine

Start with the part that makes bytecode run. The VM keeps one operand stack for the whole program and a stack of frames, one for each active function call. A frame holds the code object being run, the next instruction to execute (pc) and the function's local slots. Running a program is a loop: fetch the instruction at the top frame's pc, advance pc, and carry out the instruction.

CALL is the interesting one. It pops the arguments (in reverse, because the last argument is on top), saves the current frame on the frame stack, and starts a new frame whose first slots are the arguments and whose remaining slots start empty. RET simply drops the top frame, which resumes the caller exactly where it stopped; the return value is already on the operand stack for the caller to use. There is no separate "return address" because every frame remembers its own pc.

The next program contains the VM and two hand-assembled code objects: a recursive fact and a <main> that calls it and uses a global variable. Read the instructions next to the comments, which show the Tiny source each group came from.

Python Step 1: the VM with hand-written bytecode

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Six instructions in fact handle the base case (LOAD n, CONST 1, LE, JUMP_IF_FALSE, then CONST 1 and RET). The recursive case loads n, computes n - 1, calls fact again and multiplies the result by the n that was loaded earlier. That earlier value waits on the operand stack during the recursive call, which is why the stack is the natural place for temporary values. The deepest call stack is 5 frames, one for each of fact(5) to fact(1); the <main> frame is waiting underneath. The last test builds a bad instruction by hand to show that a run-time error carries the position stored in the instruction (line 3, column 11).

Step 2: code generation

The compiler is a recursive walk over the AST, one method for statements and one for expressions, with a few key decisions.

Locals and scopes. Each function compiler keeps a stack of scope dictionaries that map names to slot numbers. Parameters take the first slots. Every let gets the next free slot, and a new { ... } block pushes a scope so that an inner let x shadows an outer one without changing it. Slots are never reused, which wastes a few but keeps the compiler obviously correct. The program body is compiled in a mode where there is no scope for the top level: a let there is a global, while a let inside an if or while at the top level is an ordinary local of <main>. That is how the shadowing example prints 99 and then 10.

Expressions are compiled in post-order, as in the earlier projects: operands first, then the operator. and and or do not use an instruction of their own. They compile to a conditional jump so that the right operand is skipped when the left operand has already decided the answer.

Control flow uses labels that are patched after the fact. if emits JUMP_IF_FALSE with an unknown target, compiles the branch, and then fills in the target. while remembers the index of its condition, emits the conditional exit jump, compiles the body and emits an unconditional JUMP back to the top.

Calls. The callee must be a plain name that refers to a top-level function. The compiler checks the argument count, compiles the arguments left to right and emits CALL with the function's number. Function numbers are assigned before any code is generated, which is why mutual recursion works.

The safety net. A function body might end without a return, so the compiler adds CONST none; RET at the end of every function, and HALT at the end of <main>. If every path already returns, that extra code can never run, and the peephole pass below deletes it.

Step 3: two optimizers

The first optimizer works on the tree, before code generation. It folds constants: 60 * 60 + 24 becomes the literal 3624, comparisons of literals become booleans, and true or boom() becomes true because a literal left operand decides the result without looking at the right. It also removes dead branches: an if whose condition is a literal keeps only the branch that can run, and a while (false) disappears. Division is only folded when the divisor is not zero, so 1 / 0 is left in the program and fails when (and if) it runs. One detail needs care: a branch is inlined into the surrounding code only if it declares no variables of its own, because dropping the braces would otherwise change which names are visible.

The second optimizer is a peephole pass over the finished instruction list. It does three jobs:

  1. Remove unreachable code. A flood fill from instruction 0 follows jumps and fall-through, and everything it never reaches is deleted. This removes the safety net after functions whose paths all return.
  2. Remove useless push-and-pop pairs. A CONST, LOAD or GLOAD immediately followed by POP computes a value only to throw it away, as in the statement 1 + 2; after folding. The pair may not be removed if the POP is the target of a jump, because another path arrives there with a real value on the stack that the POP must still discard. (Forgetting this rule is a classic peephole bug.)
  3. Remove a jump to the next instruction.

Deleting instructions shifts every later index, so the pass builds a map from old to new positions and rewrites every jump target.

Step 4: the whole thing

Below is the complete compiler: front end, optimizers, code generator, disassembler and VM, followed by a demonstration. The program compiles a Tiny source twice, with and without optimization, prints the size and the number of executed instructions, disassembles two code objects, runs a test suite whose expected outputs were worked out by hand, and ends with an error gallery.

Python The complete Tiny compiler and VM

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first two lines are the effect of the optimizers. Both versions print the same output (24, 70, folded, true), but the optimized program has 64 instead of 89 instructions and executes 2,393 instead of 2,446. Most of the saved executions come from the loop condition i < 5 * 4: unoptimized, it pushes 5, pushes 4 and multiplies on every one of the 21 checks; optimized, it is a single CONST 20.

Now read the disassembly. In <main> you can see the globals (GSTORE 'seconds', GLOAD 'i'), the constant 3624 that replaced 60 * 60 + 24, and the loop: the line marked >> at index 6 is the jump target at the top, and the JUMP 6 at index 21 closes the loop. The if (2 > 3) has vanished completely, leaving only CONST 'folded' and PRINT. In gcd there are no GLOAD instructions at all, because a, b and t are locals: parameters take slots 0 and 1, and let t takes slot 2, so the header reports three locals. Notice also that gcd ends right after its final RET; the safety net is gone.

The tests compare the output of both optimization levels against the expected output, which catches optimizer bugs. The short-circuit test is a good example: false and boom() must not print boom. The error gallery shows that run-time errors point at the right spot in the source because every instruction carries its position.

Ideas for extending the compiler

  • Closures. Allow nested functions by capturing variables in "upvalues" that are moved to the heap when their frame ends, the technique used by Lua.
  • More peephole rules. Replace CONST 0; ADD with nothing, fold NOT followed by JUMP_IF_FALSE, or thread jumps that land on other jumps.
  • A constant pool, so each instruction carries a small index instead of a Python value, as real bytecode formats do.
  • Binary encoding. Write the instructions to a bytes object, as in the bytecode lesson, and decode them in the VM.
  • Differential testing. Run every program through both the interpreter of the previous project and this VM, and compare the outputs.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does the compiler keep locals in numbered slots instead of looking up names at run time?

    The compiler already knows which variable each name refers to, so it can replace the name by an index. At run time, reading a local is just an array access.
  2. 2. The peephole pass must not remove a CONST followed by POP when the POP is a jump target. Why?

    With short-circuit expressions used as statements, two different paths both end at the same POP. Removing the POP would leave a value behind on one of them.
  3. 3. What does the VM do when it executes RET?

    Each frame stores its own program counter. Dropping the callee's frame resumes the caller right after its CALL.
  4. 4. Why does the optimizer leave 1 / 0 in the program instead of folding it?

    Folding must never change behavior. If the division sits in code that never executes, the program is fine; if it executes, it must report the error at run time.

Summary

  • A compiler translates the tree once into bytecode; the VM then only fetches, decodes and executes, with no tree walking.
  • Locals live in numbered slots of the current frame, top-level variables are globals, and each function call creates a frame that remembers its own program counter.
  • Control flow becomes jumps whose targets are patched after the body is compiled; and and or become conditional jumps.
  • An AST optimizer folds constants and removes dead branches; a peephole pass removes unreachable code, useless push-pop pairs and jumps to the next instruction, and must remap every jump target afterwards.
  • A disassembler makes the compiler's output visible and is the best debugging tool for code generation.
  • Comparing optimized and unoptimized runs against expected output is a cheap way to catch miscompilations.

Next: Project: A JSON Parser and Pretty-Printer