Stack Machines and Execution

The Stack-Based VM

With a Chunk to hold bytecode, this lesson builds the machine that actually executes it: a stack-based virtual machine. Understanding why "stack-based" is the natural fit for expression evaluation — and how the fetch-decode-execute loop works — is the core idea here.

Why a stack

An expression like 1 + 2 * 3 naturally decomposes into "push a value, push a value, combine the top two, repeat." A stack is the perfect data structure for this: operands wait on the stack until an operator instruction consumes the top ones and pushes the result back. There's no need to name intermediate results (as a register machine would) — the stack position is the name.

The fetch-decode-execute loop

This is the heart of every VM, interpreter, and CPU: read the next byte, figure out what instruction it represents, perform it, and repeat until you hit a return or run out of code.

Operand order matters

For non-commutative operators (-, /), pop order is critical: the instruction stream pushed the left operand first, then the right operand, so the right operand is on top of the stack and gets popped first. pop() twice as b, a = pop(), pop() — b is the right-hand side, a is the left. Getting this backwards silently flips every subtraction and division: 5 - 2 would compute 2 - 5 instead.

Tracing an example

For 1 + 2 * 3, the compiler (which you'll build once expressions compile instead of being emitted by hand) would produce, respecting *'s higher precedence:

OP_CONSTANT 1      ; stack: [1]
OP_CONSTANT 2      ; stack: [1, 2]
OP_CONSTANT 3      ; stack: [1, 2, 3]
OP_MULTIPLY        ; pop 3, pop 2 -> push 6; stack: [1, 6]
OP_ADD             ; pop 6, pop 1 -> push 7; stack: [7]
OP_RETURN          ; pop 7 -> result 7

Notice the bytecode never has to represent precedence or parenthesization at all — by the time compilation is done, the order of instructions already encodes the correct evaluation order. All the operator-precedence logic your parser worked out gets "compiled away" into instruction ordering.

Edge cases to watch

• Stack underflow: popping when the stack is empty (malformed or buggy bytecode) should be treated as a serious internal error, not silently produce garbage.
• Division by zero: decide now whether this raises a runtime error or produces inf/nan, since it'll matter once real programs run through your VM.
• Instruction pointer bounds: the loop condition self.ip < len(self.chunk.code) is what prevents reading past the end of a chunk that doesn't end in OP_RETURN.