Lisp’s reputation for implementability
Lisp has a persistent reputation among programming languages as being unusually easy to implement. In discussions about writing interpreters and compilers, it often comes up as a natural first choice. That reputation is not accidental—it stems from two concrete properties of the language family: a frontend with very little syntactic machinery, and a backend that collapses into a surprisingly small evaluator.
A clarification is in order: “Lisp” here refers to a language family. Some members, like the original Lisp 1.5 or early Scheme, are minimal. Others, such as Common Lisp, Racket, or Clojure, are large and complex. The ease of implementation applies to the minimal members of the family; industrial-strength Lisps are substantial engineering efforts.
The frontend: one syntax rule
The frontend of a Lisp is simple because the language’s syntax is essentially uniform. A Lisp program is a nested list structure:
( item item ... )
The lexer only needs to recognize a small set of special characters—parens, quotes for symbols, and double quotes for strings. The parser’s job is even smaller: a single recursive rule for parsing lists. There is no operator precedence table, and no operators at all in the syntax:
(minus x y)
parses exactly like:
(- x y)
In the second form, - is merely a symbol. Whatever special meaning it carries is the interpreter’s business, not the parser’s. Lisps are also almost universally dynamically typed, which removes another layer of syntactic and semantic complexity.
The payoff goes beyond parsing. In most languages, the parser produces an AST that must be explicitly designed and then mapped from the parse tree. In Lisp, the AST is the parsed structure itself—the nested list is the tree. For (minus x y), the “AST” is a node with minus at the root and x and y as children. No separate AST data structures are needed. This is why Lisp code is famously just Lisp data, and why macros are ordinary Lisp code that manipulates other Lisp code, rather than a distinct language feature.
The backend: a small evaluator
The simplicity of the backend has roots going back to John McCarthy’s 1960 paper, Recursive Functions of Symbolic Expressions and Their Computation by Machine. A particularly clear formulation appears in Paul Graham’s 2002 essay, The Roots of Lisp, which presents the entire interpreter in a few lines:
(defun eval. (e a)
(cond
((atom e) (assoc. e a))
((atom (car e))
(cond
((eq (car e) 'quote) (cadr e))
((eq (car e) 'atom) (atom (eval. (cadr e) a)))
((eq (car e) 'eq) (eq (eval. (cadr e) a) (eval. (caddr e) a)))
((eq (car e) 'car) (car (eval. (cadr e) a)))
((eq (car e) 'cdr) (cdr (eval. (cadr e) a)))
((eq (car e) 'cons) (cons (eval. (cadr e) a) (eval. (caddr e) a)))
((eq (car e) 'cond) (evcon. (cdr e) a))
('t (eval. (cons (assoc. (car e) a) (cdr e)) a))))
((eq (caar e) 'label)
(eval. (cons (caddar e) (cdr e)) (cons (list (cadar e) (car e)) a)))
((eq (caar e) 'lambda)
(eval. (caddar e) (append. (pair. (cadar e) (evlis. (cdr e) a)) a)))))
(defun evcon. (c a)
(cond ((eval. (caar c) a)
(eval. (cadar c) a))
('t (evcon. (cdr c) a))))
(defun evlis. (m a)
(cond ((null. m) '())
('t (cons (eval. (car m) a) (evlis. (cdr m) a)))))
This evaluator assumes a handful of primitives built on lower-level operations:
(defun pair. (x y)
(cond ((and. (null. x) (null. y)) '())
((and. (not. (atom x)) (not. (atom y)))
(cons (list (car x) (car y))
(pair. (cdr x) (cdr y))))))
(defun assoc. (x y)
(cond ((eq (caar y) x) (cadar y))
('t (assoc. x (cdr y)))))
(defun null. (x) (eq x '()))
(defun and. (x y)
(cond (x (cond (y 't) ('t '())))
('t '())))
(defun not. (x)
(cond (x '())
('t 't)))
(defun append. (x y)
(cond ((null. x) y)
('t (cons (car x) (append. (cdr x) y)))))
It also relies on the built-ins quote, atom, eq, car, cdr, cons, and cond. Of these, cons, car, and cdr are the fundamental list operations: cons builds a pair, car returns its head, and cdr returns its tail. Compound accessors like cadr and caddar are just combinations of car and cdr—for example, (cadr x) is (car (cdr x)), yielding the second element. Since Lisp lists model nested trees, these accessors are conveniences for reaching specific descendants of a node.
The remarkable fact is how little supporting infrastructure the evaluator needs. One practical hurdle arises when implementing a Lisp interpreter in a systems language: the specification assumes automatic memory management. There is a cons to allocate list cells, but no explicit deallocation. That is why a C++ version of a Lisp interpreter is a natural exercise in writing a garbage collector, while a Python-based first interpreter can skip that concern entirely.
