Structure and Interpretation of Computer Programs

Exercises

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

\[ \begin{align} \frac{h}{3} \left[ y_0 + 4y_1 + 2y_2 + 4y_3 + \dots + 2y_{n-2} + 4y_{n-1} + y_n \right] \end{align} \]

where \(h = \frac{b - a}{n}\) for some integer \(n\), and \(y_k = f(a + kh)\). Increasing \(n\) increases the accuracy of the approximation.) Define 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 function to integrate cube/4 between 0 and 1 (with \(n = 100\) and \(n = 1000\)), and compare the results to those of the integral/4 function shown in the previous section.

Exercise 1.30

The sum/4 function from the previous section generates a linear recursion. The 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:

(defun sum (term a next b)
  (flet ((iter (a result)
    (if <??>
        <??>
        (iter <??> <??>))))
    (iter <??> <??>)))

Exercise 1.31

a. The sum/4 function is only the simplest of a vast number of similar abstractions that can be captured as higher-order functions.¹ Write an analogous 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 ²

\[ \begin{align} \frac{\pi}{4} = \frac{ 2 \cdot 4 \cdot 4 \cdot 6 \cdot 6 \cdot 8 \dots} { 3 \cdot 3 \cdot 5 \cdot 5 \cdot 7 \cdot 7 \dots} \end{align} \]

b. If your product 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.

Exercise 1.32

a. Show that sum/4 and product (exercise 1.31) are both special cases of a still more general notion called accumulate/6 that combines a collection of terms, using some general accumulation function:

(accumulate combiner null-value term a next b)

accumulate/6 takes as arguments the same term and range specifications as sum and product, together with a combiner 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 that specifies what base value to use when the terms run out. Write accumulate/6 and show how sum and product can both be defined as simple calls to accumulate/6.

b. If your accumulate/6 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.

Exercise 1.33

You can obtain an even more general version of accumulate/6 (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/7 abstraction takes the same arguments as accumulate, together with an additional predicate of one argument that specifies the filter. Write filtered-accumulate/7 as a function. Show how to express the following using filtered-accumulate/7:

a. the sum of the squares of the prime numbers in the interval \(a\) to \(b\) (assuming that you have a prime?/1 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 \(\text{GCD}(i,n) = 1\)).