Structure and Interpretation of Computer Programs

where x is in radians. Define a procedure 

(tan-cf x k)

 that computes an approximation to the

tangent function based on Lambert’s formula. 

K

 specifies the number of terms to compute, as in 

exercise 1.37. 

1.3.4  Procedures as Returned Values

The above examples demonstrate how the ability to pass procedures as arguments significantly

enhances the expressive power of our programming language. We can achieve even more expressive

power by creating procedures whose returned values are themselves procedures.

We can illustrate this idea by looking again at the fixed-point example described at the end of 

section 1.3.3. We formulated a new version of the square-root procedure as a fixed-point search,

starting with the observation that   x is a fixed-point of the function y   x/y. Then we used average

damping to make the approximations converge. Average damping is a useful general technique in

itself. Namely, given a function f, we consider the function whose value at x is equal to the average of 

x and f(x).

We can express the idea of average damping by means of the following procedure:

(define (average-damp f)

  (lambda (x) (average x (f x))))

Average-damp

 is a procedure that takes as its argument a procedure 

f

 and returns as its value a

procedure (produced by the 

lambda

) that, when applied to a number 

x

, produces the average of 

x

 and 

(f x)

. For example, applying 

average-damp

 to the 

square

 procedure produces a procedure

whose value at some number x is the average of x and x

2

. Applying this resulting procedure to 10

returns the average of 10 and 100, or 55:

59

((average-damp square) 10)

55

Using 

average-damp

, we can reformulate the square-root procedure as follows:

(define (sqrt x)

  (fixed-point (average-damp (lambda (y) (/ x y)))

               1.0))

Notice how this formulation makes explicit the three ideas in the method: fixed-point search, average

damping, and the function y   x/y. It is instructive to compare this formulation of the square-root

method with the original version given in section 1.1.7. Bear in mind that these procedures express the

same process, and notice how much clearer the idea becomes when we express the process in terms of

these abstractions. In general, there are many ways to formulate a process as a procedure. Experienced

programmers know how to choose procedural formulations that are particularly perspicuous, and

where useful elements of the process are exposed as separate entities that can be reused in other

applications. As a simple example of reuse, notice that the cube root of x is a fixed point of the

function y   x/y

2

, so we can immediately generalize our square-root procedure to one that extracts 

---

cube roots:

60

(define (cube-root x)

  (fixed-point (average-damp (lambda (y) (/ x (square y))))

               1.0))

Newton’s method

When we first introduced the square-root procedure, in section 1.1.7, we mentioned that this was a

special case of Newton’s method. If x   g(x) is a differentiable function, then a solution of the

equation g(x) = 0 is a fixed point of the function x   f(x) where 

and Dg(x) is the derivative of g evaluated at x. Newton’s method is the use of the fixed-point method

we saw above to approximate a solution of the equation by finding a fixed point of the function f.

61

For many functions g and for sufficiently good initial guesses for x, Newton’s method converges very

rapidly to a solution of g(x) = 0.

62

In order to implement Newton’s method as a procedure, we must first express the idea of derivative.

Note that ‘‘derivative,’’ like average damping, is something that transforms a function into another

function. For instance, the derivative of the function x   x

3

 is the function x   3x

2

. In general, if g is

a function and dx is a small number, then the derivative Dg of g is the function whose value at any

number x is given (in the limit of small dx) by 

Thus, we can express the idea of derivative (taking dx to be, say, 0.00001) as the procedure

(define (deriv g)

  (lambda (x)

    (/ (- (g (+ x dx)) (g x))

       dx)))

along with the definition

(define dx 0.00001)

Like 

average-damp

, 

deriv

 is a procedure that takes a procedure as argument and returns a

procedure as value. For example, to approximate the derivative of x   x

3

 at 5 (whose exact value is

75) we can evaluate

(define (cube x) (* x x x))

((deriv cube) 5)

75.00014999664018

With the aid of 

deriv

, we can express Newton’s method as a fixed-point process:

---

(define (newton-transform g)

  (lambda (x)

    (- x (/ (g x) ((deriv g) x)))))

(define (newtons-method g guess)

  (fixed-point (newton-transform g) guess))

The 

newton-transform

 procedure expresses the formula at the beginning of this section, and 

newtons-method

 is readily defined in terms of this. It takes as arguments a procedure that

computes the function for which we want to find a zero, together with an initial guess. For instance, to

find the square root of x, we can use Newton’s method to find a zero of the function y   y

2

 - x starting

with an initial guess of 1.

63

 This provides yet another form of the square-root procedure:

(define (sqrt x)

  (newtons-method (lambda (y) (- (square y) x))

                  1.0))

Abstractions and first-class procedures

We’ve seen two ways to express the square-root computation as an instance of a more general method,

once as a fixed-point search and once using Newton’s method. Since Newton’s method was itself

expressed as a fixed-point process, we actually saw two ways to compute square roots as fixed points.

Each method begins with a function and finds a fixed point of some transformation of the function. We

can express this general idea itself as a procedure:

(define (fixed-point-of-transform g transform guess)

  (fixed-point (transform g) guess))

This very general procedure takes as its arguments a procedure 

g

 that computes some function, a

procedure that transforms 

g

, and an initial guess. The returned result is a fixed point of the

transformed function.

Using this abstraction, we can recast the first square-root computation from this section (where we

look for a fixed point of the average-damped version of y   x/y) as an instance of this general method:

(define (sqrt x)

  (fixed-point-of-transform (lambda (y) (/ x y))

                            average-damp

                            1.0))

Similarly, we can express the second square-root computation from this section (an instance of

Newton’s method that finds a fixed point of the Newton transform of y   y

2

 - x) as

(define (sqrt x)

  (fixed-point-of-transform (lambda (y) (- (square y) x))

                            newton-transform

                            1.0))

We began section 1.3 with the observation that compound procedures are a crucial abstraction

mechanism, because they permit us to express general methods of computing as explicit elements in

our programming language. Now we’ve seen how higher-order procedures permit us to manipulate

these general methods to create further abstractions.

---