Implement a Stack-Based Virtual Machine

A virtual machine is a loop: read the next instruction, do what it says to the stack, move to the next instruction, repeat.

Learning Objectives

Build a VM: architecture, dispatch loop, program counter, operand stack, constant pool, locals, globals; arithmetic, comparison, branches, loops, I/O, halt and return.

Detect stack underflow/overflow and invalid instructions; validate before running; handle runtime errors; trace instructions; build a test harness, debug mode and disassembler.

Compare dispatch strategies (switch versus computed goto), stack caching, peephole optimisation and VM performance counters.

Plain-Language Explanation

A virtual machine is a loop: read the next instruction, do what it says to the stack, move to the next instruction, repeat. CONSTANT pushes a number, ADD pops two numbers and pushes their sum, JUMP_IF_FALSE decides where to continue. Everything else — functions, closures, errors — is built on that loop.

Precise Technical Explanation

State: the current function's code and constants, an instruction pointer, an operand stack, call frames (Module 11), a globals table and output. MiniLang's VM is about 150 lines of TypeScript.

Instruction dispatch loop ip points at the next opcode; operands are read after it; jumps modify it.

An array with a top index; push/pop are the hot path, so they must be cheap.

Read-only per function; CONSTANT k indexes it.

Local variable slots GET_LOCAL s reads stack[frame.base + s] — the locals live in the operand stack, below the temporaries.

A hash table from names to values; DEFINE_GLOBAL writes, GET_GLOBAL reads (error if missing), SET_GLOBAL updates existing.

Stack underflow and overflow Underflow: popping an empty stack (prevented by verification and checked defensively). Overflow: exceeding the stack limit (MiniLang: 256 values) or call-depth limit (64 frames) → runtime error instead of a crash.

Pop right, pop left, check types, compute, push.

EQUAL, GREATER, LESS; the compiler derives !=, >= and <= with NOT.

Branches and conditional jumps JUMP_IF_FALSE tests truthiness of the top value; JUMP is unconditional.

LOOP jumps backward to the loop condition.

Input/output operations PRINT writes to the output; a real VM would call host I/O through native functions.

Halt and return instructions HALT ends the script; RETURN ends a function and resumes the caller (Module 11).

Validate once before execution (verifier) rather than on every instruction; keep cheap defensive checks for anything the verifier cannot prove (e.g. undefined globals).

Runtime error handling Convert errors into language-level runtime errors with the source line from the line table and a stack trace of frames.

