Structure and Interpretation of Computer Programs

Figure 1.2:  Procedural decomposition of the 

sqrt

 program.

Figure 1.2:  Procedural decomposition of the 

sqrt

 program.

The importance of this decomposition strategy is not simply that one is dividing the program into

parts. After all, we could take any large program and divide it into parts -- the first ten lines, the next

ten lines, the next ten lines, and so on. Rather, it is crucial that each procedure accomplishes an

identifiable task that can be used as a module in defining other procedures. For example, when we

define the 

good-enough?

 procedure in terms of 

square

, we are able to regard the 

square

procedure as a ‘‘black box.’’ We are not at that moment concerned with how the procedure computes

its result, only with the fact that it computes the square. The details of how the square is computed can

be suppressed, to be considered at a later time. Indeed, as far as the 

good-enough?

 procedure is

concerned, 

square

 is not quite a procedure but rather an abstraction of a procedure, a so-called 

procedural abstraction. At this level of abstraction, any procedure that computes the square is equally 

good.

Thus, considering only the values they return, the following two procedures for squaring a number

should be indistinguishable. Each takes a numerical argument and produces the square of that number

as the value.

25

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

(define (square x) 

  (exp (double (log x))))

(define (double x) (+ x x))

So a procedure definition should be able to suppress detail. The users of the procedure may not have

written the procedure themselves, but may have obtained it from another programmer as a black box.

A user should not need to know how the procedure is implemented in order to use it.

Local names

One detail of a procedure’s implementation that should not matter to the user of the procedure is the

implementer’s choice of names for the procedure’s formal parameters. Thus, the following procedures

should not be distinguishable:

---

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

(define (square y) (* y y))

This principle -- that the meaning of a procedure should be independent of the parameter names used

by its author -- seems on the surface to be self-evident, but its consequences are profound. The

simplest consequence is that the parameter names of a procedure must be local to the body of the

procedure. For example, we used 

square

 in the definition of 

good-enough?

 in our square-root 

procedure:

(define (good-enough? guess x)

  (< (abs (- (square guess) x)) 0.001))

The intention of the author of 

good-enough?

 is to determine if the square of the first argument is

within a given tolerance of the second argument. We see that the author of 

good-enough?

 used the

name 

guess

 to refer to the first argument and 

x

 to refer to the second argument. The argument of 

square

 is 

guess

. If the author of 

square

 used 

x

 (as above) to refer to that argument, we see that

the 

x

 in 

good-enough?

 must be a different 

x

 than the one in 

square

. Running the procedure 

square

 must not affect the value of 

x

 that is used by 

good-enough?

, because that value of 

x

 may

be needed by 

good-enough?

 after 

square

 is done computing.

If the parameters were not local to the bodies of their respective procedures, then the parameter 

x

 in 

square

 could be confused with the parameter 

x

 in 

good-enough?

, and the behavior of 

good-enough?

 would depend upon which version of 

square

 we used. Thus, 

square

 would not

be the black box we desired.

A formal parameter of a procedure has a very special role in the procedure definition, in that it doesn’t

matter what name the formal parameter has. Such a name is called a bound variable, and we say that

the procedure definition binds its formal parameters. The meaning of a procedure definition is

unchanged if a bound variable is consistently renamed throughout the definition.

26

 If a variable is not

bound, we say that it is free. The set of expressions for which a binding defines a name is called the 

scope of that name. In a procedure definition, the bound variables declared as the formal parameters of

the procedure have the body of the procedure as their scope.

In the definition of 

good-enough?

 above, 

guess

 and 

x

 are bound variables but 

<

, 

-

, 

abs

, and 

square

 are free. The meaning of 

good-enough?

 should be independent of the names we choose

for 

guess

 and 

x

 so long as they are distinct and different from 

<

, 

-

, 

abs

, and 

square

. (If we

renamed 

guess

 to 

abs

 we would have introduced a bug by capturing the variable 

abs

. It would

have changed from free to bound.) The meaning of 

good-enough?

 is not independent of the names

of its free variables, however. It surely depends upon the fact (external to this definition) that the

symbol 

abs

 names a procedure for computing the absolute value of a number. 

Good-enough?

 will

compute a different function if we substitute 

cos

 for 

abs

 in its definition.

Internal definitions and block structure

We have one kind of name isolation available to us so far: The formal parameters of a procedure are

local to the body of the procedure. The square-root program illustrates another way in which we would

like to control the use of names. The existing program consists of separate procedures:

(define (sqrt x)

  (sqrt-iter 1.0 x))

(define (sqrt-iter guess x)

  (if (good-enough? guess x)

---