So You Want to Build a Language VM - Part 01 - Overview and a Simple VM

Covers getting a basic VM started and design goals

iridium

Introduction

Hi there! This is the first post in a series on building a VM/interpreter for a programming language in Rust. Its something I’ve been tinkering with for a few months so am turning them into a tutorial series. === Why? It is a topic in CS that has always interested me. When I began to write Elixir and Erlang code last year, I was impressed with the BEAM VM. Not just for executing code, either, but for its abilities as a command and control platform for applications, built-in clustering, and other features. I come from an infrastructure background, and one of my pet theories is that a lot of what we rely on tools like Docker for could be better served by the language VM.

Inspiration and Credits

There were a few websites, books, and projects I referenced heavily while working on this:

  1. Thorsten Ball has an awesome book, Writing an Interpreter in Go, that walks you through writing a tree-walking interpreter in Go. It is thorough, well-written, and a great introduction to the topic.

  2. The BEAM VM (https://en.wikipedia.org/wiki/BEAM_(Erlang_virtual_machine))

  3. The Lua VM (http://files.catwell.info/misc/mirror/lua-5.2-bytecode-vm-dirk-laurie/lua52vm.html) and (http://luaforge.net/docman/83/98/ANoFrillsIntroToLua51VMInstructions.pdf)

  4. The Wren VM (https://github.com/munificent/wren and http://wren.io)

  5. The Dis VM (http://www.vitanuova.com/inferno/papers/dis.html)

Code

You can find the code at https://gitlab.com/subnetzero/iridium.

Goals

We want our VM to be:

  1. Reasonably performant compared to modern implementations. We’ll use Python as our comparison.

  2. Fault tolerant.

  3. Serves as command and control platform for running applications.

  4. Clustering of VMs running on different physical servers.

Types

Interpreters fall in to one of three categories:

  1. Tree-walking

  2. Stack-based

  3. Register-based

Important
If you want a refresher on what a CPU is, assembly, etc, check out https://blog.subnetzero.io/post/building-language-vm-part-00/

Tree Walking Interpreters

A tree-walking interpreter transforms your source code into a tree-like data structure, starts at the root of the tree and visits each node, performing operations as it goes along. These are often the first interpreters someone codes.

Benefits

  • Simple

  • Allows greater flexibility to further transform the code because it is already in a data structure

Drawbacks

  • Slow compared to the other types

Stack Based Interpreters

These are the most common. The JVM is one, the Python VM is another. These VMs store operations and results on a stack. When the VM executes an instruction, it pops the most recent value off the stack, performs the operation, and pushes the result back on.

Benefits

  • Easier to code than a register-based VM

  • Decent performance

Drawbacks

  • Does not map to real hardware; CPUs use registers.

  • Most tasks require more instructions

Register Based Interpreters

These are the last type, and are the least common. Examples include the BEAM VM (sometimes called the Erlang VM), the Lua VM and the Dalvik VM (the thing that runs Java code on Android).

Benefits

  • Register-based VMs are much closer to how actual hardware works

  • More performant

Drawbacks

  • More complex to code

  • We have to worry about register allocation and de-allocation when writing our compiler

So We’re Coding…​which?

…​a register based VM!

Why? They’re more interesting to me. The Internet has quite a few tutorials on how to implement a tree-walking or stack-based virtual machine. There’s far fewer for register based VMs.

Don’t worry, it’ll be fun! =)

Assembly

The next step up from raw 0s and 1s in terms of language abstraction. Here’s an approximate hierarchy/timeline of computer languages:

  1. Binary

  2. Assembly

  3. FORTRAN, C, and later languages like Rust

    • Called "high-level languages" when they first came out, we now often refer to them as low-level languages.

  4. Perl, Bash, Python, Ruby, and later languages like Go

    • These are the "very high-level" languages

    • Yes, Go could fit into the C level languages section too

  5. SQL and other DSL (Domain Specific Languages)

    • Also Excel macros and other nightmarish horrors

As we work through this project, we’re going to create an assembly language and assembler so we can write programs in something other than a hex editor. Then later on, we’ll work on an even higher level language that compiles down to our assembly, and then down to our bytecode.

Note
If you have some experience with assembly, know the one we will be writing is a RISC-style, MIPS-inspired assembly, because it seemed simplest.

Structure of an Assembly Instruction

Our virtual CPUs will have the ability to take 32 bits of data at a time, execute it, and then go get another group of 32 bits. At a very general level, that is all hardware processors do:

  1. Read next instruction

  2. Execute instruction

  3. Repeat

They just do it really, really fast.

Breaking Up is Hard to Do

We can break our 32-bit instructions out into smaller blocks. This lets us put multiple arguments in one line:

LOAD $0 #500
and not have to do:
LOAD
$0
#500

Note
The smallest unit of bits we are going to work with right now is 8, so a single byte. A later enhancement will let us use more exotic bit numbers.

Instructions

So, a quick terminology review. A grouping of 32-bits is an Instruction. The first 8 bits of those 32 will contain our Opcode. The remaining bits will be dedicated to Operands. With this design, an Opcode can have 0, 1, 2, or 3 Operands.

The table below shows all the permutations we’ll be using:

Opcode (8 bits)

Opcode (8 bits)

Operand 1 (24 bits)

Opcode (8 bits)

Operand 1 (8 bits)

Operand 2 (16 bits)

Opcode (8 bits)

Operand 1 (8 bits)

Operand 2 (8 bits)

Operand 3 (8 bits)

This shows the ways to use our 32 bits we have available for an instruction. The HLT instruction (or opcode), which stops execution, has no operands, so we use 1 8-bit operator. The remaining 24 bits will be zero’d. Throughout the tutorial, I’ll show the bytecode in hex, laid out like so:

HLT Example
0x06 00 00 00

HLT is just the number 6, and we need no operands, so this is one complete instruction our VM could execute. Everything else is just building on top of this.

Starting the Project

Let’s begin by creating a new Rust project with cargo. The rest of this tutorial assumes you have installed the latest version of Rust and the cargo executable is on your PATH. If you haven’t, go to https://rustup.rs/ to get setup.

$ cargo new iridium --bin

Hop into the newly created iridium directory and make a new file under the src/ directory called vm.rs:

$ cd iridium
$ touch src/vm.rs

You can open vm.rs in whatever editor you prefer (which should be vim, of course).

In the Code

OK, let’s start coding! Remember, all we’re doing is writing a piece of software that emulates the functionality of a hardware CPU. So let’s start with a simple struct.

pub struct VM {

}

First off, let’s give our little VM some registers. We can represent the registers with an array:

pub struct VM {
    registers: [i32; 32]
}
Note
Why use an array and not a vector? Because we know the number we need at compile time.

And then in the implementation block for the struct:

impl VM {
    pub fn new() -> VM {
        VM {
            registers: [0; 32]
        }
    }
}

This will initialize all registers to zero whenever we create a VM.

Tests

Before we go much further, let’s write some tests. After all, we wouldn’t want to be like those developers who never write tests, would we?

In src/vm.rs, at the end, put the following:

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_create_vm() {
        let test_vm = VM::new();
        assert_eq!(test_vm.registers[0], 0)
    }
}

Next, add the following in src/main.rs at the top:

pub mod vm;

(You can also empty out the main function from the default of printing Hello World!)

You should now be able to run cargo test from the main directory and see one test run and pass. Yay! We’re on our way! In the next section, we’ll do our first opcode!

If you need some assistance with any of the topics in the tutorials, or just devops and application development in general, we offer consulting services. Check it out over here or click Services along the top.