2 posts tagged with "code"

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:

Does this sound fun? If so, read on!

Alright, are you ready to start implementing the interpreter?

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:

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

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.

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:

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:

And a function to create them:

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:

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:

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

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:

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

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

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

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:

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:

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

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:

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:

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.

Let’s create a function to define them:

Let’s try it by defining i32.sub:

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

And use it to test i32.sub:

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:

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:

And test it using checkBinop:

We can now implement the remaining relops:

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:

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:

Catch you next time!

---

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

Introduction

One of the initial explorations that started this book was how small and simple a compile-to-WebAssembly language implemented in JavaScript could be. Our first “WebAssembly compiler in a tweet” was 269 bytes; since then, we’ve managed to whittle it down to a measly 192 bytes.

The final result is a compiler that takes an arithmetic expression — written in reverse polish notation — and compiles it down to a valid WebAssembly module. That module exports a single function which returns the result of the original arithmetic expression. Here it is:

And here’s an example of how you can use it:

But this is not just a clever trick — if you take the time to understand what this code does, you’ll learn a surprising amount about WebAssembly! In the rest of the post, we’ll explain how it all works by de-obfuscating the code one step at a time.

You can play with the code in this post here: stackblitz.com/edit/rpn-to-wasm-js-compiler.

Format

The first thing we can do to make it more readable is to format it:

While it’s still pretty unreadable, now we can at least identify different parts of the code.

At a high level, what we’re doing is ‘parsing’ the expression in a very simple way, turning it into the appropriate Wasm bytecode, and then hand-crafting the bytes for a single-function module.

In a more complex compiler you would probably use a library to generate the WebAssembly module and compile the expressions but our main metric here is code size so we write the bytes directly in an array.

Remove Assignment Expression

The first trick to undo is the assignment expression.

In JavaScript the assignment operator is an expression. This means that it generates a result after evaluating, as you can see in the following examples:

The code above will output:

This is because a = 42 assigns 42 to a and the whole assignment expression evaluates to the value being assigned.

In a = b = 43, we assign the result of evaluating b = 43 to a. This equivalent expression may be easier to understand: a = (b = 43).

In our code, we use this trick to reuse variables and update their value in places where we can also use the value being assigned. It also allows us to have our compiler in a single expression, avoiding the need for curly braces, semicolons and return statements.

To undo it, we turn the body of our function into a block and do each assignment on its own line:

let c2 = (b, l) => {

b = b.split` `.flatMap(

(t) => (t > -1 ? [65, t] : 107 + "-*/".indexOf(t))

);

l = b.length + 4;

return WebAssembly.instantiate(

new Int8Array([

, 97, 115, 109, 1, , , , 1, 5, 1, 96, , 1, 127, 3, 2, 1, , 7, 4, 1, , , ,

10, l, 1, l - 2, , ...b, 11

]),

);

};

Undo Variable Tricks

Now the assignments are easier to identify but the meaning of variables and function arguments are still hard to understand. Let’s fix that by undoing a couple of variable tricks.

The first step is to stop using single letter variables, and to use more descriptive names instead. The next step is to stop reusing variables: for example, b initially holds the code to compile, but once we don’t need that any more we reuse it to hold the bytecode instructions.

To undo this we are going to introduce a new instrs variable and rename b to code. We’ll also rename l to len. This variable contains a value that is close to the number of bytecodes.

By declaring l in the body we can remove it from the function argument’s list. We did this as a trick to avoid the need to declare it with let or const, saving some bytes and the need for a function body.

The trick works by adding unused arguments at the end of the function argument list and using them as local variables. Our compiler function expects a single argument with the code; l is there for us to use since we don’t expect the caller to provide any value for it.

Here’s the code without this trick:

