Skip to main content

A WebAssembly interpreter (Part 1)

· 9 min read

In our last blog post, we showed you a WebAssembly compiler that fits in a tweet. In just 192 bytes of JavaScript, it takes arithmetic expression written in postfix notation — like 20 2 * 2 + — and produces a Wasm module with a single function which evaluates the expression.

In this post, we’re going to look at WebAssembly from another angle: we’re going to write an interpreter for Wasm from scratch. So, rather than executing the Wasm module with Node.js, we’re going to examine the instructions and evaluate them ourselves.

At the end of this post we will have a bytecode interpreter (or virtual machine) that can evaluate arithmetic and comparison expressions like 2 * 3 + 4 == 10:


const vm = new VM([
i32.const(3),
i32.const(2),
i32.mul,
i32.const(4),
i32.add,
i32.const(10),
i32.eq,
]);

Does this sound fun? If so, read on!

The WebAssembly execution model​

If you’re not intimately familiar with WebAssembly and its execution model, a bit of background might be useful before we jump in.

At its heart, WebAssembly (or Wasm for short) is a low-level bytecode format. It’s mainly intended as a compilation target, allowing languages like C++, Go, and Rust to be executed in the browser at near-native speed.

Normally, to execute a Wasm module, a WebAssembly engine (like your browser) would translate the module’s bytecode to native machine code and execute that. But many engines include an interpreter — either in addition to a compiler, or instead of one (see wasm3).

Stack machines​

Like many other bytecode formats, WebAssembly is based on a stack machine model. This means that many instructions implicitly operate on a stack of values: popping their arguments, and pushing the result back to the stack.

Here’s a diagram showing the state of an interpreter, before and after it executes an i32.mul instruction:

Note that a fully-featured Wasm interpreter contains other state, but we won’t be dealing with any of that in this post.

Alright, are you ready to start implementing the interpreter?

If you’d like to follow along by running the code yourself, then you should start by creating a file named wasm-vm.js. All of the snippets we show will be added to that file. Let’s start with a few imports:

wasm-vm.js

import assert from 'node:assert';
import test from 'node:test';

The first step is to decide how we’ll represent the instructions. Usually an interpreter would operate on a binary stream of data, and then parse (or decode) the data into a more structured form.

In this post, we’ll skip the decoding and just work directly with the structured representation. Let’s start by defining a class to represent instructions:

wasm-vm.js

class Instruction {
constructor(opcode, name, evalFn) {
this.opcode = opcode;
this.name = name;
this.evalFn = evalFn;
}
eval(vm) {
return this.evalFn(vm);
}
}

And here’s a function to create instances in a compact way:

wasm-vm.js

const instr = (opcode, name, evalFn) => new Instruction(opcode, name, evalFn);

The Instruction fields are:

  • opcode: a numeric value that identifies the instruction in the binary encoding.
  • name: a human-readable instruction identifier.
  • evalFn: a function that takes a vm argument and operates on it according to the instruction’s specification.

Following the spirit of our book, let’s start with the minimum viable instruction — the one that does nothing, nop:

wasm-vm.js

const nop = instr(0x01, 'nop', (_vm) => {});

How do we test something that “does nothing”? We can evaluate it passing null as the vm argument to make sure it doesn’t use it:

wasm-vm.js

test('nop does nothing', () => {
const vm = null;
nop.eval(vm);
});

Other than doing nothing, WebAssembly deals mostly with numbers and operations on them. As we mentioned at earlier, these operations manipulate values on a stack.

The next thing we’ll need is a way to push values to the stack. For that, we’ll need to support instructions that take a value as a parameter, which the spec refers to as an immediate argument (or just immediate, for short).

Let’s define a new subtype of instruction that takes an immediate value:

wasm-vm.js

class InstructionImm extends Instruction {
constructor(opcode, name, immediate, evalFn) {
super(opcode, name, evalFn);
this.immediate = immediate;
}
eval(vm) {
return this.evalFn(vm, this.immediate);
}
}

And a function to create them:

wasm-vm.js

const instrImm = (opcode, name, immediate, evalFn) =>
new InstructionImm(opcode, name, immediate, evalFn);

Notice that for this type of instructions evalFn takes an extra argument, the immediate value.

The last piece we need is a way to represent numbers. An interesting thing about WebAssembly is that it’s a typed assembly language. WebAssembly 1.0 has four primitive value types:

  • i32
  • i64
  • f32
  • f64

We’ll start by defining the i32 type and add support for the rest later:

wasm-vm.js

class I32 {
constructor(value) {
this.value = value;
}
}
const i32 = (value) => new I32(value);

We are now ready to define our second instruction, i32.const, which takes an immediate (the value to be pushed to the stack).

wasm-vm.js

