Build a WebAssembly Language for Fun and Profit: Lexing

WebAssembly (wasm) is a high performance assembly-like format optimized for the web. Code targeting WebAssembly can run at near-native speeds while still benefiting from the safe environment of a browser VM. Wasm has opened up a whole new world of demanding desktop-class apps that can comfortably run in the browser. For example, AutoCAD was able to port decades of code to the web using wasm. Cases like AutoCAD’s have made it clear that wasm will be a major disruptive force in how web apps are developed.

To facilitate the adoption of wasm, WebAssembly team developed a powerful compiler toolchain library called binaryen. Binaryen does a huge amount of heavy lifting for compiler authors. It offers dead code removal, code size reduction, and various performance optimizations out of the box.

As someone who has long been interested in programming languages, this piqued my interest. Writing compiled languages has always been a daunting task. What I found is binaryen made it incredibly fun and easy to build new languages that are shockingly speedy.

That's why I decided to create this guide and provide a simple overview designed to help get your feet wet in building languages and exploring the inner workings of wasm.

Here's a quick taste of the lisp inspired language we'll build, wispy:

(fn fib:i32 [val:i32]
  (if (lt_i32 val 2)
    val
    (add_i32 (fib (sub_i32 val 1)) (fib (sub_i32 val 2)))))

(fn main:i32 [] (fib 15))

This simple function calculates values of the fibonacci sequence, a sequence of numbers that appears in surprising places through mathematics and nature. It's one of my favorite illustrations of how elegantly patterns of the universe can be described in code.

This guide is designed for intermediate to advanced software developers looking for a fun side
project to challenge themselves with. By the end, we’ll have built a working compiler and runtime for wispy.

The guide will be broken down into three articles:

• Setup and Lexing (this article): the process of converting the characters of code into meaningful units called tokens
• Parsing: the process of converting the tokens into a logical tree known as an AST.
• Compiling (or code generation): the process of converting the AST into the binary instructions run by our computer

Setup

In this guide, we will be using TypeScript and NodeJS. The concepts are highly portable, so
feel free to use the environment you're most comfortable with. Our only major dependency, binaryen, has a simple C API. You are welcome to skip ahead to the next section if you're using a different language.

Requirements:

• NodeJS v16+
• Git

Quick Start

git clone git@github.com:drew-y/wispy.git
cd wispy
git checkout quickstart
npm i

Manual Setup

I've included manual setup instructions as an alternative to the quick start, in case you want to know exactly how the project was set up or just like doing things from scratch. If you've already done the quick start, skip to the next section.

1. Open a terminal window and make a new directory:

mkdir wispy
cd wispy

1. Initialize package.json:

npm init -y # Be sure to have NodeJS 16+ installed

1. Install the project dependencies:

npm i @types/node binaryen typescript

1. Add these two fields to the package.json

"type": "module", // Binaryen uses the new module format so we must follow suit
"bin": {
  "wispy": "dist/index.mjs" // This will allow us to easily run the compiler from our terminal
},

1. Create a tsconfig file:

npx tsc init .

1. Set the following fields in tsconfig.json:

"module": "ES2022",
"rootDir": "./src",
"moduleResolution": "node",
"outDir": "./dist"

Lexing

Lexing is the process of digesting each individual character of our program into a set of tokens. A token is a group of characters that take on a special meaning when put together. Take the following snippet of wispy:

(add 1 2)

There are five unique tokens in that snippet (, add, 1, 2 and ). The lexer's job is simply
to identify and list those tokens in order.Lexing is typically the first step in turning human
readable code into something closer to what a computer can understand.

Defining Our Tokens

We'll start by defining our tokens in a new file:

# mts extension is important, it tells typescript to create a corresponding mjs file, so Node knows to use modules 

mkdirp -p src/types/token.mts

First up is the IntToken. This token represents whole numbers like 1045:

// src/types/token.mts
export type IntToken = { type: "int"; value: number };

