The above examples demonstrate how the ability to pass procedures functions as arguments significantly enhances the expressive power of our programming language. We can achieve even more expressive power by creating procedures functions whose returned values are themselves procedures. functions.

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 function as a fixed-point search, starting with the observation that $\sqrt{x}$ is a fixed-point of the function $y\mapsto 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: function:

Original	Python
(define (average-damp f) (lambda (x) (average x (f x))))	def average_damp(f): return lambda x: average(x, f(x))

Average-damp is a procedure that The function average_damp takes as its argument a procedure function f and returns as its value a procedure function (produced by the lambda) (produced by the lambda expression) that, when applied to a number x, produces the average of x and (f x). f(x). For example, applying average-damp average_damp to the square procedure function produces a procedure function whose value at some number $x$ is the average of $x$ and $x^2$. Applying this resulting procedure function to 10 returns the average of 10 and 100, or 55:[1]

Original	Python
((average-damp square) 10) 55	print(average_damp(square)(10)) 55.0

Using average-damp, average_damp, we can reformulate the square-root procedure function as follows:

Original	Python
(define (sqrt x) (fixed-point (average-damp (lambda (y) (/ x y))) 1.0))	def sqrt(x): return fixed_point(average_damp(lambda y: x / y), 1)

Notice how this formulation makes explicit the three ideas in the method: fixed-point search, average damping, and the function $y\mapsto 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 functions 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. function. Experienced programmers know how to choose procedural process 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\mapsto x/y^2$, so we can immediately generalize our square-root procedure function to one that extracts cube roots:[2]

Original	Python
(define (cube-root x) (fixed-point (average-damp (lambda (y) (/ x (square y)))) 1.0))	def cube_root(x): return fixed_point(average_damp(lambda y: x / square(y)), 1)

Newton's method

When we first introduced the square-root procedure, function, in section 1.1.7, we mentioned that this was a special case of Newton's method. If $x\mapsto g(x)$ is a differentiable function, then a solution of the equation $g(x)=0$ is a fixed point of the function $x\mapsto f(x)$ where \[ \begin{array}{lll} f(x) & = & x - \dfrac{g(x)}{Dg(x)} \end{array} \] 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$.[3] 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$.[4]

In order to implement Newton's method as a procedure, function, 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\mapsto x^3$ is the function $x \mapsto 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 \[ \begin{array}{lll} Dg(x) & = & \dfrac {g(x+dx) - g(x)}{dx} \end{array} \] Thus, we can express the idea of derivative (taking $dx$ to be, say, 0.00001) as the procedure function

Original	Python
(define (deriv g) (lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))	def deriv(g): return lambda x: (g(x + dx) - g(x)) / dx

along with the definition definition

Original	Python
(define dx 0.00001)	dx = 0.00001

Like average-damp, average_damp, deriv is a procedure function that takes a procedure function as argument and returns a procedure function as value. For example, to approximate the derivative of $x \mapsto x^3$ at 5 (whose exact value is 75) we can evaluate

Original	Python
(define (cube x) (* x x x)) ((deriv cube) 5) 75.00014999664018	def cube(x): return x * x * x print(deriv(cube)(5)) 75.00014999664018

With the aid of deriv, we can express Newton's method as a fixed-point process:

Original	Python
(define (newton-transform g) (lambda (x) (- x (/ (g x) ((deriv g) x))))) (define (newtons-method g guess) (fixed-point (newton-transform g) guess))	def newton_transform(g): return lambda x: x - g(x) / deriv(g)(x) def newtons_method(g, guess): return fixed_point(newton_transform(g), guess)

The newton-transform newton_transform procedure function expresses the formula at the beginning of this section, and newtons-method newtons_method is readily defined in terms of this. It takes as arguments a procedure function 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\mapsto y^2-x$ starting with an initial guess of 1.[5] This provides yet another form of the square-root procedure: function:

Original	Python
(define (sqrt x) (newtons-method (lambda (y) (- (square y) x)) 1.0))	def sqrt(x): return newtons_method(lambda y: square(y) - x, 1)

Abstractions and first-class procedures functions

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

Original	Python
(define (fixed-point-of-transform g transform guess) (fixed-point (transform g) guess))	def fixed_point_of_transform(g, transform, guess): return fixed_point(transform(g), guess)

