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

はじめに

関数型プログラミングを学んだ人の多くは、スタックオーバーフローを回避するために再帰関数を末尾再帰の形式に変換する方法について学んでいると思います。Guile では他のプログラミング言語とは事情が異なり再帰をしてもシステムのメモリを使い尽すまではスタックオーバーフローが起きません(Racket も同様)。なので、一部の例外を除いて Guile でプログラムを書くときは無理に末尾再帰に変形せずに分かりやすくて綺麗な再帰のままにしましょう。

自然な再帰と末尾再帰の比較

リストの長さを計算する再帰的な手続き length

例としてリスト 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

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

mapmap-tail のメモリ効率の違いについて検討してみましょう。map の手続きは map の呼び出しをするたびにコールスタックを消費し、不足した場合にはコールスタックを拡張するため x が長い場合にはメモリを消費する場合があります。それに対して map-tail はどうでしょうか。map-tail では result 引数を (cons (f (car x)) result) によって置き換えています。よって map-tail でも再帰するたびにメモリを消費していきます。上記から mapmap-tailmap がコールスタックを消費するから 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 の計算が再度実行された場合に正常に動作しなくなるという問題が指摘されています)。

自然な再帰だと計算量が爆発してしまうケース

ここまでの例では Guile でなら自然な再帰で良いと言える例だったのですが、何でもそうという訳ではありません。たまに自然な再帰だと計算量が爆発的に大きくなってしまう場合がありそういった場合には別のアルゴリズムに変更する必要があります。

リストを反転する手続き

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

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

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

おわりに

Guile ではシステムのメモリを使い尽すまではスタックオーバーフローは起きないので、一般には自然な再帰をわざわざ末尾再帰の形式に変換してプログラムを読みにくくする必要はありません。末尾再帰に書き換えなくて済むプログラミングライフは大変快適なので、Guile のような再帰でスタックオーバーフローの起こさないプログラミング言語や処理系を探して使ってみてください。