Bytecode & Virtual Machines
An instruction set you get to design. Stack versus register machines, tree-walking versus bytecode, and the dispatch loop at the centre of both.
An intermediate executable representation: a flat array of instructions over an instruction set you designed, sitting between the syntax tree the frontend produced and the machine code you decided not to emit.
Operands live on a stack, so instructions do not need to say where their inputs are. `PUSH 1; PUSH 2; ADD` leaves `3` where the next instruction will look for it, and the whole encoding shrinks because of it.
Give the virtual machine numbered registers instead of an operand stack and `ADD r3, r1, r2` replaces three instructions with one — at the cost of a bigger instruction and a code generator that now has to decide which register everything lives in.
Register VMs execute fewer instructions; each instruction is larger and costs more to decode. The win is real, modest and workload-dependent, and the decision usually turns on who writes the code generator rather than on throughput.
One recursive function, `evaluate(node)`, switching on the node kind and calling itself on the children. It is the simplest correct implementation of a language, it is the right first one to write, and it pays a pointer chase and a dispatch for every node it visits.
AST to IR to bytecode to VM. The translation rule fits in one line — a three-address `%d = a op b` becomes push a, push b, op — and the interesting parts are what the operand stack replaces and why we emit from pre-SSA IR.
Fetch, decode, execute, repeat. Three lines of structure hold an entire language implementation, and the branch at the centre of them is one of the least predictable in ordinary software — which is why so much interpreter engineering is really branch engineering.
An interpreter runs the same algorithm as native code and takes roughly an order of magnitude longer to do it. The gap is a constant factor made of dispatch, type tests, boxing and memory traffic — and knowing which of the four is yours is the difference between a real speedup and a week spent on the wrong one.
The complete state of a running VM is six things: an instruction pointer, an operand stack, a stack of frames, per-frame locals, globals and a heap. Everything a VM can do is a function of that tuple, and everything a VM must decide — pausing, resuming, tracing, giving up — is a decision about where in the tuple to put the answer.