In debug mode, record each instruction with the stack before and after (MiniLang's trace option).

VM test harness Run programs on the VM and compare against expected outputs and against the reference interpreter (differential testing); run verifier tests on malformed input.

Debug mode and disassembly A debug build checks invariants on every step and can print disassembly and traces.

Instruction dispatch strategies Switch dispatch: one central switch; simple and portable; one shared indirect branch that is hard for the CPU's branch predictor. Threaded / computed-goto dispatch: each handler ends with its own indirect jump to the next handler, giving the predictor per-opcode history. Call threading and subroutine threading are other variants.

Switch dispatch versus computed-goto concept (compiler-specific)

Computed goto uses GCC/Clang's "labels as values" extension (&&label, goto *table[op]) — not standard C. CPython uses it when the compiler supports it. Measured below on this machine.

Stack caching overview Keeping the top one or two stack values in machine registers (or local variables) to avoid memory traffic; the VM's states multiply with the number of cached slots.

Bytecode peephole optimizations Rewriting short instruction windows: CONSTANT 2; CONSTANT 3; MULTIPLY → CONSTANT 6; NOT; JUMP_IF_FALSE → JUMP_IF_TRUE; removing jumps to the next instruction.

VM performance counters Count instructions executed per opcode, calls, allocations and maximum stack depth; these guide optimisation (Module 25).

VM limitations and next steps The MiniLang VM uses JavaScript values directly (no custom value representation), allocates closures on the host heap (the host's GC collects them) and has no JIT. Modules 11–14 add calls, closures, exceptions and GC concepts.

Python-style teaching VM (specification) This is deliberately minimal. A full implementation validates operands and stack depth before popping, handles malformed bytecode gracefully and defines exact instruction semantics — the complete version below does.

loop:
    opcode = code[ip]; ip += 1
    switch opcode:
        CONSTANT: push(constants[code[ip]]); ip += 1
        ADD:      b = pop(); a = pop(); push(a + b)
        ...

def run(code, constants):
    stack = []
    ip = 0

    while ip < len(code):
        instruction = code[ip]
        ip += 1

        if instruction[0] == "CONST":
            stack.append(constants[instruction[1]])
        elif instruction[0] == "ADD":
            right = stack.pop()
            left = stack.pop()
            stack.append(left + right)
        elif instruction[0] == "PRINT":
            print(stack.pop())
        elif instruction[0] == "HALT":
            return
        else:
            raise RuntimeError(f"Unknown opcode: {instruction[0]}")

Why It Matters in Real Systems

CPython, the JVM's interpreter, Lua, Ruby's YARV and WebAssembly interpreters are all variations on this loop; its efficiency sets the baseline speed of every language that runs on it.

Key Terms

Transferring control to an opcode's handler Indirect jump through a table of label addresses (GCC/Clang extension)

Keeping top-of-stack values in registers Rewriting short instruction sequences

Maximum number of instructions a run may execute

Syntax or Instruction Format

Instruction format as in Module 8. The VM's loop is the "syntax" of execution: fetch, decode, execute, repeat.

Complete Example

A complete validating stack VM in Python — validation before execution, typed operations, budget and readable errors (CPython 3.13.1):

The MiniLang VM running a loop, one instruction per line with the stack after it:

Switch versus computed-goto dispatch in C — the same tiny VM loop, 300 million instructions each (GCC 11.2 -O2, WSL2 x86-64; one real run, single-threaded; your numbers will differ):

Output (one real run):

OPS = {"CONST": 1, "ADD": 0, "SUB": 0, "MUL": 0, "LESS": 0, "JUMP": 1, "JUMP_IF_FALSE": 1, "PRINT": 0, "HALT": 0,
       "LOAD": 1, "STORE": 1, "POP": 0}
EFFECT = {"CONST": (0, 1), "ADD": (2, 1), "SUB": (2, 1), "MUL": (2, 1), "LESS": (2, 1), "JUMP": (0, 0),
          "JUMP_IF_FALSE": (1, 0), "PRINT": (1, 0), "HALT": (0, 0), "LOAD": (0, 1), "STORE": (1, 0), "POP": (1, 0)}


def validate(code, constants, n_locals):
    """Reject malformed programs before running: opcodes, operands, jump targets and stack depth on every path."""
    depth_at, work = {}, [(0, 0)]
    for i, ins in enumerate(code):
        op = ins[0]
        if op not in OPS or len(ins) != 1 + OPS[op]:
            return f"instruction {i}: bad opcode or operand count {ins}"
        if op == "CONST" and not 0 <= ins[1] < len(constants):
            return f"instruction {i}: constant index {ins[1]} out of range"
        if op in ("LOAD", "STORE") and not 0 <= ins[1] < n_locals:
            return f"instruction {i}: local slot {ins[1]} out of range"
        if op.startswith("JUMP") and not 0 <= ins[1] < len(code):
            return f"instruction {i}: jump target {ins[1]} outside the code"
    while work:
        i, d = w
…

output [42], 5 instructions
output [0, 1, 2], 40 instructions
rejected: instruction 0: ADD would underflow the stack (depth 0)
rejected: instruction 0: constant index 5 out of range
rejected: instruction 3: stack depth 0 differs from earlier 1
runtime error at instruction 2: ADD needs numbers, got 1 and 'x'
stopped: instruction budget of 1000 exceeded; output so far []

let i = 0;
while (i < 2) { print(i); i = i + 1; }

fn          offset  instruction                      stack after
<script>    0000    CONSTANT 0  ; 0                  [0]
<script>    0002    DEFINE_GLOBAL 0  ; 'i'           []
<script>    0004    GET_GLOBAL 0  ; 'i'              [0]
<script>    0006    CONSTANT 1  ; 2                  [0, 2]
<script>    0008    LESS                             [true]
<script>    0009    JUMP_IF_FALSE 15  ; → 27         [true]
<script>    0012    POP                              []
<script>    0013    GET_GLOBAL 0  ; 'i'              [0]
<script>    0015    PRINT                            []
<script>    0016    GET_GLOBAL 0  ; 'i'              [0]
<script>    0018    CONSTANT 2  ; 1                  [0, 1]
<script>    0020    ADD                              [1]
<script>    0021    SET_GLOBAL 0  ; 'i'              [1]
<script>    0023    POP                              []
<script>    0024    LOOP 23  ; → 4                   []
<script>    0004    GET_GLOBAL 0  ; 'i'              [1]
<script>    0006    CONSTANT 1  ; 2                  [1, 2]
<script>    0008    LESS                             [true]
<script>    0009    JUMP_IF_FALSE 15  ; → 27         [true]
<script>    0012    POP             
…

#include <stdint.h>
#include <stdio.h>
#include <time.h>

enum { PUSH1, ADD, DEC, JNZ, HALT };
/* program: acc += 1 repeatedly, counter-- , loop while counter != 0 */
static const uint8_t code[] = { PUSH1, ADD, DEC, JNZ, HALT };

static double now(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t); return t.tv_sec + t.tv_nsec / 1e9; }

static long run_switch(long n) {
    long acc = 0, one = 0, counter = n; int ip = 0;
    for (;;) {
        switch (code[ip++]) {
            case PUSH1: one = 1; break;
            case ADD:   acc += one; break;
            case DEC:   counter--; break;
            case JNZ:   if (counter) ip = 0; break;
            case HALT:  return acc;
        }
    }
}

static long run_goto(long n) {
    static void *labels[] = { &&L_PUSH1, &&L_ADD, &&L_DEC, &&L_JNZ, &&L_HALT };   /* GCC/Clang extension */
    long acc = 0, one = 0, counter = n; int ip = 0;
#define NEXT goto *labels[code[ip++]]
    NEXT;
L_PUSH1: one = 1; NEXT;
L_ADD:   acc += one; NEXT;
L_DEC:   counter--; NEXT;
L_JNZ:   if (counter) ip = 0; NEXT;
L_HALT:  return acc;
#undef NEXT
}

int main(void) {
    long n = 75 * 1000 * 1000;                /* 4 instructions per iteration = 300 
…

round 1  switch: 0.26 s (75000000)   computed goto: 0.17 s (75000000)
round 2  switch: 0.29 s (75000000)   computed goto: 0.17 s (75000000)

Line-by-Line Explanation

Python VM: validate checks every instruction's format and operands, then walks all control-flow paths with an abstract stack depth — rejecting underflow, bad jumps and inconsistent depths before run executes anything. run checks operand types and enforces an instruction budget.

The three rejected examples show different validation failures (underflow, a bad constant index, inconsistent stack depth at a merge point); the "x" example passes validation (types are dynamic) and fails at run time with a precise message; JUMP 0 loops forever and is stopped by the budget.

MiniLang trace: the loop's LOOP instruction jumps back to offset 4 (the start of the condition — offsets 0–3 initialise i); the final JUMP_IF_FALSE jumps to offset 27 when i < 2 is false, where POP removes the condition.

C: both functions execute the same instructions and compute the same result; only the dispatch mechanism differs. Results on modern CPUs with good indirect-branch predictors can be close — the measured difference here is specific to this machine and compiler.

Expected Output

As shown. Timings vary between runs and machines; the computed sums are deterministic (75,000,000).

Step-by-Step Runtime Behavior

For i < 2 with i = 0: GET_GLOBAL i → [0], CONSTANT 2 → [0, 2], LESS → [true], JUMP_IF_FALSE (no jump) → [true], POP → [], then the body.

Common Misconceptions

"The VM must check everything on every instruction." Validate once; keep only checks the verifier cannot prove.

"Computed goto always wins." Modern branch predictors narrow the gap; measure on your targets.

"A stack VM is just a stack." Frames, constants, globals and upvalues all matter.

Common Bugs and Failure Modes

Popping operands in the wrong order (a - b computed as b - a), forgetting to advance past operands, jumps relative to the wrong base, leaking stack values (missing POP), unbounded loops in untrusted programs.

Corrected or Safer Patterns

Pop right then left; define offsets relative to the next instruction; assert stack depth at statement boundaries in debug builds; always run with a budget.

Debugging and Inspection Techniques

Trace mode, per-opcode counters, stack-depth assertions, differential tests against the tree-walker, and the step-back VM visualizer.

Performance Considerations

Dispatch, operand decoding, value boxing and stack memory traffic dominate; register VMs, superinstructions, quickening and JITs reduce them (Modules 10, 16, 25).

Security Considerations

Every learner-provided program in the course's visualizers runs with an instruction budget and depth limits; never run unverified bytecode without bounds checks.

Portability and Version Caveats

Computed goto is a GCC/Clang extension (MSVC lacks it); portable VMs fall back to switch.

Real-World Use Cases

Embedded scripting VMs, query engines' expression evaluators, regex engines, emulators, eBPF interpreters, smart-contract VMs.

Best Practices

Separate validation from execution, keep the hot loop small, add tracing and counters behind a flag, and test against a reference interpreter.

Exercises

E1 · Beginner. Trace the stack for CONSTANT 7; CONSTANT 2; SUBTRACT; PRINT (constants 0 → 7, 1 → 2).

Answer: [7] → [7, 2] → [5] → [] (prints 5). SUBTRACT pops 2 (right) then 7 (left) and pushes 7 − 2.

E2 · Intermediate. Add a DUP instruction (duplicate the top value) to the Python VM, including validation.

Answer: Add "DUP": 0 to OPS and "DUP": (1, 2) to EFFECT (needs one value, leaves two); in run: stack.append(stack[-1]).

E3 · Advanced challenge. Write a peephole pass for the Python VM that folds CONST a; CONST b; ADD into one CONST.

Answer: Scan instructions; when three consecutive instructions match the pattern and no jump targets the second or third, replace them with CONST k for a new constant a + b, then rewrite all jump targets after the removed instructions (subtract 2). Re-validate the result.

Quiz

? In MiniLang, which value does SUBTRACT pop first?
+ The right operand :: Operands are pushed left to right, so the right one is on top.
- The left operand :: It is below the right operand.
- Both at once :: Pops happen one at a time.
- Neither; it reads them in place :: It pops both and pushes the result.

? Why does the Python VM validate before running?
+ To reject malformed bytecode safely before any instruction executes. :: Invalid jumps and underflow are caught up front.
- Because Python requires it. :: It is a design choice.
- To make loops faster. :: Validation is about safety.
- To detect infinite loops. :: The budget handles those.

? Which are dispatch strategies? (select all that apply)
+ A central switch statement :: Portable and simple.
+ Computed goto with a label table :: GCC/Clang extension.
- Garbage collection :: Memory management, not dispatch.
+ Subroutine threading :: Each instruction becomes a call.

Summary and Key Takeaways

A stack VM is a fetch–decode–execute loop over bytecode, with an operand stack, constants, locals, globals and frames. Validate once, check what you must at run time, bound every execution, trace in debug mode, and measure dispatch choices on real hardware.