Forem: Thomas Albertini

Let's build a WebAssembly compiler and runtime - Tokenizer

Thomas Albertini — Thu, 22 Dec 2022 12:44:04 +0000

Holy smokes.
A whole month has passed since my last article. I apologize, but I've been quite busy with work.

But I'm back to continue the series of articles in which I explain how I built Luna.

In the last article we started building Luna, a toy WebAssembly compiler, and we explored WAT (the WebAssembly text format).

Now that Christmas holidays are coming, it won't pass another month for the next article.

Today I want to talk about Luna's tokenizer.

First thing first
Luna is basically composed of three parts:

Tokenizer
Parser
Compiler

The flow is simple:

the input is divided into tokens
these tokens are passed onto the parser which further analyzes them and builds an AST (Abstract Syntax Tree)
the AST is passed to the compiler and transformed into a WebAssembly module.

So what is a Tokenizer?

The tokenizer, sometimes called Lexer is responsible for dividing the input stream into individual tokens, identifying the token type, and passing tokens one at a time to the Parser.

Token
It is basically a sequence of characters that are treated as a unit as it cannot be further broken down. - geeksforgeeks

So, the first step is to define tokens.
Let's say we have this input:

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

This example exports a function called "example" that takes two arguments and adds them.

Let's define the tokens:

var tokens = []string{
    "func",
    "module",
    "export",
    "result",
    "param",
}

While developing your own compiler the choice of what's going to be a token and what not is yours.
Since Luna is compiling a WAT-like language there are also "special tokens" called instructions (e.g. local.get, i32.add etc..)

For simplicity in Luna's code I've regrouped the tokens by type (because of the different manipulations the parser will later do on them)

So for instance we have

var instructions = []string{
    "local\\.get",
    "i32\\.(add|sub|mul|div|const)",
}

Wait a moment!!!
We were talking about tokens what are these instructions?
Citing WASM specification:

WebAssembly code consists of sequences of instructions. Its computational model is based on a stack machine in that instructions manipulate values on an implicit operand stack, consuming (popping) argument values and producing or returning (pushing) result values.

TLDR instructions are the mean to manipulate values.
All instructions are immediately followed by arguments (such in our example above) except control instructions

Instructions are encoded by opcodes. Each opcode is represented by a single byte.

We will look into Opcodes when we'll start talking about the parser.

Back to the Tokenizer
Okay, we have our tokens and instructions. As you might've already guessed. I decided to implement the tokenizer with Regex.

Since I'm trying to keep Luna as simple as possible and I do not care much about performances.
I'm considering switching to some FSM algorithm or doing some refactor soon but the idea behind the tokenizer will still be as follows:

Step zero

Here's the complete list of my tokens

var tokens = []string{
    "func",
    "module",
    "export",
    "result",
    "param",
}


var instructions = []string{
    "local\\.get",
    "i32\\.(add|sub|mul|div|const)",
}

var numTypes = []string{
    "i32",
    "i64",
    "f32",
    "f64",
}

// We can hard hardcode a bunch of names for function export
// so we do not need to change this everytime
// or implement a simple regex to catch anything between quotes
var literals = "\"([^\"]+)\""

First step - Preparation

Since we are using regex we compile them.

var tokensRegex = regexp.MustCompile("^(" + strings.Join(tokens, "|") + ")")
var instructionRegex = regexp.MustCompile("^(" + strings.Join(instructions, "|") + ")")
var typeNumRegex = regexp.MustCompile("^(" + strings.Join(numTypes, "|") + ")")
var literalsRegex = regexp.MustCompile("^(" + literals + ")")
var numberRegex = regexp.MustCompile("^[0-9]+")
var whitespaceRegex = regexp.MustCompile(`^\s+`)

A Luna's token has a

Type: number, literal, token, instruction etc...
Value: the token's value
Index: where's the token is positioned

Easily implemented with a Token struct

