Structure and Interpretation of Computer Programs

the basis of a technique for constructing ‘‘unbreakable codes’’ suggested by Rivest, Shamir, and 

Adleman (1977). The resulting RSA algorithm has become a widely used technique for enhancing the

security of electronic communications. Because of this and related developments, the study of prime

numbers, once considered the epitome of a topic in ‘‘pure’’ mathematics to be studied only for its own

sake, now turns out to have important practical applications to cryptography, electronic funds transfer,

and information retrieval. 

[Go to first, previous, next page;   contents;   index]

---

[Go to first, previous, next page;   contents;   index]

1.3  Formulating Abstractions with Higher-Order Procedures

We have seen that procedures are, in effect, abstractions that describe compound operations on

numbers independent of the particular numbers. For example, when we

(define (cube x) (* x x x))

we are not talking about the cube of a particular number, but rather about a method for obtaining the

cube of any number. Of course we could get along without ever defining this procedure, by always

writing expressions such as

(* 3 3 3)

(* x x x)

(* y y y)        

and never mentioning 

cube

 explicitly. This would place us at a serious disadvantage, forcing us to

work always at the level of the particular operations that happen to be primitives in the language

(multiplication, in this case) rather than in terms of higher-level operations. Our programs would be

able to compute cubes, but our language would lack the ability to express the concept of cubing. One

of the things we should demand from a powerful programming language is the ability to build

abstractions by assigning names to common patterns and then to work in terms of the abstractions

directly. Procedures provide this ability. This is why all but the most primitive programming

languages include mechanisms for defining procedures.

Yet even in numerical processing we will be severely limited in our ability to create abstractions if we

are restricted to procedures whose parameters must be numbers. Often the same programming pattern

will be used with a number of different procedures. To express such patterns as concepts, we will need

to construct procedures that can accept procedures as arguments or return procedures as values.

Procedures that manipulate procedures are called higher-order procedures. This section shows how

higher-order procedures can serve as powerful abstraction mechanisms, vastly increasing the

expressive power of our language.

1.3.1  Procedures as Arguments

Consider the following three procedures. The first computes the sum of the integers from 

a

 through 

b

:

(define (sum-integers a b)

  (if (> a b)

      0

      (+ a (sum-integers (+ a 1) b))))

The second computes the sum of the cubes of the integers in the given range:

(define (sum-cubes a b)

  (if (> a b)

      0

      (+ (cube a) (sum-cubes (+ a 1) b))))

---

The third computes the sum of a sequence of terms in the series 

which converges to   /8 (very slowly):

49

(define (pi-sum a b)

  (if (> a b)

      0

      (+ (/ 1.0 (* a (+ a 2))) (pi-sum (+ a 4) b))))

These three procedures clearly share a common underlying pattern. They are for the most part

identical, differing only in the name of the procedure, the function of 

a

 used to compute the term to be

added, and the function that provides the next value of 

a

. We could generate each of the procedures by

filling in slots in the same template:

(define (<name> a b)

  (if (> a b)

      0

      (+ (<term> a)

         (<name> (<next> a) b))))

The presence of such a common pattern is strong evidence that there is a useful abstraction waiting to

be brought to the surface. Indeed, mathematicians long ago identified the abstraction of summation of

a series and invented ‘‘sigma notation,’’ for example

to express this concept. The power of sigma notation is that it allows mathematicians to deal with the

concept of summation itself rather than only with particular sums -- for example, to formulate general

results about sums that are independent of the particular series being summed.

Similarly, as program designers, we would like our language to be powerful enough so that we can

write a procedure that expresses the concept of summation itself rather than only procedures that

compute particular sums. We can do so readily in our procedural language by taking the common

template shown above and transforming the ‘‘slots’’ into formal parameters:

(define (sum term a next b)

  (if (> a b)

      0

      (+ (term a)

         (sum term (next a) next b))))

Notice that 

sum

 takes as its arguments the lower and upper bounds 

a

 and 

b

 together with the

procedures 

term

 and 

next

. We can use 

sum

 just as we would any procedure. For example, we can

use it (along with a procedure 

inc

 that increments its argument by 1) to define 

sum-cubes

:

(define (inc n) (+ n 1))

(define (sum-cubes a b)

  (sum cube a inc b))

---