iteration

8. 繰り返し

プログラムでは、「繰り返し」同じ計算をするということが良くあります。例えば、5. 再帰の章の問題 5.1.はまさにそれにあたります。

ここでは、練習問題 5.1. を解きながら、「繰り返し」について考えてみましょう。

8.1. 「n 以下の非負整数の和」

求める関数を sum としましょう。こんなふうに考えると簡単です。

自明な場合、n = 0 の場合、これは明かに 0 です。
0 から n までの和は、n 足す、0 から n - 1 までの和です。

これらを、定義にまとめると

(define (sum n)
  (if (= n 0)
      0
      (+ n (sum (- n 1)))))

実行してみましょう。

gosh> (sum 0)
0
gosh> (sum 1)
1
gosh> (sum 10)
55

8.1.1. ロバストに

つぎに行くまえにちょいとまわり道をします。上で定義した関数はとりあえず正しく動作しますか？ほんとに大丈夫ですか？

ではちょっといじめてみましょうか。

gosh> (sum -1) ^C ;; 止まらないので Control-C で強制終了させる
*** ERROR: unhandled signal 2 (SIGINT)
Stack Trace:
_______________________________________
  0  (sum (- n 1))
        At line 4 of "(stdin)"
  1  (sum (- n 1))
        At line 4 of "(stdin)"
  2  (sum (- n 1))
        At line 4 of "(stdin)"
...

なにが起ってますか？traceしてみましょう。

