Structure and Interpretation of Computer Programs (17 page)
Read Structure and Interpretation of Computer Programs Online
Authors: Harold Abelson and Gerald Jay Sussman with Julie Sussman
to approximate zeros of the cubic
x
3
+
a
x
2
+
b
x
+
c
.
Exercise 1.41.
Define a procedure
double
that takes a procedure of one
argument as argument and
returns a procedure that applies 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
d
x
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
-
d
x
),
f
(
x
), and
f
(
x
+
d
x
). 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 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
.
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
y
⟼
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
⟼
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
⟼
x
/
y
n
-1
. Use this to implement a simple procedure for computing
n
th roots using
fixed-point
,
average-damp
, and the
repeated
procedure of exercise
1.43
.
Assume that any arithmetic operations you need are available as primitives.
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
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.1.7
and the
fixed-point
procedure of
section
1.3.3
in terms of
iterative-improve
.
49
This series,
usually written in the equivalent form (π/4) = 1 - (1/3) + (1/5) - (1/7) +
···
, is due to Leibniz. We'll see how
to use this as the basis for some fancy numerical tricks in
section
3.5.3
.
50
Notice
that we have used block structure (section
1.1.8
) to
embed the definitions of
pi-next
and
pi-term
within
pi-sum
, since these procedures are unlikely to be useful for any
other purpose. We will see how to get rid of them altogether in
section
1.3.2
.
51
The intent of
exercises
1.31
-
1.33
is to
demonstrate the expressive power that is attained by using an
appropriate abstraction to consolidate many seemingly disparate
operations. However, though accumulation and filtering are elegant
ideas, our hands are somewhat tied in using them at this point since
we do not yet have data structures to provide suitable means of
combination for these abstractions. We will return to these ideas in
section
2.2.3
when we show how
to use
sequences
as interfaces for combining filters and
accumulators to build even more powerful abstractions. We will see
there how these methods really come into their own as a powerful and
elegant approach to designing programs.
52
This formula was discovered by the seventeenth-century
English mathematician John Wallis.
53
It would be clearer and less intimidating to
people learning Lisp if a name more obvious than
lambda
, such as
make-procedure
, were used. But the convention is firmly
entrenched. The notation is adopted from the
λ calculus, a
mathematical formalism introduced by the mathematical logician Alonzo
Church (1941). Church developed the λ calculus to provide a
rigorous foundation for studying the notions of function and function
application. The λ calculus has become a basic tool for
mathematical investigations of the semantics of programming
languages.
54
Understanding internal definitions well enough to be sure a
program means what we intend it to mean requires a more elaborate
model of the evaluation process than we have presented in this
chapter. The subtleties do not arise with internal definitions of
procedures, however. We will return to this issue in
section
4.1.6
, after we learn more about
evaluation.
55
We have used 0.001 as a representative “small” number to indicate a
tolerance for the acceptable error in a calculation. The appropriate
tolerance for a real calculation depends upon the problem to be solved
and the limitations of the computer and the algorithm. This is often
a very subtle consideration, requiring help from a numerical analyst
or some other kind of magician.
56
This
can be accomplished using
error
, which takes as
arguments a number of items that are printed as error
messages.
57
Try this during a boring lecture: Set your calculator to
radians mode and then repeatedly press the
cos
button until you
obtain the fixed point.
58
⟼
(pronounced “maps to”) is
the mathematician's way of writing
lambda
.
y
⟼
x
/
y
means
(lambda(y) (/ x y))
, that is, the
function whose value at
y
is
x
/
y
.
59
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.
60
See exercise
1.45
for a further
generalization.
61
Elementary calculus books usually describe Newton's
method in terms of the sequence of approximations
x
n
+1
=
x
n
-
g
(
x
n
)/
D
g
(
x
n
). Having language for talking about
processes and using the idea of fixed points simplifies the description
of the method.
62
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.
63
For finding square roots, Newton's method converges rapidly to the
correct solution from any starting point.
64
The notion of first-class status of programming-language
elements is due to the British computer scientist Christopher
Strachey (1916-1975).
65
We'll see
examples of this after we introduce data structures in chapter 2.
66
The major implementation cost of first-class
procedures is that allowing procedures to be returned as values
requires reserving storage for a procedure's free variables even while
the procedure is not executing. In the Scheme implementation we will
study in section
4.1
, these variables are stored in the
procedure's environment.
Building Abstractions with Data
We now come to the decisive step of mathematical abstraction: we Hermann Weyl, |
We concentrated in chapter 1 on computational processes and on the
role of procedures in program design. We saw how to use primitive
data (numbers) and primitive operations (arithmetic operations), how to
combine procedures to form compound procedures through composition,
conditionals, and the use of parameters, and how to abstract
procedures by using
define
. We saw that a procedure can be
regarded as a pattern for the local evolution of a process, and we
classified, reasoned about, and performed simple algorithmic analyses
of some common patterns for processes as embodied in procedures. We
also saw that higher-order procedures enhance the power of our
language by enabling us to manipulate, and thereby to reason in terms
of, general methods of computation. This is much of the essence of
programming.
In this chapter we are going to look at more complex data. All the
procedures in chapter 1 operate on simple numerical data, and simple
data are not sufficient for many of the problems we wish to address
using computation. Programs are typically designed to model complex
phenomena, and more often than not one must construct computational
objects that have several parts in order to model real-world phenomena
that have several aspects. Thus, whereas our focus in chapter 1 was
on building abstractions by combining procedures to form compound
procedures, we turn in this chapter to another key aspect of any
programming language: the means it provides for building abstractions
by combining data objects to form
compound data
.
Why do we want compound data in a programming language? For the same
reasons that we want compound procedures: to elevate the conceptual
level at which we can design our programs, to increase the modularity
of our designs, and to enhance the expressive power of our language.
Just as the ability to define procedures enables us to deal with
processes at a higher conceptual level than that of the primitive
operations of the language, the ability to construct compound data
objects enables us to deal with data at a higher conceptual level than
that of the primitive data objects of the language.