Building a LISP Interpreter in Rust

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.


  1. Background
  2. REPL: The Structure of an Interpreter
    1. Loop
    2. Read
    3. Evaluate
    4. Print


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
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:

REPL: The Structure of an Interpreter

A crude illustration of a REPL
A crude illustration of a REPL.
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.


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.


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.