i32.const = (value) =>
instrImm(0x41, 'i32.const', value, (vm, imm) => vm.push(i32(imm)));

Since nop didn’t use the vm argument, we never defined a type for it. But i32.const pushes a value to the stack, so let’s define a Stack:

wasm-vm.js

class Stack {
constructor() {
this.items = [];
}
push(value) {
this.items.push(value);
}
// ...
}

Now we can test that our new instruction does the right thing:

wasm-vm.js

test('i32.const pushes an I32 to the stack', () => {
const vm = new Stack();
const instr = i32.const(42);
instr.eval(vm);
assert.deepStrictEqual(vm.items, [i32(42)]);
});

Notice that we pass an instance of Stack as the vm argument — it’s sufficient for now.

With values in the stack it makes sense to want to pop them too. The drop instruction does that:

wasm-vm.js

const drop = instr(0x1a, 'drop', (vm) => vm.pop());

To complete the implementation, we need to add the pop method to Stack:

wasm-vm.js

class Stack {
// ...
pop() {
return this.items.pop();
}
// ...
}

Let’s test that we can push and pop values:

wasm-vm.js

test('drop pops from the stack', () => {
const vm = new Stack();
run(vm, [i32.const(42), drop]);
assert.deepStrictEqual(vm.items, []);
});

Here’s the definition of the run function to evaluate a list of instructions:

wasm-vm.js

function run(vm, instructions) {
for (const instr of instructions) {
instr.eval(vm);
}
}

Ok, the test should now pass!

Pushing and popping values is a decent start, but what else can we do with them? We can add them together, with the i32.add instruction:

wasm-vm.js

i32.add = instr(0x6a, 'i32.add', (vm) => {
const c2 = vm.popI32();
const c1 = vm.popI32();
const c = i32(c1.value + c2.value);
vm.push(c);
});

To evaluate i32.add:

  • Pop two values from the stack, asserting that they are of type i32
  • Add them
  • Push the result back to the stack.

This instruction uses a new method: popI32. Let’s extend Stack with methods to operate on the top value and check its type:

wasm-vm.js

class Stack {
// ...
peek() {
return this.items.at(-1);
}
topIsOfType(Class) {
return this.peek() instanceof Class;
}
assertTopIsOfType(Class) {
if (!this.topIsOfType(Class)) {
throw new Error(
`Expected ${Class.name} on top of stack, got ${this.peek()}`,
);
}
}
popType(T) {
this.assertTopIsOfType(T);
return this.pop();
}
popI32() {
return this.popType(I32);
}
// ...
}

Now we have everything we need to test i32.add:

wasm-vm.js

test('i32.add pops two I32s and pushes their sum', () => {
const vm = new Stack();
run(vm, [i32.const(42), i32.const(23), i32.add]);
assert.deepStrictEqual(vm.items, [i32(65)]);
});

The run function runs the instructions to completion, but it would be nice to step and inspect the intermediate states too.

Let’s create a proper VM class with a stack, a list of instructions, and a program counter (pc) to keep track of the current instruction. We’ll add methods to manipulate the stack and step through instructions:

wasm-vm.js

class VM {
constructor(instructions) {
this.stack = new Stack();
this.instructions = instructions;
this.pc = 0;
}
push(value) {
this.stack.push(value);
}
pop() {
return this.stack.pop();
}
peek() {
return this.stack.peek();
}
popI32() {
return this.stack.popI32();
}
popType(T) {
return this.stack.popType(T);
}
step() {
const instruction = this.instructions[this.pc];
instruction.eval(this);
this.pc += 1;
}
steps(count) {
for (let i = 0; i < count; i++) {
this.step();
}
}
}

Notice that most of the methods delegate to the stack. An interesting one is the step method: it fetches the current instruction, evaluates it, and increments the program counter.

Let’s add two numbers again, but this time, we’ll check the stack after each step:

wasm-vm.js

test('VM executes two i32.const and an i32.add', () => {
const vm = new VM([i32.const(42), i32.const(23), i32.add]);
vm.step(); // Eval `i32.const 42`
assert.deepStrictEqual(vm.stack.items, [i32(42)]);
vm.step(); // Eval `i32.const 23`
assert.deepStrictEqual(vm.stack.items, [i32(42), i32(23)]);
vm.step(); // Eval `i32.add`
assert.deepStrictEqual(vm.stack.items, [i32(42 + 23)]);
});

This test should pass.

A natural next step is to implement the rest of the arithmetic operations that, like i32.add:

  1. Take two values from the stack
  2. Perform an operation on them
  3. Push the result back.

In the spec, these operations are collectively called t.binop, where t is the type — in our case, i32.

Let’s create a function to define them:

wasm-vm.js

