Building a Tiny Interpreter in Lisp

Building an interpreter teaches you what a language actually is

Most developers use languages every day without ever seeing the machinery beneath them. Building an interpreter strips that machinery down to its essentials.

A programming language is not magic. At a small scale, it is just a few ideas working together: a way to represent code, a way to look up names, and a set of rules for evaluation. Once you build those rules yourself, concepts like lexical scope, closures, special forms, and recursion stop feeling abstract.

The tiny language we are going to support

To keep the interpreter understandable, we will support a deliberately small language. Every expression will be one of these forms:

• Numbers, like 42
• Symbols, like x or +
• Lists, like (+ 1 2) or (if cond a b)

And we will implement these features:

For simplicity, we will assume that input is already parsed into Lisp data. In real Common Lisp, you can often leverage the host reader and work directly with s-expressions.

Reading input: from text to Lisp data

In many languages, this is the hardest first step. You need tokenizers, parsers, precedence rules, and AST nodes. In Lisp, source code is already expressed as lists, symbols, and literals. That means the host language can often read your tiny language for you.

For example, if the user types this:

(+ 1 (* 2 3))

Lisp naturally sees that as a nested list structure. That is exactly what the interpreter wants.

If you want a very small helper that turns a string into one expression in Common Lisp, it can look like this:

(defun read-expr (string)
  (read-from-string string))

That is not a complete parser for a production language, but for a tiny interpreter experiment it is wonderfully convenient. The real lesson is bigger: in Lisp, code and data share the same shape.

Environment: where names get their meaning

An evaluator needs somewhere to store variable bindings. That structure is usually called an environment. In a tiny interpreter, the environment only has to answer two questions:

1. What value does a symbol name refer to?
2. When a function creates a new scope, how do we fall back to outer scopes?

A clean way to model this is a chained environment: each scope has a table of bindings and an optional parent.

(defstruct env
  table
  parent)

