Building a LISP Interpreter in Rust

Dominick Allen

Published on 27 June 2020.

Last edited on 21:50 27 June 2020.

If you couldn't already tell from the title of the page and the headline, I'm writing a LISP interpreter in Rust. If you want to look at the source code, go to my repo. If you want to install it, tinker with it, or do whatever, then follow the instructions here.

Contents

Background
REPL: The Structure of an Interpreter

Loop
Read
Evaluate
Print

Background

I enjoy writing code in LISP. When I first started to learn how to program, I decided to write a command line calculator program. Coincidentally, I still think writing a calculator a great way to learn how to program, but I digress: when I wrote my calculator program, I made the fateful decision to use LISP's Polish notation. My reasoning was simple: parsing S-expressions is dead simple. The consequences of this decision were to be realized later when I started to think it would be nice if I could define simple functions; it was only a small jump from the implementation of simple functions to higher order functions, and I found myself with a Turing complete programming language.

An S-expression tree. Created by Natecull under CC-BY-SA 3.0.

However, my implementation was slow, used a lot of resources, and I was about to go to college. My creation, written in a pre-1.0 version of the Rust programming language, was left behind. I've wanted to redo it again for a long time, with the intent to write a fast and efficient version that is intended to be an interpreter from day one. I want to record my experience with this process on this website, to document my decisions and share how I solve the problems I encounter along the way.

Okay, but why Rust?

I decided to write this in Rust for a couple reasons. First of all, I used rust for my original implementation, and I wanted to do it again. Second, Rust actually has some nice features:

Rust is fast.
Rust is not C or C++. I get enough C++ at work.
Rust is not a LISP. Writing a LISP interpreter in LISP is cheating.
I really like Rust's type system. Type deduction, traits, and function signatures are all great.
I like pattern matching.

REPL: The Structure of an Interpreter

The term REPL defines the essence of an interpreter. It stands for Read, Evaluate, Print, Loop. In a loop, a user's input is read, then evaluated, and the result of the evaluation is printed. Simple, right? I think it's more easy to start with the loop part than the read part, personally.

Loop

Looping is the simplest part of REPL, and its construction takes many forms. We don't actually want the interpreter to run forever, but to quit when the user wants to do so.

Read

In the context of my LISP interpreter, reading is done by inputting an expresion, using rustyline to make the input experience nice and to save history. That input is transformed into a string, which is then parsed into an S-Expression. Look here about how I tokenize and parse inputs.