gosh> (use ggc.debug.trace)
(#<module ggc.debug.trace> #<module gauche.interactive>)
gosh> (trace sum)
#<closure 0x8ae1c00(x)>
gosh> (sum -1) ^C ;; 止まらないので Control-C で強制終了させる
(sum -1)
0:(sum -1)
1:  (sum -2)
2:    (sum -3)
3:      (sum -4)
4:        (sum -5)
5:          (sum -6)
6:            (sum -7)
7:    *** ERROR: unhandled signal 2 (SIGINT)
...

こりゃだめですよね。問題は、sum の引数が、非負でなければならないのに負の数を与えてしまった。からです。すこし、修正しましょう。

(define (sum n)
  (if (negative? n)
      (error "Not non-negative number -- SUM " n)
      (if (= 0 n)
          0
          (+ n (sum (- n 1))))))

与えられた引数が、負だったらエラーになるようにしました。

gosh> (sum -1)
*** ERROR: Not non-negative number -- SUM -1
Stack Trace:
_______________________________________

大丈夫かなぁ。

gosh> (sum 5.5)
*** ERROR: Not non-negative number -- SUM  -0.5
Stack Trace:
_______________________________________
  0  (sum (- n 1))
        At line 25 of "(stdin)"
  1  (sum (- n 1))
        At line 25 of "(stdin)"
  2  (sum (- n 1))
        At line 25 of "(stdin)"
  3  (sum (- n 1))
        At line 25 of "(stdin)"
  4  (sum (- n 1))
        At line 25 of "(stdin)"
  5  (sum (- n 1))
        At line 25 of "(stdin)"

ちょっと、エラーメッセージが変ですよね。「整数じゃなくちゃダメだよ」というメッセージにしたいですね。

(define (sum n)
  (cond ((not (integer? n)) (error "Not integer -- SUM" n))
        ((negative? n) (error "Not non-negative number -- SUM" n))
        (else (if (zero? n)
                  0
                  (+ n (sum (- n 1)))))))

cond は条件によって分岐するためのスペシャルフォーム(特殊形式)です。さてどうでしょう。

gosh> (sum 3.5)
*** ERROR: Not integer -- SUM 3.5
Stack Trace:
_______________________________________
gosh> (sum -2)
*** ERROR: Not non-negative number -- SUM -2
Stack Trace:
_______________________________________
gosh> (sum 10.0)
55.0
gosh> (use ggc.debug.trace)
(#<module ggc.debug.trace> #<module gauche.interactive>)
gosh> (trace sum)
#<closure 0x8ae17a0(x)>
gosh> (sum 5)
0:(sum 5)
1:  (sum 4)
2:    (sum 3)
3:      (sum 2)
4:        (sum 1)
5:          (sum 0)
            ->0
          ->1
        ->3
      ->6
    ->10
  ->15
; trace: sum has been called 6 times.
15

まぁこんなとこですか？

8.2. 繰り返しのパターン

繰り返しのあらわれる関数の定義にはあるパターンが存在します。

8.2.1. 和と階乗との比較

では、5. 再帰で定義した階乗計算と比較してみましょう。両方とも(ロバストではない)素朴な実装で比べてみます。関数名を同じにすると、

和

(define (f n)
  (if (= n 0)
      0
      (+ n (f (- n 1)))))

階乗

(define (f n)
  (if (= n 0)
      1
      (* n (f (- n 1)))))

そっくりですねぇ。違いは

n = 0 だったときに返す値(一方は 0 で他方は 1)
+ か * かです。

8.2.2. 繰り返しパターンを関数にする

このように構造がそっくりで一部だけ違うというのなら、その相違する部分を引数にして、和や階乗を計算する関数を生成することができます。

(define (accumulator-gen b i)
  (lambda (n)
    (if (= n 0)
        i
        (b n ((accumulator-gen b i) (- n 1))))))

引数の b は二つの数値を引数としてとり、数値を返す関数。したがって、+ とか * も b に渡せる関数です。
引数の i は、作った関数の引数が 0 であったときに返す数。

こうすると、たとえば、階乗を計算する関数 fact は

gosh> (define fact (accumulator-gen * 1))
fact
gosh> (fact 10)
3628800

和を計算する方は

gosh> (define sum (accumulator-gen + 0))
sum
gosh> (sum 10)
55

さらに便利なことに、n以下の非負整数の自乗の和というのは、

(accumulator-gen (lambda (x y) (+ (square x) y)) 0)

と定義できますよね。(実行してみる前に、じっくり考えて下さい)

gosh> (define (square x) (* x x))
square
gosh> (define sum-squares (accumulator-gen (lambda (x y) (+ (square x) y)) 0))
sum-squares
gosh> (sum-squares 10)
385

このようにプログラムの中で自由自在に関数つくれるのが、Gauche の醍醐味です。

8.3. もうひとつ別の繰り返しパターン

8.3.1. 「n 以下の非負整数の和」ふたたび

8.1. とは違う考えかたで、「n 以下の非負整数の和」を考えてみましょう。

1. 0に1を足す
2. その結果に2を足す
3. その結果に3を足す

n. その結果にnを足す
nになったのでおわり

という手順です。もうすこしプログラム風にいえば、

計算のあるステップは、それまでの部分的な結果とカウンタをもらって、新しい部分的な結果と更新されたカウンタを計算して次のステップに行く。
もらった、カウンタの値が n を超えていたらそのとき貰った部分的な結果を最終結果として返す

というものです。この方針で、まず「n 以下の非負整数の和」を定義してみましょう。とりあえず関数の名前を sum-iter とでもしておきましょう。

(define (sum-iter partial-sum counter max-count)
  (if (> counter max-count)
      partial-sum
      (sum-iter (+ partial-sum counter) (+ counter 1) max-count)))

これでいいはずです。これで例えば、0 から 10 までの和ということなら、

gosh> (sum-iter 0 0 10)
55

ちゃんと計算できましたね。まえの sum と、この sum-iter の計算が進む様子を手でシミュレートして比較してみましょう。まず、(sum 5)から

(sum 5)
(+ 5 (sum 4))
(+ 5 (+ 4 (sum 3)))
(+ 5 (+ 4 (+ 3 (sum 2))))
(+ 5 (+ 4 (+ 3 (+ 2 (sum 1)))))
(+ 5 (+ 4 (+ 3 (+ 2 (+ 1 (sum 0))))))
(+ 5 (+ 4 (+ 3 (+ 2 (+ 1 0)))))
(+ 5 (+ 4 (+ 3 (+ 2 1))))
(+ 5 (+ 4 (+ 3 3)))
(+ 5 (+ 4 6))
(+ 5 10)
15

つぎに、(sum-iter 0 0 5)

(sum-iter 0 0 5)
(sum-iter 0 1 5)
(sum-iter 1 2 5)
(sum-iter 3 3 5)
(sum-iter 6 4 5)
(sum-iter 10 5 5)
(sum-iter 15 6 5)
15

これを見ると、sum の方は、だんだん長く(括弧の入れ子が深く)なって、それから、だんだんそれが短く(括弧の入れ子が浅く)なっているのに対して、sum-iter の方は、長さが(括弧の入れ子の深さが)変らないことがわかります。

sum のような括弧の入れ子が深くなって、ふたたび浅くなるようなパターンの繰り返し計算のプロセスのことを、再帰的プロセスといいます。また、sum-iter のような括弧の入れ子が変化しないような繰り返し計算のプロセスのことを、反復的プロセスといいます。再帰的プロセス、反復的プロセスというのは、関数の定義が再帰的かどうかということではありません。

8.3.2. 内部定義

「n以下の非負整数の和」を計算するのに必要な情報は、n の具体的な値だけです。ところが、sum-iter では引数が3つもあります。以下のようにすると、引数ひとつだけの、sum-bis が構成できます。

(define (sum-bis n)
  (define (iter partial-sum counter)
    (if (> counter n)
        partial-sum
        (iter (+ partial-sum counter) (+ counter 1))))
  (iter 0 0))

まず、この定義でちゃんと動くことを確かめましょう。

gosh> (sum-bis 5)
15
gosh> (sum-bis 10)
55

では、sum-bis の定義がどのように構成されているのか見てみましょう。

(define (sum-bis n)
  ...
  (iter 0 0))

のようになっていますので、(sum-bis 5) と呼びだすと、(iter 0 0) の結果が返ってきます。この iter が、sum-bis の定義の中に定義されている内部定義の関数です。それが

  (define (iter partial-sum counter)
    (if (> counter n)
        partial-sum
        (iter (+ partial-sum counter) (+ counter 1))))

の部分です。さて、注意深いかたなら、この iter の定義と先の節で定義した sum-iter とが少しだけ違うということに気づいたと思います。それは引数の数です。sum-iter の第3引数であった、max-count がなくなっています。

最初の if 式でカウンタが n を超えたかどうかの判断をしていますね。この n はどこから来たのでしょう。iter の引数として来たわけではありません。これは、sum-bis の引数としてきた n です。このように内部定義の関数は、外側の関数の引数の定義を参照することができます、いいかえれば、 iterが実際に呼ばれる前に定義されていれば、iterは自分の引数ではない変数を参照することができます。

8.3.3. もうひとつの繰り返しパターンの関数

8.2.2. でやったように、反復的プロセスの繰り返しパターンの関数を作ってみましょう。もう簡単ですね。

(define (accumulator-gen-bis b i)
  (lambda (n)
    (define (iter partial-result count)
      (if (> count n)
          partial-result
          (iter (b partial-result count) (+ count 1))))
    (iter i 1)))

そうすると、sum-bis は

gosh> (define sum-bis (accumulator-gen-bis + 0))
sum-bis
gosh> (sum-bis 5)
15
gosh> (sum-bis 10)
55

8.4. 練習問題

問題 8.1
accumulator-gen-bis を使って、階乗を求める関数 fact-bis を定義しなさい。

問題 8.2.
accumulator-gen-bis を使って、n以下の非負整数の自乗の和を求める関数を定義しなさい。

8.5. 小難しい話

8.5.1. 高階関数

関数を引数としたり、返り値が関数であったり、あるいは、その両方であるような関数のことを高階関数といいます。高階関数が定義できるようなプログラミング言語のことを「関数が第一級の計算対象(first-class object) である言語」といいます。この属性は、関数型とよばれるようなプログラミング言語の特徴です。 Gauche をはじめ、あらゆる Scheme、Lisp はこのような「関数が第一級の計算対象(first-class object)」の言語です。 Scheme や Lisp が関数型言語の範疇にいれられことがあるのは、この性質をもつというのがその理由です。

8.5.2. 末尾再帰

計算パターンが再帰プロセスなるような繰り返し計算が正しく行えるのは、 Gauche の処理系が、次にするべき計算を記憶してくれるからです。どういうことかというと、上の手でおこなったシミュレーションでは、

(+ 5 (sum 4))

という部分の計算は、(sum 4) の計算を行って (sum 4) の結果が返ってきたとき「そのあと 5 をそれに足す」ということ(これを継続といいます)を覚えているということです。

一寸処理系を苛めてみましょう。

gosh> (sum 10000000)
GC Warning: Out of Memory!  Returning NIL!
out of memory (20).  aborting...

Process scheme exited abnormally with code 1

ああ、可愛いそうに、継続を覚えておく領域がたりなくなってお亡くなりに。。。

ところが、計算パターンが反復プロセスになるような繰り返し計算の場合にはこのような覚えておくべき継続はありません。そのかわりに、部分計算を partial-sum (あるいは partial-result)という変数で明示的に保持し、それを次のステップに渡しています。引数は増えますが、Gaucheの処理系が裏で覚えなくてもよいことになります。

では同じ計算をやらせてみましょう。

gosh> (sum-bis 10000000)
5000000050000000

ちょっと時間はかかりましたが、ちゃんと計算できましたね。

このような計算パターンが反復プロセスになるような繰り返し計算の定義は定義パターンの形から、「末尾再帰」といいます。

Scheme の処理系では、末尾再帰で定義された計算は、継続を保存する必要がないので保存しないようにすることになっています。

Kahua

News

Site Info

Kahua開発日記

Enjoy Gauche