Advent of Code '21 in hand written WebAssembly

Hi wasm builders! 👋

Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

I decided this year to test my knowledge of WebAssembly by solving the puzzles in WAT. WAT is a textual representation of the WebAssembly binary format. It's designed to be read and edited by humans.

I like to think that I have a fairly good mental model of the WebAssembly virtual machine, mostly because I work on one. However, I still think the challenge will be quite hard. WAT is a language really close to the binary format and doesn't offer any of the higher level constructs like data structures (lists, vectors, maps, etc.), memory allocators or simple helper functions like string splitting. It's going to be on us to recreate the whole universe by hand. Let's see how far into the calendar we can get before giving up 😊.

If you would like just to check out the final solutions, you can find them on GitHub.

The setup

To make it somewhat easier, I intend to "cheat" a bit. Instead of writing a whole application that reads an input file, parses integers and outputs the result to command line; I will attempt to embed the input values directly into the WebAssembly module. This will require a few transformations on the input and converting the input to hexadecimal values with an online tool.

I still intend to write the whole module by hand and convert it to a binary .wasm files using the wat2wasm command line application.

To execute the file I will use the wasmtime cli.

Wasmtime has an experimental feature that allows you to print out the return value of a function. This will save us to deal with i/o.

The WebAssembly execution model

If we have a bit of a simplistic look at a WebAssembly runtime, it's basically a stack machine. This means we push operands onto the stack and execute instructions that take operands from the top, do calculations and push the result back onto the stack.

Let's look at the following program flow in an imaginary language:

push 40, push 1, push 1, add, add

After executing the first 3 instructions, our stack is going to look like this:

1   ^
1   | The stack grows upwards
40  |

Now if we execute the first add instruction it will take the top two values, add them together and push the result back onto the stack:

2
40

After the second add is executed our final stack looks like this:

42

Fairly straight forward! WebAssembly has a big set of instructions that are grouped into functions and other concepts (memory, tables, ...), but this is almost everything you need to know for now. I will explain individual concepts once we run into them.

WebAssembly Text Format (WAT)

The WebAssembly Text format is a mixture of Lisp (s-expressions) and Forth. There are usually multiple ways of expressing the same intention and it can be confusing if you come across examples on the internet and you are not used to the specific style of the author.

Let's jump into it right away and look at a WebAssembly module that only contains a function that adds two numbers:

(module
  (func $add (param $a i32) (param $b i32) (result i32)
    local.get $a
    local.get $b
    i32.add)
  (export "add" (func $add)))

Now we can translate this file to the binary format:

> wat2wasm add.wat

And invoke the exported add function with wasmtime:

> wasmtime add.wasm --invoke add 40 2
# 42

We need to explicitly state in the module which functions should be exported and available for invocation. We can define the export name directly in the function definition:

(module
  (func (export "add") (param $a i32) (param $b i32)
    (result i32)

    local.get $a
    local.get $b
    i32.add))

This way of writing instruction may remind you of our previous example (push 40, push 1, push 1, add, add). We first push the first argument $a onto the stack with local.get $a, then $b (local.get $b) and then add them (i32.add). The return value is going to be whatever is left on the stack.

The WAT language lets us write this in a more lispy way too:

(module
  (func (export "add") (param $a i32) (param $b i32)
        (result i32)
    (i32.add (local.get $a) (local.get $b))))

Now we specify the arguments to the i32.add operation like we would do a function invocations in other languages.

The $a and $b names are just helpers here. We can refer to function arguments by index:

(module
  (func (export "add") (param i32) (param i32)
        (result i32)
    (i32.add (local.get 0) (local.get 1))))

You can even mix the lispy and forth syntaxes into something like this:

(module
  (func (export "add") (param i32) (param i32)
        (result i32)
      local.get 0
    (i32.add (local.get 1))))

You can also write the local.get instruction as get_local:

(module
  (func (export "add") (param i32) (param i32)
        (result i32)
      get_local 0
    (i32.add (get_local 1))))

However, you can't do the same with i32.add 🤔.

As you probably noticed by now, the whole WAT is a bit of an inconsistent mess and truly WAT.

It's also important to point out that this is just a quirk of the WAT language and once you translate them to WebAssembly binary code, all examples generate identical files.

I will try to be consistent with my writing style in the rest of the series and stick to:

• The forth notation of instructions, to be close to the actual WebAssembly execution model.
• Name variable by prefixing the names with $.
• Use the . notation for instructions when available (e.g. local.get instead of get_local).
• Close parentheses together on one line to minimise vertical scrolling.

If you would like to learn a bit more about WAT before diving deeper into the puzzles I can recommend the Raw WebAssembly article by Surma, Writing WebAssembly By Hand by Colin or the Stack machines and assembly Stanford course.

I think we are ready to jump into solving the Day 1 puzzle.