let c3 = (code) => {

const instrs = code.split` `.flatMap(

(t) => (t > -1 ? [65, t] : 107 + "-*/".indexOf(t))

);

const len = instrs.length + 4;

return WebAssembly.instantiate(

new Int8Array([

, 97, 115, 109, 1, , , , 1, 5, 1, 96, , 1, 127, 3, 2, 1, , 7, 4, 1, , , ,

10, len, 1, len - 2, , ...instrs, 11

]),

);

};

Add Missing Zeros

If you look at the array in our code, you may notice that there are many commas followed by another comma instead of a value. This syntax defines “sparse arrays”. Here’s an example:

Which is equivalent to:

We use this syntactic trick to save one byte each time we need a 0 to appear in the array. This works because Typed Arrays coerce all array items to numbers, and an “empty item” will be converted to 0:

which produces:

Let’s undo this trick by adding all the zeroes back:

let c4 = (code) => {

const instrs = code.split` `.flatMap(

(t) => (t > -1 ? [65, t] : 107 + "-*/".indexOf(t))

);

const len = instrs.length + 4;

return WebAssembly.instantiate(

new Int8Array([

0, 97, 115, 109, 1, 0, 0, 0, 1, 5, 1, 96, 0, 1, 127, 3, 2, 1, 0, 7, 4, 1, 0, 0, 0,

10, len, 1, len - 2, 0, ...instrs, 11

]),

);

};

Remove Extra 4 bytes on Length Definition

In our code, we have a variable len that contains a number that is close to the number of bytecodes in the compiled expression, but not exactly the same:

In the WebAssembly module we need to use the number of bytes in the function body (the expression to evaluate) in two places:

• To define the code section’s length
• To define the function body’s length

Since there’s only one function in the code section both values are similar:

• The section takes two extra bytes (section identifier and number of code entries)
• The function body takes another two bytes (number of locals and end instruction)

To avoid writing b.length twice we assign to l the value of b.length + 4 in the place where we need the code section byte count and then calculate l - 2 (b.length + 2) where we need the function body byte count.

This is all a trick to avoid having to write b.length twice.

let’s assign the length to len and calculate the right value in each place:

let c5 = (code) => {

const instrs = code.split` `.flatMap(

(t) => (t > -1 ? [65, t] : 107 + "-*/".indexOf(t))

);

const len = instrs.length;

return WebAssembly.instantiate(

new Int8Array([

0, 97, 115, 109, 1, 0, 0, 0, 1, 5, 1, 96, 0, 1, 127, 3, 2, 1, 0, 7, 4, 1, 0, 0, 0,

10, 4 + len, 1, 2 + len, 0, ...instrs, 11

]),

);

};

Remove String Template Literal Instead of Function Call

The next trick to undo is code.split` `. In this case, we use the Tagged Template feature of String Template Literals.

Let’s see how it works by creating a simple tagged template that turns the string to uppercase:

And use it:

As you can see, the first argument to the tagged template function is an array. Luckily for us, the first argument of String.prototype.split is handled in the following way:

All values that are not undefined or objects with a [Symbol.split]() method are coerced to strings.

And coercing an array with one string in it is the same as the string itself:

Since the function we want to call takes a single string argument, we can use it as a tagged template and save the parentheses in the function call.

Let’s write it as a function call instead:

let c6 = (code) => {

const instrs = code.split(' ').flatMap(

(t) => (t > -1 ? [65, t] : 107 + "-*/".indexOf(t))

);

const len = instrs.length;

return WebAssembly.instantiate(

new Int8Array([

0, 97, 115, 109, 1, 0, 0, 0, 1, 5, 1, 96, 0, 1, 127, 3, 2, 1, 0, 7, 4, 1, 0, 0, 0,

10, 4 + len, 1, 2 + len, 0, ...instrs, 11

]),

);

};

Remove the Ternary Operator

Next, let’s undo the Ternary Operator and turn it into an if statement.

The ternary operator has expressions on each branch saving us the return statements. Here’s what the code looks like when we use an if statement instead:

