Lesson 0.2 — Interpreters: tree walkers, bytecode VMs and dispatch¶
Techniques: tree-walking interpreters, stack-based bytecode VMs, register-based bytecode VMs, dispatch (switch, direct and indirect threading) · Pebble uses:
pir-run, a reference interpreter that walks PIR's control-flow graph · Lab: tree-walker vs stack VM (switch and threaded dispatch) vs JIT, labs/ch00-exec · Prerequisites: Lesson 0.1 · Time: 5–7 hours
An interpreter runs a program without first translating it to machine code. Here is the same six-line loop run by three interpreters that ship on the course machine:
| system | what it interprets | command |
|---|---|---|
| LLVM | LLVM IR, instruction by instruction | lli -force-interpreter sum.ll |
| CPython 3.11 | stack bytecode | python3 -c 'import dis; …' |
| V8 12.4 (Node 22) | register/accumulator bytecode (Ignition) | node --print-bytecode … |
They differ in what they interpret (a tree, a stack code, a register code) and how they get from one instruction to the next (dispatch). This lesson makes both precise, using the Tiny language of the lab as the running example.
1. Problem and motivation¶
The problem. Given a program \(p\) in a language \(L\) with a formal semantics (Definition 0.2.2), compute \(\mathrm{Beh}(p)\) (Lesson 0.1, Definition 0.1.1) directly, with a program written in a host language, as fast as possible and with as little up-front work as possible.
Tree-walking interpreters¶
The oldest and simplest interpreter evaluates the syntax tree recursively, one function case per construct. McCarthy's eval for LISP (1960) is the original [McC60]; it is still how many languages start (Ruby before YARV, early JavaScript engines, Crafting Interpreters' jlox [Nys21]). It is the executable form of a big-step semantics, which makes it the natural reference implementation: pir-run plays that role for Pebble, and the lab's tree-walker is the oracle the other engines are tested against. Its weakness is speed: every node visit costs a function call, a type switch and pointer chasing through a tree that the processor cannot prefetch well.
Stack-based bytecode VMs¶
Compile the tree once into a flat array of compact instructions for an abstract machine with an operand stack, and interpret that array instead. Operands are implicit (on the stack), so instructions are short and the compiler is trivial (postorder emission). Pascal's P-code (1970s), Smalltalk-80, the JVM, .NET's CIL, CPython and WebAssembly all use stack bytecode [Dragon2, §2.8]. The stack-code compiler in this lesson (Algorithm 0.2.5) is the one the lab asks for.
Register-based bytecode VMs¶
Stack code spends instructions moving values onto the stack. A register VM names its operands explicitly (ADD r1 r2 r3), like a machine with many registers stored in the frame, so each operator is one instruction. Lua 5.0 switched from a stack to a register VM and reports fewer instructions and faster execution [IdFC05]; Shi et al. translated JVM stack code to register code and report, in their abstract, that more than 47% of executed VM instructions are eliminated while the code grows by roughly 25%, and that execution time on a Pentium 4 with switch dispatch drops by 32.3% [SGBE05]. V8's Ignition (with an accumulator), Dalvik and LuaJIT's interpreter are register VMs.
Dispatch: switch and threaded code¶
Every bytecode interpreter has a dispatch step: find the handler of the next instruction and jump to it. The obvious C implementation is a switch inside a loop. Bell's threaded code [Bel73] instead stores handler addresses in the code, so each handler ends with a jump straight to the next handler. Ertl and Gregg showed that on the processors of the 2000s the indirect branch of dispatch dominates interpreter cost and that threaded code halves its mispredictions [EG03]; later work shows modern predictors narrow (but do not erase) the gap [RSS15]. CPython uses computed-goto threading when the C compiler supports it; the lab measures both.
2. Definitions and algorithms¶
Definition 0.2.1 (Tiny: abstract syntax and states)
Let \(\mathbb{Z}_{64} = \{-2^{63}, \dots, 2^{63} - 1\}\) and \(\mathrm{Var}\) a set of identifiers. Expressions, statements and programs are
where \(\bar{s}\) is a (possibly empty) sequence of statements. A state is a total map
\(\sigma : \mathrm{Var} \to \mathbb{Z}_{64}\); the initial state is \(\sigma_0 = \lambda x.\,0\).
The concrete grammar (precedence, # comments) is in the lab
SPEC.
Definition 0.2.2 (Big-step semantics of Tiny)
Let \(\mathrm{wrap}(n)\) be the unique \(v \in \mathbb{Z}_{64}\) with \(v \equiv n \pmod{2^{64}}\). Operators are total functions on \(\mathbb{Z}_{64}\): \(a \mathbin{\hat{+}} b = \mathrm{wrap}(a + b)\) (likewise \(-\), \(*\)); \(a \mathbin{\hat{/}} b = 0\) if \(b = 0\), \(\mathrm{wrap}(-a)\) if \(b = -1\), and \(\mathrm{trunc}(a / b)\) otherwise; \(a \mathbin{\hat{\%}} b = a\) if \(b = 0\), \(0\) if \(b = -1\), and \(a - b \cdot (a \mathbin{\hat{/}} b)\) otherwise; comparisons return \(1\) or \(0\). The judgments \(\langle e, \sigma \rangle \Downarrow v\) and \(\langle \bar{s}, \sigma \rangle \Downarrow \sigma'\) are the least relations closed under:
where \(\bar{b}_v\) is \(\bar{b}_1\) if \(v \ne 0\) and \(\bar{b}_0\) otherwise. A program \(\bar{s}\ \mathbf{return}\ e\) evaluates to \(v\) if \(\langle \bar{s}, \sigma_0 \rangle \Downarrow \sigma\) and \(\langle e, \sigma \rangle \Downarrow v\); if no derivation exists (a loop that never exits), the program diverges. Expressions always evaluate (every operator is total), so \(\mathrm{Beh}(p)\) never contains \(\mathrm{ub}\).
The totality rules at work
\(\langle 7 / 0, \sigma \rangle \Downarrow 0\) and \(\langle 7 \% 0, \sigma \rangle \Downarrow 7\),
so \(a = (a / b) * b + a \% b\) holds for every \(b\), including \(0\) and \(-1\)
(tools/course/tests/test_ch00.py checks it on all pairs of edge values).
\(\langle (-2^{63}) / (-1), \sigma \rangle \Downarrow -2^{63}\) because the true quotient
\(2^{63}\) wraps. C and LLVM IR leave both cases undefined; the lab's JIT must therefore
guard its sdiv (see the lab SPEC).
Tree-walking interpreters¶
Algorithm 0.2.3 (Tree-walking interpreter)
- Input: a Tiny program \(\bar{s}\ \mathbf{return}\ e\) as a syntax tree.
- Output: the value \(v\) the program evaluates to (Definition 0.2.2), if it terminates.
- Precondition: the tree is well formed (the parser built it).
- Postcondition:
Eval(e, σ)returns the \(v\) with \(\langle e, \sigma \rangle \Downarrow v\);Exec(ss, σ)returns the \(\sigma'\) with \(\langle \bar{s}, \sigma \rangle \Downarrow \sigma'\) (Theorem 0.2.11). - Invariant: every recursive call is made on a proper subtree, or (for
while) on the same statement with a state reached by one more iteration.
function Eval(e, σ):
case e of
k: return k
x: return σ(x)
−e1: return wrap(−Eval(e1, σ))
!e1: return 1 if Eval(e1, σ) = 0 else 0
e1 && e2: if Eval(e1, σ) = 0: return 0
return 1 if Eval(e2, σ) ≠ 0 else 0
e1 || e2: if Eval(e1, σ) ≠ 0: return 1
return 1 if Eval(e2, σ) ≠ 0 else 0
e1 ⊕ e2: a ← Eval(e1, σ); b ← Eval(e2, σ); return Apply(⊕, a, b)
function Exec(ss, σ):
for s in ss:
case s of
x = e: σ ← σ[x ↦ Eval(e, σ)]
while c {b}: while Eval(c, σ) ≠ 0: σ ← Exec(b, σ)
if c {b1} else {b0}: σ ← Exec(b1 if Eval(c, σ) ≠ 0 else b0, σ)
return σ
function Run(ss return e): return Eval(e, Exec(ss, λx.0))
# Apply(⊕, a, b) computes a ⊕̂ b exactly as Definition 0.2.2 defines it.
LLVM's own IR interpreter vs its JIT
Reproduce (lli 23.1.2; bash's time):
cat > big.ll <<'EOF'
@fmt = private constant [15 x i8] c"sum(1e7) = %d\0A\00"
declare i32 @printf(ptr, ...)
define i32 @sum(i32 %n) {
entry:
br label %loop
loop:
%i = phi i32 [ 0, %entry ], [ %i.next, %body ]
%s = phi i32 [ 0, %entry ], [ %s.next, %body ]
%done = icmp sge i32 %i, %n
br i1 %done, label %exit, label %body
body:
%s.next = add i32 %s, %i
%i.next = add i32 %i, 1
br label %loop
exit:
ret i32 %s
}
define i32 @main() {
%r = call i32 @sum(i32 10000000)
call i32 (ptr, ...) @printf(ptr @fmt, i32 %r)
ret i32 0
}
EOF
time lli big.ll
time lli -force-interpreter big.ll
Output (timings vary by machine; user/sys lines cut):
What to notice: the same IR, the same answer (the sum wraps in i32). With
-force-interpreter, lli walks the IR one instruction at a time through a visitor
(llvm/lib/ExecutionEngine/Interpreter/Execution.cpp, Interpreter::visitBinaryOperator
[LLVM-Interp]) — a walker over a graph instead of a tree, with a big switch per
instruction kind — and is about 110 times slower than the ORC JIT that lli uses by default.
Stack-based bytecode VMs¶
Definition 0.2.4 (Stack machine)
A stack program is an array \(c[0..n)\) of instructions push k, load x, store x,
a binary operator add sub mul div rem lt le gt ge eq ne, a unary neg not, jmp t,
jz t, jnz t, ret. A configuration is \((pc, S, \sigma)\) with \(S\) a sequence of
values (the operand stack, top at the right). One step \(\to\) executes \(c[pc]\):
push k: \((pc, S, \sigma) \to (pc{+}1, S \cdot k, \sigma)\);
load x: \(\to (pc{+}1, S \cdot \sigma(x), \sigma)\);
store x: \((pc, S \cdot v, \sigma) \to (pc{+}1, S, \sigma[x \mapsto v])\);
binary \(\oplus\): \((pc, S \cdot a \cdot b, \sigma) \to (pc{+}1, S \cdot (a \mathbin{\hat{\oplus}} b), \sigma)\) — the right operand is on top;
neg/not replace the top \(v\) by \(\mathrm{wrap}(-v)\) / \([v = 0]\);
jmp t: \(\to (t, S, \sigma)\);
jz t: \((pc, S \cdot v, \sigma) \to (t, S, \sigma)\) if \(v = 0\), else \((pc{+}1, S, \sigma)\) (dually jnz);
ret halts with result the top of the stack.
Algorithm 0.2.5 (Stack code generation)
- Input: a Tiny program as a syntax tree.
- Output: a stack program \(c\) (Definition 0.2.4).
- Precondition: none beyond well-formedness.
- Postcondition: running \(c\) from \((0, \langle\rangle, \sigma_0)\) halts with the program's value whenever the program terminates (Theorem 0.2.12); the operand stack never exceeds \(D(e)\) during an expression \(e\) (Theorem 0.2.13).
- Invariant:
Code(e)leaves exactly one value above the stack it started with;Code(s)leaves the stack as it found it.
function CodeE(e): # appends to the global array c
case e of
k: Emit(push, k)
x: Emit(load, x)
−e1 / !e1: CodeE(e1); Emit(neg / not)
e1 ⊕ e2: CodeE(e1); CodeE(e2); Emit(op(⊕)) # postorder
e1 && e2: CodeE(e1); j1 ← Emit(jz, HOLE); CodeE(e2); j2 ← Emit(jz, HOLE)
Emit(push, 1); j3 ← Emit(jmp, HOLE)
Patch(j1, |c|); Patch(j2, |c|); Emit(push, 0); Patch(j3, |c|)
e1 || e2: same with jnz, and the constants 0 and 1 swapped
function CodeS(ss):
for s in ss:
case s of
x = e: CodeE(e); Emit(store, x)
while ...: as Algorithm 0.1.10 (loop head, jz exit, body, jmp head)
if ...: as Algorithm 0.1.10 (jz else, then-branch, jmp end, else-branch)
function Compile(ss return e): CodeS(ss); CodeE(e); Emit(ret)
# Emit and Patch as in Algorithm 0.1.10.
CPython's stack bytecode, before and after quickening
Reproduce (CPython 3.11.15):
cat > sum.py <<'EOF'
import dis
def sum_to(n):
s = 0
for i in range(n):
s += i
return s
dis.dis(sum_to)
for _ in range(1000):
sum_to(100)
print("--- after warm-up (adaptive=True) ---")
dis.dis(sum_to, adaptive=True)
EOF
python3 sum.py
Output (complete):
3 0 RESUME 0
4 2 LOAD_CONST 1 (0)
4 STORE_FAST 1 (s)
5 6 LOAD_GLOBAL 1 (NULL + range)
18 LOAD_FAST 0 (n)
20 PRECALL 1
24 CALL 1
34 GET_ITER
>> 36 FOR_ITER 7 (to 52)
38 STORE_FAST 2 (i)
6 40 LOAD_FAST 1 (s)
42 LOAD_FAST 2 (i)
44 BINARY_OP 13 (+=)
48 STORE_FAST 1 (s)
50 JUMP_BACKWARD 8 (to 36)
7 >> 52 LOAD_FAST 1 (s)
54 RETURN_VALUE
--- after warm-up (adaptive=True) ---
3 0 RESUME_QUICK 0
4 2 LOAD_CONST 1 (0)
4 STORE_FAST 1 (s)
5 6 LOAD_GLOBAL_BUILTIN 1 (NULL + range)
18 LOAD_FAST 0 (n)
20 PRECALL_BUILTIN_CLASS 1
24 CALL_ADAPTIVE 1
34 GET_ITER
36 FOR_ITER 7 (to 52)
38 STORE_FAST__LOAD_FAST 2 (i)
6 40 LOAD_FAST__LOAD_FAST 1 (s)
42 LOAD_FAST 2 (i)
44 BINARY_OP_ADD_INT 13 (+=)
48 STORE_FAST 1 (s)
50 JUMP_BACKWARD_QUICK 8 (to 36)
7 >> 52 LOAD_FAST 1 (s)
54 RETURN_VALUE
What to notice: s += i is LOAD_FAST s; LOAD_FAST i; BINARY_OP +=; STORE_FAST s —
exactly Algorithm 0.2.5's postorder load s, load i, add, store s. After warm-up the
interpreter has rewritten its own bytecode (PEP 659 quickening): BINARY_OP_ADD_INT is
specialized to integers, and LOAD_FAST__LOAD_FAST is a superinstruction that does two
loads with one dispatch (§6).
Register-based bytecode VMs¶
Definition 0.2.6 (Register machine, three-address code)
A register program has instructions \(r \gets a \oplus b\), \(r \gets \ominus a\),
\(r \gets a\), jz a, t, jmp t and ret a, where \(r\) is a register (a slot in the
interpreter's frame: every variable has one, and temporaries \(t_1, t_2, \dots\) get fresh
ones) and each operand \(a, b\) is a register or a constant. Such instructions are also
called three-address code. Executing \(r \gets a \oplus b\) sets
\(\rho(r) = \rho(a) \mathbin{\hat{\oplus}} \rho(b)\) in the register file \(\rho\).
Algorithm 0.2.7 (Three-address code generation)
- Input: an expression \(e\) and an optional destination register \(d\).
- Output: an operand holding the value of \(e\) (a constant, a variable's register, or a register written by the emitted code).
- Precondition: every variable has its own register.
- Postcondition: the emitted code contains exactly one instruction per operator of \(e\) (Proposition 0.2.15); if \(d\) is given and \(e\) is an operator node, the last instruction writes \(d\).
- Invariant: temporaries are fresh, so no emitted instruction overwrites a register that is still needed.
function Gen(e, d = none):
case e of
k: return k # constants are operands, no instruction
x: return reg(x) # variables live in registers
⊖e1: a ← Gen(e1); r ← d or NewTemp(); Emit(r ← ⊖ a); return r
e1 ⊕ e2: a ← Gen(e1); b ← Gen(e2); r ← d or NewTemp()
Emit(r ← a ⊕ b); return r
# an assignment x = e with e an operator node compiles to Gen(e, reg(x)): ONE instruction
# for s = s + i, where the stack machine needs four (load s, load i, add, store s).
V8's Ignition: a register machine with an accumulator
Reproduce (Node.js 22.22.2, V8 12.4.254.21; addresses masked because they change per run):
cat > sum.js <<'EOF'
function sum(n) {
let s = 0;
for (let i = 0; i < n; i++) s += i;
return s;
}
console.log(sum(10));
EOF
node --print-bytecode --print-bytecode-filter=sum sum.js | sed -E 's/0x[0-9a-f]+/0x…/g' | head -21
Output (the first 21 lines; the program's own output 45 follows):
[generated bytecode for function: sum (0x… <SharedFunctionInfo sum>)]
Bytecode length: 32
Parameter count 2
Register count 3
Frame size 24
28 S> 0x… @ 0 : 0c LdaZero
0x… @ 1 : c9 Star0
46 S> 0x… @ 2 : 0c LdaZero
0x… @ 3 : c8 Star1
51 S> 0x… @ 4 : 0b 03 Ldar a0
51 E> 0x… @ 6 : 71 f8 00 TestLessThan r1, [0]
0x… @ 9 : 9e 14 JumpIfFalse [20] (0x… @ 29)
61 S> 0x… @ 11 : 0b f8 Ldar r1
66 E> 0x… @ 13 : 3b f9 01 Add r0, [1]
0x… @ 16 : 19 f9 f7 Mov r0, r2
0x… @ 19 : c9 Star0
57 S> 0x… @ 20 : 0b f8 Ldar r1
0x… @ 22 : 53 02 Inc [2]
0x… @ 24 : c8 Star1
33 E> 0x… @ 25 : 8e 15 00 03 JumpLoop [21], [0], [3] (0x… @ 4)
71 S> 0x… @ 29 : 0b f9 Ldar r0
What to notice: s and i live in registers r0 and r1 (Definition 0.2.6) and
Add r0, [1] names its operand explicitly; the implicit accumulator holds the other
operand and the result, which keeps instructions short (a hybrid of Definitions 0.2.4 and
0.2.6). One iteration executes 11 instructions (offsets 4–25: test, body, increment,
JumpLoop); the Tiny stack code of the running example executes 13 per iteration
(pc 4–16). The [1], [2]
operands index the feedback vector that records observed types for the optimizing tiers
(Lesson 0.3).
Dispatch: switch and threaded code¶
Definition 0.2.8 (Dispatch schemes)
Let \(H(o)\) be the machine-code handler of opcode \(o\). Switch dispatch executes
loop: o ← c[pc].op; goto table[o] with one indirect jump shared by all handlers, each
handler ending with goto loop. Direct threading [Bel73] translates \(c\) once into
\(\hat{c}\) with \(\hat{c}[i].\mathrm{handler} = H(c[i].\mathrm{op})\) and jump targets
replaced by addresses in \(\hat{c}\); every handler ends with its own indirect jump
goto *(++ip)->handler. Indirect threading stores in \(\hat{c}[i]\) the address of a
cell holding \(H(o)\) (one more load per dispatch, but code independent of handler
addresses). Token threading keeps opcodes in the code and ends every handler with
goto *table[(++ip)->op] (replicated switch).
Definition 0.2.9 (Last-target branch predictor model)
A dispatch executes an indirect branch at some site (an address in the interpreter). The model predictor remembers, per site, the target the site jumped to last time, and predicts that target; a site's first execution is a miss. For an executed opcode trace \(t_1, \dots, t_m\): under switch dispatch every dispatch is at the one switch site; under threaded dispatch, the dispatch to \(t_{i+1}\) is at the end of handler \(t_i\) (site \(t_i\)), and the dispatch to \(t_1\) is at an entry site. \(M_{\mathrm{sw}}\) and \(M_{\mathrm{th}}\) denote the numbers of misses. (Real branch target buffers are finite and tagged, and modern ones use global history [RSS15]; the model is the one Ertl and Gregg use to explain the effect [EG03].)
Algorithm 0.2.10 (Direct-threaded execution)
- Input: a stack program \(c\) (Definition 0.2.4) and handler addresses \(H\).
- Output: the value returned by
ret. - Precondition: \(c\) is closed (every jump target is an index in \([0, n)\)) and ends every path with
ret; the host compiler supports taking label addresses (GNU C&&label). - Postcondition: the sequence of instructions executed is exactly the one the switch VM executes on \(c\) (Theorem 0.2.16).
- Invariant:
ippoints at \(\hat{c}[i]\) exactly when the switch VM would have \(pc = i\).
function Translate(c): # once, in prepare()
for i in 0 .. n−1:
ĉ[i].handler ← H(c[i].op); ĉ[i].arg ← c[i].arg
if c[i].op ∈ {jmp, jz, jnz}: ĉ[i].target ← address of ĉ[c[i].arg]
return ĉ
function RunThreaded(ĉ):
ip ← address of ĉ[0]; sp ← empty stack
goto *ip.handler
L_push: push(ip.arg); ip ← ip + 1; goto *ip.handler
L_add: b ← pop(); a ← pop(); push(a +̂ b); ip ← ip + 1; goto *ip.handler
L_jz: if pop() = 0: ip ← ip.target else: ip ← ip + 1
goto *ip.handler
L_jmp: ip ← ip.target; goto *ip.handler
L_ret: return top()
# the other handlers follow the same pattern: their effect (Definition 0.2.4), then
# advance ip, then their OWN indirect jump.
CPython is built with threaded dispatch
Reproduce (CPython 3.11.15 on Linux):
Output (complete):
What to notice: USE_COMPUTED_GOTOS = 1 means Python/ceval.c was compiled with
#define USE_COMPUTED_GOTOS 1, so _PyEval_EvalFrameDefault dispatches through the table
in Python/opcode_targets.h with goto *opcode_targets[opcode] at the end of each
handler — token threading (Definition 0.2.8) [CPY-Ceval]. Without GCC or clang, CPython
falls back to switch.
3. Worked examples¶
Running example (Tiny; inputs/ of the lab has larger ones):
Tree-walking interpreters¶
Algorithm 0.2.3, one row per Exec step of the outer statement list and of the loop body; \(\sigma\) lists only \(s\) and \(i\).
| step | statement executed | Eval calls it makes (value) |
\(\sigma\) after |
|---|---|---|---|
| 1 | s = 0 |
0 (0) |
s=0, i=0 |
| 2 | i = 0 |
0 (0) |
s=0, i=0 |
| 3 | while test |
i < 2: i (0), 2 (2) → 1 |
s=0, i=0 |
| 4 | s = s + i |
s (0), i (0), + → 0 |
s=0, i=0 |
| 5 | i = i + 1 |
i (0), 1 (1), + → 1 |
s=0, i=1 |
| 6 | while test |
i < 2 → 1 |
s=0, i=1 |
| 7 | s = s + i |
→ 1 | s=1, i=1 |
| 8 | i = i + 1 |
→ 2 | s=1, i=2 |
| 9 | while test |
i < 2 → 0: loop ends |
s=1, i=2 |
| 10 | return s |
s (1) |
result 1 |
Eval is called 24 times (every node of every evaluated expression tree); each call is a C++ function call with a switch on the node kind.
Stack-based bytecode VMs¶
Algorithm 0.2.5 produces the 19 instructions of Lesson 0.1's single-pass table (0: push 0 … 18: ret). Executing them (Definition 0.2.4), with the stack before each instruction:
| # | pc | instruction | stack before | # | pc | instruction | stack before |
|---|---|---|---|---|---|---|---|
| 1 | 0 | push 0 |
[] | 19 | 5 | push 2 |
[1] |
| 2 | 1 | store s |
[0] | 20 | 6 | lt |
[1, 2] |
| 3 | 2 | push 0 |
[] | 21 | 7 | jz 17 |
[1] |
| 4 | 3 | store i |
[0] | 22 | 8 | load s |
[] |
| 5 | 4 | load i |
[] | 23 | 9 | load i |
[0] |
| 6 | 5 | push 2 |
[0] | 24 | 10 | add |
[0, 1] |
| 7 | 6 | lt |
[0, 2] | 25 | 11 | store s |
[1] |
| 8 | 7 | jz 17 |
[1] | 26 | 12 | load i |
[] |
| 9 | 8 | load s |
[] | 27 | 13 | push 1 |
[1] |
| 10 | 9 | load i |
[0] | 28 | 14 | add |
[1, 1] |
| 11 | 10 | add |
[0, 0] | 29 | 15 | store i |
[2] |
| 12 | 11 | store s |
[0] | 30 | 16 | jmp 4 |
[] |
| 13 | 12 | load i |
[] | 31 | 4 | load i |
[] |
| 14 | 13 | push 1 |
[0] | 32 | 5 | push 2 |
[2] |
| 15 | 14 | add |
[0, 1] | 33 | 6 | lt |
[2, 2] |
| 16 | 15 | store i |
[1] | 34 | 7 | jz 17 |
[0] → jump |
| 17 | 16 | jmp 4 |
[] | 35 | 17 | load s |
[] |
| 18 | 4 | load i |
[] | 36 | 18 | ret |
[1] → result 1 |
36 dispatches. The stack never holds more than 2 values: \(D(i < 2) = \max(1, 1 + 1) = 2\) and \(D(s + i) = 2\) (Theorem 0.2.13).
Register-based bytecode VMs¶
Algorithm 0.2.7 with destinations, plus compare-and-branch code for the loop test:
0: s ← 0
1: i ← 0
2: t1 ← i < 2
3: jz t1, 7
4: s ← s + i # Gen(s + i, reg(s)): one instruction
5: i ← i + 1
6: jmp 2
7: ret s
Executed: 0, 1, then (2, 3, 4, 5, 6) twice, then 2, 3, 7 — 15 dispatches instead of 36. Fusing t1 ← i < 2; jz t1, 7 into one jge i, 2, 7 (what Lua's OP_LT + jump pair and Ignition's TestLessThan/JumpIfFalse approximate) gives 12. The price is size: each register instruction encodes three operands.
Dispatch: switch and threaded code¶
The 36-instruction trace above under Definition 0.2.9. The opcode sequence starts push store push store load push lt jz load load add store load push add store jmp load ….
| # | opcode | switch predicts | switch | threaded site | site predicts | threaded |
|---|---|---|---|---|---|---|
| 1 | push | — | miss | entry | — | miss |
| 2 | store | push | miss | push | — | miss |
| 3 | push | store | miss | store | — | miss |
| 4 | store | push | miss | push | store | hit |
| 5 | load | store | miss | store | push | miss |
| 6 | push | load | miss | load | — | miss |
| 7 | lt | push | miss | push | store | miss |
| 8 | jz | lt | miss | lt | — | miss |
| 9 | load | jz | miss | jz | — | miss |
| 10 | load | load | hit | load | push | miss |
| 11 | add | load | miss | load | load | miss |
| 12 | store | add | miss | add | — | miss |
| 13 | load | store | miss | store | load | hit |
| 14 | push | load | miss | load | add | miss |
| 15 | add | push | miss | push | lt | miss |
| 16 | store | add | miss | add | store | hit |
| 17 | jmp | store | miss | store | load | miss |
| 18 | load | jmp | miss | jmp | — | miss |
| 19 | push | load | miss | load | push | hit |
| 20 | lt | push | miss | push | add | miss |
| 21 | jz | lt | miss | lt | jz | hit |
| 22 | load | jz | miss | jz | load | hit |
| 23 | load | load | hit | load | push | miss |
| 24 | add | load | miss | load | load | miss |
| 25 | store | add | miss | add | store | hit |
| 26 | load | store | miss | store | jmp | miss |
| 27 | push | load | miss | load | add | miss |
| 28 | add | push | miss | push | lt | miss |
| 29 | store | add | miss | add | store | hit |
| 30 | jmp | store | miss | store | load | miss |
| 31 | load | jmp | miss | jmp | load | hit |
| 32 | push | load | miss | load | push | hit |
| 33 | lt | push | miss | push | add | miss |
| 34 | jz | lt | miss | lt | jz | hit |
| 35 | load | jz | miss | jz | load | hit |
| 36 | ret | load | miss | load | push | miss |
\(M_{\mathrm{sw}} = 34\) (hits only at #10 and #23, the two load load pairs), \(M_{\mathrm{th}} = 24\). The threaded sites lt, jz, jmp, add learn their successors after one iteration; the shared load, push and store handlers keep missing because many different static instructions use them — the motivation for replicated handlers and superinstructions (§6).
Try it
./course drill stack-code --seed 4 --difficulty hard --solution (stack code, depth,
register count, Ershov number) and ./course drill dispatch --seed 1 --difficulty easy
--solution (a trace like the table above).
4. Invariants and correctness¶
Tree-walking interpreters¶
Theorem 0.2.11 (The tree walker implements the big-step semantics)
For all \(e, \sigma, v\): Eval(e, σ) returns \(v\) iff \(\langle e, \sigma \rangle \Downarrow v\).
For all \(\bar{s}, \sigma, \sigma'\): Exec(ss, σ) terminates with \(\sigma'\) iff
\(\langle \bar{s}, \sigma \rangle \Downarrow \sigma'\), and it runs forever iff no
derivation exists.
Proof
Expressions, by structural induction on \(e\): each case of Eval computes exactly the
conclusion of the one rule whose premises it evaluates (for &&, the two rules are
distinguished by the value of \(e_1\), and Eval tests the same condition); expressions
always terminate because recursion is on proper subtrees and every operator is total.
Statements, "if": by induction on the height of the derivation of
\(\langle \bar{s}, \sigma \rangle \Downarrow \sigma'\); the while rule with \(v \ne 0\) has
premises for the body and for the same loop in state \(\sigma_1\), both of smaller height,
and Exec performs exactly one iteration and then continues the same loop in \(\sigma_1\).
"Only if": by induction on the number of iterations of Exec's loops; a terminating
run builds the derivation rule by rule. If Exec does not terminate, a derivation would
give (by "if") a terminating run of the same deterministic procedure, a contradiction.
Stack-based bytecode VMs¶
Theorem 0.2.12 (Stack code is correct)
Let CodeE(e) be placed at addresses \([a, a + \ell)\) of \(c\). If
\(\langle e, \sigma \rangle \Downarrow v\) then for every stack \(S\),
\((a, S, \sigma) \to^{*} (a + \ell, S \cdot v, \sigma)\), and every intermediate stack has
\(S\) as a prefix. If \(\langle \bar{s}, \sigma \rangle \Downarrow \sigma'\) then
\((a, S, \sigma) \to^{*} (a + \ell, S, \sigma')\) for CodeS(ss) placed at \([a, a + \ell)\).
Consequently Compile(p) returns the value of every terminating program.
Proof
Expressions, by structural induction on \(e\). Constants and variables: one step pushes
\(v\). \(-e_1\): by induction \(\mathrm{CodeE}(e_1)\) reaches \(S \cdot v_1\); neg gives
\(S \cdot \mathrm{wrap}(-v_1)\). \(e_1 \oplus e_2\): induction on \(e_1\) gives \(S \cdot v_1\);
induction on \(e_2\) with stack \(S \cdot v_1\) gives \(S \cdot v_1 \cdot v_2\) without
touching \(S \cdot v_1\); the operator pops \(v_2\) (top) then \(v_1\) and pushes
\(v_1 \mathbin{\hat{\oplus}} v_2\) — the order matters for \(-\), \(/\), \(\%\) and comparisons.
\(e_1 \mathbin{\&\&} e_2\): after \(\mathrm{CodeE}(e_1)\) the stack is \(S \cdot v_1\); if
\(v_1 = 0\) the jz pops it and jumps to the final push 0, which is the last
instruction, giving \(S \cdot 0\); otherwise it falls through, \(\mathrm{CodeE}(e_2)\) gives
\(S \cdot v_2\), the second jz either jumps to push 0 (\(v_2 = 0\)) or falls through to
push 1; jmp past the end — \(S \cdot [v_2 \ne 0]\) in both cases, as the rules require.
Prefix property: every case only pushes above \(S\) or pops what its own sub-codes pushed.
Statements, by induction on derivation height, exactly as in Theorem 0.2.11: an
assignment ends with store, which pops the value and updates \(\sigma\); a while whose
test gives \(v \ne 0\) runs the test code, falls through jz, runs the body (induction),
and jmps back to the test with state \(\sigma_1\), where the premise for the remaining
loop applies (smaller height); a test giving \(0\) jumps to the exit by Theorem 0.1.18.
Theorem 0.2.13 (Stack depth of postorder code)
During CodeE(e) the stack holds at most \(D(e)\) values above \(S\) (on every path), where
\(D(k) = D(x) = 1\), \(D(-e_1) = D(!e_1) = D(e_1)\),
\(D(e_1 \oplus e_2) = \max(D(e_1),\ 1 + D(e_2))\) and
\(D(e_1 \mathbin{\&\&} e_2) = D(e_1 \mathbin{\Vert} e_2) = \max(D(e_1), D(e_2))\); the bound
is reached.
Proof
Structural induction. Leaves push one value. Unary operators replace the top. For
\(e_1 \oplus e_2\): while \(\mathrm{CodeE}(e_1)\) runs, at most \(D(e_1)\) values; afterwards
one value (\(v_1\)) stays while \(\mathrm{CodeE}(e_2)\) runs on top of it, so at most
\(1 + D(e_2)\); the operator then shrinks the stack to 1. The maximum is attained because
each sub-bound is attained (induction). For &&/|| the jump pops \(v_1\) before
\(e_2\) runs, and the final constant is pushed onto an empty (relative) stack, so the
maximum is \(\max(D(e_1), D(e_2), 1) = \max(D(e_1), D(e_2))\) since \(D \ge 1\).
Theorem 0.2.14 (Ershov numbers: the optimal operand order)
Suppose that at each binary node \(e_1 \oplus e_2\) (with \(\oplus\) not &&/||) code may
evaluate either operand first (using a reversed operator such as "reverse subtract"
when it evaluates \(e_2\) first). The minimum over all such choices of the maximum stack
depth is the Ershov number \(E(e)\): \(E(k) = E(x) = 1\), \(E(\ominus e_1) = E(e_1)\), and
Proof
By structural induction; leaves and unary nodes are immediate. At a binary node, by Theorem 0.2.13 applied to both orders, evaluating \(e_1\) first costs \(\max(d_1, 1 + d_2)\) and \(e_2\) first costs \(\max(d_2, 1 + d_1)\), where \(d_i\) is the depth chosen inside \(e_i\). Both expressions are monotone in \(d_1\) and \(d_2\), so choosing the optimal order inside each child (\(d_i = E(e_i)\), induction hypothesis) is optimal for the parent (the children's choices are independent). With \(a = E(e_1)\), \(b = E(e_2)\): if \(a > b\) then \(\max(a, 1 + b) = a\), and no order can use fewer than \(a\) (the code for \(e_1\) alone needs \(a\)); symmetrically for \(b > a\); if \(a = b\) both orders give \(a + 1\). The numbering is due to Ershov [Ers58]; Sethi and Ullman [SU70] prove the corresponding register-optimality theorem for code generation [Dragon2, §8.10].
Ershov on \((a + b) * (c - d * e)\)
Postorder: load a, load b, add, load c, load d, load e, mul, sub, mul, depth
\(D = \max(D(a+b), 1 + D(c - d{*}e)) = \max(2, 1 + 3) = 4\). Ershov: \(E(a+b) = 2\),
\(E(d * e) = 2\), \(E(c - d{*}e) = \max(1, 2) = 2\), so \(E = 2 + 1 = 3\): evaluate the right
operand \(c - d * e\) first.
Register-based bytecode VMs¶
Proposition 0.2.15 (Instruction counts)
For an expression \(e\) without &&/||, with \(\ell\) leaves and \(o\) operators,
\(\lvert \mathrm{CodeE}(e) \rvert = \ell + o\) and Algorithm 0.2.7 emits exactly \(o\)
instructions. An assignment \(x = e\) with \(o \ge 1\) costs \(\ell + o + 1\) stack
instructions and \(o\) register instructions.
Proof
By structural induction: a leaf emits one stack instruction and no register instruction;
each operator node emits one instruction in both schemes plus its children's. For the
assignment, the stack code adds store x; Gen(e, reg(x)) writes \(x\) with the root's
instruction, adding nothing. Correctness of the register code is the same induction as
Theorem 0.2.12 with "stack" replaced by "register file": fresh temporaries (the
algorithm's invariant) are never overwritten while live.
Dispatch: switch and threaded code¶
Theorem 0.2.16 (Threaded execution simulates switch execution)
Under the precondition of Algorithm 0.2.10, the threaded VM and the switch VM of Definition 0.2.4 execute the same sequence of instructions on the same stacks and return the same value.
Proof
By induction on the number of steps, with the invariant "ip \(= \&\hat{c}[pc]\), same
stack, same state". Initially ip \(= \&\hat{c}[0]\) and \(pc = 0\). Step: the handler
reached through ip.handler is \(H(c[pc].\mathrm{op})\) by construction of \(\hat{c}\), so it
performs the same effect on the stack as the switch case for that opcode; it then sets
ip to \(\&\hat{c}[pc + 1]\) or to ip.target \(= \&\hat{c}[c[pc].\mathrm{arg}]\), exactly
where the switch VM sets \(pc\). Both stop at the same ret. Closedness guarantees every
target is a valid address.
Proposition 0.2.17 (Misprediction counts in the model)
For a trace \(t_1, \dots, t_m\) (\(m \ge 1\)): \(M_{\mathrm{sw}} = 1 + \lvert \{\, i \in [2, m] \mid t_i \ne t_{i-1} \,\} \rvert\) and \(M_{\mathrm{th}} = \lvert \{\, i \in [1, m] \mid \mathrm{last}_i(t_{i-1}) \ne t_i \,\} \rvert\), where \(t_0 = \mathrm{entry}\) and \(\mathrm{last}_i(o)\) is the \(t_{j+1}\) for the largest \(j < i - 1\) with \(t_j = o\) (undefined, hence a miss, if none).
Proof
Switch: the site's last target before dispatch \(i \ge 2\) is \(t_{i-1}\), so dispatch \(i\)
hits iff \(t_i = t_{i-1}\); dispatch 1 is cold. Threaded: dispatch \(i\) happens at site
\(t_{i-1}\), whose previous execution (if any) was the dispatch at position \(j + 1\) for the
last earlier occurrence \(t_j = t_{i-1}\); it hits iff that target equals \(t_i\). The two
formulas are what tiny.mispredictions computes; test_ch00.py checks them against an
independent re-implementation on 300 random traces.
5. Complexity¶
Variables: \(N\) = number of operator and leaf evaluations of the program's run (dynamic node count), \(n\) = static program size, \(T\) = number of executed bytecode instructions.
| Technique | Time (worst) | Time (typical) | Space | Variables |
|---|---|---|---|---|
| Tree-walking | \(\Theta(N)\) node visits, each a call + switch + pointer loads | slowest here: 180 ms on bench-sum |
tree \(O(n)\); recursion depth = expression depth | \(N, n\) |
| Stack VM | compile \(O(n)\); run \(\Theta(T)\) with \(T = \ell + o\) per expression evaluation | 1.6–1.9× the tree-walker (switch) | code \(O(n)\), stack \(\le D(e)\) | \(T, n\) |
| Register VM | compile \(O(n)\); run \(\Theta(o)\) per expression evaluation | fewer dispatches (15 vs 36 on the running example) | code larger per instruction; frame holds temporaries | \(o, n\) |
| Threaded dispatch | same \(T\) as switch; \(\Theta(n)\) extra translation | 1.5–1.9× faster than switch on the lab benchmarks | translated code: one pointer per instruction | \(T, n\) |
Proposition 0.2.18 (Costs)
Algorithms 0.2.5 and 0.2.7 run in \(O(n)\) time; the tree walker performs one Eval call
per node visit; the stack VM executes \(\ell + o\) instructions per evaluation of an
expression without &&/||, the register VM \(o\); Algorithm 0.2.10's translation is
\(\Theta(n)\) and its run performs exactly the switch VM's \(T\) dispatches.
Proof
Each code generator visits each node once and emits \(O(1)\) instructions per node
(Proposition 0.2.15); Patch is \(O(1)\). The per-evaluation counts are Proposition 0.2.15
applied dynamically. Translation touches each instruction once; the dispatch count
follows from Theorem 0.2.16.
Pathological inputs. (1) A right-leaning expression \(x_1 - (x_2 - (\dots - x_k))\) has \(D = k\) (the stack grows with every left operand waiting), while its Ershov number is 2 — the order of evaluation matters by a factor of \(k/2\). (2) For dispatch, an opcode trace alternating \(A, B\) misses on every switch dispatch (\(M_{\mathrm{sw}} = m\)) but only on the first three threaded ones; conversely a trace in which one opcode is followed by a different opcode each time (the load handler in the running example) defeats per-handler prediction too — replication fixes it (§6). (3) Deeply nested expressions overflow the tree walker's native stack before they bother a bytecode VM with an explicit stack.
At scale. Measured on the lab (ch00-bench --runs=5, reference solution, x86-64): tree 180.7 ms, switch 92.8 ms, threaded 53.3 ms on bench-sum (5·10⁶ iterations); on bench-collatz 376 / 232 / 150 ms. Shi et al. report 47% fewer executed instructions for a register VM on Java benchmarks [SGBE05].
6. Variants and refinements¶
Tree-walking interpreters¶
- Closure compilation [FL87] — convert each node once into a host closure that calls its children's closures; the per-node
switchdisappears. Trade-off: memory for closures; a common first step up from a naive walker. - Self-optimizing AST interpreters (Truffle) — nodes rewrite themselves to type-specialized versions as they run, and the tree is then partially evaluated into machine code [WWH+17] (Lesson 0.3). Trade-off: a large framework.
Stack-based bytecode VMs¶
- Superinstructions — combine frequent sequences (
LOAD_FAST__LOAD_FASTin the CPython box) into one opcode, cutting dispatches [EG03b]. Trade-off: more handlers and a bigger interpreter. - Quickening / inline caching — rewrite generic instructions to specialized ones after observing operand types (PEP 659,
BINARY_OP_ADD_INT) [CPY-Spec]. Trade-off: code becomes mutable; needs deoptimization back to the generic form. - Stack caching — keep the top one or two stack elements in machine registers, removing most memory traffic [EG03]. Trade-off: handlers exist per cache state.
Register-based bytecode VMs¶
- Accumulator machines (V8 Ignition) — one implicit operand/result register shortens instructions; a hybrid between stack and register designs.
- Stack-to-register translation — translate stack bytecode (JVM) to register code at load time, then apply copy propagation to remove moves [SGBE05]. Trade-off: translation time.
Dispatch: switch and threaded code¶
- Replicated handlers and superinstructions for prediction — give each static instruction its own copy of a handler so each dispatch site sees one successor [EG03b]. Trade-off: code size, i-cache pressure.
- Subroutine threading / context threading — emit a native
call handlerper instruction, turning the VM program into a sequence of calls that the return-address predictor handles well; a step toward a baseline JIT. Trade-off: requires emitting machine code. - Tail-calling interpreters — each handler is a function that tail-calls the next (
musttailin clang; CPython 3.14's optional tail-calling interpreter); portable threaded dispatch without computed goto. Trade-off: depends on guaranteed tail calls.
7. In real compilers¶
Tree-walking interpreters¶
LLVM
llvm/lib/ExecutionEngine/Interpreter/Execution.cpp — Interpreter::run fetches the
next instruction and dispatches through InstVisitor to visitBinaryOperator, … (LLVM 23.1.2)
[LLVM-Interp]; selected by lli -force-interpreter (llvm/tools/lli/lli.cpp, option
ForceInterpreter).
- pir-run
pebble/lib/PIR/— the course's reference PIR interpreter walks basic blocks and statements; it is the oracle for Pebble's end-to-end tests. - The lab
solutions/labs/ch00-exec/src/TreeWalker.cpp— the reference tree walker (spoiler).
Find where LLVM does it. Open llvm/lib/ExecutionEngine/Interpreter/Execution.cpp at llvmorg-23.1.2 and find the main loop. Question: what is the name of the member function that runs the loop over instructions? (quiz llvm-where-interpreter)
Stack-based bytecode VMs¶
- CPython
Python/ceval.c—_PyEval_EvalFrameDefault, oneTARGET(op)block per opcode (v3.11.15) [CPY-Ceval];Python/specialize.c—_PyCode_Quicken,_Py_Specialize_BinaryOp[CPY-Spec]. - HotSpot
src/hotspot/share/interpreter/templateInterpreter.cpp— the JVM interprets stack bytecode with handlers generated as machine-code templates at VM start (jdk-21+35) [HS-Interp].
JVM bytecode is stack code too
Reproduce (OpenJDK 21.0.10 javac + javap):
cat > Sum.java <<'EOF'
public class Sum {
static int sum(int n) {
int s = 0;
for (int i = 0; i < n; i++) s += i;
return s;
}
public static void main(String[] args) {
long t = 0;
for (int k = 0; k < 200000; k++) t += sum(10);
System.out.println(t);
}
}
EOF
javac Sum.java
javap -c Sum | sed -n '/static int sum/,/^$/p'
Output (complete):
static int sum(int);
Code:
0: iconst_0
1: istore_1
2: iconst_0
3: istore_2
4: iload_2
5: iload_0
6: if_icmpge 19
9: iload_1
10: iload_2
11: iadd
12: istore_1
13: iinc 2, 1
16: goto 4
19: iload_1
20: ireturn
What to notice: s += i is iload_1, iload_2, iadd, istore_1 — Algorithm 0.2.5 —
while i++ uses the specialized iinc 2, 1 (a superinstruction for "add a constant to a
local") and the loop test fuses comparison and branch (if_icmpge).
Register-based bytecode VMs¶
- Lua 5.4
lvm.c—luaV_execute,vmdispatch (GET_OPCODE(i))over register instructions whoseiABCformat is documented inlopcodes.h(v5.4.6) [LUA-Src]. - V8
src/interpreter/interpreter.cc—Interpreter::NewCompilationJobproduces Ignition bytecode; opcodes insrc/interpreter/bytecodes.h(12.4.254.21) [V8-Ignition].
Dispatch: switch and threaded code¶
- CPython
Python/opcode_targets.h— the computed-goto table used whenUSE_COMPUTED_GOTOSis set [CPY-Ceval]. - Lua 5.4
lvm.c—vmdispatchis a plainswitchby default (#define vmdispatch(o) switch(o)), with aljumptab.hcomputed-goto variant for GCC [LUA-Src]. - The lab
solutions/labs/ch00-exec/src/VM.cpp— both loops over one bytecode (spoiler).
The lab's four engines, measured
Reproduce (course repository, clang 23.1.2 -O2 build; reference solution):
cmake --preset linux -B build/sol -DPEBBLE_USE_SOLUTION=tiny-exec
cmake --build build/sol --target ch00-bench
build/sol/bin/ch00-bench --runs=5
Output (abridged to two programs; timings vary by machine):
| program | engine | prepare (ms) | run (ms, min of 5) | x tree | result |
|---|---|---:|---:|---:|---:|
| bench-collatz.tiny | tree | 0.001 | 376.102 | 1.0 | 6135095 |
| bench-collatz.tiny | vm-switch | 0.005 | 232.074 | 1.6 | 6135095 |
| bench-collatz.tiny | vm-threaded | 0.005 | 149.724 | 2.5 | 6135095 |
| bench-collatz.tiny | jit | 9.567 | 6.069 | 62.0 | 6135095 |
| bench-sum.tiny | tree | 0.000 | 180.715 | 1.0 | 4773166019248396768 |
| bench-sum.tiny | vm-switch | 0.006 | 92.813 | 1.9 | 4773166019248396768 |
| bench-sum.tiny | vm-threaded | 0.007 | 53.336 | 3.4 | 4773166019248396768 |
| bench-sum.tiny | jit | 4.533 | 0.000 | - | 4773166019248396768 |
What to notice: same bytecode, only the dispatch differs: threaded is 1.55–1.75×
faster than switch (1.5–1.9× over all four programs). Part of that is branch prediction (Proposition 0.2.17), part is
fewer instructions per dispatch (no bounds check, no reload of pc). The JIT row
anticipates Lesson 0.3: 9.6 ms of compilation buys a 62× faster run — and on
bench-sum, whose loop has no input, LLVM folded the whole program to a constant.
8. Comparison¶
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Tree-walking interpreters | full language; the reference semantics | \(\Theta(N)\) node visits · slowest (1× in the lab) | best: errors point at tree nodes with source positions | lowest (one function per construct) | reference interpreters (pir-run), prototypes, DSLs |
| Stack-based bytecode VMs | same | \(\Theta(\ell + o)\) per expression · 1.6–1.9× the tree walker | good (bytecode keeps position tables) | low: postorder compiler + loop | JVM, CPython, WebAssembly, .NET |
| Register-based bytecode VMs | same | \(\Theta(o)\) per expression · ~47% fewer instructions [SGBE05] | good | medium: temporaries, operand encoding | Lua 5, V8 Ignition, Dalvik |
| Dispatch: switch and threaded code | same (only the dispatch changes) | same \(T\) · threaded 1.5–1.9× faster than switch in the lab | identical | switch: trivial; threading: needs computed goto or tail calls | CPython (threaded), Lua (switch), HotSpot (template handlers) |
Choose a tree walker when you need a trustworthy reference or a language prototype this afternoon. Choose stack bytecode when you want compact, easy-to-generate code for a portable VM (and possibly a verifier). Choose register bytecode when dispatch cost dominates and you can afford a slightly smarter compiler. Choose threaded dispatch when the host compiler supports computed goto or guaranteed tail calls; it is a local change to the interpreter loop with a measurable payoff.
9. Assessment¶
| Technique | Quiz ids (solutions/quizzes/ch00.yaml) |
Drill | Flashcard tag | Exercises |
|---|---|---|---|---|
| Tree-walking interpreters | tree-walk-eval-count, llvm-where-interpreter, bigstep-division |
— (Theorem 0.2.11 is traced in the lab: the tree walker is the oracle of L2) | tree-walker |
lab L2 |
| Stack-based bytecode VMs | stack-code-order, stack-depth, ershov-number |
./course drill stack-code |
stack-vm |
lab L3 |
| Register-based bytecode VMs | register-count, register-vs-stack |
./course drill stack-code --difficulty medium |
register-vm |
— (★ stretch goal of the lab) |
| Dispatch: switch and threaded code | dispatch-switch-misses, dispatch-threaded-misses, threading-kinds |
./course drill dispatch |
dispatch |
lab L4 |
Pitfall
"Threaded code" has nothing to do with threads. It means the code is a thread of addresses the interpreter follows [Bel73]; the lab's threaded VM is single-threaded.
References¶
See the chapter references.