Create Your Own Programming Language with Rust

Virtual Machine

We’ve seen two ways to execute code: interpret the AST directly, or JIT compile to native machine code. There’s a third approach that sits in between: compile to bytecode, then interpret that.

Why would we do this?

• Simpler than JIT - No LLVM dependency, works everywhere
• Faster than AST interpretation - Bytecode is more compact and cache-friendly
• Portable - Same bytecode runs on any machine with our VM

This is how Python, Java, Ruby, and many other languages work. You compile source code to bytecode once, then run the bytecode interpreter wherever you need it.

What Is Bytecode?

Think of bytecode as a simplified assembly language designed for our VM. Real assembly has hundreds of instructions. Our bytecode has just four:

That’s it! With just these four operations, we can evaluate any arithmetic expression.

Step 1: Define Opcodes

We represent opcodes as bytes. This makes bytecode compact and fast to decode:

pub enum OpCode {
    OpConstant(u16), // pointer to constant table
    OpPop,           // pop is needed for execution
    OpAdd,
    OpSub,
    OpPlus,
    OpMinus,
}

calculator/src/compiler/vm/opcode.rs

Each opcode is assigned a unique byte value. When the VM sees 0x03, it knows to add. When it sees 0x01, it knows to load a constant.

We also need a way to construct these bytes:

        OpCode::OpConstant(arg) => make_three_byte_op(0x01, arg),
        OpCode::OpPop => vec![0x02],  // decimal repr is 2
        OpCode::OpAdd => vec![0x03],  // decimal repr is 3
        OpCode::OpSub => vec![0x04],  // decimal repr is 4
        OpCode::OpPlus => vec![0x0A], // decimal repr is 10
        OpCode::OpMinus => vec![0x0B], // decimal repr is 11

OpConstant is special - it takes an argument (which constant to load). We encode this as two bytes following the opcode, giving us up to 65,536 constants.

Step 2: Define Bytecode Structure

Our bytecode consists of two parts:

pub struct Bytecode {
    pub instructions: Vec<u8>,
    pub constants: Vec<Node>,
}

calculator/src/compiler/vm/bytecode.rs

• instructions - A flat array of bytes. Opcodes and their arguments, all mixed together.
• constants - A table of literal values. Instead of encoding 42 in the instruction stream, we store it in the constants table and reference it by index.

Example: Compiling 1 + 2

Let’s trace through what happens when we compile 1 + 2:

The AST has three nodes: Int(1), Int(2), and BinaryExpr(+). We walk the tree and emit bytecode:

1. Visit 1 - Add Int(1) to constants table (index 0). Emit OpConstant(0).
2. Visit 2 - Add Int(2) to constants table (index 1). Emit OpConstant(1).
3. Visit + - Emit OpAdd.
4. Done - Emit OpPop to clean up.

The result:

ByteCode {
    instructions: [1, 0, 0, 1, 0, 1, 3, 2],
    //             ^-----^  ^-----^  ^  ^
    //             OpConstant(0)  OpAdd  OpPop
    //                    OpConstant(1)
    constants: [Int(1), Int(2)]
}

Let’s decode those bytes:

• [1, 0, 0] = OpConstant with index 0 (two bytes: 0x00, 0x00)
• [1, 0, 1] = OpConstant with index 1
• [3] = OpAdd
• [2] = OpPop

Now we implement the compiler that generates this bytecode:

pub struct Interpreter {
    bytecode: Bytecode,
}

impl Compile for Interpreter {
    type Output = Bytecode;

    fn from_ast(ast: Vec<Node>) -> Self::Output {
        let mut interpreter = Interpreter {
            bytecode: Bytecode::new(),
        };
        for node in ast {
            println!("compiling node {:?}", node);
            interpreter.interpret_node(node);
            // pop one element from the stack after
            // each expression statement to clean up
            interpreter.add_instruction(OpCode::OpPop);
        }
        interpreter.bytecode
    }
}

calculator/src/compiler/vm/bytecode.rs

Notice how similar this is to the AST interpreter - we still recurse through the tree. The difference is that instead of computing results, we emit instructions.

Step 3: The Virtual Machine