type Token struct {
    Type  string
    Value string
    Index int
}

Optionally an helper Matcher struct to help handling the regex matches.

type Matcher struct {
    Type  string
    Value string
}

Second step

The tokenize function

func Tokenize(input string) []Token {
    tokens := []Token{}
    matches := []Matcher{}
    index := 0

    matchers := []func(string, int) (Matcher, error){
        matchChecker(tokensRegex, texts.TypeToken),
        matchChecker(instructionRegex, texts.TypeInstruction),
        matchChecker(typeNumRegex, texts.TypeNum),
        matchChecker(literalsRegex, texts.TypeLiteral),
        matchChecker(numberRegex, texts.Number),
        matchChecker(whitespaceRegex, texts.Whitespace),
    }

    for index < len(input) {
        for _, m := range matchers {
            matchFound, notFound := m(input, index)

            // Prevent panic if no match is found
            if notFound != nil {
                continue
            }

            matches = append(matches, matchFound)
        }
        if len(matches) == 0 {
            index++
            continue
        }
        match := &Token{
            Type:  matches[0].Type,
            Value: matches[0].Value,
            Index: index,
        }

        if match.Type != "whitespace" {
            tokens = append(tokens, *match)
        }

        index += len(matches[0].Value)
        matches = []Matcher{}
    }
    return tokens
}

This is quite intuitive.
The tokenize function loops through the input and runs all the regex we have compiled earlier.

This is not the best solution if you want to make it fast. Please refer to other algorithms if that's your purpose.

Third step

Does the token exist?

func matchChecker(rxp *regexp.Regexp, whichType string) func(string, int) (Matcher, error) {

    return func(input string, index int) (Matcher, error) {

        substr := input[index:]
        match := rxp.FindString(substr)

        if len(match) > 0 {
            return Matcher{Type: whichType, Value: match}, nil
        }

        return Matcher{}, errors.New("no match found")
    }
}

Now try pass the input above to your Tokenize function and if you see this:

func main() {
       input := `(module
                (func (export "example") (param i32 i32) (result i32)
                    local.get 0
                    local.get 1
                    i32.add)
                )
            `
       tokens := Tokenize(input)
       fmt.Println("Tokens:", tokens)
}

Tokens: [{token module 1} {token func 13} {token export 19} {literal "example" 26} {token param 38} {typeNum i32 44} {typeNum i32 48} {token result 54} {typeNum i32 61} {instruction local.get 71} {number 0 81} {instruction local.get 88} {number 1 98} {instruction i32.add 105}]

Congratulation!
You have a tokenizer.

If my explanation was not clear enough or you have any code improvements, you can check and contribute to the source code directly, here.
And of course I apologize for that.

Try Luna: https://luna-demo.vercel.app

Resources:
WebAssembly Specs

Next we'll tackle the parser!

Stay safe and Merry Christmas 🫱🏻‍🫲🏽✨

Let's build a WebAssembly compiler and runtime - WebAssembly Text Format

Thomas Albertini — Tue, 15 Nov 2022 20:24:49 +0000

Today I want to start a series of articles on how I've managed to build a WebAssembly compiler.

Luna is a really tiny compiler written mainly as a quest to conquer the WebAssembly dungeon.

If you do not know what I'm talking about I suggest to read the introductory article.

Long story short, some weeks ago I've decided to build my own Web Assembly compiler.
This was quite the challenge.

First of all what the heck is WAT??
Second problem: I didn't know how to write a compiler.

So here I am trying to dissect my journey and the informations I've acquired while writing Luna.

Today I'll give you an overview of the WebAssembly Text Format (the thing we are going to compile).

WAT (WebAssembly Text Format)

The WebAssembly text format is a textual representation of the WASM binary format.

Let's say we have the following .wat file:

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

What the code above does is simple (and quite intuitive): it exports a function aliased as "add" that takes two arguments and returns the sum of them.

