Platform
Docs
Solutions
ContactLog In

Start Routing Notifications Today!

Courier is a notification service that centralizes all of your templates and messaging channels in one place which increases visibility and reduces engineering time.

Sign-up

webassembly-language-lexing-header
ENGINEERING

Build a WebAssembly Language for Fun and Profit: Lexing

Drew Youngwerth

August 18, 2022

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:

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

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:
  1. Initialize package.json:
  1. Install the project dependencies:
  1. Add these two fields to the package.json
  1. Create a tsconfig file:
  1. Set the following fields in tsconfig.json:

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:

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:

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

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

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:

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.

Finally we define the top level Token type:

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:

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:

Define the lex function:

Next we define the consumeNextWord function:

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

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.

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:

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

Now build the lexer:

Finally, run the lexer:

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

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.

Start Routing Notifications Today!

Courier is a notification service that centralizes all of your templates and messaging channels in one place which increases visibility and reduces engineering time.

Sign-up

More from Engineering

courier-ios-thumbnail
PRODUCT NEWSENGINEERING

Simplifying notifications with the Courier iOS SDK

Push notifications are a valuable tool for keeping users informed and increasing their engagement with your app. You can use push notifications to alert users about promotions, new content, or any other important updates. While push notifications are a powerful tool, setting up push notifications in iOS can be a daunting task that requires a significant amount of effort and time. Fortunately, the Courier iOS Mobile Notifications Software Development Kit (SDK) simplifies this process.

Mike Miller

Mike Miller

March 23, 2023

Courier Android SDK thumbnail
PRODUCT NEWSENGINEERING

Building Android push notifications with Firebase and Courier’s SDK

Push notifications have become an essential part of modern mobile apps, allowing you to keep your users engaged and informed. However, implementing push for different platforms can be a complex and time-consuming task, requiring developers to set up and handle token management, testing, and other logistical details.

Mike Miller

Mike Miller

March 21, 2023

Build your first notification in minutes

Send up to 10,000 notifications every month, for free.

Get started for free

Email & push notification

Build your first notification in minutes

Send up to 10,000 notifications every month, for free.

Get started for free

Email & push notification

Platform

Users

Content

Channels

Sending

Workflows

Preferences

Inbox

Workspaces

Observability

API Status

Changelog

© 2024 Courier. All rights reserved.