The Lisp Interpreter

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

• read an input expression
• evaluate the expression
• print the results

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:

• If the reader sees a character with read-macro function, it calls that function, and returns whatever expression that function returns. For example, ' has a pre-defined read-macro function that basically says (list (quote quote) (read)). Thus, 'abc becomes (quote abc).
• If the reader sees a ", it collects characters until it sees another ", and creates a string object with the characters found between the string quotes. Thus, the 5 characters "abc" become the 3-character string with the characters a, b, and c.
• If the reader sees a digit (0 - 9), it collects the digits that follow, and creates the number those digits represent (base 10). Thus, the three characters 123 become the single number 123.
• If the reader sees an alphabetic character, it collects characters until it sees a space or parenthesis, and then gets the symbol (using Lisp's intern function) that has those characters (converted to upper case) as its name. Thus the three characters abc become the single unique symbol ABC.
• If the reader sees a left parenthesis, it reads more characters, turning them into expressions, using all these rules, until it sees a right parenthesis. Then it returns the list of expressions read. Thus, the 7 characters (A B C) become the 3 element list (A B C).

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:

• The value of a symbol is looked up in the current lexical environments. If none is found, symbol-value is called. If that fails, there's an error (unbound variable).
• The value of any other kind of atom is the atom itself.

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

• If the symbol names a special function, use the rules for evaluation stored with the special function.
• If the symbol has a macro function attached, apply the macro function to the rest of the list, and evaluate the result.
• If the symbol has a normal function attached, evaluate the other elements in the list, and apply the function to a list of the values returned. The value the function returns is the final value.

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

• If the list has the form ((lambda (vars) exps) args), then evaluate the arguments, and apply the lambda function to the list of results. The value the lambda returns is the final value.

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:

• If the expression is an string, print " then the characters in the string, then another ".
• If the expression is a symbol, print the characters in the symbol's name.
• If the expression is a number, print the digits representing that numbers (base 10).
• If the expression is a list, print a left parenthesis, then print each element in the list, with a space after each element but the last, then print a right parenthesis.

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:

not

"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.