This very general procedure function takes as its arguments a procedure function g that computes some function, a procedure function 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 \mapsto x/y$) as an instance of this general method:

Original	Python
(define (sqrt x) (fixed-point-of-transform (lambda (y) (/ x y)) average-damp 1.0))	def sqrt(x): return fixed_point_of_transform(lambda y: x / y, average_damp, 1)

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\mapsto y^2-x$) as

Original	Python
(define (sqrt x) (fixed-point-of-transform (lambda (y) (- (square y) x)) newton-transform 1.0))	def sqrt(x): return fixed_point_of_transform(lambda y: square(y) - x, newton_transform, 1)

We began section 1.3 with the observation that compound procedures functions 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 functions 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 functions 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:[6]

• They may be named by variables. They may be referred to using names.
• They may be passed as arguments to procedures. functions.
• They may be returned as the results of procedures. functions.
• They may be included in data structures.[7]

Lisp, Python, unlike other like other high-level programming languages, awards procedures functions full first-class status. This poses challenges for efficient implementation, but the resulting gain in expressive power is enormous.[8]

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

Original	Python
(newtons-method (cubic a b c) 1)	newtons_method(cubic(a, b, c), 1)

to approximate zeros of the cubic $x^3 +ax^2 +bx +c$.

Solution

Original	Python
	def cubic(a, b, c): return lambda x: cube(x) + a * square(x) + b * x + c

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

Original	Python
(((double (double double)) inc) 5)	print(double(double(double))(inc)(5))

Solution

Original	Python
	def double(f): return lambda x: f(f(x))

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

Original	Python
((compose square inc) 6) 49	print(compose(square, inc)(6)) 49

returns 49.

Solution

Original	Python
	def compose(f, g): return lambda x: f(g(x))

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(\ldots(f(x))\ldots))$. For example, if $f$ is the function $x \mapsto x+1$, then the $n$th repeated application of $f$ is the function $x \mapsto 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 function that takes as inputs a procedure function that computes $f$ and a positive integer $n$ and returns the procedure function that computes the $n$th repeated application of $f$. Your procedure function should be able to be used as follows:

Original	Python
((repeated square 2) 5) 625	print(repeated(square, 2)(5)) 625

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

Solution

Original	Python
	def repeated(f, n): return (lambda x: x) if n == 0 else compose(f, repeated(f, n - 1))

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 function smooth that takes as input a procedure function that computes $f$ and returns a procedure function that computes the smoothed $f$. It is sometimes valuable to repeatedly smooth a function (that is, smooth the smoothed function, and so on) to obtained 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.

Solution

Original	Python
	dx = 0.00001 def smooth(f): return lambda x: (f(x - dx) + f(x) + f(x + dx)) / 3 def n_fold_smooth(f, n): return repeated(smooth, n)(f)

Exercise 1.45 We saw in section 1.3.3 that attempting to compute square roots by naively finding a fixed point of $y\mapsto 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\mapsto 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 $y\mapsto x/y^3$ converge. On the other hand, if we average-damp twice (i.e., use the average damp of the average damp of $y\mapsto x/y^3$) the fixed-point search does converge. Do some experiments to determine how many average damps are required to compute $n$th roots as a fixed-point search based upon repeated average damping of $y\mapsto x/y^{n-1}$. Use this to implement a simple procedure function for computing $n$th roots using fixed-point, fixed_point, average-damp, average_damp, and the repeated procedure function of exercise 1.43. Assume that any arithmetic operations you need are available as primitives.

Solution

def nth_root(n, x): return fixed_point(repeated(average_damp, math_floor(math_log2(n))) (lambda y: x / fast_expt(y, n - 1)), 1)

Exercise 1.46 Several of the numerical methods described in this chapter are instances of an extremely general computational strategy known as iterative improvement. Iterative improvement 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 function iterative-improve iterative_improve that takes two procedures functions as arguments: a method for telling whether a guess is good enough and a method for improving a guess. Iterative-improve The function iterative_improve should return as its value a procedure function that takes a guess as argument and keeps improving the guess until it is good enough. Rewrite the sqrt procedure function of section 1.1.7 and the fixed-point fixed_point procedure function of section 1.3.3 in terms of iterative-improve. iterative_improve.

Solution

def iterative_improve(is_good_enough, improve): def iterate(guess): return guess if is_good_enough(guess) else iterate(improve(guess)) return iterate