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 _{} is
a fixed-point of the function _{}.
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:

Notice how this formulation makes explicit the three ideas in the method: fixed-point search, average damping, and the function(define (sqrt x) (fixed-point (average-damp (lambda (y) (/ x y))) 1.0))

(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 *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

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* 3*x*^{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

along with the definition(define (deriv g) (lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))

`
(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:

The(define (newton-transform g) (lambda (x) (- x (/ (g x) ((deriv g) x))))) (define (newtons-method g guess) (fixed-point (newton-transform g) guess))

(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:

This very general procedure takes as its arguments a procedure(define (fixed-point-of-transform g transform guess) (fixed-point (transform g) guess))

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 _{}) as an
instance of this general method:

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(define (sqrt x) (fixed-point-of-transform (lambda (y) (/ x y)) average-damp 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.(define (sqrt x) (fixed-point-of-transform (lambda (y) (- (square y) x)) newton-transform 1.0))

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 elements in language
* first-class* status. Some of the "rights and privileges" of
first-class elements are: ^{64}

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. ^{66}

**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)`

to approximate the zeros of the cubic *x ^{3} +
ax^{2} + bx + c*.

**Exercise 1.41**

Define a procedure `double` that takes a procedure of one
argument as argument and returns a procedure that applies to the
original procedure `twice`. For example, if `inc` is a
procedure that adds 1 to its argument, then `(double inc)`
should be a procedure that adds 2. What value is returned by

`
(((double (double double)) inc) 5)`

**Exercise 1.42**

Let *f* and *g* be two one-argument functions. The
*composition f* after *g* is defined to be the function
*x* *f (g (x) )*. Define a procedure
`compose` that implements composition. For example, if
`inc` is a procedure that adds 1 to its argument,

`((compose square inc) 6)
49`

**Exercise 1.43**

If *f* is a numerical function and *n* is a positive
integer, then we can form the *n*th repeated application of
*f*, which is defined to be the function whose value at
*x* is *f ( f ( ... ( f (x) ) ...) )*. For example, if
*f* is the function *x x + 1*, then
the *n*th repeated application of *f* is the function
*x x + n*. If *f* is the operation
of squaring a number, then the *n*th repeated application of
*f* is the function that raises its argument to the
2 ^{n}th power. Write a procedure that takes as inputs
a procedure that computes *f* and a positive integer *n*
and returns the procedure that computes the *n*th repeated
application of *f*. Your procedure should be able to be used as
follows:

`((repeated square 2) 5)`

*625*

Hint: You may find it convenient to use `compose` from exercise
1.42.

**Exercise 1.44**

The idea of *smoothing* a function is an important concept in
signal processing. If *f* is a function and *dx* is some
small number, then the smoothed version of *f* is the function
whose value at a point *x* is the average of * f (x -
dx)*, *f (x)*, and *f (x + dx)*. Write a procedure
`smooth` that takes as input a procedure that computes
*f* and returns a procedure that computes the smoothed
*f*. It is sometimes valuable to repeatedly smooth a function
(that is, smooth the smoothed function, and so on) to obtain the
*n-fold smoothed function.* Show how to generate the
*n*-fold smoothed function of any given function using
`smooth` and `repeated` from exercise 1.43.

**Exercise 1.45**

We saw in section 1.3.3 that attempting to compute square roots by
naively finding a fixed point of *y*
*x / y* does not converge, and that this can be fixed by average
damping. The same method works for finding cube roots as fixed points
of the average-damped *y*
*x / y ^{2}*. Unfortunately, the process does not work for
fourth roots a single average damp is not enough to make a
fixed-point search for

**Exercise 1.46**

Several of the numerical methods described in this chapter are
instances of an extremely general computational startegy known as
*iterative improvement*. Iterative imporvement says that, to
compute something, we start with an initial guess for the answer, test
if the guess is good enough, and otherwise improve the guess and
continue the process using the improved guess as the new guess. Write
a procedure `iterative-improve that takes two procedures as
arguments: a method for telling whether a guess is good enough and a
method for improving a guess. Iterative-improve should return
as its value a procedure that takes a guess as argument and keeps
improving the guess until it is good enough. Rewrite the sqrt
procedure of section 1.17 and the fixed-point procedure of
section 1.3.3 in terms of iterative-improve.
`

`
`

`
`

`
`

`
`

`
`

` `