Structure and Interpretation of Computer Programs

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:

64

 

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.

65

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 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 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 nth

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 nth repeated application of f is the function x   x + 

n. If f is the operation of squaring a number, then the nth 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 nth 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

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

---