Easy.

So let's analyze each word.

Module

A module is the fundamental unit of code in WebAssembly and it is loaded by a WASM runtime. In textual format a module is represented as a big S-Expression which Wikipedia defines as:

an expression in a like-named notation for nested list (tree-structured) data.

NOTE: the shortest WASM program you can write is (module) which does absolutely nothing lol, but it is still a valid WASM program.

Inside our module above there are two structures:

Func: the first structure is a function declared by the func keyword.
Export: the second structure is an export declared by the export keyword

The function has:

An identifier $add that is the name of the function
Two parameters $num1 e $num2 of type i32 (WebAssembly provides only four basic number types i32, i64, f32, f64)
A result of type i32.
Three instructions local.get 0, local.get 1, i32.add (to understand them we need to first learn about Stack Machines)

Stack Machines

WASM execution is defined in terms of stack machines. The idea behind of a stack machine is that every instruction is executed in order and either pushes or pops a number (i32/i64/f32/f64) from a stack.
There are basically two types of instructions:

Simple instructions (e.g. i32.add, f32.sub etc...): generally pop arguments from the stack and push the result back on it.
- Control instructions: alter the control flow (we won't be seeing them in this series).

(func (param $n i32) (result i32)
  local.get $n
  local.get $n
  i32.add)

For example local.get takes the param $n and pushes it onto the stack, i32.add instruction adds them (or better, adds all the elements present in the stack) and pushes the result onto the stack.

So, I hope I've give you an idea of how to start writing your own WAT modules. They ain't that scary, are they?

But there's one last thing I want to show before we get to the code.

At the beginning of the article I've said that WebAssembly Text Format is a textual representation of the WASM binary format, but how does a WASM binary format look like?

WASM Binary Format

Our .wat example

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

would look like this (compiled with wat2wasm)

0000000: 0061 736d                                 ; WASM_BINARY_MAGIC
0000004: 0100 0000                                 ; WASM_BINARY_VERSION
; section "Type" (1)
0000008: 01                                        ; section code
0000009: 00                                        ; section size (guess)
000000a: 01                                        ; num types
; func type 0
000000b: 60                                        ; func
000000c: 02                                        ; num params
000000d: 7f                                        ; i32
000000e: 7f                                        ; i32
000000f: 01                                        ; num results
0000010: 7f                                        ; i32
0000009: 07                                        ; FIXUP section size
; section "Function" (3)
0000011: 03                                        ; section code
0000012: 00                                        ; section size (guess)
0000013: 01                                        ; num functions
0000014: 00                                        ; function 0 signature index
0000012: 02                                        ; FIXUP section size
; section "Export" (7)
0000015: 07                                        ; section code
0000016: 00                                        ; section size (guess)
0000017: 01                                        ; num exports
0000018: 03                                        ; string length
0000019: 6164 64                                  add  ; export name
000001c: 00                                        ; export kind
000001d: 00                                        ; export func index
0000016: 07                                        ; FIXUP section size
; section "Code" (10)
000001e: 0a                                        ; section code
000001f: 00                                        ; section size (guess)
0000020: 01                                        ; num functions
; function body 0
0000021: 00                                        ; func body size (guess)
0000022: 00                                        ; local decl count
0000023: 20                                        ; local.get
0000024: 00                                        ; local index
0000025: 20                                        ; local.get
0000026: 01                                        ; local index
0000027: 6a                                        ; i32.add
0000028: 0b                                        ; end
0000021: 07                                        ; FIXUP func body size
000001f: 09                                        ; FIXUP section size

or like this (compiled with Luna

As you can see, each module is divided in sections and each section has its own rules, there's the MAGIC WORD, a section for the function body, a section for the code, a section for the function type and whatnot...

Do not worry,
we will be tackling them all and we will conquer this WebAssembly dungeon.

Conclusion

Thank you for the reading, I hope you've enjoyed this and if you want to go deeper in the explanation I will leave some useful resources below. See ya in the next article!!

WebAssembly Spec
Understanding WebAssembly Text Format

Luna's Repo
Luna's Demo

Luna 🌙 - Wrote a tiny WebAssembly compiler, that also runs in browser, built for demonstrative and educational purposes.

Thomas Albertini — Tue, 01 Nov 2022 21:27:07 +0000

I've been wanting to learn how to make my own programming language for a really long time, but I could not find the road in the hard theory behind compilers, parsers, ASTs etc... I found the tutorials hard and my attention was not lasting for more than 5 minutes before completely shut down the project.

Some days ago, though something changed.
I'm currently in love with WebAssembly and had this absurd idea of developing a programming language that compiles to WebAssembly.

I didn't know how WebAssembly internals worked so it was the perfect stage to learn something new and make a cool project.

Sold!

Started doing some researches and I found no tutorials except two amazing articles, one was how to build a compile for a custom programming language that compiles to WebAssembly (exactly what i was looking for), the other was a series of articles on how to build a Web assembly compiler (exactly what i was looking for, again!)

But here come the problems: the first was written in Typescript and the second in Rust.

I wanted to practice Go and I don't know anything about Rust.

So long story short I studied the theory behind those two amazing articles, WebAssembly specification etc... and I started writing a compiler in Go (i love Go).

I've really found no articles about writing WebAssembly compilers with Go, so I decided to document the building of Luna so future Gophers that will have my same idea won't have to struggle as much as I did to find resources.

Luna mainly compiles WebAssembly Text Format to Wasm, but with small modifications in the tokenizer and parser, it could also serve as a blueprint for developing custom programming languages in the browser that compile to WebAssembly.

So this is Luna and in this series of articles I will explain EXACTLY how I built it.

Meanwhile you can have a look at:

Source code: https://github.com/thomscoder/luna
Demo: https://luna-demo.vercel.app

Luna is really tiny and it's in early stage, feel free to contribute (update docs, open PR, issues, leaving feedback or suggestions etc...), anything is welcomed!!

Building a Git tool to play with Git entirely in-memory on the browser

Thomas Albertini — Sun, 09 Oct 2022 13:46:53 +0000

Hello everyone,
today I released v0.0.3 of Harmony, a git tool, powered by web assembly, that runs entirely in-memory on the browser.

Harmony was born as a tool to create and/or modify local files, on the fly, in your browser.
Few weeks ago I decided to try to implement a sort of version control system in it.

I think it would be cool one day to either use it for personal use or to teach Git concepts in a sandboxed area. Harmony is powered by web assembly and it runs all the git related stuff in-memory.

In this release I brought an initial support for directories and the possibility to checkout to a particular commit

It is still in very early stages (couple of weeks of development)

Repo: https://github.com/thomscoder/harmony

Website: https://harmonyland.vercel.app

Harmony ✨- Create, upload, edit (multiple) files on the fly, in the browser and track them with Git, via Web Assembly.

Thomas Albertini — Thu, 29 Sep 2022 18:04:23 +0000

I write my first post here to present Harmony. My latest project.

Some months ago, I built Nova a Git playground in Go in which you can clone repositories, create files, branches, commits etc... all in-memory.

What does that have to do with Harmony ? Well, I'm currently experimenting with WebAssembly and the first idea that I had was to port Nova to the Web to give other people a better UX.

So Golang -> WASM -> Javascript -> React BOOM!
I can finally present a stable version of Harmony.

What Harmony does is simple:

Allows the creation, upload and editing of multiple (local) files.
Allows the creation of Git Branches and Commits to save different "workspaces"
Allows to switch between files and between "workspaces" in one click.

It does all that right in your browser. In-memory. Refresh the page to start anew, in another empty repository.

I won't go into how, that's for another post (maybe).

Here's the repository where there's a video.

Here's the demo.