Consider the following three procedures. The first computes the sum
of the integers from ` a` through ` b`:

The second computes the sum of the cubes of the integers in the given range:(define (sum-integers a b) (if (> a b) 0 (+ a (sum-integers (+ a 1) b))))

(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 _{} (very slowly):^{49}

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(define (pi-sum a b) (if (> a b) 0 (+ (/ 1.0 ( a (+ a 2))) (pi-sum (+ a 4) b))))

(define (_{}a b) (if (> a b) 0 (+ (_{}a) (_{}(_{}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:

Notice that(define (sum term a next b) (if (> a b) 0 (+ (term a) (sum term (next a) next b))))

Using this, we can compute the sum of the cubes of the integers from 1 to 10:(define (inc n) (+ n 1)) (define (sum-cubes a b) (sum cube a inc b))

`
(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`:

Then we can add up the integers from 1 to 10:(define (identity x) x) (define (sum-integers a b) (sum identity a inc b))

`
(sum-integers 1 10)
55
`

We can also define ` pi-sum` in the same way:^{50}

Using these procedures, we can compute an approximation to :(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))

`( 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:

(The exact value of the integral of(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

**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 interger *n*, and
*y _{k} = f (a+kh)*. (Increasing

**Exercise 1.30**

The `sum` procedure shown 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 analagous procedure called

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 case 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 of
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).