function binop(opcode, name, fn) {
return instr(opcode, name, (vm) => {
// 2. Pop the value t.const c2 from the stack.
const c2 = vm.popI32();
// 3. Pop the value t.const c1 from the stack.
const c1 = vm.popI32();
// 4.1 Let c be a possible result of computing binop<t>(c1, c2).
const c = i32(fn(c1.value, c2.value));
// 4.2 Push the value t.const c to the stack.
vm.push(c);
});
}

Let’s try it by defining i32.sub:

wasm-vm.js

i32.sub = binop(0x6b, 'i32.sub', (c1, c2) => c1 - c2);

Testing binops is as regular as defining them. Let’s create a function for testing binary operations:

wasm-vm.js

function checkBinop(c1, c2, instruction, expected) {
const vm = new VM([i32.const(c1), i32.const(c2), instruction]);
vm.steps(3);
assert.deepStrictEqual(vm.stack.items, [i32(expected)]);
}

And use it to test i32.sub:

wasm-vm.js

test('i32.sub', () => {
checkBinop(42, 23, i32.sub, 42 - 23);
});

Now let’s define i32.mul and i32.div_s, and a small test for each:

wasm-vm.js

i32.mul = binop(0x6c, 'i32.mul', (c1, c2) => c1 * c2);
i32.div_s = binop(0x6d, 'i32.div_s', (c1, c2) => Math.trunc(c1 / c2));
test('i32.mul', () => {
checkBinop(42, 23, i32.mul, 42 * 23);
});
test('i32.div_s', () => {
checkBinop(42, 23, i32.div_s, Math.trunc(42 / 23));
checkBinop(2, -3, i32.div_s, Math.trunc(2 / -3));
});

After arithmetic operations a good next step is to implement comparison operations, known in the spec as relops.

A relop is like a binop in that it takes two values from the stack and pushes one back. The difference is that the value it pushes back is either i32(1) to represent true or i32(0) to represent false.

Let’s create a function to define them:

wasm-vm.js

function relop(opcode, name, fn) {
return binop(opcode, name, (c1, c2) => (fn(c1, c2) ? 1 : 0));
}

We are reusing binop and wrapping the provided fn in a function that returns 1 if the call to fn(c1, c2) is truthy and 0 if not.

Let’s define our first relop, i32.eq which checks if two i32s are equal:

wasm-vm.js

i32.eq = relop(0x46, 'i32.eq', (c1, c2) => c1 === c2);

And test it using checkBinop:

wasm-vm.js

test('i32.eq', () => {
checkBinop(42, 23, i32.eq, 0);
checkBinop(23, 23, i32.eq, 1);
});

We can now implement the remaining relops:

wasm-vm.js

i32.ne = relop(0x47, 'i32.ne', (c1, c2) => c1 !== c2);
i32.lt_s = relop(0x48, 'i32.lt_s', (c1, c2) => c1 < c2);
i32.gt_s = relop(0x4a, 'i32.gt_s', (c1, c2) => c1 > c2);
i32.le_s = relop(0x4c, 'i32.le_s', (c1, c2) => c1 <= c2);
i32.ge_s = relop(0x4e, 'i32.ge_s', (c1, c2) => c1 >= c2);

And that’s it for now! All the tests should be passing. We now have an interpreter that does arithmetic and comparison operations using a stack — let’s try it with a complex expression:

wasm-vm.js

test('complex expression works', () => {
// 2 * 3 + 4 == 10;
const vm = new VM([
i32.const(3),
i32.const(2),
i32.mul,
i32.const(4),
i32.add,
i32.const(10),
i32.eq,
]);
vm.steps(3); // Eval `i32.const 3; i32.const 2; i32.mul`
assert.strictEqual(vm.stack.peek().value, 6);
vm.steps(2); // Eval `i32.const 4; i32.add`
assert.strictEqual(vm.stack.peek().value, 10);
vm.steps(2); // Eval `i32.const 10; i32.eq`
assert.deepStrictEqual(vm.stack.items, [i32(1)]);
});

🏁 wasm-vm-01/wasm-vm.js
Open in StackBlitz

That’s a pretty good start! We’ve got the core of a simple interpreter for WebAssembly 1.0 instructions. In the next post, we’ll extend this interpreter, and add support for instructions that operate on local variables.

Let’s finish things off by exporting all the things that we’ll use in the next post:

wasm-vm.js

export {I32, drop, i32, instr, nop, Stack, VM};

Catch you next time!

Thanks to Job van der Zwan and Karl Weber for providing helpful feedback on this post.

If you enjoyed this post, you should check out WebAssembly from the Ground Up — an online book to learn Wasm by building a simple compiler in JavaScript.

If you’d like to be notified when we publish the next post, you can sign up for our mailing list, where we share periodic updates on the book and interesting WebAssembly tidbits.