How to Write a Lisp Interpreter in Python
Implementing a language interpreter is a fundamental exercise in understanding how computers process code. Peter Norvig's "Lispy" project demonstrates that a nearly complete subset of the Scheme dialect of Lisp can be implemented in approximately 117 lines of Python code, proving that the core mechanics of a powerful language can be expressed very concisely.
The Architecture of a Language Interpreter
An interpreter consists of two primary components: parsing and execution. The process follows a linear pipeline: Program $\rightarrow$ Parse $\rightarrow$ Abstract Syntax Tree (AST) $\rightarrow$ Eval $\rightarrow$ Result.
1. Parsing
Parsing converts a raw sequence of characters into an internal representation, typically an Abstract Syntax Tree (AST). This is further divided into two stages:
- Lexical Analysis (Tokenization): The input string is broken into tokens. In Lispy, this is achieved by adding spaces around parentheses and using Python's
str.split(). - Syntactic Analysis: Tokens are assembled into a nested structure. Lispy uses a recursive function
read_from_tokensto build Python lists that mirror the nested parentheses of Scheme.
2. Execution (Evaluation)
Execution processes the AST according to the semantic rules of the language. In Lispy, the eval function determines the value of an expression based on its type: atoms (numbers or symbols) are handled directly, while lists are treated as either special forms (like if or define) or procedure calls.
Implementing the Lispy Calculator
The first iteration of Lispy is a basic calculator supporting five syntactic forms:
| Expression | Syntax | Semantics |
|---|---|---|
| Variable Reference | symbol |
Returns the value of the variable from the environment. |
| Constant Literal | number |
Evaluates to the number itself. |
| Conditional | (if test conseq alt) |
Evaluates test; returns conseq if true, else alt. |
| Definition | (define symbol exp) |
Binds the value of exp to symbol in the environment. |
| Procedure Call | (proc arg...) |
Evaluates proc and args, then applies the procedure to the values. |
Extending to Full Lispy: Procedures and Lexical Scoping
To move from a calculator to a full language, Lispy introduces three additional forms: quote (literal return), set! (assignment), and lambda (procedure creation).
Lexical Scoping and Environments
To support local variables within procedures, the environment (Env) is redefined as a class that inherits from dict. This allows for nested environments where a local environment maintains a reference to its "outer" environment.
When a variable is referenced, the interpreter uses a find method to search the innermost environment first, moving outward to the global environment if the variable is not found. This mechanism is known as lexical scoping.
The Procedure Object
User-defined procedures are represented by a Procedure class containing:
- A list of parameter names.
- The body of the procedure.
- The environment in which the procedure was defined.
When a procedure is called, a new Env is created, binding the provided arguments to the parameters, with the procedure's original definition environment as the outer scope.
Evaluation of Lispy's Performance and Completeness
Lispy is designed for educational clarity rather than production use. Its characteristics include:
- Size: Extremely compact, consisting of roughly 117 non-comment lines and 4KB of source code.
- Speed: Capable of computing
(fact 100)in approximately 0.003 seconds. - Completeness: It is a subset of Scheme. It lacks several standard features, including tail-call optimization,
call/cc, strings, booleans, and comprehensive error recovery.
Community Insights and Perspectives
Discussion among developers highlights the enduring value of this exercise for understanding language design. Some contributors suggest that implementing a Lisp or Forth is an "illuminating experience" that changes how a programmer views syntax and structure.
Other developers have noted the isomorphism between Lisp's nested structures and the tree structures used by linguists to annotate sentence structures. Additionally, the community has produced various derivatives, including versions in Rust and JavaScript, and even a "syntax sugar" library called fakelisp that allows embedding Lisp snippets directly into valid Python code.