Structure and Interpretation of Computer Programs

This only begs the question.

The contrast between function and procedure is a reflection of the general distinction between

describing properties of things and describing how to do things, or, as it is sometimes referred to, the

distinction between declarative knowledge and imperative knowledge. In mathematics we are usually

concerned with declarative (what is) descriptions, whereas in computer science we are usually

concerned with imperative (how to) descriptions.

20

How does one compute square roots? The most common way is to use Newton’s method of successive

approximations, which says that whenever we have a guess y for the value of the square root of a

number x, we can perform a simple manipulation to get a better guess (one closer to the actual square

root) by averaging y with x/y.

21

 For example, we can compute the square root of 2 as follows.

Suppose our initial guess is 1:

Guess 

Quotient 

Average

  

1 

(2/1) = 2 

((2 + 1)/2) = 1.5 

  

1.5 

(2/1.5) = 1.3333 

((1.3333 + 1.5)/2) = 1.4167 

  

1.4167 

(2/1.4167) = 1.4118 

((1.4167 + 1.4118)/2) = 1.4142 

  

1.4142 

...

...

Continuing this process, we obtain better and better approximations to the square root.

Now let’s formalize the process in terms of procedures. We start with a value for the radicand (the

number whose square root we are trying to compute) and a value for the guess. If the guess is good

enough for our purposes, we are done; if not, we must repeat the process with an improved guess. We

write this basic strategy as a procedure:

(define (sqrt-iter guess x)

  (if (good-enough? guess x)

      guess

      (sqrt-iter (improve guess x)

                 x)))

A guess is improved by averaging it with the quotient of the radicand and the old guess:

(define (improve guess x)

  (average guess (/ x guess)))

where

---

(define (average x y)

  (/ (+ x y) 2))

We also have to say what we mean by ‘‘good enough.’’ The following will do for illustration, but it is

not really a very good test. (See exercise 1.7.) The idea is to improve the answer until it is close

enough so that its square differs from the radicand by less than a predetermined tolerance (here 

0.001):

22

(define (good-enough? guess x)

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

Finally, we need a way to get started. For instance, we can always guess that the square root of any

number is 1:

23

(define (sqrt x)

  (sqrt-iter 1.0 x))

If we type these definitions to the interpreter, we can use 

sqrt

 just as we can use any procedure:

(sqrt 9)

3.00009155413138

(sqrt (+ 100 37))

11.704699917758145

(sqrt (+ (sqrt 2) (sqrt 3)))

1.7739279023207892

(square (sqrt 1000))

1000.000369924366

The 

sqrt

 program also illustrates that the simple procedural language we have introduced so far is

sufficient for writing any purely numerical program that one could write in, say, C or Pascal. This

might seem surprising, since we have not included in our language any iterative (looping) constructs

that direct the computer to do something over and over again. 

Sqrt-iter

, on the other hand,

demonstrates how iteration can be accomplished using no special construct other than the ordinary

ability to call a procedure.

24

 

Exercise 1.6.  Alyssa P. Hacker doesn’t see why 

if

 needs to be provided as a special form. ‘‘Why

can’t I just define it as an ordinary procedure in terms of 

cond

?’’ she asks. Alyssa’s friend Eva Lu

Ator claims this can indeed be done, and she defines a new version of 

if

:

(define (new-if predicate then-clause else-clause)

  (cond (predicate then-clause)

        (else else-clause)))

Eva demonstrates the program for Alyssa:

(new-if (= 2 3) 0 5)

5

(new-if (= 1 1) 0 5)

0

---

Delighted, Alyssa uses 

new-if

 to rewrite the square-root program:

(define (sqrt-iter guess x)

  (new-if (good-enough? guess x)

          guess

          (sqrt-iter (improve guess x)

                     x)))

What happens when Alyssa attempts to use this to compute square roots? Explain. 

Exercise 1.7.  The 

good-enough?

 test used in computing square roots will not be very effective for

finding the square roots of very small numbers. Also, in real computers, arithmetic operations are

almost always performed with limited precision. This makes our test inadequate for very large

numbers. Explain these statements, with examples showing how the test fails for small and large

numbers. An alternative strategy for implementing 

good-enough?

 is to watch how 

guess

 changes

from one iteration to the next and to stop when the change is a very small fraction of the guess. Design

a square-root procedure that uses this kind of end test. Does this work better for small and large

numbers? 

Exercise 1.8.  Newton’s method for cube roots is based on the fact that if y is an approximation to the

cube root of x, then a better approximation is given by the value 

Use this formula to implement a cube-root procedure analogous to the square-root procedure. (In 

section 1.3.4 we will see how to implement Newton’s method in general as an abstraction of these

square-root and cube-root procedures.) 

1.1.8  Procedures as Black-Box Abstractions

Sqrt

 is our first example of a process defined by a set of mutually defined procedures. Notice that the

definition of 

sqrt-iter

 is recursive; that is, the procedure is defined in terms of itself. The idea of

being able to define a procedure in terms of itself may be disturbing; it may seem unclear how such a

‘‘circular’’ definition could make sense at all, much less specify a well-defined process to be carried

out by a computer. This will be addressed more carefully in section 1.2. But first let’s consider some

other important points illustrated by the 

sqrt

 example.

Observe that the problem of computing square roots breaks up naturally into a number of

subproblems: how to tell whether a guess is good enough, how to improve a guess, and so on. Each of

these tasks is accomplished by a separate procedure. The entire 

sqrt

 program can be viewed as a

cluster of procedures (shown in figure 1.2) that mirrors the decomposition of the problem into 

subproblems.

---