Structure and Interpretation of Computer Programs

Using this, we can compute the sum of the cubes of the integers from 1 to 10:

(sum-cubes 1 10)

3025

With the aid of an identity procedure to compute the term, we can define 

sum-integers

 in terms of 

sum

:

(define (identity x) x)

(define (sum-integers a b)

  (sum identity a inc b))

Then we can add up the integers from 1 to 10:

(sum-integers 1 10)

55

We can also define 

pi-sum

 in the same way:

50

(define (pi-sum a b)

  (define (pi-term x)

    (/ 1.0 (* x (+ x 2))))

  (define (pi-next x)

    (+ x 4))

  (sum pi-term a pi-next b))

Using these procedures, we can compute an approximation to   :

(* 8 (pi-sum 1 1000))

3.139592655589783

Once we have 

sum

, we can use it as a building block in formulating further concepts. For instance, the 

definite integral of a function f between the limits a and b can be approximated numerically using the

formula 

for small values of dx. We can express this directly as a procedure:

(define (integral f a b dx)

  (define (add-dx x) (+ x dx))

  (* (sum f (+ a (/ dx 2.0)) add-dx b)

     dx))

(integral cube 0 1 0.01)

.24998750000000042

(integral cube 0 1 0.001)

.249999875000001

(The exact value of the integral of 

cube

 between 0 and 1 is 1/4.)

---

Exercise 1.29.  Simpson’s Rule is a more accurate method of numerical integration than the method

illustrated above. Using Simpson’s Rule, the integral of a function f between a and b is approximated

as 

where h = (b - a)/n, for some even integer n, and y

k

 = f(a + kh). (Increasing n increases the accuracy of

the approximation.) Define a procedure that takes as arguments f, a, b, and n and returns the value of

the integral, computed using Simpson’s Rule. Use your procedure to integrate 

cube

 between 0 and 1

(with n = 100 and n = 1000), and compare the results to those of the 

integral

 procedure shown

above. 

Exercise 1.30.  The 

sum

 procedure above generates a linear recursion. The procedure can be rewritten

so that the sum is performed iteratively. Show how to do this by filling in the missing expressions in

the following definition:

(define (sum term a next b)

  (define (iter a result)

    (if <??>

        <??>

        (iter <??> <??>)))

  (iter <??> <??>))

Exercise 1.31.   

a.  The 

sum

 procedure is only the simplest of a vast number of similar abstractions that can be

captured as higher-order procedures.

51

 Write an analogous procedure called 

product

 that returns

the product of the values of a function at points over a given range. Show how to define 

factorial

in terms of 

product

. Also use 

product

 to compute approximations to   using the formula

52

 

b.  If your 

product

 procedure generates a recursive process, write one that generates an iterative

process. If it generates an iterative process, write one that generates a recursive process. 

Exercise 1.32.  a. Show that 

sum

 and 

product

 (exercise 1.31) are both special cases of a still more

general notion called 

accumulate

 that combines a collection of terms, using some general

accumulation function:

(accumulate combiner null-value term a next b)

Accumulate

 takes as arguments the same term and range specifications as 

sum

 and 

product

,

together with a 

combiner

 procedure (of two arguments) that specifies how the current term is to be

combined with the accumulation of the preceding terms and a 

null-value

 that specifies what base

value to use when the terms run out. Write 

accumulate

 and show how 

sum

 and 

product

 can both

be defined as simple calls to 

accumulate

.

b. If your 

accumulate

 procedure generates a recursive process, write one that generates an iterative

process. If it generates an iterative process, write one that generates a recursive process. 

---

Exercise 1.33.  You can obtain an even more general version of 

accumulate

 (exercise 1.32) by

introducing the notion of a filter on the terms to be combined. That is, combine only those terms

derived from values in the range that satisfy a specified condition. The resulting 

filtered-accumulate

 abstraction takes the same arguments as accumulate, together with an

additional predicate of one argument that specifies the filter. Write 

filtered-accumulate

 as a

procedure. Show how to express the following using 

filtered-accumulate

:

a. the sum of the squares of the prime numbers in the interval a to b (assuming that you have a 

prime?

 predicate already written)

b. the product of all the positive integers less than n that are relatively prime to n (i.e., all positive

integers i < n such that GCD(i,n) = 1). 

1.3.2  Constructing Procedures Using 

Lambda

In using 

sum

 as in section 1.3.1, it seems terribly awkward to have to define trivial procedures such as 

pi-term

 and 

pi-next

 just so we can use them as arguments to our higher-order procedure. Rather

than define 

pi-next

 and 

pi-term

, it would be more convenient to have a way to directly specify

‘‘the procedure that returns its input incremented by 4’’ and ‘‘the procedure that returns the reciprocal

of its input times its input plus 2.’’ We can do this by introducing the special form 

lambda

, which

creates procedures. Using 

lambda

 we can describe what we want as

(lambda (x) (+ x 4))

and 

(lambda (x) (/ 1.0 (* x (+ x 2))))

Then our 

pi-sum

 procedure can be expressed without defining any auxiliary procedures as

(define (pi-sum a b)

  (sum (lambda (x) (/ 1.0 (* x (+ x 2))))

       a

       (lambda (x) (+ x 4))

       b))

Again using 

lambda

, we can write the 

integral

 procedure without having to define the auxiliary

procedure 

add-dx

:

(define (integral f a b dx)

  (* (sum f

          (+ a (/ dx 2.0))

          (lambda (x) (+ x dx))

          b)

     dx))

In general, 

lambda

 is used to create procedures in the same way as 

define

, except that no name is

specified for the procedure:

(lambda (<formal-parameters>) <body>)

---