Stack machine, part 1 - The deleted slide

During my ElixirConf talk I compared and contrasted register-based virtual machines, like the BEAM, to stack-based virtual machines, like the JVM. In doing so, I went through a disassembled Java method that adds its two arguments and doubles the sum before returning it. I also mentioned how comparably easy it is to implement stack-based virtual machines and originally intended to include a basic implementation in the talk. In the end I decided to cut that part in order to have a more focused and cohesive talk.

Released a few days after the conference, in episode 199 of the Elixir Sips screencast, Josh Adams demonstrates how to implement a register-based virtual machine in Elixir. Apparently, he got inspired during my talk to do so which is quite gratifying.

@avdi @confreaks @ElixirConf @DevLCSC can confirm it was great. I wrote http://t.co/sm3MbXUbBT during it!

— Elixir Sips (@elixirsips) October 15, 2015

Given this, I thought it could be entertaining to resurrect the deleted slide, expand on it, and use it as the basis of a series of posts. Enjoy!

A basic stack-based virtual machine

Let’s say we have some bytecode that we want to execute. The bytecode consists of a mix of instructions and data. Normally it’d be in a binary format like for example a BEAM file, but for clarity we’ll represent the bytecode with a list. Instead of binary opcodes, we’ll represent our instructions as atoms. For this particular example, we’ll only use integers as data.

Behold our glorious program!

[:push, 4, :push, 5, :add, :push, 2, :multiply]

We’ll start by pushing the value 4 onto the stack, followed by the value 5. We’ll then add the top two values on the stack and place the result back on the stack. That should give us a stack of a single value; 9. Then we push the value 2 onto the stack. Lastly we multiply the two top values on the stack, placing the final result back on the stack. We should end with the stack having one element; the value 18.

So how do we go about doing this? Well, let’s start with a public execute/1 function that takes the list representing the bytecode and dispatches to the private _execute/2 function, injecting an empty stack in the form of a list.

defmodule StackMachine do
  def execute(code), do: _execute(code, [])

Since the _execute/2 function will process a single instruction at a time and then call itself, we start with the base case of not having any bytecode to process. In that case we simply return the stack unaltered.

  defp _execute([], stack), do: stack

Next up is the push instruction. Since it inherently is followed by the value to be pushed onto the stack, we pattern match on the instruction opcode, here the atom :push, followed by a value. We then make a recursive call using the rest of the bytecode and the changed stack as parameters.

  defp _execute([:push | [value | code]], stack) do
    _execute(code, [value | stack])
  end

The add and multiply instructions on the other hand, only consume a single element of the bytecode. In return, they both pop the two first elements of the stack, and put back the result on the stack.

  defp _execute([:add | code], [a | [b | rest_of_stack]]) do
    _execute(code, [a + b | rest_of_stack])
  end
  defp _execute([:multiply | code], [a | [b | rest_of_stack]]) do
    _execute(code, [a * b | rest_of_stack])
  end

As we only need to support these three instructions, we stop here, giving us the following code.

defmodule StackMachine do
  def execute(code), do: _execute(code, [])

  defp _execute([], stack), do: stack
  defp _execute([:push | [value | code]], stack) do
    _execute(code, [value | stack])
  end
  defp _execute([:add | code], [a | [b | rest_of_stack]]) do
    _execute(code, [a + b | rest_of_stack])
  end
  defp _execute([:multiply | code], [a | [b | rest_of_stack]]) do
    _execute(code, [a * b | rest_of_stack])
  end
end

Running this, we see that we do in fact get the expected result of 18 as the only remaining part of the stack.

iex(1)> code = [:push, 4, :push, 5, :add, :push, 2, :multiply]
[:push, 4, :push, 5, :add, :push, 2, :multiply]
iex(2)> StackMachine.execute code
[18]

A bit too basic

While this does demonstrate the general principle of a stack-based machine, surely we wouldn't want to leak the stack as the result rather than the result itself?

True enough and easily fixed. We can let the default _execute/2 clause act as an implicit return instruction, extracting the top-most stack value and discard the rest of the stack.

  defp _execute([], stack), do: hd(stack)

But does the lack of further instructions to execute really entail returning the top of the stack? Doesn't it really tell us to stop program execution? If so, we would be better served by adding an explicit return instruction to our bytecode.

[:push, 4, :push, 5, :add, :push, 2, :multiply, :return]

And we add another _execute/2 function clause to handle the new instruction.

  defp _execute([:return | _code], stack), do: hd(stack)

But a return instruction does more than just returning a value. It also continues program execution at the place of the function call. This leads us into the realm of codifying functions and keeping track of what piece of code we're actually executing. Let's look at that in the next part of this series.