let c7 = (code) => {

const instrs = code.split(" ").flatMap((t) => {

if (t > -1) {

return [65, t];

} else {

return 107 + "-*/".indexOf(t);

}

});

const len = instrs.length;

return WebAssembly.instantiate(

new Int8Array([

0, 97, 115, 109, 1, 0, 0, 0, 1, 5, 1, 96, 0, 1, 127, 3, 2, 1, 0, 7, 4, 1, 0, 0, 0,

10, 4 + len, 1, 2 + len, 0, ...instrs, 11

]),

);

};

Remove Number Check With Coercion

The next trick to undo is the one present twice in the following code:

First we use coercion in t > -1 to check if the token t is a string representing a positive number. Then we use coercion again in [65, t] to let JavaScript turn t into a Number in the Int8Array:

The code above evaluates to:

Let’s write the parsing and checking explicitly:

let c8 = (code) => {

const instrs = code.split(" ").flatMap((t) => {

const num = parseInt(t, 10);

if (Number.isFinite(num)) {

return [65, num];

} else {

return 107 + "-*/".indexOf(t);

}

});

const len = instrs.length;

return WebAssembly.instantiate(

new Int8Array([

0, 97, 115, 109, 1, 0, 0, 0, 1, 5, 1, 96, 0, 1, 127, 3, 2, 1, 0, 7, 4, 1, 0, 0, 0,

10, 4 + len, 1, 2 + len, 0, ...instrs, 11

]),

);

};

The semantics of our compiler change a little bit here. The original version will only accept positive integers as input; if you want a negative number you have to subtract from zero: 0 - 1 to get -1. The new version allows negative numbers since it checks with Number.isFinite(num) instead of t > -1.

Remove indexOf -1 Trick

The next trick is in the else branch:

Our calculator compiler only accepts four arithmetic operations: +, -, *, and /. But in the code above you can only see three: -*/ and a magical number: 107. Here’s how it works — these are the bytecode numbers for arithmetic operations in WebAssembly:

• +: 106
• -: 107
• *: 108
• /: 109

We only enter this branch if the token t is not a number, which means it can only be one of the arithmetic operators above. So, given a single character which is one of those four operators, we want to produce the appropriate opcode.

We could have written 106 + "+-*/".indexOf(t). That is, we find the symbol’s index in the string:

• +: 0
• -: 1
• *: 2
• /: 3

…and add 106 to it to get the bytecode number. But when t is not in the string, "+-*/" indexOf returns -1. We can use that to our advantage, and treat -1 to mean “plus or any other token”:

• +: -1 (any other token will be -1 too)
• -: 0
• *: 1
• /: 2

And that’s why we add 107 instead of 106. Let’s undo the -1 trick:

let c9 = (code) => {

const instrs = code.split(" ").flatMap((t) => {

const num = parseInt(t, 10);

if (Number.isFinite(num)) {

return [65, num];

} else {

return 106 + "+-*/".indexOf(t);

}

});

const len = instrs.length;

return WebAssembly.instantiate(

new Int8Array([

0, 97, 115, 109, 1, 0, 0, 0, 1, 5, 1, 96, 0, 1, 127, 3, 2, 1, 0, 7, 4, 1, 0, 0, 0,

10, 4 + len, 1, 2 + len, 0, ...instrs, 11

]),

);

};

Here again the semantics change a little bit. Before, if the token t wasn’t found, the expression would evaluate to 107 + -1 which would map to an addition. Now it will evaluate to 106 + -1 which will map to bytecode 105 which is the popcnt instruction.

But don’t worry, we’ll fix it in the next step.

Remove indexOf Trick

After explaining how the indexOf trick works and removing the -1 part, let’s go ahead and remove the trick completely. To do it we are going to create an object that maps from an arithmetic operation token to its bytecode:

const OP_TO_BYTECODE = {

"+": 106,

"-": 107,

"*": 108,

"/": 109,

};

