5 Lisp Evaluation
In this chapter we examine the process by which Lisp evaluates, or interprets, Lisp expressions in order to produce results. Since Lisp programs are built out of Lisp expressions, understanding this evaluation process is key to understanding Lisp notation and the behavior of the music programs we will develop over the course of this book. In a very real sense the process of evaluation defines how Lisp operates as a programming language.
In Chapter 4 we learned how to interact with Lisp by typing input expressions into the Listener window and then observing the results that Lisp printed back to the window. The Listener window supports this interaction using a program called the interpreter, or read-eval-print loop (Figure 5-1).
Figure 5-1. The Lisp interpreter continuously processes input in its read-eval-print loop.
The terms read, eval and print define three
different stages in the processing of Lisp input expressions. (These
stages are literally implemented by three separate Lisp functions
In the read step the text string that the user inputs into the Listener window is first parsed from the window and then assembled into a true Lisp expression. If a valid Lisp expression results then the interpreter goes on to the next step (eval) in the process. If a Lisp object cannot be parsed from the input then the interpreter signals an error and waits for the user to correct the problem.
During the eval step the interpreter determines the value, or result, of an input Lisp expression. This evaluation process lies at the very heart of the language. Unfortunately, the evaluation process is not actually visible in the Listener window — it happens “behind the scenes”, before any output is printed back for the user to see. This may make the effects of evaluation seem a bit mysterious to the novice Lisp composer. But the mechanism is simple to understand if the rules that govern its behavior are understood. These evaluation rules are covered in the next few sections of this chapter.
In the print step the interpreter displays the results of evaluation back to the Listener window. The print step is in some sense the “reverse” of the read step — the Lisp expression that results from the eval step is translated into a text string and then displayed on a new line in the window. Once this output has been printed the interpreter starts the read-eval-print loop all over again by displaying the input prompt and waiting for the user to enter the next command string.
The “goal” of Lisp is to determine the value of Lisp expressions. Evaluation is accomplished by applying a small number of “interpretation rules” to an input expression. The applicability of these rules is determined by the datatype of the input expression. This means that the easiest way to learn about the evaluation process is to observe its effects on the basic datatypes that were presented in Chapter 2.
The Evaluation of Numbers, Booleans and Strings
Numbers, booleans and strings are self-evaluating expressions. A self-evaluating expression means that the expression does not change as a result of evaluation. Common sense tells us that numbers and booleans must be self-evaluating because, if they were not, the laws of mathematics and logic would make no sense — zero, one, true and false must remain ever so! Strings are self-evaluating expressions because Lisp simply declares them to be so.
Note that — although self-evaluating expressions remain unchanged by the evaluation process — their “appearance” in the print step may be different than in the read step. This difference does not mean that the value has actually changed, but only that the print step has notated the value differently than how the user first entered it.
Interaction 5-1. Some self-evaluating expressions.
cm> 44100 44100 cm> #xFFFF 65535 cm> .500 0.5 cm> "Ondes Martenot" "Ondes Martenot" cm>
We can summarize our observations about self-evaluating expressions in a simple rule to remember:
- Lisp Evaluation Rule 1:
- A number, boolean or string evaluates to itself.
Symbol Evaluation and Variables
In Chapter 2 we learned that symbols can be treated
as words and grouped into lists to form symbolic expressions.
But here are two symbolic expressions that use the symbol
(pi is a greek letter) (* 2 pi)
The first expression treats the symbol
pi as the name of a Greek
letter. But the second expression appears to represent
an action: "multiply 2 and pi together." In this case the
pi would clearly be standing for a particular numerical
A symbol that stands for a value is called a variable. It is important to understand that a symbol and a variable are not exactly the same thing. A symbol names a variable. A symbol is created just by typing its name but a variable can only be created by defining it using special mechanisms provided by Lisp. Although Lisp symbols appear to be just words they are actually complex objects that possess a number of different properties. One of the properties of a symbol is it's print name, the text that you see printed on the screen. A symbol also has a value cell property. This value cell allows a value (any Lisp expression) to be associated with the symbol. This association is called a variable binding. It is only through the eval step that symbols can be treated as variables. When the eval step encounters a bound symbol its value is returned instead of the symbol. If the symbol is not bound before it is evaluated then Lisp will signal an “unbound variable” error. One of the interesting features of Lisp that distinguishes it from many other programming languages is the fact that a symbol's value cell can hold any Lisp value. Most programming languages constrain variables to hold only one particular type of data. But in Lisp it is the data itself that is typed, or classified, rather than the variable. This makes it simple to work with variables in Lisp because the composer does not have to “declare” a variable's type or insure that the variable is set to only one specific type of data.
Interaction 5-2. Symbols are evaluated as variables.
cm> pi 3.141592653589793 cm> messiaen > Error: Unbound variable: messiaen Aborted cm>
In Interaction 5-2 the result of evaluating pi produced a value because the
pi was defined to represent that value. The evaluation of
messiaen signaled an error because this symbol was not
defined to have a value before it was evaluated. We summarize symbols
used as variables in a second rule of evaluation:
- Lisp Evaluation Rule 2:
- A symbol evaluates to its variable value. Lisp signals an “unbound variable” error if the variable does not have a value.
Evaluation of Function Call Lists
A function call is the application of a Lisp program to input data. Function calls are notated as lists: the first element of the list is the function and the rest of the elements are called the arguments to the function. In the expression:
(* 2 pi)
the symbol * is the function and 2 pi are its two arguments. The evaluation of a function call requires that each argument to the function be evaluated before the function is actually called. This process can be demonstrated using the example above. Before the multiplication can occur the two arguments 2 and pi are first evaluated in left to right order to produce the values that are to be multiplied. The first argument 2 is a number and therefore evaluates according to our Rule 1 to produce the value 2. The second argument pi is a symbol and so it is evaluated as a variable, according to Rule 2. The application of the second rule results in the value 3.141592653589793. Since neither argument produced an error, their values are passed to the function *, which multiplies them together and produces the result 6.283185307179586 that is is then returned as the value of the function call.
Since each argument in a function call is evaluated before the
function is called, arguments may include variables and other function
calls. It is very common to see nested function calls in lisp
programming. A nested function call is an argument to a function that
is itself a function call. In the last input expression in Interaction 5-3
the function call (* 2 pi 1/4) is nested as the argument to
Interaction 5-3. Function call notation.
cm> (* 2 pi) 6.283185307179586 cm> (list 2 pi) (2 3.141592653589793) cm> (sin (* 2 pi 1/4)) 1.0 cm>
Each of the input lists in Interaction 5-3 are function calls. Recall that the first element in a function call is a function and the rest of the elements are arguments to the function. This means that in the expressions above the symbols *, list and sin are treated as functions because they are symbols in the first position of a list. The symbol pi is not a function because it is not the first element of a list. Lisp signals an error if the first element is not a function of if any argument cannot be evaluated. Arguments in a function call are evaluated in left to right order to produce input values to the function. The inputs are passed to the function and the result returned by the function becomes the value of the function call expression. We summarize function call lists in a third evaluation rule:
- Lisp Evaluation Rule 3:
- A Lisp list is evaluated as a function call. Lisp signals an “undefined function” error if the first element is not a function.
The previous two sections have described how the eval step processes symbols and lists. This brings up the obvious question: how can symbols be tokens or lists be data structures if the evaluator always treats them as programming variables and function calls? For example, how can pi ever be used as a word or a list used to represent a 12-tone row? The answer to both these questions is that the eval step provides a simple mechanism that allows us to selectively “turn off” the evaluation of any input expression such that the expression becomes data, with no special interpretation made by the eval step.
The Lisp Quote
The single quote character: ' is a very special prefix character that “defeats” evaluation, by forcing Lisp to accept the expression that appears just after the quote exactly as the user typed it. Another way of saying this is that the eval step evaluates a quoted expression by stripping off the quote and returning the (now unquoted) expression as the value. The quote character can be applied to any Lisp expression. In the case of numbers, booleans and strings the quote will have no effect since these are self-evaluating anyway. But a quote in front of a symbol causes Lisp to “see” just the symbol itself rather than any variable value it may have. A quote in front of a list of numbers allows that list to represent a grouping of data, for example, a twelve-tone row. A quote before a function call will cause it to become just a list of data rather than a function call.
Interaction 5-4. The effect of quote on evaluated expressions.
cm> '44100 44100 cm> '"Ondes Martenot" "Ondes Martenot" cm> pi 3.141592653589793 cm> 'pi pi cm> ''pi 'pi cm> '(0 2 5) (0 2 5) cm> (* 2 pi) 6.283185307179586 cm> '(* 2 pi) (* 2 pi) cm>
- Lisp Evaluation Rule 4:
- A quoted expression evaluates to the expression without the quote.
To quote or not to quote...
It is easy for a novice Lisp composer to become confused about when and when not to use quote in the Lisp Listener. Although no set of rules can cover all possible situations there are a few simple guidelines that should help make this determination less confusing:
- Numbers never need to be quoted.
- Booleans (true and false) never need to be quoted.
- Strings never need to be quoted.
- Symbols need to be quoted unless they have been defined as variables or they are keywords (symbols starting with the colon character)
- Lists need to be quoted unless they are function calls.
The Lisp backquote
The Lisp backquote character: ` is related to the quote character. But rather than block evaluation altogether, the backquote performs selective evaluation. Backquote is used primarily to specify lists in which some elements should be evaluated and others not. A backquoted list acts as a template in which elements in which each element remains constant unless it preceded by a comma, in which case it will be replaced by its evaluated value (Interaction 5-5).
Interaction 5-5. The effects of quote and backquote on lists.
cm> '(a b pi c) (a b pi c) cm> `(a b ,pi c) (a b 3.141592653589793 c) cm>
The first input expression in Interaction 5-5 is a quoted list and so Lisp returns the entire list exactly as it was typed as the evaluated result. The second input expression is a backquoted list that selectively evaluates the variable pi and replaces it with its evaluated result in the list. A backquoted list acts just like a quoted list except that expressions preceded by a comma “,” are explicitly evaluated. The backquote is particularly useful for notating lists that will contain many unevaluated tokens and a few expressions that must be evaluated. Since each unevaluated expression would otherwise have to be quoted in an evaluated list, the backquote can substantially reduce the size and complexity of a notated expression by eliminating the need for explicit quotes. The following two expressions are equivalent:
Interaction 5-6. Equivalent expressions using list and backquote
cm> (list 'a 'b pi 'c) (a b 3.141592653589793 c) cm> `(a b ,pi c) (a b 3.141592653589793 c) cm>
Chapter Source Code
The source code to all of the examples and interactions in this chapter can be found in the file eval.cm located in the same directory as the HTML file for this chapter. The source file can be edited in a text editor or evaluated inside the Common Music application.