Section 3: Bytecode and the Virtual Machine

You have a working language and a specification. Now you build it a second time.

This section designs an instruction set, writes a disassembler, compiles the AST into it, and executes it in a virtual machine — and then, in the lab that matters most, proves the two backends agree on every program you have.

It covers Milestones M6, M7, and M8.

Three things get faster, and they are the three costs you measured in Lab 8:

   TREE WALKER                              BYTECODE VM
   ───────────                              ───────────
   name → hash → walk scope chain     →     stack[base + 3]          one add, one load
   Vec<Value> allocated per call      →     arguments already on the stack, zero alloc
   match on an AST node, chase Box    →     match on a u32 in a flat Vec, no pointer chasing
   Flow enum threaded through frames  →     JUMP
   no place to put a budget check     →     one check in the fetch position covers everything

Notice that only the last two are about "compiled versus interpreted" at all. The first three are about data layout, and that is the real lesson of this section.

What You Build

Module	What it does	Lab
`src/bytecode.rs`	`Op`, `Chunk`, `Proto`, the constant pool, the line table, the disassembler	9
`src/compiler.rs`	AST → `Chunk`: scopes, slot allocation, jump emission and patching	10
`src/vm.rs`	The dispatch loop, `CallFrame`, the value stack, `ember trace`	11
`tests/differential.rs`	Eight lines that turn every test you own into a two-backend test	12
`src/bin/ember.rs`	`ember disassemble`, `ember trace`, `ember run --interp`	9, 11

The Layer You Are Building

                  AST  (unchanged from §1)
                   │
                   ▼
   ┌───────────────────────────────────────────────────────────────────────┐
   │  COMPILER                                          compiler.rs        │
   │                                                                       │
   │   scopes: Vec<Local>  ──▶ NAMES BECOME SLOT NUMBERS                   │
   │   constants: dedup    ──▶ literals become indices                     │
   │   jumps: emit 0, patch later ──▶ control flow becomes offsets         │
   │   protos: nested functions compiled recursively                       │
   └───────────────────────────────────┬───────────────────────────────────┘
                                       │  Chunk { code, constants, lines, protos }
              ┌────────────────────────┴────────────────────────┐
              ▼                                                 ▼
   ┌──────────────────────┐                    ┌───────────────────────────────────┐
   │  DISASSEMBLER        │                    │  VM                       vm.rs   │
   │  bytecode.rs         │                    │                                   │
   │  Chunk → listing     │                    │  loop {                           │
   │  written BEFORE the  │                    │    budget.tick()?;   ← sandbox    │
   │  VM, so you can read │                    │    let op = code[ip]; ip += 1;    │
   │  the compiler's      │                    │    match op { ... }               │
   │  output before       │                    │  }                                │
   │  anything runs it    │                    │                                   │
   └──────────────────────┘                    │  stack:  Vec<Value>   ← operands  │
                                               │                         AND locals│
                                               │  frames: Vec<CallFrame>           │
                                               │          { proto, base, ip }      │
                                               └───────────────────────────────────┘

Note: The disassembler is written before the VM, in Lab 9. That ordering is deliberate: you want to be able to read the compiler's output before anything is executing it, so that when Lab 11's VM produces the wrong answer you already know whether the bytecode was right. Debugging a compiler and a VM at the same time, with no window into the artifact between them, is how people lose a week.

The Concepts, and Where Each Is Treated

Concept	Chapter	Why it matters
What an instruction set is, and how to design one	Instruction Set Design	Thirty decisions, each of which you will revisit in §7
Stack machines versus register machines	Stack vs Register	ADR-002, and the biggest fork in the road
Constant pools, operand widths, encoding	Constant Pools and Encoding	Where "how big is an instruction?" gets decided
Code generation, jump patching, slot allocation	Code Generation	The compiler's three jobs, and the off-by-ones in each
Fetch, decode, execute; dispatch techniques	Dispatch	The loop everything runs in, and what §7 does to it
The normative opcode table	Opcode Reference	Operands, stack before, stack after, errors — for every opcode

The Labs

Lab	Title	Milestone	You end able to run
9	Bytecode and the Disassembler	M6	`ember disassemble x.ember`
10	The Compiler	M7	the whole golden corpus compiles
11	The Virtual Machine	M8	`ember trace x.ember`, and `ember run` uses the VM
12	Differential Testing	M8	`cargo test --test differential`

Deliverables

