Structure and Interpretation of Computer Programs

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 

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

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

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

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

---

the values of numerals are the numbers that they name,

the values of built-in operators are the machine instruction sequences that carry out the

corresponding operations, and

the values of other names are the objects associated with those names in the environment.

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

1.1.4  Compound Procedures

We have identified in Lisp some of the elements that must appear in any powerful programming 

language:

Numbers and arithmetic operations are primitive data and procedures.

Nesting of combinations provides a means of combining operations.

Definitions that associate names with values provide a limited means of abstraction.

Now we will learn about procedure definitions, a much more powerful abstraction technique by which

a compound operation can be given a name and then referred to as a unit.

We begin by examining how to express the idea of ‘‘squaring.’’ We might say, ‘‘To square something,

multiply it by itself.’’ This is expressed in our language as 

(define (square x) (* x x))

We can understand this in the following way:

(define (square  x)        (*         x     x))

                                                 

 To      square something, multiply   it by itself.

---

We have here a compound procedure, which has been given the name 

square

. The procedure

represents the operation of multiplying something by itself. The thing to be multiplied is given a local

name, 

x

, which plays the same role that a pronoun plays in natural language. Evaluating the definition

creates this compound procedure and associates it with the name 

square

.

12

The general form of a procedure definition is

(define (<name> <formal parameters>) <body>)

The <name> is a symbol to be associated with the procedure definition in the environment.

13

 The 

<formal parameters> are the names used within the body of the procedure to refer to the

corresponding arguments of the procedure. The <body> is an expression that will yield the value of the

procedure application when the formal parameters are replaced by the actual arguments to which the

procedure is applied.

14

 The <name> and the <formal parameters> are grouped within parentheses,

just as they would be in an actual call to the procedure being defined.

Having defined 

square

, we can now use it:

(square 21)

441

(square (+ 2 5))

49

(square (square 3))

81

We can also use 

square

 as a building block in defining other procedures. For example, x

2

 + y

2

 can

be expressed as

(+ (square x) (square y))

We can easily define a procedure 

sum-of-squares

 that, given any two numbers as arguments,

produces the sum of their squares:

(define (sum-of-squares x y)

  (+ (square x) (square y)))

(sum-of-squares 3 4)

25

Now we can use 

sum-of-squares

 as a building block in constructing further procedures:

(define (f a)

  (sum-of-squares (+ a 1) (* a 2)))

(f 5)

136

Compound procedures are used in exactly the same way as primitive procedures. Indeed, one could

not tell by looking at the definition of 

sum-of-squares

 given above whether 

square

 was built

into the interpreter, like 

+

 and 

*

, or defined as a compound procedure.

---