Next up is the FloatToken. This token represents numbers that may have a decimal, like 1.8:

// src/types/token.mts
export type FloatToken = { type: "float"; value: number };

/** Previously defined tokens omitted for brevity */

Now, let's define some identifier tokens. In wispy, an identifier can represent either the name
of a function, or the name of a function parameter. We have two types of identifier tokens,
a standard IdentifierToken and a TypedIdentifierToken.

An IdentifierToken is used in the body of a function to refer to the function's parameters or
to call another function.

A TypedIdentifierToken is used when defining a function or a parameter. Typed identifiers
take the form identifier:type. For example, val:i32 defines a parameter that is a 32-bit integer.
When defining a function, the type represents the function's return type. For example, fib:i32 is
a function that returns a 32-bit integer.

Here are the definitions:

// src/types/token.mts
export type IdentifierToken = { type: "identifier"; value: string };
export type TypedIdentifierToken = { type: "typed-identifier"; value: string };

/** Previously defined tokens omitted for brevity */

Up next is BracketToken. Wispy uses S-expression
syntax, like lisp. So brackets are very important. To keep things simple we allow two kinds of
brackets () and []. To keep things even more simple the compiler will treat () and
[] as interchangeable. In actual use we will only use [] to define parameters.

// src/types/token.mts
export type BracketToken = { type: "bracket"; value: Bracket };
export type Bracket = "(" | ")" | "[" | "]";

/** Previously defined tokens omitted for brevity */

Finally we define the top level Token type:

// src/types/token.mts
export type Token = BracketToken | IntToken | FloatToken | IdentifierToken | TypedIdentifierToken;
/** Previously defined tokens omitted for brevity */

Token is a discriminated union. Discriminated Unions are an incredibly powerful programming language construct. They represent a value that can be one of many types. In our case, a Token can be any one of the more specific token types we defined earlier, such as IntToken or FloatToken. You'll notice that each of these tokens have a unique type field, such as type: "int" in the case of IntToken. This is the discriminator. Down the line you can pass a Token to a function and that function can use the type field to figure out which specific token it's working
with.

At this point src/types/token.mts is finished and should look like a file.

To make our new types easily accessible, export them from a new index.mts file:

// src/types/index.mts
export * from "./token.mjs";

The Lex Function

Now that we have our tokens defined we can write the actual lex function. The lex function
will take a string (i.e. a .wispy file) and output an array of tokens (Token[]):

Make a new lex file:

mkdirp -p src/lexer.mts

Define the lex function:

// src/lexer.mts
import { Bracket, Token } from "./types/index.mjs";

export const lex = (input: string): Token[] => {
  const chars = input
    // Remove any leading or trailing whitespace for simplicity
    .trim()
    // Break up the file into single characters
    .split("");

  // This array stores our tokens
  const tokens: Token[] = [];

  // The loop continues as long as we have characters to consume
  while (chars.length) {
    // Here, a word is an unidentified token. It is usually any single group of non-whitespace
    // characters such as 123 or 123.4 or im_a_function
    const word = consumeNextWord(chars); // We'll define this function later

    // We ran out of tokens. Break out of the loop.
    if (word === undefined) break;

    const token = identifyToken(word); // We'll define this function later

    // Add the token to our store
    tokens.push(token);
  }

  // Return the tokens
  return tokens;
};

Next we define the consumeNextWord function:

// src/lexer.mts

/** previous function(s) omitted for brevity */

