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:
For this, we will use the Rust crate
logos which provides a very easy way to define the lexer.