Virtual Machine

Last updated May 26, 2023 Edit Source

A tree-walk Abstract Syntax Tree interpreter is slow. The parser converts tokens into individual AST objects, which use up a lot of memory and do not take advantage of spatial locality.

Structurally, bytecode resembles machine code. It’s a dense, linear sequence of binary instructions. That keeps overhead low and plays nice with the cache. However, it’s a much simpler, higher-level instruction set than any real chip out there. (In many bytecode formats, each instruction is only a single byte long, hence “bytecode”.)

Bytecode is an idealized fantasy instruction set that makes your life as the compiler writer easier.

The problem with a fantasy architecture, of course, is that it doesn’t exist. We solve that by writing an emulator—a simulated chip written in software that interprets the bytecode one instruction at a time. A virtual machine (VM), if you will.

The VM is the runtime of the bytecode. It will execute bytecode instructions to do what we want.

A VM which uses a stack to execute instructions. When an instruction “produces” a value, it pushes it onto the stack. When it needs to consume one or more values, it gets them by popping them off the stack.

1
2
3
4
5
6

define BINARY_OP(op) \
    do { \
      double b = pop(); \
      double a = pop(); \
      push(a op b); \
    } while(false)