Guile ではスタック溢れを気にせず再帰しよう

例としてリスト x の長さ(要素の数)を計算する length 手続きを Guile で実装することを考えてみましょう。

(define (length x)
  (if (null? x)
      0
      (+ 1 (length (cdr x)))))

length の実行例:

(length '(a b c))

3

length 手続きは下記のように読み下すことができます。

x の長さ(length)とは:

• a. x が空リスト(null?)のときは 0
• b. さもなくば、先頭以外(cdr)の長さ(length)に 1 を足したもの

a のような自身 length を含まない場合のことを基底部、b のような自身を含む場合のことを帰納部と呼びます。 再帰手続きの正しさは基底部と帰納部をそれぞれ読んで「ふむ、確かにそうだな」と思えるのであれば正しいので理解するのはとても簡単です。 このような自然に読める再帰的な定義のことをここでは「自然な再帰」と呼ぶことにします。

Guile 以外の多くのプログラミング言語ではこのような再帰手続きにはスタックオーバーフローのリスクがあります。どういうことかというと、手続き呼び出しをしたときに元に戻る場所を覚えておくためコールスタックを使用するのですが多くのプログラミング言語ではコールスタックに上限が設定されています。コールスタックの上限に到達した段階でそれ以上の計算が不能になり途中で計算が停止してしまうのです。そのため、今回の場合リスト x がコールスタックの上限よりも大きい場合には (length x) を求めることはできません。 この問題を回避するためには末尾呼び出しの形式に変換する必要があります(ただし、末尾呼び出しの最適化が行なわれるプログラミング言語・処理系に限ります。そうでない場合は繰り返しを表現する構文を使って書き換える必要があります。構文上の違いのみでこれから議論する末尾再帰との比較には影響しないので末尾再帰の話を繰り返しに置き換えて読んでいただいても問題ありません)。

ではスタックオーバーフローの回避のために末尾再帰呼び出しの形式に変換したリストの長さを求める手続き 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

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 の長さを表わしている

とても考えることが多く難しいことを分かっていただけたでしょうか。 length-tail という例が極めて簡単であったために難しいことを納得しにくいということはあるかもしれません。それでも、 length は基底部と帰納部をそれぞれ読むだけでプログラムの正しさについて納得できたのに対し、 length-tail を理解するにはプログラム全体の流れを追わないとよく分からないというのは大きな違いです。

このような苦労をして length-tail を書くよりも length を書いた方が良いと思うでしょう。Guile ではスタックオーバーフローは起きないので問題ありません。 length の方を書きましょう。ただし、一点だけ注意があります。

実は 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 の計算が再度実行された場合に正常に動作しなくなるという問題が指摘されています)。

リストを反転する手続きを自然な再帰で実装してみましょう。特に効率などを考慮しなければ下記のように実装しようと思うかもしれません。

(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 の方が圧倒的に早いのです。

このように自然な再帰では計算に時間がかかり過ぎてしまう場合もあります。これは末尾再帰かどうかという話ではなくて、アルゴリズムが異なるために生じている違いであり今回の再帰手続きを末尾再帰の手続きに直す必要性の有無とは少しずれた話ではあります。こういう重い計算をしていてそれが問題となる場合には別のアルゴリズムを検討する必要があります。