A modular, multi-backend Scheme interpreter designed for experimentation
This repository is, very deliberately, an experiment in building software
with AI coding agents. The overwhelming majority of its code, tests,
documentation, and planning documents were written by an AI agent (Claude
Code) working under human direction: the human sets the goals, reviews the
designs and diffs, merges every PR, and owns every decision — the agent does
the reading, writing, debugging, benchmarking, and bookkeeping. The history
is honest about this: nearly every commit carries a Co-Authored-By: Claude
trailer, and the PRD/ directory contains the actual working documents the
human–agent pair planned with, warts and all.
Two consequences worth stating plainly:
- Read it as an experiment. It is a probe of what agent-driven development can produce on a substantial project (an interpreter with a bytecode VM, hygienic macros, and a full numeric tower) — not a hardened production Scheme.
- It is tested like it matters anyway. 1163/1163 of the chibi-scheme R7RS suite on both backends, ~1,400 integration tests, and differential testing between the two backends gate every change.
Patina is an educational and experimental Scheme interpreter with ambitious goals:
Our primary focus is complete conformance to the R7RS-small specification. We validate against the comprehensive Chibi Scheme test suite maintained by Alex Shinn, chairman of the R7RS Small Language committee.
Current status: 100% of chibi r7rs-tests.scm passing (1163/1163 tests) on both backends.
Patina separates concerns into independent crates with two key abstractions:
Pipeline - Orchestrates the entire evaluation flow:
Source Code → Parse → Expand → Desugar → Evaluate → Result
Different pipelines can compose phases differently (e.g., adding optimization passes, bytecode compilation).
Backend - Handles evaluation of parsed expressions:
trait Backend {
fn eval(&self, expr: TaggedValue, env: &Rc<Environment>)
-> Result<TaggedValue, Self::Error>;
}This separation allows swapping evaluation strategies (tree-walker, VM, JIT) without changing the pipeline, or adding pipeline stages without touching the backend.
patina-frontend → Lexer, Parser, Desugarer
patina-ir → CoreExpr intermediate representation
patina-macros → Hygienic macro expansion (scope sets)
patina-runtime → Core types, Backend trait, Library system
patina-pipeline → Pipeline orchestration
patina-vm → Register-based bytecode VM (default backend)
patina-tree-walker → CPS tree-walking backend (--tree-walker)
patina-interpreter → High-level API
patina-repl → Terminal REPL
patina-tests → Integration tests (~1400 tests)
The architecture is designed to support future exploration:
syntax-caseprocedural macros- Nanopass-style optimization passes
- Language extensions (gradual typing, reactive concurrency, logic programming)
- Garbage collection is stop-the-world. A non-moving mark-and-sweep
collector runs on both backends (
(gc)and(gc-stats)in(patina debug)give manual control). Pauses are unbounded by generational or incremental techniques — that work is staged indocs/GC_DESIGN.md. - Performance is that of a young interpreter: far beyond a naive tree-walker and improving quickly (the VM gained 2–3× on arithmetic- and list-heavy code in the most recent optimization wave), but not yet competitive with mature Schemes like Chez.
Patina prioritizes clarity over cleverness:
- Well-documented Rust with clear separation of concerns
- Educational value - learn both Scheme and interpreter design
- Comprehensive test suite
- Reference implementations studied: Chibi Scheme, Chez Scheme
# Build and run the REPL
cargo build --release
./target/release/patina
# Run a Scheme script (uses VM backend by default)
./target/release/patina script.scm
# Use the tree-walking backend instead
./target/release/patina --tree-walker script.scm
# Disassemble bytecode / trace execution
./target/release/patina --dump script.scm
./target/release/patina --trace script.scm
# R7RS compliance suite (the canonical gate)
./scripts/run_chibi_tests.sh
# Rust unit + integration tests
cargo test --all --lib --testspatina> (define factorial
(lambda (n)
(if (<= n 1)
1
(* n (factorial (- n 1))))))
patina> (factorial 10)
3628800
patina> (define-syntax when
(syntax-rules ()
((when test body ...)
(if test (begin body ...)))))
patina> (when (> 3 2) (display "yes\n"))
yesA minimal intermediate representation with 13 core forms:
enum CoreExprKind {
Literal, Var, Quote, Quasiquote, // Values
Lambda, If, Set, Begin, // Core forms
Define, Import, Expand, // Toplevel
App, Apply, // Application
}All derived forms (let, cond, case, do, and, or, when,
define-record-type, etc.) are syntax-rules macros written in Scheme
(lib/scheme/) that expand to these primitives.
Racket-style scope sets hygiene (based on "Binding as Sets of Scopes", Flatt 2016):
- Pattern matching with ellipsis
- Flip-scope algorithm for use-site vs introduced identifier discrimination
- No alpha-renaming needed
Complete R7RS-compliant library system:
.sldfiles - R7RS library definitions with exports and includes- Rust primitives - Performance-critical operations in internal modules
- Scheme implementations - Macros and derived forms in
.scmfiles - Full support -
cond-expand,include,include-ci,include-library-declarations
Complete Scheme numeric hierarchy with automatic promotion:
Integer (i64) → BigInteger → Rational → Real (f64) → Complex
| Document | Description |
|---|---|
| VM Decisions | Settled VM architecture decisions (master reference) |
| VM ISA | Instruction set architecture and semantics |
| VM Compiler | The 5-pass compiler pipeline |
| VM Runtime | Execution loop and control primitives |
| Macro System | Scope-set hygiene and the flip-scope algorithm |
| Test Organization | Test structure and running tests |
The PRD/ directory holds the living planning documents — including
PRD/TRACK_P_PERFORMANCE_PRD.md with the measured performance progress log.
patina/
├── crates/
│ ├── patina-runtime/ # Core types, Backend trait, internal primitives
│ ├── patina-ir/ # CoreExpr IR
│ ├── patina-frontend/ # Lexer, Parser, Desugarer
│ ├── patina-macros/ # Macro expansion
│ ├── patina-pipeline/ # Pipeline orchestration
│ ├── patina-vm/ # Register-based bytecode VM (default)
│ ├── patina-tree-walker/ # CPS tree-walking backend
│ ├── patina-interpreter/ # High-level API
│ ├── patina-repl/ # Terminal REPL
│ └── patina-tests/ # Integration tests (~1400 tests)
├── lib/ # Scheme standard library
│ └── scheme/ # R7RS .sld libraries and implementations
├── docs/ # User documentation
├── PRD/ # Planning documents
└── spec/ # R7RS specification
- R7RS Small Specification
- Local copy in
spec/r7rs-small-spec/
- Chibi Scheme - R7RS reference implementation
- Chez Scheme - High-performance Scheme
scheme_tests/chibi/r7rs-tests.scmis from chibi-scheme (BSD 3-Clause); seescheme_tests/README.mdfor attribution and the full license text.crates/patina-tests/bench_programs/{nboyer,sboyer}.scmare the classic Boyer benchmarks (Public Domain, original headers retained), vendored via ecraven/r7rs-benchmarks.
MIT License - See LICENSE file for details
- R7RS editors and contributors for the excellent specification
- Alex Shinn and the Chibi Scheme project
- The Scheme community for decades of language design wisdom