Every opcode is documented in the opcode reference with operands, stack before, stack after, and possible errors — and a test asserts the documented stack effect matches the implementation.
The disassembler renders constants, line numbers, local names, and absolute jump targets.
Every golden program compiles, and you have read the disassembly of at least three by hand.
Constants are deduplicated: 1 + 1 produces one constant, not two.
Local slots are reused after a block ends.
Jump patching is correct for if/elseif/else, while, for, break, and, and or.
The VM runs the whole corpus and produces byte-identical output to the tree walker.
ember trace prints ip, opcode, and the stack before and after each instruction.
The budget check is in the fetch position, and while true do end terminates with ErrorKind::Limit.
A bytecode validator rejects out-of-range jump targets, constant indices, and slot numbers before execution.
cargo bench re-run; the speedup over docs/learning/baseline-interp.txt is recorded, along with whether your Lab 7 predictions were right.
docs/adr/ADR-002-stack-vm.md written.
docs/learning/05-bytecode.md and 06-vm.md written.

Common Mistakes in This Section

Mistake	Symptom	Correction
Writing the VM before the disassembler	A wrong answer, and no way to tell which of two new components caused it	Lab 9 first. Always.
Jump patching off by one	Loops run one iteration too many or skip the first	Decide once whether an offset names the jump instruction or the one after it, write it in a comment, and print absolute targets in the disassembly. Never debug patching by reading the compiler.
Forgetting to pop	The stack grows monotonically; a long loop OOMs	Every opcode's stack effect is documented. Add a test that runs each golden program and asserts the stack is empty at `Return`.
`and`/`or` compiled as ordinary binary ops	Short-circuiting silently lost	They compile to a jump that keeps the operand. See the opcode reference for `JUMP_IF_FALSE_KEEP`.
Swapping operands for `>` and `>=`	Evaluation order silently reversed	Lua can do this because it does not guarantee operand order. Ember does, so `Gt`/`Ge` are real opcodes. This is an earlier decision charging rent.
Slot numbers assigned per-function instead of per-scope-depth	Locals in sibling blocks collide	Slots are allocated on a stack and released when the scope closes. Check with `ember disassemble` on nested blocks.
Constants stored per occurrence	The pool grows with program size instead of distinct-literal count	Dedup on insert with a lookup map keyed by the value's bit pattern.
Trusting a `Chunk` you did not just compile	A malformed jump index panics or reads out of bounds	Validate before executing. §5 will accept chunks from a cache; the validator is what makes that safe.
Optimizing the VM in this section	An intricate dispatch loop with two remaining bugs	Correctness first. §7 has the benchmarks that justify changes; you do not have them yet.

How to Verify Success

# 1. Read the compiler's output before anything runs it.
ember disassemble -e 'local x = 10 + 20'
ember disassemble -e 'if a then b() else c() end'      # check the jump targets by hand
ember disassemble -e 'while a do b() end'              # the back-edge must go to the CONDITION
ember disassemble -e 'local a = x and y'               # a KEEP jump, and one Pop

# 2. Watch it execute.
ember trace -e 'local x = 10 + 20 * 3 return x'

# 3. The whole corpus, both backends, identical output. THE test.
cargo test --test differential

# 4. The budget is in the fetch position and covers everything.
ember run --max-instructions 1000 -e 'while true do end'; echo $?    # 1
ember run --max-instructions 1000 -e 'local function f() return f() end f()'; echo $?

# 5. Malformed bytecode is rejected, not executed.
cargo test --lib bytecode::validate

# 6. The number you have been waiting for since Lab 7.
cargo bench 2>&1 | tee docs/learning/baseline-vm.txt
diff <(grep time docs/learning/baseline-interp.txt) <(grep time docs/learning/baseline-vm.txt)

Step 3 is the one that gates the section. A VM that runs your examples is not done; a VM that agrees with an independent implementation on every program you own is.

Section Profile: What a Section 3 Graduate Can Do

Design an instruction set for a small language and defend each opcode's existence.
Explain the stack-versus-register tradeoff in terms of dispatch count and decode cost, and name production systems on both sides.
Read a disassembly listing — yours, Lua's, CPython's, or the JVM's — and follow the control flow.
Implement jump patching and explain the off-by-one that everyone hits.
Write a dispatch loop and say where the instruction budget goes and why nowhere else works.
Explain why a bytecode VM is faster than a tree walker in terms of memory and name resolution, not vibes.
Set up differential testing between two implementations and state what it cannot catch.

Next: Instruction Set Design.

Open-Source Engineer & Contributor