let c10 = (code) => {

const instrs = code.split(" ").flatMap((t) => {

const num = parseInt(t, 10);

if (Number.isFinite(num)) {

return [65, num];

} else {

return OP_TO_BYTECODE[t] ?? 106;

}

});

const len = instrs.length;

return WebAssembly.instantiate(

new Int8Array([

0, 97, 115, 109, 1, 0, 0, 0, 1, 5, 1, 96, 0, 1, 127, 3, 2, 1, 0, 7, 4, 1, 0, 0, 0,

10, 4 + len, 1, 2 + len, 0, ...instrs, 11

]),

);

};

To keep the initial semantics, if the token is not a valid operation we return the bytecode for +: in OP_TO_BYTECODE[t] ?? 106.

Remove the Empty Export Name

From the usage example at the beginning of the post, you may have noticed that the exported function’s name is the empty string:

We did this to save us the bytes needed to specify the export name, but also to save an extra byte/character in the code because with the length of the export name being 0 we can use the sparse array syntax to leave an empty spot in the WebAssembly module array.

To revert this trick we are going to name the exported function as a, which in UTF-8 is the byte 97:

const OP_TO_BYTECODE = {

"+": 106,

"-": 107,

"*": 108,

"/": 109,

};

let c11 = (code) => {

const instrs = code.split(" ").flatMap((t) => {

const num = parseInt(t, 10);

if (Number.isFinite(num)) {

return [65, num];

} else {

return OP_TO_BYTECODE[t] ?? 106;

}

});

const len = instrs.length;

return WebAssembly.instantiate(

new Int8Array([

0, 97, 115, 109, 1, 0, 0, 0, 1, 5, 1, 96, 0, 1, 127, 3, 2, 1, 0, 7, 5, 1, 1, 97, 0, 0,

10, 4 + len, 1, 2 + len, 0, ...instrs, 11

]),

);

};

We can now call it with a nicer name:

Implicit Design Decisions

Our initial implementation only supported positive numbers, but that’s not the only number restriction in our compiler.

To keep WebAssembly modules as small as possible, numbers are encoded using a variable-length encoding algorithm called LEB128. You can tell we are not implementing the whole algorithm by looking at the part of the code that encodes numbers: [65,t]. We’re assuming the number being encoded fits in 7 bits, the shortest possible LEB128 representation.

Let’s try the limits of our implementation:

This means the only numbers that will be parsed correctly are from 0 to 63.

Fails with:

Uncaught CompileError: WebAssembly.instantiate(): Compiling function #0 failed: function body must end with “end” opcode @+33

In the last one we went over the 7 bits and the module was rejected during validation.

Explaining and implementing LEB128 takes a lot of text and code. If you want to read more about it we have a whole deep dive on LEB128 in our book.

A Trick that Almost Worked

During the code golfing phase I had a literal shower thought but sadly it didn’t work.

The idea was to simplify 106 + "+-*/".indexOf(t) by using the UTF-8 character code plus an offset like this: 63 + t.charCodeAt() and saving 3 bytes in the process. The reason it didn’t work is that the characters +-*/ don’t appear in the same order in UTF-8 and WebAssembly bytecode.

Explaining the Numbers in the Array

The last part to expand/explain is the array of numbers used to build the WebAssembly module.

It takes a big part of a specification to explain every byte in the array, but here’s a commented version that should give you a high level idea of what each part does:

Conclusion

There you go! We’ve turned a rather opaque 192-byte snippet into something that’s almost readable. And in the process, you hopefully learned a little bit about WebAssembly.

If we dropped the size restrictions, there are lots of things we might want to improve in this compiler: handle numbers greater than 127, add nicer syntax, add support for conditionals, loops, etc. If you’re interested in what that might look like, I encourage you to check out our book WebAssembly from the Ground Up. You’ll learn the ins and outs of WebAssembly by writing a real compiler for a simple programming language. It’s a lot of fun!

Special thanks to lexi for contributing some of the tricks used above.