[ 目次, 前節, 次節, 索引 ]

1.3.1 引数としての手続き



次の三つの手続きを考えよう. 最初のはaからbまでの整数の和を計算する:

(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))))
三番目のは級数の項の並びの和



を計算する. これは(非常に遅いが)π/8に収束する:49

(define (pi-sum a b)
  (if (> a b)
      0
      (+ (/ 1.0 (* a (+ a 2))) (pi-sum (+ a 4) b))))

   三つの手続きは明らかに共通の基本パターンを持っている. 手続き名と, 加算される項を計算するaの関数と, aの次の値を用意する関数が違うだけで, 後は殆んどの部分が同じである. 同じ雛型:

(define (⟨name⟩ a b)
  (if (> a b)
      0
      (+ (⟨term⟩ a)
         (⟨name⟩ (⟨next⟩ a) b))))
のスロットを埋めることでそれぞれの手続きが生成出来る.

   こういう共通なパターンがあるということは, 表舞台に引き出されるのを待っている有用な抽象がある強い証拠である. 数学者は遥か昔に 級数の総和(summation of a series)という抽象を見出し 「総和記号」を発明した. 例えば:



がこの概念を表す. 総和記号の表現力は, 数学者に, 特定の和を扱うのでなく, ---例えば加算する特定の級数とは無関係に総和の一般的結果を導くというような---総和自身の概念を扱うことを可能にした.

   同様にプログラムの設計者として, われわれは言語が十分強力で, 特定の和を表現する手続きでなく, 総和自身の概念を表現する手続きが書けるようにしたい. われわれの手続き言語では, 上のような雛型をとり, 「スロット」を仮パラメタに変えることでそれがすぐに出来る:


(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))
sumは引数として下限と上限のabとともに, 手続き termnextをとることに注意しよう. sumは他の手続きのように使える. 例えば(引数を1増やす手続きincとともに)sum-cubesを定義するのに使える:

(define (inc n) (+ n 1))


(define (sum-cubes a b)
  (sum cube a inc b))
これを使えば1から10までの整数の三乗の和が計算出来る:
(sum-cubes 1 10)
3025
項を計算する恒等手続きidentityの助けを借り, sumを使ってsum-integersが定義出来る:

(define (identity x) x)


(define (sum-integers a b)
  (sum identity a inc b))
そうすると1から10までの整数が足せて:
(sum-integers 1 10)
55
同様にpi-sumも定義出来る:50

(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

   sumがひと度出来ると, これは更なる概念を作るための構成部品となる. 例えばa, b間の関数fの定積分は数値的には式



を使ってdxの小さい時の近似値が得られる. これを手続きとして表現出来て:


(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
(0と1の間のcubeの積分の正確な値は1/4である. )

問題 1.29


Simpsonの公式は上に示したのより更に正確な数値積分法である. Simpsonの公式を使えば, aからbまでの関数fの積分は, 偶整数nに対し, h = (b - a)/nまたyk = f(a + kh)として



で近似出来る. (nの増加は近似の精度を増加する.) 引数としてf, a, bnをとり, Simpson公式を使って計算した積分値を返す手続きを定義せよ. その手続きを使って(n = 100とn = 1000で)0から1までcubeを積分し, またその結果を上のintegral手続きの結果と比較せよ.

問題 1.30


上のsumの手続きは線形再帰を生成する. 総和が反復的に実行出来るように手続きを書き直せる. 次の定義の欠けているところを補ってこれを示せ:
(define (sum term a next b)
  (define (iter a result)
    (if ⟨??⟩
        ⟨??⟩
        (iter ⟨??⟩ ⟨??⟩)))
  (iter ⟨??⟩ ⟨??⟩))


問題 1.31


a. sum手続きは高階手続きとして書ける, 同様な数多い抽象の最も単純なものに過ぎない.51 与えられた範囲の点での関数値の積を返すproductという似た手続きを書け. productを使って, factorialを定義せよ. また式



によってπの近似値を計算するのにproductを使え.52

b. 上のproductが再帰的プロセスを生成するなら, 反復的プロセスを生成するものを書け. 反復的プロセスを生成するなら, 再帰的プロセスを生成するものを書け.

問題 1.32


a. sumと(問題1.31の)productは, 一般的なアキュムレーションの関数:
(accumulate combiner null-value term a next b)
を使い, 項の集りを組み合せるaccumulateという更に一般的なものの特殊な場合であることを示せ. accumulateは引数としてsum productと同様, 項と範囲指定と, 先行する項のアキュムレーションと現在の項をどう組み合せるかを指定する(二引数の)combiner手続き, 項がなくなった時に使う値を指定するnull-valueをとる. accumulateを書き, sumproductaccumulateの単なる呼出しで定義出来ることを示せ.

b. 上のaccumulateが再帰的プロセスを生成するなら, 反復的プロセスを生成するものを書け. 反復的プロセスを生成するなら, 再帰的プロセスを生成するものを書け.

問題 1.33


組み合せる項に フィルタ(filter)の考えを入れることで, accumulate(問題1.32)の更に一般的なものが得られる. つまり範囲から得られて, 指定した条件を満した項だけを組み合せる. 出来上ったfiltered-accumulate抽象は, accumulate と同じ引数の他, フィルタを指定する一引数の述語をとる. filtered-accumulateを手続きとして書け. filtered-accumulateを使い, 次をどう表現するかを示せ.

a. 区間a, bの素数の二乗の和(prime?述語は持っていると仮定する.)

b. nと互いに素で, nより小さい正の整数(つまりi < nでGCD(i, n)=1なる全整数i)の積



49 通常と書くこの級数はLeibnizによる. 3.5.3節で, すばらしい数値トリックがこの級数に基づいているのを見る.

50 pi-nextpi-termの定義を(これらの手続きは他の目的に使うことはなさそうなので)pi-sumの中に定義するのにブロック構造(1.1.8節)を使っていることに注意しよう. これらを全部取り除く方法は1.3.2節で見る.

51 問題1.31--1.33の意図は, 一見異る演算を, 適切な抽象を使って統合することで達成された表現力を明示することである. しかしアキュムレーションとフィルタは素晴らしい着想ではあるが, これらの抽象のために組み合せる手段を提供するデータ構造を持っていないので, 現時点ではこれらの使用は多少不自由である. この問題には2.2.3節で更に強力な抽象を構築するためフィルタやアキュムレータを組み合せるインターフェースとして, 並び(sequences)の使い方を見た時に戻ることにしよう. これらの方法がプログラム設計の強力で優美な解決法としてすぐにそれらと融合するのが分る.

52 この公式は十七世紀, 英国の数学者 John Wallisが見つけた.

[ 目次, 前節, 次節, 索引 ]