1.3.1 Functions as Arguments - SICP Comparison Edition

Permalink copied!

1.3.1

Consider the following three functions. The first computes the sum of the integers from a through 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:

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]

function pi_sum(a, b) {
    return a > b
           ? 0
           : 1 / (a * (a + 2)) + pi_sum(a + 4, b);
}

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

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 function that expresses the concept of summation itself rather than only functions that compute particular sums. We can do so readily in our functional language by taking the common template shown above and transforming the slots into parameters:

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

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:

sum_cubes(1, 10);

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

function identity(x) {
    return x;
}

function sum_integers(a, b) {
    return sum(identity, a, inc, b);
}

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

sum_integers(1, 10);

We can also define pi_sum in the same way:

[2]

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 functions, we can compute an approximation to $\pi$:

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 function:

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

integral(cube, 0, 1, 0.01);

0.24998750000000042

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.) 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 function to integrate cube between 0 and 1 (with $n=100$ and $n=1000$), and compare the results to those of the integral function shown above.

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 function above 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 declaration:

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$); }

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

The sum 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
1. sum 関数は、高階関数として捉えられる多数の類似した抽象の中で最も単純なものにすぎません。与えられた範囲の各点における関数の値の積を返す、 product という類似の関数を書いてください。product を使って factorial を定義する方法を示してください。また、product を使って次の公式で $\pi$ の近似値を計算してください。 [3][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 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.
  あなたの product 関数が再帰的プロセスを生成する場合は、反復的プロセスを生成するものを書いてください。反復的プロセスを生成する場合は、再帰的プロセスを生成するものを書いてください。
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:
  
  sum と product （演習問題 1.31）が、ある一般的な累積関数を使って項の集まりを結合する、 accumulate と呼ばれるさらに一般的な概念の特殊ケースであることを示してください：
  accumulate(combiner, null_value, term, a, next, b);
  
  The function accumulate 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 and show how sum and product can both be declared as simple calls to accumulate.
  関数 accumulate は、sum や product と同じ項と範囲の指定に加えて、現在の項をそれ以前の項の累積とどのように結合するかを指定する（2引数の）関数 combiner と、項がなくなったときに使う基底値を指定する null_value を引数として受け取ります。accumulate を書き、sum と product の両方が accumulate への単純な呼び出しとして宣言できることを示してください。
  
  If your accumulate 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.
  あなたの accumulate 関数が再帰的プロセスを生成する場合は、反復的プロセスを生成するものを書いてください。反復的プロセスを生成する場合は、再帰的プロセスを生成するものを書いてください。
  
  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 function. Show how to express the following using filtered_accumulate:
  
  the sum of the squares of the prime numbers in the interval $a$ to $b$ (assuming that you have an is_prime predicate already written)
  
  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$).
  
  結合する項に フィルタの概念を導入することで、 accumulate（演習問題 1.32）のさらに一般的なバージョンを得ることができます。つまり、範囲内の値のうち指定された条件を満たすものから導出された項だけを結合します。得られる filtered_accumulate という抽象は、accumulate と同じ引数に加えて、フィルタを指定する1引数の述語を受け取ります。 filtered_accumulate を関数として書いてください。 filtered_accumulate を使って次のものを表現する方法を示してください：
  
  区間 $a$ から $b$ までの素数の2乗の合計（ is_prime 述語はすでに書かれているものとします）
  
  $n$ より小さい正の整数のうち、$n$ と互いに素であるものすべての積（すなわち、$\textrm{GCD}(i,n)=1$ であるような $i < n$ のすべての正の整数）
  
  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); }
//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); }

//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);
}

[1]

This series, usually written in the equivalent form $\frac {\pi}{4} = 1-\frac{1} {3}+\frac{1}{5}-\frac{1}{7}+\cdots$, is due to Leibniz. We'll see how to use this as the basis for some fancy numerical tricks in section 3.5.3.

[2]

Notice that we have used block structure (section 1.1.8) to embed the declarations of pi_next and pi_term within pi_sum, since these functions are unlikely to be useful for any other purpose. We will see how to get rid of them altogether in section 1.3.2.

[3]

The intent of exercises 1.31–1.33 is to demonstrate the expressive power that is attained by using an appropriate abstraction to consolidate many seemingly disparate operations. However, though accumulation and filtering are elegant ideas, our hands are somewhat tied in using them at this point since we do not yet have data structures to provide suitable means of combination for these abstractions. We will return to these ideas in section 2.2.3 when we show how to use sequences as interfaces for combining filters and accumulators to build even more powerful abstractions. We will see there how these methods really come into their own as a powerful and elegant approach to designing programs.

[4]

This formula was discovered by the seventeenth-century English mathematician John Wallis.

< Previous

Next >

1.3.1

Functions as Arguments