Introduction

It's some form of Elvish. I can't read it.

This is the second book in the "Rust Projects" series. Just like "Build a Redis Clone", it was born out of my desire to use Rust to solve a practical problem and, in doing so, to learn it "in action".

In this case, the practical problem is the creation of an interpreter from scratch. As with the previous entry in the series, it closely follows a CodeCrafters challenge: "Build your own Interpreter". That, in turn, is based on the fantastic book Crafting Interpreters by Robert Nystrom, which is available under a pay-what-you-want scheme.

That book is an invaluable resource for anyone wanting to step into the rich and complex world of programming languages, compilers, and interpreters. My suggestion is that you treat Crafting Interpreters as an essential companion while reading this book. Ideally, read each chapter of that book thoroughly — before or after following the implementation presented here. The CodeCrafters challenge mirrors the structure of Nystrom’s book quite closely, and so will I, but the language and idioms will be Rust’s rather than Java’s.

Rust, of course, comes with its own concepts: ownership, borrowing, enums, and pattern matching among the most prominent ones. Some of those are shared with Java and others are unique to Rust. All of these shape the way we design and implement an interpreter. This book, however, won't be a line-by-line adaptation of Nystrom’s code. Instead, I’ll use the CodeCrafters challenge as a guide for what needs to be done, and focus more on Nystrom’s design strategies than on the specific implementation.

Writing a programming language, even a simple one, is in my opinion one of the most fulfilling experiences a software developer can have. It’s the closest thing, in our domain, to what Tolkien called sub-creation: the urge of those living in the Primary World to create a world within the world, imitating the Creator. And just as sub-creators cannot but be amazed when they see their creation come to life, I can promise that the first time you see your programming language successfully execute a piece of code, you’ll feel you’ve accomplished something truly exceptional.

Much like my Redis book, this one is meant to be flexible. You can read it from beginning to end and follow along step by step, treating it as a structured guide. You can code on your own and compare approaches. Or you can use it as a base to find alternative solutions to the same problems. However you approach it, I hope you will find it useful.

As the author, this project has been yet another opportunity to deepen my understanding of core concepts, both those specific to Rust and those relating to language design. It's written with the mindset of a learner, not an expert.

There will be mistakes, both technical and grammatical. But I hope, despite those, that you’ll enjoy this new adventure and learn something valuable.

CodeCrafters#

This book originates from one of the most interesting projects I encountered in the past decade, CodeCrafters. This company, founded in 2022 by Sarup Banskota and Paul Kuruvilla, provides a very simple service: a set of well-paced challenges that guide you to implement an important piece of software from scratch.

Are you into databases? Here is the Build your own Redis challenge. Do you want to create your own language? No problem, head to Build your own Interpreter. Want to dig into network protocols? Build your own HTTP server and Build your own DNS server to the rescue. And the nice thing is that you can solve it with your favourite programming language, and see the solutions of other coders.

It's TDD applied to integration tests, where CodeCrafters provides the code that tests features of your software, and you provide the code that implements such features.

You don't need CodeCrafters to enjoy the book, but I will follow the challenge "Build your own Interpreter" strictly, so you might benefit from having an account. You can get discounted access using the code below which gives you a free week of access to the platform and a discount of 40% if you decide to subscribe to the paid tier.

Why this book comes for free#

The first reason I started writing a technical blog was to share with others my discoveries, and to save them the hassle of going through processes I had already cracked. Moreover, I always enjoy the fact that explaining something forces me to better understand that topic, and writing requires even more study to get things clear in my mind, before attempting to introduce other people to the subject.

Much of what I know comes from personal investigations, but without the work of people who shared their knowledge for free I would not have been able to make much progress. The Free Software Movement didn't start with Internet, and I got a taste of it during the 80s and 90s, but the World Wide Web undeniably gave an impressive boost to the speed and quality of this knowledge sharing.

So this book is a way to say thanks to everybody who gave their time to write blog posts, free books, software, and to organise conferences, groups, meetups. This is why I teach people at conferences, this is why I write a technical blog, this is the reason behind this book.

That said, if you want to acknowledge my effort with money, thanks! However, the best thing you can do is to become part of this process of shared knowledge; experiment, learn and share what you learn.

Typographic conventions#

Here are some typographic conventions used throughout the book.

Regular text appears like this, while inline code is displayed like this. When a library or a Rust concept is mentioned for the first time, a link to the official documentation will be added in this form [docs].

When the text mentions concepts that are not directly connected with the project at hand but are worth further investigation an aside will contain details or links.

The code of the project is presented in a box like the one shown below.

fn main() {
    println!("Hello, world!");
}

This means that the given code is added to the file specified in the title.

When smaller chunks of code are added or removed the change will be shown using green (add) and red (remove) highlight.

fn main() {
    println!("Hello, world!");
    println!("Good morning, world!");
}

Often, the changed lines are part of a long function, and maybe also part of a structure. To make it easy to see where the change occurs without copying large quantities of code anchors and ellipsis can be added to the code. For example, you can have

