Structure and Interpretation of Computer Programs

What happens if we (perversely) ask the interpreter to evaluate the combination 

(f f)

? Explain. 

1.3.3  Procedures as General Methods

We introduced compound procedures in section 1.1.4 as a mechanism for abstracting patterns of

numerical operations so as to make them independent of the particular numbers involved. With

higher-order procedures, such as the 

integral

 procedure of section 1.3.1, we began to see a more

powerful kind of abstraction: procedures used to express general methods of computation, independent

of the particular functions involved. In this section we discuss two more elaborate examples -- general

methods for finding zeros and fixed points of functions -- and show how these methods can be

expressed directly as procedures.

Finding roots of equations by the half-interval method

The half-interval method is a simple but powerful technique for finding roots of an equation f(x) = 0,

where f is a continuous function. The idea is that, if we are given points a and b such that f(a) < 0 < 

f(b), then f must have at least one zero between a and b. To locate a zero, let x be the average of a and 

b and compute f(x). If f(x) > 0, then f must have a zero between a and x. If f(x) < 0, then f must have a

zero between x and b. Continuing in this way, we can identify smaller and smaller intervals on which f

must have a zero. When we reach a point where the interval is small enough, the process stops. Since

the interval of uncertainty is reduced by half at each step of the process, the number of steps required

grows as   (

log

( L/T)), where L is the length of the original interval and T is the error tolerance (that

is, the size of the interval we will consider ‘‘small enough’’). Here is a procedure that implements this 

strategy:

(define (search f neg-point pos-point)

  (let ((midpoint (average neg-point pos-point)))

    (if (close-enough? neg-point pos-point)

        midpoint

        (let ((test-value (f midpoint)))

          (cond ((positive? test-value)

                 (search f neg-point midpoint))

                ((negative? test-value)

                 (search f midpoint pos-point))

                (else midpoint))))))

We assume that we are initially given the function f together with points at which its values are

negative and positive. We first compute the midpoint of the two given points. Next we check to see if

the given interval is small enough, and if so we simply return the midpoint as our answer. Otherwise,

we compute as a test value the value of f at the midpoint. If the test value is positive, then we continue

the process with a new interval running from the original negative point to the midpoint. If the test

value is negative, we continue with the interval from the midpoint to the positive point. Finally, there

is the possibility that the test value is 0, in which case the midpoint is itself the root we are searching 

for.

To test whether the endpoints are ‘‘close enough’’ we can use a procedure similar to the one used in 

section 1.1.7 for computing square roots:

55

(define (close-enough? x y)

  (< (abs (- x y)) 0.001))

---

Search

 is awkward to use directly, because we can accidentally give it points at which f’s values do

not have the required sign, in which case we get a wrong answer. Instead we will use 

search

 via the

following procedure, which checks to see which of the endpoints has a negative function value and

which has a positive value, and calls the 

search

 procedure accordingly. If the function has the same

sign on the two given points, the half-interval method cannot be used, in which case the procedure

signals an error.

56

(define (half-interval-method f a b)

  (let ((a-value (f a))

        (b-value (f b)))

    (cond ((and (negative? a-value) (positive? b-value))

           (search f a b))

          ((and (negative? b-value) (positive? a-value))

           (search f b a))

          (else

           (error "Values are not of opposite sign" a b)))))

The following example uses the half-interval method to approximate   as the root between 2 and 4 of 

sin

 x = 0:

(half-interval-method sin 2.0 4.0)

3.14111328125

Here is another example, using the half-interval method to search for a root of the equation x

3

 - 2x - 3

= 0 between 1 and 2:

(half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3))

                      1.0

                      2.0)

1.89306640625

Finding fixed points of functions

A number x is called a fixed point of a function f if x satisfies the equation f(x) = x. For some functions 

f we can locate a fixed point by beginning with an initial guess and applying f repeatedly,

until the value does not change very much. Using this idea, we can devise a procedure 

fixed-point

 that takes as inputs a function and an initial guess and produces an approximation to a

fixed point of the function. We apply the function repeatedly until we find two successive values

whose difference is less than some prescribed tolerance:

(define tolerance 0.00001)

(define (fixed-point f first-guess)

  (define (close-enough? v1 v2)

    (< (abs (- v1 v2)) tolerance))

  (define (try guess)

    (let ((next (f guess)))

      (if (close-enough? guess next)

          next

          (try next))))

---