Now we need a machine to execute our bytecode. Our VM is a stack machine - it keeps intermediate values on a stack.

Here’s the structure:

const STACK_SIZE: usize = 512;

pub struct VM {
    bytecode: Bytecode,
    stack: [Node; STACK_SIZE],
    stack_ptr: usize, // points to the next free space
}

• bytecode - The program to execute
• stack - Where we store intermediate values (a fixed-size array for speed)
• sp - Stack pointer: points to the next free slot

How Execution Works

The VM reads instructions left-to-right with an instruction pointer (IP). For 1 + 2, it processes OpConstant(0) (push 1), OpConstant(1) (push 2), OpAdd (pop both, push 3), and OpPop (return 3). Each opcode manipulates the stack accordingly.

Here’s the execution loop:

    pub fn run(&mut self) {
        let mut ip = 0; // instruction pointer
        while ip < self.bytecode.instructions.len() {
            let inst_addr = ip;
            ip += 1;

            match self.bytecode.instructions[inst_addr] {
                0x01 => {
                    //OpConst
                    let const_idx = convert_two_u8s_to_usize(
                        self.bytecode.instructions[ip],
                        self.bytecode.instructions[ip + 1],
                    );
                    ip += 2;
                    self.push(self.bytecode.constants[const_idx].clone());
                }
                0x02 => {
                    //OpPop
                    self.pop();
                }
                0x03 => {
                    // OpAdd
                    match (self.pop(), self.pop()) {
                        (Node::Int(rhs), Node::Int(lhs)) => self.push(Node::Int(lhs + rhs)),
                        _ => panic!("Unknown types to OpAdd"),
                    }
                }
                0x04 => {
                    // OpSub
                    match (self.pop(), self.pop()) {
                        (Node::Int(rhs), Node::Int(lhs)) => self.push(Node::Int(lhs - rhs)),
                        _ => panic!("Unknown types to OpSub"),
                    }
                }
                0x0A => {
                    // OpPlus
                    match self.pop() {
                        Node::Int(num) => self.push(Node::Int(num)),
                        _ => panic!("Unknown arg type to OpPlus"),
                    }
                }
                0x0B => {
                    // OpMinus
                    match self.pop() {
                        Node::Int(num) => self.push(Node::Int(-num)),
                        _ => panic!("Unknown arg type to OpMinus"),
                    }
                }
                _ => panic!("Unknown instruction"),
            }
        }
    }

    pub fn push(&mut self, node: Node) {
        self.stack[self.stack_ptr] = node;
        self.stack_ptr += 1; // ignoring the potential stack overflow
    }

    pub fn pop(&mut self) -> Node {
        // ignoring the potential of stack underflow
        // cloning rather than mem::replace for easier testing
        let node = self.stack[self.stack_ptr - 1].clone();
        self.stack_ptr -= 1;
        node
    }

calculator/src/compiler/vm/vm.rs

This is a fetch-decode-execute loop:

1. Fetch - Read the next byte (self.bytecode.instructions[ip])
2. Decode - Match on the opcode to determine what operation to perform
3. Execute - Manipulate the stack accordingly
4. Repeat - Increment IP and continue until we’re out of instructions

Why Stacks?

You might wonder: why use a stack? Why not just have named variables?

Stacks are neat because they handle any nesting automatically. For (1 + 2) * (3 + 4), we first compute 1 + 2 = 3 (leaving 3 on the stack), then 3 + 4 = 7 (now stack has [3, 7]), then multiply to get 21. Each operation just pops its inputs and pushes its output. The stack naturally tracks what’s “in progress.”

Running the VM

To compile and run code through our VM:

let byte_code = Interpreter::from_source(source);
println!("byte code: {:?}", byte_code);
let mut vm = VM::new(byte_code);
vm.run();
println!("{}", vm.pop_last());

Run tests locally:

cargo test vm --tests --features vm

Trade-offs: VM vs JIT vs Interpreter

The VM hits a sweet spot for many use cases. It’s why Python and Ruby use bytecode VMs - fast enough for most code, simple enough to implement everywhere.

Checkout the next section to see how to create a REPL for our Calc to compare different compilation paths interactively.