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

Original	JavaScript
(define (sum-integers a b) (if (> a b) 0 (+ a (sum-integers (+ a 1) b))))	function sum_integers(a, b) { return a > b ? 0 : a + sum_integers(a + 1, b); }

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

Original	JavaScript
(define (sum-cubes a b) (if (> a b) 0 (+ (cube a) (sum-cubes (+ a 1) b))))	function sum_cubes(a, b) { return a > b ? 0 : cube(a) + sum_cubes(a + 1, b); }

The third computes the sum of a sequence of terms in the series \[ \frac{1}{1\cdot3}+\frac{1}{5\cdot7}+\frac{1}{9\cdot11}+\cdots \] which converges to $\pi/8$ (very slowly):[1]

Original	JavaScript
(define (pi-sum a b) (if (> a b) 0 (+ (/ 1.0 (* a (+ a 2))) (pi-sum (+ a 4) b))))	function pi_sum(a, b) { return a > b ? 0 : 1 / (a * (a + 2)) + pi_sum(a + 4, b); }

These three procedures functions clearly share a common underlying pattern. They are for the most part identical, differing only in the name of the procedure, function, 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 functions by filling in slots in the same template:

Original	JavaScript
(define ($\langle name \rangle$ a b) (if (> a b) 0 (+ ($\langle term \rangle$ a) ($\langle name \rangle$ ($\langle next \rangle$ a) b))))	function $name$(a, b) { return 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 \[\begin{array}{lll} \displaystyle\sum_{n=a}^{b}\ f(n)&=&f(a)+\cdots+f(b) \end{array}\] 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 function that expresses the concept of summation itself rather than only procedures functions that compute particular sums. We can do so readily in our procedural functional language by taking the common template shown above and transforming the slots into formal parameters: parameters:

Original	JavaScript
(define (sum term a next b) (if (> a b) 0 (+ (term a) (sum term (next a) next b))))	function sum(term, a, next, b) { return 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 functions term and next. We can use sum just as we would any procedure. function. For example, we can use it (along with a procedure function inc that increments its argument by 1) to define sum-cubes: sum_cubes:

Original	JavaScript
(define (inc n) (+ n 1)) (define (sum-cubes a b) (sum cube a inc b))	function inc(n) { return n + 1; } function sum_cubes(a, b) { return sum(cube, a, inc, b); }

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

Original	JavaScript
(sum-cubes 1 10) 3025	sum_cubes(1, 10); 3025

With the aid of an identity procedure function to compute the term, we can define sum-integers sum_integers in terms of sum:

Original	JavaScript
(define (identity x) x)	function identity(x) { return x; }

Original	JavaScript
(define (sum-integers a b) (sum identity a inc b))	function sum_integers(a, b) { return sum(identity, a, inc, b); }

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

Original	JavaScript
(sum-integers 1 10) 55	sum_integers(1, 10); 55

We can also define pi-sum define pi_sum in the same way:[2]

Original	JavaScript
(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))	function pi_sum(a, b) { function pi_term(x) { return 1 / (x * (x + 2)); } function pi_next(x) { return x + 4; } return sum(pi_term, a, pi_next, b); }

Using these procedures, functions, we can compute an approximation to $\pi$:

Original	JavaScript
(* 8 (pi-sum 1 1000)) 3.139592655589783	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 \[ \begin{array}{lll} \displaystyle\int_{a}^{b}f & = & \left[\,f\!\left( a+\dfrac{dx}{2} \right)\,+\,f\!\left(a+dx+\dfrac{dx}{2} \right)\,+\,f\!\left( a+2dx+\dfrac{dx}{2}\right)\,+\,\cdots \right] dx \end{array} \] for small values of $dx$. We can express this directly as a procedure: function:

Original	JavaScript
(define (integral f a b dx) (define (add-dx x) (+ x dx)) (* (sum f (+ a (/ dx 2)) add-dx b) dx))	function integral(f, a, b, dx) { function add_dx(x) { return x + dx; } return sum(f, a + dx / 2, add_dx, b) * dx; }

Original	JavaScript
(integral cube 0 1 0.01) 0.24998750000000042	integral(cube, 0, 1, 0.01); 0.24998750000000042

Original	JavaScript
(integral cube 0 1 0.001)	integral(cube, 0, 1, 0.001); 0.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 \[ \frac{h}{3}[ y_0 +4y_1 +2y_2 +4y_3 +2y_4 +\cdots+2y_{n-2} +4y_{n-1}+y_n ] \] 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 Declare a function that takes as arguments $f$, $a$, $b$, and $n$ and returns the value of the integral, computed using Simpson's Rule. Use your procedure function to integrate cube between 0 and 1 (with $n=100$ and $n=1000$), and compare the results to those of the integral procedure function shown above.

Solution

Original	JavaScript
	function inc(k) { return k + 1; } function simpsons_rule_integral(f, a, b, n) { function helper(h) { function y(k) { return f((k * h) + a); } function term(k) { return k === 0 || k === n ? y(k) : k % 2 === 0 ? 2 * y(k) : 4 * y(k); } return sum(term, 0, inc, n) * (h / 3); } return helper((b - a) / n); }

Exercise 1.30 The sum procedure function above generates a linear recursion. The procedure function 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: declaration:

Original	JavaScript
(define (sum term a next b) (define (iter a result) (if ?? ?? (iter ?? ??))) (iter ?? ??))	function sum(term, a, next, b) { function iter(a, result) { return $\langle{}$??$\rangle$ ? $\langle{}$??$\rangle$ : iter($\langle{}$??$\rangle$, $\langle{}$??$\rangle$); } return iter($\langle{}$??$\rangle$, $\langle{}$??$\rangle$); }

Solution

function sum(term, a, next, b) { function iter(a, result) { return a > b ? result : iter(next(a), result + term(a)); } return iter(a, 0); }

Exercise 1.31

1. The sum procedure function is only the simplest of a vast number of similar abstractions that can be captured as higher-order proceduresfunctions.[3] Write an analogous procedure function 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 $\pi$ using the formula[4] \[ \begin{array}{lll} \dfrac{\pi}{4} & = & \dfrac{2 \cdot 4\cdot 4\cdot 6\cdot 6\cdot 8\cdots}{3\cdot 3\cdot 5\cdot 5\cdot 7\cdot 7\cdots} \end{array} \]
2. If your product procedure function generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.

Solution

Original	JavaScript
	//recursive process function product_r(term, a, next, b) { return a > b ? 1 : term(a) * product_r(term, next(a), next, b); } //iterative process function product_i(term, a, next, b) { function iter(a, result) { return a > b ? result : iter(next(a), term(a) * result); } return iter(a, 1); }

Exercise 1.32

1. 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:

   Original	JavaScript
   (accumulate combiner null-value term a next b)	accumulate(combiner, null_value, term, a, next, b);

   Accumulate The function accumulate takes as arguments the same term and range specifications as sum and product, together with a combiner procedure function (of two arguments) that specifies how the current term is to be combined with the accumulation of the preceding terms and a null-value 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 declared as simple calls to accumulate.
2. If your accumulate procedure function generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.

Solution

Original

JavaScript

//recursive process function accumulate_r(combiner, null_value, term, a, next, b) { return a > b ? null_value : combiner(term(a), accumulate_r(combiner, null_value, term, next(a), next, b)); } function sum_r(term, a, next, b) { function plus(x, y) { return x + y; } return accumulate_r(plus, 0, term, a, next, b); } function product_r(term, a, next, b) { function times(x, y) { return x * y; } return accumulate_r(times, 1, term, a, next, b); } //iterative process function accumulate_i(combiner, null_value, term, a, next, b) { function iter(a, result) { return a > b ? result : iter(next(a), combiner(term(a), result)); } return iter(a, null_value); } function sum_i(term, a, next, b) { function plus(x, y) { return x + y; } return accumulate_i(plus, 0, term, a, next, b); } function product_i(term, a, next, b) { function times(x, y) { return x * y; } return accumulate_i(times, 1, term, a, next, b); }

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 filtered_accumulate abstraction takes the same arguments as accumulate, together with an additional predicate of one argument that specifies the filter. Write filtered-accumulate filtered_accumulate as a procedure. function. Show how to express the following using filtered-accumulate: filtered_accumulate:

1. the sum of the squares of the prime numbers in the interval $a$ to $b$ (assuming that you have an prime? is_prime predicate already written)
2. 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 $\textrm{GCD}(i,n)=1$).

Solution

Original	JavaScript
	function filtered_accumulate(combiner, null_value, term, a, next, b, filter) { return a > b ? null_value : filter(a) ? combiner(term(a), filtered_accumulate(combiner, null_value, term, next(a), next, b, filter)) : filtered_accumulate(combiner, null_value, term, next(a), next, b, filter); }