Many years ago, Peter Norvig wrote a beautiful article about www a lisp interpreter in Python. It’s the most fun tutorial I’ve seen, not just because it teaches you about my favorite language family(Lisp), but because it cuts through to the essence of interpreters, is fun to follow and quick to finish.
Recently, I had some time and wanted to learn Rust. It’s a beautiful systems language, and I’ve seen some great work come out from those who adopt it. I thought, what better way to learn Rust, than to create a lisp interpreter in it?
Hence, Risp — a lisp in rust — was born. In this essay you and I will follow along with Norvig’s Lispy, but instead of Python, we’ll do it in Rust 🙂.
Syntax, Semantics and Notes on Following Along
If you haven’t heard of lisp, some Paul Graham’s essays(one,two, three), alongside some Rich Hickey talks will get you fired up. In short, everything is a list, everything is an expression, and that makes for a very powerful language.
Our structure will be similar to Norvig’s tutorial, though I depart slightly in two ways:
Instead of 2 stopping points(Lispy Calculator and Full Lispy), we have 4 stopping points. This reflects the phases I took to build it in Rust.
Norvig’s syntax is based on Scheme. We will base it on Scheme too, but since I’m also a Clojure fan, I sometimes used slightly different naming, and different implementations for a few functions. I will note when I do that in the essay.
Finally, this is the first program I wrote in Rust. I may have misused some things, so if you’re a Rust hacker, I’d love to hear your feedback 🙂.
With the notes out of the way, let’s get into it.
Language 1: Just a Risp calculator
As Norvig suggests, our first goal is to create a subset of lisp, that can do what a basic calculator can do.
To make it as simple as possible tofollow, for language 1, we’ll only support addition and subtraction. No variable definitions, no if statements, nada.
This departs a bit from Lispy, but I found this stopping point a lot more convenient when writing it in Rust. So, our goal:
(+ 1052) //=> 17
(- 1052) //=> 3
The important process we need to remember is the flow of an interpreter:
our program ⟶parse⟶ abstract syntax tree ⟶eval⟶ result
We will need to parse our program and convert it into an abstract syntax tree. After that, we can eval the abstract syntax tree and get our result.(Refer to Norvig’s article for more detailed definitions and explanations).
Type Definitions
Risp can have three kinds of values for now:
#[derive(Clone)]
enumRispExp {
Symbol(String),
Number(f64),
List(Vec<RispExp>),
}
We’ll also need an error type:
#[derive(Debug)]
enumRispErr {
Reason(String),
}
Finally, we’ll need an environment type. This is where we will store defined variables, built-in functions, and so forth:
Syntax, Semantics and Notes on Following Along
Language 1: Just a Risp calculator
(+ 10 5 2) //=> 17(- 10 5 2) //=> 3Type Definitions
#[derive(Clone)]enum RispExp { Symbol(String), Number(f64), List(Vec<RispExp>),}#[derive(Debug)]enum RispErr { Reason(String),}