The above examples demonstrate how the ability to pass
proceduresfunctions
as arguments significantly enhances the expressive power of our programming
language. We can achieve even more expressive power by creating
proceduresfunctions
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
procedurefunction
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
JavaScript
(define (average-damp f)
(lambda (x) (average x (f x))))
function average_damp(f) {
return x => average(x, f(x));
}
Average-damp
is a procedure that
The function
average_damp
takes as its argument a
procedurefunctionf and returns as its value a
procedurefunction(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-dampaverage_damp
to the squareprocedurefunction
produces a
procedurefunction
whose value at some number $x$ is the average of
$x$ and $x^2$.
Applying this resulting
procedurefunction
to 10 returns the average of 10 and 100, or 55:[1]
Original
JavaScript
((average-damp square) 10)
55
average_damp(square)(10);
55
Using
average-damp,average_damp,
we can reformulate the
square-root
procedurefunction
as follows:
function sqrt(x) {
return fixed_point(average_damp(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
proceduresfunctions
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
proceduralprocess
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
procedurefunction
to one that extracts
cube roots:[2]
function cube_root(x) {
return fixed_point(average_damp(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
procedurefunction
function deriv(g) {
return x => (g(x + dx) - g(x)) / dx;
}
along with the
definitiondeclaration
Original
JavaScript
(define dx 0.00001)
const dx = 0.00001;
Like
average-damp,average_damp,deriv is a
procedurefunction
that takes a
procedurefunction
as argument and returns a
procedurefunction
as value. For example, to approximate the derivative of
$x \mapsto x^3$ at 5 (whose exact value is 75)
we can evaluate
Original
JavaScript
(define (cube x) (* x x x))
((deriv cube) 5)
75.00014999664018
function cube(x) { return x * x * x; }
deriv(cube)(5);
75.00014999664018
With the aid of deriv, we can express
Newton's method as a fixed-point process:
function newton_transform(g) {
return x => x - g(x) / deriv(g)(x);
}
function newtons_method(g, guess) {
return fixed_point(newton_transform(g), guess);
}
The
newton-transformnewton_transformprocedurefunction
expresses the formula at the beginning of this section, and
newtons-methodnewtons_method
is readily defined in terms of this. It takes as arguments a
procedurefunction
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:
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
JavaScript
(define (fixed-point-of-transform g transform guess)
(fixed-point (transform g) guess))
function fixed_point_of_transform(g, transform, guess) {
return fixed_point(transform(g), guess);
}
This very general
procedurefunction
takes as its arguments a
procedurefunctiong
that computes some function, a
procedurefunction
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:
function sqrt(x) {
return fixed_point_of_transform(
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
function sqrt(x) {
return fixed_point_of_transform(
y => square(y) - x,
newton_transform,
1);
}
We began section 1.3 with the
observation that compound
proceduresfunctions
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
proceduresfunctions
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
proceduresfunctions
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.
Lisp,JavaScript,
unlike other
like other high-level
programming languages, awards
proceduresfunctions
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 procedureDeclare a functioncubic that can be used together with the
newtons-methodnewtons_methodprocedurefunction
in expressions of the form
Original
JavaScript
(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$.
Original
JavaScript
function cubic(a, b, c) {
return x => cube(x) + a * square(x) + b * x + c;
}
Exercise 1.41 Define a procedureDeclare a functiondouble that takes a
procedurefunction
of one argument as argument and returns a
procedurefunction
that applies the original
procedurefunction
twice. For example, if inc is a
procedurefunction
that adds 1 to its argument, then
(double inc)double(inc)
should be a
procedurefunction
that adds 2. What value is returned by
Original
JavaScript
(((double (double double)) inc) 5)
double(double(double))(inc)(5);
Original
JavaScript
function double(f) {
return 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 procedureDeclare a functioncompose that implements composition. For
example, if inc is a
procedurefunction
that adds 1 to its argument,
Original
JavaScript
((compose square inc) 6)
49
compose(square, inc)(6);
49
returns 49.
Original
JavaScript
function compose(f, g) {
return 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
procedurefunction
that takes as inputs a
procedurefunction
that computes $f$ and a positive integer
$n$ and returns the
procedurefunction
that computes the $n$th repeated application of
$f$. Your
procedurefunction
should be able to be used as follows:
Original
JavaScript
((repeated square 2) 5)
625
repeated(square, 2)(5);
625
Hint: You may find it convenient to use
compose from
exercise 1.42.
Original
JavaScript
function repeated(f, n) {
return n === 0
? x => x
: 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
procedurefunctionsmooth that takes as input a
procedurefunction
that computes $f$ and returns a
procedurefunction
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.
Original
JavaScript
const dx = 0.00001;
function smooth(f) {
return x => (f(x - dx) + f(x) + f(x + dx)) / 3;
}
function 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
procedurefunction
for computing $n$th roots using
fixed-point,fixed_point,average-damp,average_damp,
and the repeatedprocedurefunction
of exercise 1.43. Assume that any arithmetic
operations you need are available as primitives.
function nth_root(n, x) {
return fixed_point(repeated(average_damp,
math_floor(math_log2(n)))
(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
procedurefunctioniterative-improveiterative_improve
that takes two
proceduresfunctions
as arguments: a method for telling whether a guess is good enough and a
method for improving a guess.
Iterative-improveThe function
iterative_improve
should return as its value a
procedurefunction
that takes a guess as argument and keeps improving the guess until it is
good enough. Rewrite the sqrtprocedurefunction
of section 1.1.7 and the
fixed-pointfixed_pointprocedurefunction
of section 1.3.3 in terms of
iterative-improve.iterative_improve.
function iterative_improve(is_good_enough, improve) {
function iterate(guess) {
return is_good_enough(guess)
? guess
: iterate(improve(guess));
}
return iterate;
}
Observe that this is a combination whose operator is itself
a combination. Exercise 1.4 already
demonstrated the ability to form such combinations, but that was only a toy
example. Here we begin to see the real need for such
combinations—when applying a procedure
that is obtained as the value returned by a higher-order procedure.
Observe that this
is an application whose function expression is itself
an application. Exercise 1.4 already
demonstrated the ability to form such applications, but that was only a toy
example. Here we begin to see the real need for such
applications—when applying a function
that is obtained as the value returned by a higher-order function.
[2]
See exercise 1.45
for a further generalization.
[3]
Elementary calculus books
usually describe Newton's method in terms of the sequence of
approximations $x_{n+1}=x_n-g(x_n)/Dg(x_n)$.
Having language for talking about processes and using the idea of fixed
points simplifies the description of the method.
[4]
Newton's method does not
always converge to an answer, but it can be shown that in favorable cases
each iteration doubles the number-of-digits accuracy of the approximation
to the solution. In such cases,
Newton's method will converge much more rapidly than the half-interval
method.
[5]
For finding square roots, Newton's method converges
rapidly to the correct solution from any starting point.
[6]
The notion of
first-class status of programming-language
elements is due to the British computer scientist
Christopher Strachey (1916–1975).
[7]
We'll see
examples of this after we introduce data structures in
chapter 2.
[8]
The major implementation cost of first-class
proceduresfunctions
is that allowing
proceduresfunctions
to be returned as values requires reserving storage for a
procedure's free variablesfunction's free names
even while the
procedurefunction
is not executing.
In the Scheme implementation we will study in
section 4.1, these variables are stored in
the procedure's
In the JavaScript implementation we will study in
section 4.1, these names are stored in the
function's
environment.