(defun make-root-env ()
  (make-env :table (make-hash-table :test #'eq)
            :parent nil))

(defun env-lookup (environment symbol)
  (multiple-value-bind (value found)
      (gethash symbol (env-table environment))
    (cond
      (found value)
      ((env-parent environment)
       (env-lookup (env-parent environment) symbol))
      (t
       (error "Unbound symbol: ~a" symbol)))))

(defun env-define (environment symbol value)
  (setf (gethash symbol (env-table environment)) value)
  value)

(defun env-extend (parent bindings)
  (let ((child (make-env :table (make-hash-table :test #'eq)
                         :parent parent)))
    (dolist (pair bindings child)
      (setf (gethash (car pair) (env-table child)) (cdr pair)))))

With this, local scopes become easy. A function call can create a child environment that maps parameter names to argument values, while still seeing outer bindings through parent.

The heart of it all: a recursive evaluator

The evaluator is where the language becomes real. It examines an expression and decides what it means. The simplest version follows the shape of the language model we defined earlier.

(defun self-evaluating-p (expr)
  (numberp expr))

(defun truthy-p (value)
  (not (null value)))

(defun tiny-eval (expr environment)
  (cond
    ;; numbers evaluate to themselves
    ((self-evaluating-p expr)
     expr)

    ;; symbols are looked up in the environment
    ((symbolp expr)
     (env-lookup environment expr))

    ;; lists are either special forms or function calls
    ((consp expr)
     (let ((head (car expr))
           (args (cdr expr)))
       (case head
         (quote (car args))
         (if    (eval-if args environment))
         (define (eval-define args environment))
         (lambda (eval-lambda args environment))
         (t     (eval-application expr environment)))))

    (t
     (error "Unknown expression type: ~a" expr))))

There are only three major branches here:

• Literals evaluate to themselves.
• Symbols resolve through the environment.
• Lists represent either special syntax or function application.

Special forms: syntax with evaluation rules

If every list were treated as a normal function call, the language would be too limited. Some forms need custom rules. For example, in an if, you only want to evaluate one branch, not both.

define for variables

(defun eval-define (args environment)
  (destructuring-bind (name value-expr) args
    (let ((value (tiny-eval value-expr environment)))
      (env-define environment name value))))

if for conditionals

(defun eval-if (args environment)
  (destructuring-bind (test then else) args
    (if (truthy-p (tiny-eval test environment))
        (tiny-eval then environment)
        (tiny-eval else environment))))

quote for raw data

quote prevents evaluation. That matters because otherwise lists are assumed to be executable forms.

(tiny-eval '(quote (1 2 3)) env) ; => (1 2 3)

This is another reason Lisp is such a nice playground for interpreters. The boundary between code and data is visible and teachable.

User-defined functions and closures

Functions are where the interpreter starts to feel alive. A user-defined function needs three things:

• The parameter list
• The function body
• The environment where the function was created

That last part is what makes a closure. It allows the function to remember surrounding bindings even after it is called somewhere else.

(defstruct closure
  params
  body
  env)

(defun eval-lambda (args environment)
  (destructuring-bind (params body) args
    (make-closure :params params
                  :body body
                  :env environment)))

Next, we need function application. Some procedures will be host-language functions like + and *. Others will be closures created by lambda.

(defun tiny-apply (fn arg-values)
  (cond
    ((functionp fn)
     (apply fn arg-values))

    ((closure-p fn)
     (let* ((params (closure-params fn))
            (body (closure-body fn))
            (saved-env (closure-env fn))
            (bindings (mapcar #'cons params arg-values))
            (call-env (env-extend saved-env bindings)))
       (tiny-eval body call-env)))

    (t
     (error "Cannot apply: ~a" fn))))

(defun eval-application (expr environment)
  (let* ((fn (tiny-eval (car expr) environment))
         (arg-values (mapcar (lambda (arg)
                               (tiny-eval arg environment))
                             (cdr expr))))
    (tiny-apply fn arg-values)))

Notice how closures use the environment from the moment they were created, not the one from the call site. That is lexical scoping in action.

Example: a function that remembers context

(define make-adder
  (lambda (n)
    (lambda (x)
      (+ x n))))

When make-adder returns a function, that inner function still remembers n. That is the closure capturing its defining environment.

Adding built-in functions to the root environment

Before the interpreter can do anything interesting, the root environment needs a few primitives. These can be ordinary Common Lisp functions stored as values.

(defun install-builtins (environment)
  (env-define environment '+ #'+)
  (env-define environment '- #'-)
  (env-define environment '* #'* )
  (env-define environment '/ #'/)
  (env-define environment '= #'=)
  (env-define environment '< #'<)
  (env-define environment '> #'>)
  environment)

(defparameter *global-env*
  (install-builtins (make-root-env)))

With that done, your tiny language can immediately evaluate expressions like these:

(tiny-eval '(+ 1 2 3) *global-env*)        ; => 6
(tiny-eval '(define radius 10) *global-env*) ; => 10
(tiny-eval '(* radius 2) *global-env*)     ; => 20
(tiny-eval '(if (> radius 5) 99 0) *global-env*) ; => 99

Wrap it in a tiny REPL

Once you have a reader and evaluator, the final step is the classic REPL: Read, Eval, Print, Loop. Even a tiny one makes the project feel dramatically more complete.

(defun repl ()
  (format t "Tiny Lisp REPL. Type :quit to exit.~%")
  (loop
    (format t "tiny> ")
    (finish-output)
    (let ((input (read-line)))
      (when (string= input ":quit")
        (return))
      (handler-case
          (let* ((expr (read-expr input))
                 (result (tiny-eval expr *global-env*)))
            (format t "~s~%" result))
        (error (e)
          (format t "Error: ~a~%" e))))))

That little loop is enough to let you experiment, test ideas, and watch the interpreter grow in real time. It also shows why Lisp culture is so tied to interactive development. The feedback cycle is incredibly tight.

The tiny interpreter as one mental model

By now, the whole architecture should fit in your head:

• The reader turns text into Lisp data.
• The environment maps names to values.
• The evaluator recursively interprets expressions.
• Special forms define syntax with custom rules.
• Closures carry both code and remembered scope.

That is already enough to explain a surprising amount of language theory. Many advanced topics are just refinements of these same pieces.

Where to go next after the tiny version works

Once your interpreter is running, the temptation is to add everything. Resist that for a moment and add features in a way that teaches you something each time.