Structure and Interpretation of Computer Programs (16 page)

Exercise 1.39.
  
A continued fraction representation of the tangent function was
published in 1770 by the German mathematician J.H. Lambert:

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
.

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
²
. Applying
this resulting procedure to 10 returns the average of 10 and 100, or
55:
⁵⁹

((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
²
, so we can immediately
generalize our square-root procedure to one that extracts
cube
roots:
⁶⁰

(define (cube-root x)
  (fixed-point (average-damp (lambda (y) (/ x (square y))))
               1.0))

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
D
g
(
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
.
⁶¹
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.
⁶²

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
³
is the function
x
⟼ 3
x
²
. In general, if
g
is a
function and
d
x
is a small number, then the derivative
D
g
of
g
is
the function whose value at any number
x
is given (in the limit of
small
d
x
) by

Thus, we can express the idea of derivative (taking
d
x
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
³
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
²
-
x
starting with
an initial guess of 1.
⁶³
This provides yet another form of the square-root
procedure:

(define (sqrt x)
  (newtons-method (lambda (y) (- (square y) x))
                  1.0))

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

As programmers, we should be alert to opportunities to identify the
underlying abstractions in our programs and to build upon them and
generalize them to create more powerful abstractions. This is not to
say that one should always write programs in the most abstract way
possible; expert programmers know how to choose the level of
abstraction appropriate to their task. But it is important to be able
to think in terms of these abstractions, so that we can be ready to
apply them in new contexts. The significance of higher-order
procedures is that they enable us to represent these abstractions
explicitly as elements in our programming language, so that they can
be handled just like other computational elements.

In general, programming languages impose restrictions on the ways in
which computational elements can be manipulated. Elements with the
fewest restrictions are said to have
first-class
status. Some
of the “rights and privileges” of first-class elements are:
⁶⁴

• They may be named by variables.
  
• They may be passed as arguments to procedures.
  
• They may be returned as the results of procedures.
  
• They may be included in data structures.
  ⁶⁵
  

Lisp, unlike other common programming languages, awards procedures
full first-class status. This poses challenges for efficient
implementation, but the resulting gain in expressive power is
enormous.
⁶⁶

Exercise 1.40.
  Define a procedure
cubic
that can be used together with the
newtons-method
procedure in expressions of the form

(newtons-method (cubic a b c) 1)