I've put together a hands-on tutorial for building a Lisp interpreter in Rust from scratch — 74 steps, zero dependencies, 42 tests passing.
Full disclosure upfront: This tutorial was developed with the help of an AI coding assistant. I want to be upfront about that.
What I did do: followed every step myself, ran cargo test after each change, debugged every compiler error, and verified all 42 tests pass. The code runs — you can clone it and try it right now.
What the AI helped with: explaining concepts, structuring the tutorial, writing prose, and catching my mistakes. Think of it as a very patient pair programmer — but I typed the code, I ran the compiler, and I verified the results.
I'm sharing this because I think the step-by-step approach might be genuinely useful to someone learning Rust or interpreters. If that's not for you, that's totally fine.
Why another Lisp interpreter tutorial?
Most tutorials I've seen either:
- Assume you already know the language well, or
- Skip the hard parts (closures, TCO, macros), or
- Use tons of dependencies that hide what's really happening
This one is different in a few ways:
1. Truly zero dependencies. The Cargo.toml has no third-party crates. Everything — lexer, parser, evaluator, even the hash map — is built from the standard library. (Well, we do use FxHasher from std::collections, but no external crates.)
2. Gradual performance optimization. Instead of starting with the fastest design, we first get it working with String everywhere, then optimize in three passes:
- Step 40-41: String interning (symbols become
u64IDs) - Step 42: Zero-copy lexing (
&strtokens borrowing the source) - Step 43:
FxHasherfor faster hash lookups
I found this "make it work, then make it fast" approach much more educational than starting with the optimized version.
3. Closures explained with a "backpack" metaphor. This is the part I'm most proud of. Instead of throwing Rc<RefCell<Env>> at readers immediately, the tutorial builds intuition first:
Every function carries a "backpack"
— the environment where it was born. When it needs a variable, it checks its backpack first.
Then we trace through a make-counter example step by step, showing exactly what goes into the backpack and when. Only after that do we look at the Rust code.
4. TCO via trampoline loop. Step 39 walks through converting recursive eval calls into a loop { match ...; continue } trampoline. The demo shows 1,000,000 tail-recursive iterations succeeding while ~10,000 non-tail-recursive iterations overflow the stack.
What it covers
- Lexing (zero-copy tokenizer)
- Recursive descent parser
- Environment chaining with lexical scoping (
Rc<RefCell<LispEnv>>) - Closures
- Tail call optimization (trampoline)
- Macros (
defmacro, quasiquote/unquote,gensym) - String interning + FxHasher optimization
- A REPL with multi-line input
Who is it for?
The tutorial has multiple entry points — you can start from "what is programming" or jump straight to closures/TCO if you've written an interpreter before. It's bilingual (English + Chinese).
Try it
git clone https://github.com/lisering/lisp-rs.git
cd lisp-rs
cargo test
cargo run -- demo_tco.lisp # TCO demo
I'd love feedback on the teaching approach — especially the closure explanation and the gradual optimization strategy. Is the "backpack" metaphor helpful? Are there parts that could be clearer?
Why another Lisp interpreter tutorial?
Most tutorials I've seen either:
- Assume you already know the language well, or
- Skip the hard parts (closures, TCO, macros), or
- Use tons of dependencies that hide what's really happening
This one is different in a few ways:
1. Truly zero dependencies. The Cargo.toml has no third-party crates. Everything — lexer, parser, evaluator, even the hash map — is built from the standard library. (Well, we do use FxHasher from std::collections, but no external crates.)
2. Gradual performance optimization. Instead of starting with the fastest design, we first get it working with String everywhere, then optimize in three passes:
- Step 40-41: String interning (symbols become
u64IDs) - Step 42: Zero-copy lexing (
&strtokens borrowing the source) - Step 43:
FxHasherfor faster hash lookups
I found this "make it work, then make it fast" approach much more educational than starting with the optimized version.
3. Closures explained with a "backpack" metaphor. This is the part I'm most proud of. Instead of throwing Rc<RefCell<Env>> at readers immediately, the tutorial builds intuition first:
Every function carries a "backpack"
Then we trace through a make-counter example step by step, showing exactly what goes into the backpack and when. Only after that do we look at the Rust code.
4. TCO via trampoline loop. Step 39 walks through converting recursive eval calls into a loop { match ...; continue } trampoline. The demo shows 1,000,000 tail-recursive iterations succeeding while ~10,000 non-tail-recursive iterations overflow the stack.
What it covers
- Lexing (zero-copy tokenizer)
- Recursive descent parser
- Environment chaining with lexical scoping (
Rc<RefCell<LispEnv>>) - Closures
- Tail call optimization (trampoline)
- Macros (
defmacro, quasiquote/unquote,gensym) - String interning + FxHasher optimization
- A REPL with multi-line input
Who is it for?
The tutorial has multiple entry points — you can start from "what is programming" or jump straight to closures/TCO if you've written an interpreter before. It's bilingual (English + Chinese).
Try it
git clone https://github.com/lisering/lisp-rs.git
cd lisp-rs
cargo test
cargo run -- demo_tco.lisp # TCO demo
I'd love feedback on the teaching approach — especially the closure explanation and the gradual optimization strategy. Is the "backpack" metaphor helpful? Are there parts that could be clearer?