Writing a simple Lisp interpreter in Rust

Lisp is a family of multi-paradigm programming languages (functional, procedural, reflective, …), which can be similar to Lambda Calculus. The name stands for “list processing”.

The syntax is based on the concept of S-Expression (short for: Symbolic Expression). The code is therefore organized in a tree-like data structure. In Lisp, code is data, and data is code.

In this article, we will write a very simple (non standard?) Lisp interpreter in Rust. This will be a great way to explore the Rust ecosystem, and what it can do for us, language designers.

The interpreter will be split in 3 parts:

• the frontend, to parse S-Expressions
• the backend, to evaluate the S-Expressions
• the REPL, to provide a simple CLI to execute Lisp code

NB: All the code present in this article is available in this repository:

GitHub - linkdd/lispers: Educational project: How to implement a Lisp interpreter in Rust?

Part 1: Parsing S-Expressions

Lisp usually defines 3 types of data:

• atoms: symbols, numbers, booleans
• strings: delimited by double-quotes
• lists: delimited by parenthesis

Here is an example of S-Expression:

(a b (c d) "hello world" (+ 1 2))

Step 1: Lexical analysis

Or in other words: transforming the stream of characters into a stream of tokens. If we take the above example, the corresponding tokens would be:

ParenOpen
Symbol("a")
Symbol("b")
ParenOpen
Symbol("c")
Symbol("d")
ParenClose
String("hello world")
ParenOpen
Symbol("+")
Integer(1)
Integer(2)
ParenClose
ParenClose

For this, we will use the Rust crate logos which provides a very easy way to define the lexer.

GitHub - maciejhirsz/logos: Create ridiculously fast Lexers