const consumeNextWord = (chars: string[]): string | undefined => {
  const token: string[] = [];

  while (chars.length) {
    // Save a preview of the current character without modifying the array
    const char = chars[0];

    // No more characters to read
    if (char === undefined) break;

    // Whitespace characters terminate the token (we'll define the isWhitespace function later)
    if (isWhitespace(char) && token.length) {
      chars.shift(); // Remove the whitespace so it doesn't get included in the next token
      break;
    }

    // Discard leading whitespace characters
    if (isWhitespace(char)) {
      chars.shift();
      continue;
    }

    // Terminator tokens signify the end of the current token (if any). (we'll define the isTerminatorToken function later)
    if (isTerminatorToken(char) && token.length) break;

    // Add the character to the token and discard it from the input
    token.push(char);
    chars.shift();

    // If the only token we've received so far is a single character token, that's our whole token.
    if (isTerminatorToken(char)) break;
  }

  // If we have characters for our token, join them into a single word. Otherwise, return undefined to signal to the lexer
  // that we are finished processing tokens.
  return token.length ? token.join("") : undefined;
};

Now we'll define our identifyToken function. As the name suggests, this function takes
a word and figures out what token that word represents.

// src/lexer.mts

/** previous function(s) omitted for brevity */

const identifyToken = (word: string): Token => {
  // Don't worry we'll get to all the `is` helper functions in a bit
  if (isInt(word)) return { type: "int", value: parseInt(word) };
  if (isFloat(word)) return { type: "float", value: parseFloat(word) };
  if (isIdentifier(word)) return { type: "identifier", value: word };
  if (isBracket(word)) return { type: "bracket", value: word };
  if (isTypedIdentifier(word)) return { type: "typed-identifier", value: word };

  throw new Error(`Unknown token: ${word}`);
};

Finally, we define our helper functions. These functions all take a string and return
true if the string passes their test, false otherwise. Most are written using regex. If
you're unfamiliar with regex, I highly recommend regexone as a resource to learn more. In a nutshell, regex is an expression syntax that's used to extract meaningful information from text. In our case, we'll use it to match words against tokens.

const isInt = (word: string) => /^[0-9]+$/.test(word);

const isFloat = (word: string) => /^[0-9]+\.[0-9]+$/.test(word);

const isIdentifier = (word: string) => /^[a-zA-Z_][a-zA-Z0-9_\-]*$/.test(word);

const isTypedIdentifier = (word: string) =>
  /^[a-zA-Z_][a-zA-Z0-9_\-]*:[a-zA-Z_][a-zA-Z0-9_\-]*$/.test(word);

const isBracket = (word: string): word is Bracket => /[\(\)\[\]]/.test(word);

/** Brackets are the only terminator tokens for now */
const isTerminatorToken = (word: string): word is Bracket => isBracket(word);

// Not sure why I didn't use regex here ¯\_(ツ)_/¯
const isWhitespace = (char: string) => char === " " || char === "\n" || char === "\t";

At this point, src/lexer.mts is finished and should look something like this file.

Running the Lexer

It's time to actually run the lexer. Start by making a new file src/index.mts:

#!/usr/bin/env node

// src/index.mts

import { readFileSync } from "fs";
const file = process.argv[2];
const input = readFileSync(file, "utf8");
const tokens = lex(input);
console.log(JSON.stringify(tokens, undefined, 2));

Next, create an example.wispy file in the project root to compile.

(fn fib:i32 [val:i32]
  (if (lt_i32 val 2)
    val
    (add_i32 (fib (sub_i32 val 1)) (fib (sub_i32 val 2)))))

(fn main:i32 [] (fib 15))

Now build the lexer:

npx tsc
npm link # This will make wispy available to run as its own command

Finally, run the lexer:

wispy example.wispy

# Note, if npm link failed you can call our compiler directly with this as an alternative:
node dist/index.mjs example.wispy

If everything goes well, wispy should output something like this:

[
  {
    "type": "bracket",
    "value": "("
  },
  {
    "type": "identifier",
    "value": "fn"
  },
  {
    "type": "typed-identifier",
    "value": "fib:i32"
  },
  {
    "type": "bracket",
    "value": "["
  },
  {
    "type": "typed-identifier",
    "value": "val:i32"
  },
  // Omitting the rest for brevity
]

With that we have a working lexer. We can break our code down into tokens. This is a good place to break for now. In the next article, we’ll move onto parsing these tokens into a logical tree that will ultimately be converted to wasm.