Building a stack-based virtual machine

I've been reading Fletcher Haynes' great series about register-based VM's over the last few days and I thought it was about time I talked about how I created stack-vm crate.

Let's start with some background; my goto exercise when I am learning a new language is to implement a programming language. Building a language uses all the tools in a programmer's toolbox and gives you plenty of opportunity to flex your brain muscle. I figure if you can make a working (if simple) programming language using a particular tool then you can make almost anything your customer or employer wants. Over the years I've build languages in Ruby, Rubinius, Elixir, Erlang, Rust and C++/LLVM. Collectively all these languages have been called "Huia", despite not having anything in common except their author. Some of them are lying around the internet, some have been removed for posterity.

When it came time to learn Rust last year I decided than rather than build a language as a horrible complected mess I would pick specific parts of a programming environment and build them. This is why I built wrc and stack-vm.

What is a stack-based virtual machine?

There are three main types of Von Neumann machines:

• Accumulator - the most basic form of processor where only a single register is used to store the results of computation.
• Stack - stack machines use an operand stack to push and pop results off the top.
• Register - register machines use a number of named (or numbered) registers to store values or pass arguments.

As far as I can tell most language virtual machines are stack machines (non-scientific sample - don't at me). I expect that this is largely due to the fact that they're a little easier to write and you don't have to keep track of your register usage when writing your assembly.
Interestingly both stack and register machines can emulate each other which makes sense since we run them all on physical processors which are usually register machines.

You can think of a stack as something as simple as an array. When you initialize your machine the stack is empty (i.e [ ]) and each instruction executed by the machine can pop values off the top of the stack and push values onto the stack. Say we start with the simple calculator example and add two numbers:

• Initialize machine ([ ])
• Use a push instruction to add the number 2 onto the stack: push 2 ([ 2 ])
• Push the number 3 onto the stack: push 3 ([ 2, 3 ])
• Use an add instruction to pop two items off the stack and push back the result add ([ 5 ])

Hopefully that's enough for you to get a basic idea of how a stack machine works.

Stack machine terminology

Here's a few basic terms that we're going to use in the course of this series:

• Stack - A pile of values, usually in the form of an array or vector where values can be added and removed from the "top" only.
• Operand - The values that are being added and removed to the stack and operated upon by the instructions.
• Instruction - The smallest unit of behaviour in our machine. Instructions can pop operands off the stack, operate on them and then push results back onto the stack.
• Opcode - Short for operation code. A unique number which corresponds to a specific instruction to allow programs to be serialised more compactly than using their names.
• Program - A list of instructions (usually by opcode) and their operand arguments for the machine to execute.
• Instruction Pointer - A index into the program which keeps track of the currently executing (or next) instruction.

There are a few other bits and bobs but we'll cover them off as we go.

Want to see some actual code? Move on to part 2.