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 (very slowly):

(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

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

(sum-cubes 1 10) 3025With the aid of an identity procedure to compute the term, we can define

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

(sum-integers 1 10) 55We can also define

(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

**Exercise.**
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.**
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.**

aThe `sum` procedure is only the simplest of a vast number of
similar abstractions that can be captured as higher-order procedures.
^{} 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
^{}

bIf 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.**
a. Show that `sum` and `product`
(exercise ) 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)

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.**
You can obtain an even more general version of `accumulate`
(exercise ) 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
).