The heart of the Lisp interpreter is the "read-eval-print" loop. That is, the interpreter does the following three jobs over and over:

This loop can be written in Lisp itself very simply:

(loop (print (eval (read)))

Of course, this doesn't take into account error handling, multiple values, and so on, but much of what Lisp does, including some things that seem unintuitive, can be understood by reasoning about the above three step process.

The Lisp Reader

The input to the Lisp reader is a sequence of characters. The output is a Lisp expression. The job of the reader is to convert objects in character world to objects in expression world.

In character world, there are no pointers, no lists, no symbols, just characters like A, b, `, and (. That is, (A B (C D) E) is not a list, it is a sequence of parentheses, spaces, and letters. "abc" is not a string, it is a sequence of letters.

In expression world, there are no parentheses, no spaces, no quote marks, just atoms and lists. That is, (A B (C D) E) has no parentheses or spaces. It is a list of three atoms and a list. "abc" has no quote marks. It is a string with three characters.

The Common Lisp reader is quite complex (Steele has a full description), but it works roughly like this:

The Lisp Evaluator

The Lisp evaluator takes an expression and returns an expression. The expression returned is called the value of the expression evaluated. [I'll ignore expressions that return multiple values here.]

The rules for evaluation are surprisingly simple. Graphically, it looks like this:

First, there are two rules for atoms:

There are three rules for lists that start with a symbol. If they don't work, there's an error. The rules are:

There is one other case for lists, but it appears rarely in modern code:

Anything that can be done with a lambda can also be done with either let or destructuring-bind.

The Lisp Printer

The input to the Lisp printer is a Lisp expression. The output is a sequence of characters. The job of the printer is to convert objects in expression world to objects in character world.

The printer's rules are pretty simple. They all involve taking an expression and printing a sequence of characters:

There are also rules for printing structures, special characters, and so on.

The purpose of the above rules is to make the following as true as possible:

(equal exp (read-from-string (write-to-string exp)))

Often, however, that is not what we want. For example, we probably want the string "Pick an option:" to appear on the screen as

Pick an option:


"Pick an option:"

The latter is correct in so far as, if Lisp read it, it would see a string, but we want people to read this message, not Lisp.

Use functions like write-string, princ, and the ~A format command to print things "for people" rather than for Lisp. However, don't use these functions for printing debugging information. The information these functions hide for readability may be exactly what you need for debugging.

Faculty: Chris Riesbeck
Time: MWF: 4:00pm - 4:50pm
Location: Tech LR 2


Important Links