1. Evaluate the subexpressions of the combination.

2. Apply the procedure that is the value of the leftmost subexpression (the operator) to the arguments that are the values of the other subexpressions (the operands).

Even this simple rule illustrates some important points about
processes in general. First, observe that the first step dictates
that in order to accomplish the evaluation process for a combination
we must first perform the evaluation process on each element of the
combination. Thus, the evaluation rule is recursion *
recursive* in nature; that is, it includes, as one of its steps,
the need to invoke the rule itself. ^{
10}

Notice how succinctly the idea of recursion can be used to express what, in the case of a deeply nested combination, would otherwise be viewed as a rather complicated process. For example, evaluating

((+ 2 ( 4 6)) (+ 3 5 7))

requires that the evaluation rule be applied to four different combinations. We can obtain a picture of this process by the combination in the form of a tree, as shown in figure 1.1. Each combination is represented by a node with branches corresponding to the operator and the operands of the combination stemming from it. The terminal nodes (that is, nodes with no branches stemming from them) represent either operators or numbers.

** Figure 1.1** Tree representation, showing the value of each
subcombination.

Viewing evaluation in terms of the tree, we can imagine that the
values of the operands percolate upward, starting from the terminal
nodes and then combining at higher and higher levels. In general, we
shall see that recursion is a very powerful technique for dealing with
hierarchical, treelike objects. In fact, the "percolate values
upward" form of the evaluation rule is an example of a general kind of
process known as * tree accumulation*.

Next, observe that the repeated application of the first step brings us to the point where we need to evaluate, not combinations, but primitive expressions such as numerals, built-in operators, or other names. We take care of the primitive cases by stipulating that

We may regard the second rule as a special case of the third one by
stipulating that symbols such as ` +` and ` *` are also
included in the global environment, and are associated with the
sequences of machine instructions that are their "values." The key
point to notice is the role of the environment in determining the
meaning of the symbols in expressions. In an interactive language
such as Lisp, it is meaningless to speak of the value of an expression
such as ` (+ x 1)` without specifying any information about the
environment that would provide a meaning for the symbol ` x`
(or even for the symbol ` +`). As we shall see in chapter 3,
the general notion of the environment as providing a context in which
evaluation takes place will play an important role in our
understanding of program execution.

Notice that the evaluation rule given above does not handle
definitions. For instance, evaluating ` (define x 3)` does not
apply ` define` to two arguments, one of which is the value of
the symbol ` x` and the other of which is 3, since the purpose
of the ` define` is precisely to associate ` x` with a
value. (That is, ` (define x 3)` is not a combination.)

Such exceptions to the general evaluation rule are called * special
forms*. ` Define` is the only example of a special form
that we have seen so far, but we will meet others shortly. Each
special form has its own evaluation rule. The various kinds of
expressions (each with its associated evaluation rule) constitute the
syntax of the programming language. In comparison with most other
programming languages, Lisp has a very simple syntax; that is, the
evaluation rule for expressions can be described by a simple general
rule together with specialized rules for a small number of special
forms. ^{11}