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.

The Interpreter

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.

[./img/repl.png]

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 called read, eval and print.) At the beginning of each cycle through the loop the interpreter waits for the user to input an expression. Once a user enters some text — either by typing it and pressing the Return key or by remotely evaluating a block of text in an Emacs buffer — the interpreter processes the input by invoking the three steps of the read-eval-print loop in successive order. We now examine each of these steps in more detail.

Read

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.

Eval

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.

Print

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.

Lisp Evaluation

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 differently:

(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 symbol pi would clearly be standing for a particular numerical value: 3.141592653589793.

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 symbol pi was defined to represent that value. The evaluation of the symbol 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 the sin function.

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.

Blocking Evaluation

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:

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.