Guile ではスタック溢れを気にせず再帰しよう
目次
1. はじめに
追記 Guile だけでなく割と多くの Scheme の処理系で同様の挙動をするようです。 あと、スタック溢れを気にしなくていい挙動はメモリを食いつくして崩壊する危険を伴うのでいいことだけではないです。
「末尾再帰への書き換え」をやめよう!という記事を作成しました。再帰の美しさの説明などが強化されています。 また、GNU Guile では スタックに制限をかけることができ、制限をかけてスタックオーバーフローが起きた場合にハンドリングできます。
追記 新しく関数型プログラミングを学んだ人の多くは、スタックオーバーフローを回避するために再帰関数を末尾再帰の形式に変換する方法について学んでいると思います。Guile では他のプログラミング言語とは事情が異なり再帰をしてもシステムのメモリを使い尽すまではスタックオーバーフローが起きません(Racket も同様)。なので、一部の例外を除いて Guile でプログラムを書くときは無理に末尾再帰に変形せずに分かりやすくて綺麗な再帰のままにしましょう。
2. 自然な再帰と末尾再帰の比較
2.1. リストの長さを計算する再帰的な手続き length
例としてリスト x
の長さ(要素の数)を計算する length
手続きを Guile
で実装することを考えてみましょう。
(define (length x) (if (null? x) 0 (+ 1 (length (cdr x)))))
length
の実行例:
(length '(a b c))
3
2.2. 再帰手続きの読み方
length
手続きは下記のように読み下すことができます。
x
の長さ(length
)とは:
- a.
x
が空リスト(null?
)のときは0
- b. さもなくば、先頭以外(
cdr
)の長さ(length
)に 1 を足したもの
a のような自身 length
を含まない場合のことを基底部、b
のような自身を含む場合のことを帰納部と呼びます。
再帰手続きの正しさは基底部と帰納部をそれぞれ読んで「ふむ、確かにそうだな」と思えるのであれば正しいので理解するのはとても簡単です。
このような自然に読める再帰的な定義のことをここでは「自然な再帰」と呼ぶことにします。
2.3. 再帰手続きとスタックオーバーフロー
Guile
以外の多くのプログラミング言語ではこのような再帰手続きにはスタックオーバーフローのリスクがあります。どういうことかというと、手続き呼び出しをしたときに元に戻る場所を覚えておくためコールスタックを使用するのですが多くのプログラミング言語ではコールスタックに上限が設定されています。コールスタックの上限に到達した段階でそれ以上の計算が不能になり途中で計算が停止してしまうのです。そのため、今回の場合リスト
x
がコールスタックの上限よりも大きい場合には (length x)
を求めることはできません。
この問題を回避するためには末尾呼び出しの形式に変換する必要があります(ただし、末尾呼び出しの最適化が行なわれるプログラミング言語・処理系に限ります。そうでない場合は繰り返しを表現する構文を使って書き換える必要があります。構文上の違いのみでこれから議論する末尾再帰との比較には影響しないので末尾再帰の話を繰り返しに置き換えて読んでいただいても問題ありません)。
2.4. 末尾再帰版の length-tail
ではスタックオーバーフローの回避のために末尾再帰呼び出しの形式に変換したリストの長さを求める手続き
length-tail
を見てみましょう。 len
という引数を追加していて、これには
0
を渡すことを想定しています(Scheme
では手続きの中に手続きの定義がかけるので、 len
引数を隠蔽することも可能なのですが、分かりやすさのためにあえて len
引数を残しています)。
(define (length-tail x len) (if (null? x) len (length-tail (cdr x) (+ len 1))))
length-tail
の実行例:
(length-tail '(a b c) 0)
3
2.5. 末尾再帰の手続きは理解が難しい
length
では手続きの定義を読み下すだけで理解できましたが、 length-tail
は少し難しいです。なぜなら、 length
の場合は基底部と帰納部をそれぞれ確認して正しいと思うことができましたが、 length-tail
の基底部は len
であり単独では理解不能です。帰納部も
(length-tail (cdr x) (+ len 1))
とあり正しいかどうかは len
変数の値によるということになります。
length-tail
を理解するには計算の流れ全体を見なければいけません。
- a.
len
の初期状態は0
- b.
x
を(cdr x)
で置き換える度にlen
の値は1
増加する - c.
x
が空リスト(null?
) になったら、len
が初期のx
の長さを表わしているためlen
を返却する- c1. 初期の
x
が空リストになるには、初期のx
の長さと同じ回数 b の計算を繰り返したときである - c2. len の初期状態が 0 のため b を繰り返した回数が len の値となる
- c3. c1, c2 より
x
が空リストのとき len は初期の x の長さを表わしている
- c1. 初期の
とても考えることが多く難しいことを分かっていただけたでしょうか。 length-tail
という例が極めて簡単であったために難しいことを納得しにくいということはあるかもしれません。それでも、 length
は基底部と帰納部をそれぞれ読むだけでプログラムの正しさについて納得できたのに対し、 length-tail
を理解するにはプログラム全体の流れを追わないとよく分からないというのは大きな違いです。
このような苦労をして length-tail
を書くよりも length
を書いた方が良いと思うでしょう。Guile
ではスタックオーバーフローは起きないので問題ありません。 length
の方を書きましょう。ただし、一点だけ注意があります。
2.6. 末尾再帰と効率について
実は Guile を使う場合であっても length
と length-tail
手続きの間には違いがあります。
length-tail
では末尾再帰の最適化により呼び出し時の続きの計算を記憶しておく必要がありません。つまり、コールスタックに新しく追加する必要がありません。それに対して
length
では呼び出した後に続く計算を覚えておく必要があるのでコールスタックを消費します。 length
では length-tail
と違って残りの計算を記憶するために記憶領域を消費してしまうのです。Guile
ではコールスタックを消費しきったらヒープ領域を使ってコールスタックを拡張するので、与えるリストが長い場合には
length-tail
よりも length
の方がメモリを多く使用してしまう可能性があるのです。ただし、メモリを消費するといっても与えるリストと同じくらいしか使わないので大した問題ではないでしょう。よほどメモリの消費に気を使う必要のあるようなケースでしか問題にならないと考えて良いでしょう。
また、非末尾再帰の方が末尾再帰のよりも常に効率が悪いということではありません。むしろ末尾再帰にしない方が効率が良い場合もあります。手続き
f
とリスト x
を取り、それぞれの要素を f
によって変換したリストを返す map
手続きについて考えてみましょう。
(define (map f x) (if (null? x) '() (cons (f (car x)) (map f (cdr x)))))
map
の実行例:
(map - '(1 2 3))
(-1 -2 -3)
末尾再帰版の map-tail
を実装してみましょう。 result
引数には空リストを渡す想定です。
(define (map-tail f x result) (if (null? x) (reverse result) (map-tail f (cdr x) (cons (f (car x)) result))))
map-tail の実行例:
(map-tail - '(1 2 3) '())
(-1 -2 -3)
map
と map-tail
のメモリ効率の違いについて検討してみましょう。 map
の手続きは map
の呼び出しをするたびにコールスタックを消費し、不足した場合にはコールスタックを拡張するため
x
が長い場合にはメモリを消費する場合があります。それに対して
map-tail
はどうでしょうか。 map-tail
では result
引数を
(cons (f (car x)) result)
によって置き換えています。よって map-tail
でも再帰するたびにメモリを消費していきます。上記から map
と map-tail
で map
がコールスタックを消費するから map
の方がメモリを多く使うとは必ずしもいえません。 さらに、 map-tail
では基底部で reverse
を呼び出しています。これは map-tail
と同じくらいの計算量とメモリを消費するため、 map-tail
の計算の方が時間がかかりそうです。
試しに実行にかかる時間を計測して比較してみましょう。
(use-modules (ice-9 time)) (define-syntax-rule (dotimes (var n) form ...) (let ((end n)) (do ((var 0 (+ var 1))) ((<= end var)) form ...))) (for-each (lambda (n) (define x (iota (expt 10 n))) (for-each display (list (expt 10 n) " 個のリストの場合\n")) (display "map(100回):\n") (time (dotimes (i 100) (map - x))) (display "map-tail(100回):\n") (time (dotimes (i 100) (map-tail - x '()))) (newline)) (iota 3 3))
1000 個のリストの場合 map(100回): clock utime stime cutime cstime gctime 0.04 0.03 0.01 0.00 0.00 0.01 map-tail(100回): clock utime stime cutime cstime gctime 0.05 0.05 0.00 0.00 0.00 0.01 10000 個のリストの場合 map(100回): clock utime stime cutime cstime gctime 0.40 0.38 0.01 0.00 0.00 0.10 map-tail(100回): clock utime stime cutime cstime gctime 0.52 0.50 0.00 0.00 0.00 0.17 100000 個のリストの場合 map(100回): clock utime stime cutime cstime gctime 3.76 3.45 0.22 0.00 0.00 0.49 map-tail(100回): clock utime stime cutime cstime gctime 4.48 4.36 0.01 0.00 0.00 0.95
予想通り map-tail
の方が少し遅いという結果になりました(map-tail
の実装に引数を破壊する版の reverse!
を使った場合についても調べたところ、その場合は map
とほぼ同じ計算時間になることを確認しています。計算時間が変わらないのであれば
map
の方が良いでしょう。また、Guile
のマニュアルの Stack Overflow の節で reverse!
を使うと継続安全(continuation-safe)が損なわれ、 map-tail
の計算が終了した後に f
の計算が再度実行された場合に正常に動作しなくなるという問題が指摘されています)。
3. 自然な再帰だと計算量が爆発してしまうケース
ここまでの例では Guile でなら自然な再帰で良いと言える例だったのですが、何でもそうという訳ではありません。たまに自然な再帰だと計算量が爆発的に大きくなってしまう場合がありそういった場合には別のアルゴリズムに変更する必要があります。
3.1. リストを反転する手続き
リストを反転する手続きを自然な再帰で実装してみましょう。特に効率などを考慮しなければ下記のように実装しようと思うかもしれません。
(define (reverse x) (if (null? x) '() (append (reverse (cdr x)) (list (car x)))))
reverse
の実行例:
(reverse '(a b c))
(c b a)
この手続きは自然でたしかに正しいことはコードを読めば理解できるでしょう。ただし、一つ落とし穴があります。Lisp
のリストは先頭に要素を追加する場合は O(1)
の計算量でできるのに対してリストの最後に要素を追加する場合は O(n)
かかるのです。 この影響でリストが長くなると激的に遅くなります。
(time (reverse (iota 20000))) 'done
clock utime stime cutime cstime gctime 7.30 7.10 0.01 0.00 0.00 1.46 done
これに対してリストの先頭に追加する操作しか行なわない reverse-tail
を試してみましょう。
(define (reverse-tail x result) (if (null? x) result (reverse-tail (cdr x) (cons (car x) result))))
reverse-tail
の実行例
(reverse-tail '(a b c) '())
(c b a)
reverse-tail
の実行時間の計測:
(time (reverse-tail (iota 50000) '())) 'done
clock utime stime cutime cstime gctime 0.02 0.02 0.00 0.00 0.00 0.00 done
リストが長い場合は reverse
と比較すると reverse-tail
の方が圧倒的に早いのです。
このように自然な再帰では計算に時間がかかり過ぎてしまう場合もあります。これは末尾再帰かどうかという話ではなくて、アルゴリズムが異なるために生じている違いであり今回の再帰手続きを末尾再帰の手続きに直す必要性の有無とは少しずれた話ではあります。こういう重い計算をしていてそれが問題となる場合には別のアルゴリズムを検討する必要があります。
4. おわりに
Guile ではシステムのメモリを使い尽すまではスタックオーバーフローは起きないので、一般には自然な再帰をわざわざ末尾再帰の形式に変換してプログラムを読みにくくする必要はありません。末尾再帰に書き換えなくて済むプログラミングライフは大変快適なので、Guile のような再帰でスタックオーバーフローの起こさないプログラミング言語や処理系を探して使ってみてください。