Building a stack-based virtual machine, part 5 - the machine
Tags: rust, language, theory, computerscience
Published: 2018-09-09 21:39:32

---
title: Building a stack-based virtual machine, part 5 - the machine
published: true
description: The fifth part in my exploration of stack based VMs and how they work
tags: rust, language, theory, computerscience
---

In the [last episode](https://dev.to/jimsy/building-a-stack-based-virtual-machine-part-4---code-3lmi) we built a code generator and a program representation so we now have all but that last bit we need to run our virtual machine.

## Introducing the machine

So far we've built all the primary structures required to assemble our program, we have [code](https://dev.to/jimsy/building-a-stack-based-virtual-machine-part-4---code-3lmi), [instructions](https://dev.to/jimsy/building-a-stack-based-virtual-machine-part-3---instructions-4b3a) and [a stack](https://dev.to/jimsy/building-a-stack-based-virtual-machine-part-2---the-stack-d07).  The last major thing we need to do before we can run our programs is the machine itself.  Like Captain Planet we're going to assemble our constituent parts into a greater whole.

Here's our machine:

```rust
pub struct Machine<'a, T> {
  code: Code<T>,
  instruction_table: &'a InstructionTable<T>,
  ip: usize,
  operand_stack: Stack<T>
}

impl<'a, T> Machine<'a, T> {
  pub fn new(code: Code<T>, instruction_table: &'a InstructionTable<T>) -> Machine<'a, T> {
    Machine {
      code: code,
      instruction_table: instruction_table,
      ip: 0,
      operand_stack: Stack::new()
    }
  }
}

```

So when we create our machine we pass in our code and our instruction table.  It sets the instruction pointer to zero (ie the first instruction in the code), creates an empty stack and returns our fancy new machine.

Before we can run any code we need to give it some handy helper methods for manipulating the operand stack and retrieving data from the data section.  These are used by our instructions because if you remember they receive a mutable reference to the machine as their first argument.

```rust
impl<'a, T> Machine<'a, T> {

    pub fn operand_push(&mut self, value: T) {
        self.operand_stack.push(value);
    }

    pub fn operand_pop(&mut self) -> T {
        self.operand_stack.pop()
    }

    pub fn get_data(&self, idx: usize) -> &T {
        self.code
            .data
            .get(idx)
            .expect(&format!("Constant data is not present at index {}.", idx))
    }

}
```

No we can finally go ahead and add our `run` method to the machine.  It's a reasonable chunk of code so let's break it down a bit first into some basic ideas:

  * Keep looping until the instruction pointer (IP) is the same as the length of the program (ie we've run out of program).
  * Read the opcode from our program at IP.
  * Read the arity from our program at IP + 1.
  * From 0 to arity read argument indexes from the program and push them into an arguments vector.
  * Call the instruction with the arguments.

```rust
impl<'a, T> Machine<'a, T> {

    pub fn run(&mut self) {
        loop {
            if self.ip == self.code.code.len() {
                break;
            }

            let op_code = self.next_code();
            let arity = self.next_code();

            let instr = self.instruction_table.by_op_code(op_code).expect(&format!(
                "Unable to find instruction with op code {}",
                op_code
            ));

            let mut args: Vec<usize> = vec![];

            for _i in 0..arity {
                args.push(self.next_code());
            }

            let fun = instr.fun;
            fun(self, args.as_slice());
        }
    }

    fn next_code(&mut self) -> usize {
        let code = self.code.code[self.ip];
        self.ip = self.ip + 1;
        code
    }

}
```

Now we have enough infrastructure in place to run our first program!

We're going to make a really simple arithmetic machine because I can do that without making this blog post too long.  We need two instructions; *Push* which takes data and pushes it to the stack and *Add* which pops two operands off the stack, adds them together and pushes the result back onto the stack:

```rust
fn push(machine: &mut Machine<isize>, args: &[usize]) {
    let arg = *machine.get_data(args[0]);
    machine.operand_push(arg);
}

fn add(machine: &mut Machine<isize>, _args: &[usize]) {
    let rhs = machine.operand_pop();
    let lhs = machine.operand_pop();
    machine.operand_push(lhs + rhs);
}

fn instruction_table() -> InstructionTable<isize> {
    let mut it = InstructionTable::new();
    it.insert(Instruction::new(0, "push", 1, push));
    it.insert(Instruction::new(1, "add", 0, add));
}
```

Next we need our program, it's going to add `2` and `3` together:

```rust
fn build_program(it: &InstructionTable<isize>) -> Code<isize> {
    let mut builder = Builder::new(&it);
    builder.push("push", vec![2]);
    builder.push("push", vec![3]);
    builder.push("add", vec![]);
    Code::from(builder)
}
```

Now let's run it:

```rust
#[test]
fn addition_example() {
    let it = instruction_table();
    let code = build_program(&it);
    let mut machine = Machine::new(code, &it);
    machine.run();
    let result = machine.operand_pop();
    assert_eq!(result, 5);
}
```

And that's it. We've run our very first program in our virtual machine.  Of course it's not very useful without function calls, so we'll add them in the [next episode](https://dev.to/jimsy/building-a-stack-based-virtual-machine-part-6---function-calls-2md5).