(How to Write a (Lisp) Interpreter (in Python))

This page has two purposes: to describe how to implement computer language interpreters in general, and in particular to build an interpreter for most of the Scheme dialect of Lisp using Python 3 as the implementation language. I call my language and interpreter Lispy (lis.py). Years ago, I showed how to write a semi-practical Scheme interpreter Java and in in Common Lisp). This time around the goal is to demonstrate, as concisely and simply as possible, what Alan Kay called "Maxwell's Equations of Software."

Why does this matter? As Steve Yegge said, "If you don't know how compilers work, then you don't know how computers work." Yegge describes 8 problems that can be solved with compilers (or equally well with interpreters, or with Yegge's typical heavy dosage of cynicism).

Syntax and Semantics of Scheme Programs

The syntax of a language is the arrangement of characters to form correct statements or expressions; the semantics is the meaning of those statements or expressions. For example, in the language of mathematical expressions (and in many programming languages), the syntax for adding one plus two is "1 + 2" and the semantics is the application of the addition operation to the two numbers, yielding the value 3. We say we are evaluating an expression when we determine its value; we would say that "1 + 2" evaluates to 3, and write that as "1 + 2" ⇒ 3.

Scheme syntax is different from most other programming languages. Consider:

Java      Scheme

if (x.val() > 0) {   return fn(A[i] + 3 * i,             new String[] {"one", "two"}); }   (if (> (val x) 0)     (fn (+ (aref A i) (* 3 i))         (quote (one two)))

Java has a wide

variety of syntactic conventions (keywords, infix operators, three kinds of brackets, operator precedence, dot notation, quotes, commas, semicolons), but Scheme syntax is much simpler:

Scheme programs consist solely of expressions. There is no statement/expression distinction. Numbers (e.g. 1) and symbols (e.g. A) are called atomic expressions; they cannot be broken into pieces. These are similar to their Java counterparts, except that in Scheme, operators such as + and > are symbols too, and are treated the same way as A and fn. Everything else is a list expression: a "(", followed by zero or more expressions, followed by a ")". The first element of the list determines what it means:

A list starting with a keyword, e.g. (if ...), is a special form; the meaning depends on the keyword. A list starting with a non-keyword, e.g. (fn ...), is a function call.

The beauty of Scheme is that the full language only needs 5 keywords and 8 syntactic forms. In comparison, Python has 33 keywords and 110 syntactic forms, and Java has 50 keywords and 133 syntactic forms. All those parentheses may seem intimidating, but Scheme syntax has the virtues of simplicity and consistency. (Some have joked that "Lisp" stands for "Lots of Irritating Silly Parentheses"; I think it stand for "Lisp Is Syntactically Pure".)

In this page we will cover all the important points of the Scheme language and its interpretation (omitting some minor details), but we will take two steps to get there, defining a simplified language first, before defining the near-full Scheme language.

Language 1: Lispy Calculator

Lispy Calculator is a subset of Scheme using only five syntactic forms (two atomic, two special forms, and the procedure call). Lispy Calculator lets you do any computation you could do on a typical calculator—as long as you are comfortable with prefix notation. And you can do two things that are not offered in typical calculator languages: "if" expressions, and the definition of new variables.

Here's an example program, that computes the area of a circle of radius 10, using the formula π r2:

(define r 10) (* pi (* r r))

Here is a table of all the allowable expressions:

ExpressionSyntaxSemantics and Example

variable referencesymbolA symbol is interpreted as a variable name; its value is the variable's value. Example: r ⇒ 10 (assuming r was previously defined to be 10)

constant literalnumberA number evaluates to itself. Examples: 12 ⇒ 12 or -3.45e+6 ⇒ -3.45e+6

conditional(if test conseq alt) Evaluate test; if true, evaluate and return conseq; otherwise alt. Example: (if (> 10 20) (+ 1 1) (+ 3 3)) ⇒ 6

definition (define symbol exp) Define a new variable and give it the value of evaluating the expression exp. Examples: (define r 10) procedure call(proc arg...) If proc is anything other than one of the symbols if, define, or quote then it is treated as a procedure. Evaluate proc and all the args, and then the procedure is applied to the list of arg values. Example: (sqrt (* 2 8)) ⇒ 4.0

In the Syntax column of this table, symbol must be a symbol, number must be an integer or floating point number, and the other italicized words can be any expression. The notation arg... means zero or more repetitions of arg.

What A Language Interpreter Does

A language interpreter has two parts:

Parsing: The parsing component takes an input program in the form of a sequence of characters, verifies it according to the syntactic rules of the language, and translates the program into an internal representation.

In a simple interpreter the internal representation is a tree structure (often called an abstract syntax tree) that closely mirrors the nested structure of statements or expressions in the program. In a language translator called a compiler there is often a series of internal representations, starting with an abstract syntax tree, and progressing to a sequence of instructions that can be directly executed by the computer. The Lispy parser is implemented with the function parse. Execution: The internal representation is then processed according to the semantic rules of the language, thereby carrying out the computation. Lispy's execution function is called eval (note this shadows Python's built-in function of the same name).

Here is a picture of the interpretation process:

program ➡ parse ➡ abstract-syntax-tree ➡ eval ➡ result

And here is a short example of what we want parse and eval to be able to do (begin evaluates each expression in order and returns the final one):

>> program = "(begin (define r 10) (* pi (* r r)))"

>>> parse(program) ['begin', ['define', 'r', 10], ['*', 'pi', ['*', 'r', 'r']]]

>>> eval(parse(program)) 314.1592653589793

Type Definitions

Let's be explicit about our representations for Scheme objects:

Symbol = str # A Scheme Symbol is implemented as a Python str Number = (int, float) # A Scheme Number is implemented as a Python int or float Atom = (Symbol, Number) # A Scheme Atom is a Symbol or Number List = list # A Scheme List is implemented as a Python list Exp = (Atom, List) # A Scheme expression is an Atom or List Env = dict # A Scheme environment (defined below) # is a mapping of {variable: value}

Parsing: parse, tokenize and read_from_tokens

Parsing is traditionally separated into two parts: lexical analysis, in which the input character string is broken up into a sequence of tokens, and syntactic analysis, in which the tokens are assembled into an abstract syntax tree. The Lispy tokens are parentheses, symbols, and numbers.

There are many tools for lexical analysis (such as Mike Lesk and Eric Schmidt's lex), but for now we'll use a very simple tool: Python's str.split. The function tokenize takes as input a string of characters; it adds spaces around each paren, and then calls str.split to get a list of tokens:

def tokenize(chars: str) -> list: "Convert a string of characters into a list of tokens." return chars.replace('(', ' ( ').replace(')', ' ) ').split()

Here we apply tokenize to our sample program:

>>> program = "(begin (define r 10) (* pi (* r r)))" >>> tokenize(program) ['(', 'begin', '(', 'define', 'r', '10', ')', '(', '*', 'pi', '(', '*', 'r', 'r', ')', ')', ')']

Our function parse will take a string representation of a program as input, call tokenize to get a list of tokens, and then call read_from_tokens to assemble an abstract syntax tree. read_from_tokens looks at the first token; if it is a ')' that's a syntax error. If it is a '(', then we start building up a list of sub-expressions until we hit a matching ')'. Any non-parenthesis token must be a symbol or number. We'll let Python make the distinction between them: for each non-paren token, first try to interpret it as an int, then as a float, and if it is neither of those, it must be a symbol. Here is the parser:

def parse(program: str) -> Exp: "Read a Scheme expression from a string." return read_from_tokens(tokenize(program))

def read_from_tokens(tokens: list) -> Exp: "Read an expression from a sequence of tokens." if len(tokens) == 0: raise SyntaxError('unexpected EOF') token = tokens.pop(0) if token == '(': L = [] while tokens[0] !

= ')': L.append(read_from_tokens(tokens)) tokens.pop(0) # pop off ')' return L elif token == ')': raise SyntaxError('unexpected )') else: return atom(token)

def atom(token: str) -> Atom: "Numbers become numbers; every other token is a symbol." try: return int(token) except ValueError: try: return float(token) except ValueError: return Symbol(token)

parse works like this:

>>> program = "(begin (define r 10) (* pi (* r r)))"

>>> parse(program) ['begin', ['define', 'r', 10], ['*', 'pi', ['*', 'r', 'r']]]

We're almost ready to define eval. But we need one more concept first.

Environments

An environment is a mapping from variable names to their values. By default, eval will use a global environment that includes the names for a bunch of standard functions (like sqrt and max, and also operators like *). This environment can be augmented with user-defined variables, using the expression (define symbol value).

import math import operator as op

def standard_env() -> Env: "An environment with some Scheme standard procedures." env = Env() env.update(vars(math)) # sin, cos, sqrt, pi, ... env.update({ '+':op.add, '-':op.sub, '*':op.mul, '/':op.truediv, '>':op.gt, '<':op.lt, '>=':op.ge, '<=':op.le, '=':op.eq, 'abs': abs, 'append': op.add, 'apply': lambda proc, args: proc(*args), 'begin': lambda *x: x[-1], 'car': lambda x: x[0], 'cdr': lambda x: x[1:], 'cons': lambda x,y: [x] + y, 'eq?': op.is_, 'expt': pow, 'equal?':