fn main() {

    match command.as_str() {

            let mut t = Tokenizer {
                ...
            };

            t.advance();

            for token in &mut t {
                ...
            }

Here, the changed line has been inserted inside the function main (first anchor) and the match construct (second anchor). No ellipsis are used in this case, even though both main and match contain lines of code that have been ignored. The ellipses are instead used inside Tokenizer and the for loop to signal that a small piece of code has been removed for visual purposes.

In general, this book tries to simplify as much as possible the visual impact of code listings, so ellipsis are used scarcely and most of the time chunks of code will be silently omitted. Please refer to the Git diff of the relevant section in case you are not sure of what changes have been applied.

In certain cases, it's useful to reason about code structure or to highlight specific details. The following box with a magnifying glass icon shows code snippets or meta code.

fn main() {
    println!("Hello, world!");
}

If the code shown is not correct, either because it doesn't compile or for other reason, it will be shown like this.

fn main() {
    println!("Hello, world!");
}

The output of commands run in the terminal, such as the compiler, the test suite, or other shell commands is shown in a box like this.

$ run -a --command

This is the output of the command in a terminal

The code shown in the book can be used to complete the CodeCrafters challenge "Build your own Interpreter". Whenever the code passes a specific stage a box like this will provide details.

Finally, the code of the project is available in a repository and the current step will be highlighted with a box like this

Set up the development environment#

The project consists of an implementation of the language Lox using Rust. I initially decided to call it "Rocks", playing on the pronunciation of "Lox" and on the fact that I expected it to be amazing! Unfortunately, I found that someone had the same idea, so I decided to be a bit humbler and call it "Pebble". Once again, there is already a project with that name, but at least it is not written in Rust.

To follow the project you need an editor (pick your favourite one and make sure you have support for Rust) and the Rust compiler. You can install Rust in your system following the official guide. To be able to use CodeCrafters you also need to configure a Git repository, but you can follow the instructions in the challenge page.

My advice is to turn off any AI helper in your editor. AI is extremely useful on a daily basis to improve your productivity, but while you are learning something new you should make sure you write every piece of code yourself, and understand why it is there. In this case, rather than using AI to write code use it to explore new concepts and to dig into the details of what we are going to do.

Create the Rust project (CodeCrafters)#

If you are using CodeCrafters, follow the instructions they provide. You will clone a repository provided by them that contains the Rust project and a script to run the server.

Create the Rust project (manual)#

If you don't want to use CodeCrafters you can simply clone my project from GitHub. The branch main points to the commit that contains the initial state of the code.

How to build the code and run tests#

Since we are using Cargo, you can build the code with

$ cargo build

and run unit tests with

$ cargo test

Throughout the book make sure you build often to check the modules you use. In general, it is difficult to highlight exactly which changes happen in that part of the code, so it is your responsibility to check that the code is consistent. The Git commits are correct, so you can always double check your code using them.

How to test code (CodeCrafters)#

If you are using CodeCrafters, tests will be run every time you commit and push. Make sure you read the official documentation, in particular if you want to use the CodeCrafters CLI.

How to test code (manual)#

You can run the CodeCrafters tests manually on your machine. Clone the tests repository and change the file Makefile

current_version_number := $(shell git tag --list "v*" | sort -V | tail -n 1 | cut -c 2-)
next_version_number := $(shell echo $$(($(current_version_number)+1)))
project_dir := "/FULL/PATH/OF/YOUR/CODE/pebble"

...

test_scanning_w_jlox: build
       CODECRAFTERS_REPOSITORY_DIR=./craftinginterpreters/build/gen/chap04_scanning \
       CODECRAFTERS_REPOSITORY_DIR=${project_dir} \

...

test_parsing_w_jlox: build
       CODECRAFTERS_REPOSITORY_DIR=./craftinginterpreters/build/gen/chap06_parsing \
       CODECRAFTERS_REPOSITORY_DIR=${project_dir} \

...

[do this for each target]

You can then run the tests locally using the provided Makefile. There are several tests that correspond to the base challenge and to the extensions. For the base challenge run

$ make test_scanning

This will however run all the tests in the base challenge, so if you want to check only the steps you completed so far you can copy that rule into a custom one and add steps while you progress, e.g.

test_scanning_prog: build
       CODECRAFTERS_REPOSITORY_DIR=${project_dir} \
       CODECRAFTERS_TEST_CASES_JSON="[ \
               {\"slug\":\"ry8\",\"tester_log_prefix\":\"stage_101\", \
                \"title\":\"Stage #1: Scanning: Empty File\"}, \
               {\"slug\":\"ol4\",\"tester_log_prefix\":\"stage_102\", \
                \"title\":\"Stage #2: Scanning: Parentheses\"}, \
               {\"slug\":\"oe8\",\"tester_log_prefix\":\"stage_103\", \
                \"title\":\"Stage #3: Scanning: Braces\"}, \
               {\"slug\":\"xc5\",\"tester_log_prefix\":\"stage_104\", \
                \"title\":\"Stage #4: Scanning: Single-character tokens\"} \
       ]" \
       $(shell pwd)/dist/main.out

Make sure you remove the final comma from the last line (Single-character tokens in the example above), as the code has to be valid JSON.

At this point you can run your custom test suite with

$ make test_scanning_prog

Artwork#

The cover photo is by Dana Ward and can be found on Unsplash.

The website theme is a custom version of PrettyDocs designed by Xiaoying Riley.