「末尾再帰への書き換え」の弊害について
目次
1. はじめに
Lisp Advent Calendar 2024 の25日目の記事です。
美しい再帰手続き(再帰関数)を 分かりにくい末尾再帰(反復アルゴリズム)に変換することなく、 そのままの美しさを保つことを推奨します。
深くネストした再帰に起因するスタックオーバーフローは、 プログラミング言語の処理系が課す厳しい制約であり、 無条件に認めるべき前提ではありません。
深くネストした再帰をサポートしている処理系であれば、 可読性に優れた美しい再帰手続きが書けます。
一般的なタイトルを付けましたが、 本記事では Scheme の処理系についてのみ調査しています。
本当は Scheme に限定した記事を書くつもりだったのですが、 主題自体は一般的な内容であり、 スタックオーバーフローするから末尾再帰にすることを推奨する書籍や記事が無数にあるため、 意図的に一般化したタイトルとしました。
本記事は過去記事の「Guile ではスタック溢れを気にせず再帰しよう」 を一般化したタイトルに変更し、再帰の美しさの説明を強化したバージョンです。
2. 再帰の何がよいのか
再帰手続きは再帰的な構造したデータを対象に 計算を行なうのに方法です。
再帰的なデータ構造の処理を再帰で扱うと、 宣言的な記述で処理を定義でき、 停止性の条件を満たしつつ、 正しく式を書き換えるだけで再帰関数を定義できます。
読む場合も式の書き換えが正しいことに 納得すればそれだけで再帰手続きを理解できます。
これが再帰の力であり美しさです。
再帰手続きの何がよいのかを説明している章であるため、 再帰が美しく分かりやすい記述であると納得している方は、 この章は飛ばしてしまって問題ありません。
2.1. 再帰的なデータ構造
まず再帰的なデータ構造について本記事で扱うものを紹介します。
2.1.1. リスト
Scheme におけるリストは次のように定義できます。
- 空リストはリストである
- cdr部がリストのペアはリストである
2.1.2. 自然数
ここでは自然数は 0
から始まるとします。
自然数も次のように再帰的にデータ構造として定義できます。
(数学的に厳密な自然数の定義については「ペアノ公理系」を参照してください)
0
は自然数である- 自然数の「次の」数も自然数である
2.2. 再帰手続きは宣言的記述
綺麗な再帰手続きは、 計算の手順を記述したものとしてではなく、 宣言的な定義として読めます。
たとえばリストを連結する手続きを Scheme で書いてみましょう。
(define (my-append lst1 lst2) (if (not (pair? lst1)) (if (null? lst1) lst2 (error "my-append: 入力は真リストでなければなりません" lst1)) (cons (car lst1) (my-append (cdr lst1) lst2))))
この定義では lst1
の値によって3つの場合に分けて、
それぞれ (my-append lst1 lst2)
をどのように置き換えるかということを記述しています。
ここでは、二つの式「 x
と y
が等しい」を (equal? x y)
、「 p
ならば q
」を (implies p q)
と表現することにします。
;; 1. lst1 がペアでなくかつ lst1 が null? (空リスト)場合 ;; (null? lst1) より lst1 は '() (implies (and (not (pair? lst1)) (null? lst1)) (equal? (my-append '() lst2) lst2)) ;; 2. lst1 がペアでなく空リストでもないときはエラー ;; lst1 はリストでないため入力エラーとする (implies (and (not (pair? lst1)) (not (null? lst1))) (equal? (my-append lst1 lst2) (error "my-append: 引数は真リストでなければなりません" lst1))) ;; 3 lst1 がペアのとき、(my-append lst1 lst2) と (cons (car lst1) (my-append (cdr lst1) lst2)) は等しい (implies (pair? lst1) (equal? (my-append lst1 lst2) (cons (car lst1) (my-append (cdr lst1) lst2))))
1番目と2番目は自明です。
1番目は空リストと他のリストを連結した場合は変化しないということを意味しています。
2番目は lst1
がリストではなかった場合です。
この場合は引数がリストであるという前提に違反しているのでエラーでよいでしょう。
問題は3番目です。
equal?
の部分が真でよいのか考えてみましょう。
3番目のケースは lst1
を先頭の要素 (car lst1)
と
残りのリスト (cdr lst1)
に分割しています。
私が想像しているリストの連結では lst1
がペアなら
(my-append lst1 lst2)
もペアであるです。
そのため、両辺を car
, cdr
で二つに分けてそれぞれ考えましょう。
;; 1. lst1 と lst2 を連結したとき、最初の要素は lst1 の最初の要素と等しい (implies (pair? lst1) (equal? (car (my-append lst1 lst2)) (car lst1))) ;; 2. lst1 と lst2 を連結したとき先頭を除いたリストは ;; lst1 の先頭を除いたリストと lst2 を連結したものと等しい (implies (pair? lst1) (equal? (cdr (my-append lst1 lst2)) (my-append (cdr lst1) lst2)))
以上の二つですが、 (my-append lst1 lst2)
が「リストの連結」
を意味しているのであれば、その性質から真であるべきです。
このように定義は意図した通りであると確認できました。
しかし、再帰的定義では単に書き換えが意図したものであれば、 いいわけではないことに注意が必要です。 再帰手続きはうまく定義しないと計算が終了しない可能性があります。 計算が終了しないのは致命的なバグですので、 停止することを確認する必要があります。
これを確認するには手続き内の全ての再帰呼び出しについて確認する必要があります。
今回は (my-append (cdr lst1) lst2)
にフォーカスするとよいです。
my-append
の一つ目の引数では、
リストの要素数を一つ減らしていることに注目してください。
リスト要素数は減少を繰り返すといずれ必ず長さの最小値である0に到達します。
長さが0のリストは pair?
ではなく pair?
でない場合は再帰呼び出しをしないため、
my-append
は必ず停止します。
以上のように停止性についての考慮は必要ではありますが、 それさえ確認ができれば再帰手続きの正当性を確かめるのに必要なのは、 それぞれのケースにおいて式の書き換えが妥当であるということだけです。
計算量に対する考察も必要ではあるのですが、 この式が何やっているかという点については、 式を見れば分かるという程度の性質のものであり、 計算の流れを追いかけないと分からないというものではないのです。
これこそが再帰による記述の強みです。 再帰は理解が容易で検証が簡単なプログラムの書き方なのです。
「末尾再帰への書き換え」 は再帰アルゴリズムの優れた性質を大きく損なうし、 計算効率上の利点もないケースが多くあるので、 必要ないならやめた方がいいというのが本記事の主張です。
3. 末尾再帰への書き換えとは何か
末尾再帰への書き換えとは、 以上のように自然に書いた再帰関数を、 スタックオーバーフローのリスクを回避するために、 末尾再帰に書き換えることです。
たとえば、リストの要素をそれぞれ手続き proc
で変換したリスト作成する my-map
手続きを考えてみましょう。
(define (my-map proc lst) (if (not (pair? lst)) '() (cons (proc (car lst)) (my-map proc (cdr lst)))))
も先程と同じように以下のように、
リスト を car
と cdr
に分けて確認すれば、
正しく定義できていることを確認できます。
((not (pair? lst))
の場合は自明のため省略)
(implies (pair? lst) (equal? (car (my-map f lst)) (f (car lst)))) (implies (pair? lst) (equal? (cdr (my-map f lst)) (my-map f (cdr lst))))
しかし、
多くの書籍や記事ではこのまま書き方では問題があるとしています。
lst
のリストが長い場合に、
スタックオーバーフローが発生して実行時エラーとなる可能性があるからです。
この場合は末尾呼び出しが最適化されることが前提となりますが、
以下のように書き換えるよう推奨されます(ループでもよいです)。
(define (my-map-tail proc lst) (%my-map-tail proc lst '())) (define (%my-map-tail proc lst acc) (if (not (pair? lst)) (reverse acc) (%my-map-tail proc (cdr lst) (cons (proc (car lst)) acc))))
さて、この %my-map-tail
についていままでと同様に考えてみましょう
(not (pair? lst))
の場合は (reverse acc)
です。
まず、この時点で「 acc
って何?」と思いませんか?
これは my-map
が (not (pair? lst))
の場合について、
解説が省略されるほど自明であったのとは対照的です。
acc
を理解するには、 (pair? lst)
の場合について先に考える必要があります。
(pair? lst)
の場合はこうなります。
(implise (pair? lst) (equal? (%my-map-tail proc lst acc) (%my-map-tail proc (cdr lst) (cons (proc (car lst)) acc))))
いままでと同様に car
と cdr
で分けてみましょう。
(implise (pair? lst) (equal? (car (%my-map-tail proc lst acc)) (car (%my-map-tail proc (cdr lst) (cons (proc (car lst)) acc))))) (implise (pair? lst) (equal? (cdr (%my-map-tail proc lst acc)) (cdr (%my-map-tail proc (cdr lst) (cons (proc (car lst)) acc)))))
いままではこれで簡単に理解できたのに、
car
と cdr
で場合分けしてみても何も分かりませんでした。
このアプローチは末尾再帰に変換したアルゴズムの前には無力です。
この手続きを理解するには、 引数の状態の変化に着目する必要があります。
再帰呼び出しのたびに、 引数の状態は次のように変化していきます。
lst
- 先頭要素を取り除く
acc
lst
の先頭要素に手続きproc
を呼び出した結果をacc
の先頭に追加
これを繰り返すと、 lst
が空になったときには、
acc
に最初の lst
に入っていた要素が全て proc
の計算結果になって
入っています。 ただし、順番は逆順となっています。
逆になっていると困るということで、
最後に reverse
手続きで順番を元に戻しているのです。
このアルゴリズは以上のように「計算の流れ」を追跡しないと理解できません。
特に (pair? lst)
の場合とそうでない場合が独立しておらず、
相互に依存しあっているので複雑です。
実は my-map
と %my-map-tail
が同じ計算をすることは、
数学的帰納法のテクニックを使うことで証明可能です。
なので、「計算の流れ」を追跡しなくても、 my-map
と同じであることを示せば理解可能なのですが、
だからといってこれが一目みて確かだと思えるようなものではないという
のは間違いありません。
よく言われる「末尾再帰への書き換え」は、 明らかに正しかった再帰的な定義を一見して正しいのかよく分からない 複雑な記述へと書き換えているのです!
3.1. 末尾再帰への書き換えはループへの書き換えである
「末尾再帰への書き換え」と言われますが、 やっていることはループへの書き換えです。
Scheme には名前付きletという構文があり、 以下のようにも書けます。
(define (my-map-tail proc lst) (let loop ((lst lst) (acc '())) (if (not (pair? lst)) (reverse acc) (loop proc (cdr lst) (cons (proc (car lst)) acc)))))
これもまた末尾再帰なのですが、
ほぼほぼループ構文みたいな記述になります。
なお、名前付き let
を使って末尾再帰でない再帰手続きを書くことも可能なので
そこは注意してください。
さらに、Scheme の do
という繰り返し用の構文を使って
書くこともできます。
(define (my-map-tail proc lst) (do ((lst lst (cdr lst)) (acc '() (cons (proc (car lst)) acc))) ((not (pair? lst)) (reverse acc))))
Scheme では do
も実態としては末尾再帰をしているのですが、
こちらはより繰り返し機能にフォーカスした構文となっています。
これら全部同じです。 末尾再帰への書き換えとかいっていますが、 ようするにループへの書き換えです。 末尾再帰への書き換えの実態はループへの書き換えです。
繰り返しよりも末尾再帰の方が好きなんだ! と思う方もいるかもしれませんが、 残念ながらこの使い方においてはループと同じです。
4. 計算の効率はどうなのか
「末尾再帰の方が計算効率がよい」ために、 末尾再帰を採用するのであって、スタックオーバーフローの 回避のためだけではないという意見もあるでしょう。
前述した my-map
と %my-map-tail
を比較します。
この二つではどちらが効率的でしょうか?
(ここでは proc
呼び出しの処理は無視して比較します)
なお、 my-map
と %my-map-tail
の計算量の違いというのは、
わずかでありオーダー記法で比較しても無意味なレベルなので
空間使用量やステップ数を推定してどちらが速そうか検討します。
my-map
を再掲します。
(define (my-map proc lst) (if (not (pair? lst)) '() (cons (proc (car lst)) (my-map proc (cdr lst)))))
my-map
を再帰呼び出しをする度に、
呼び出し元を記憶するためにコールスタックに push する必要があります。
また、残りの処理ではコールスタックを pop しながら戻り、
それぞれ残りの処理で cons
していきます。
%my-map-tail
を再掲します。
(define (my-map-tail proc lst) (%my-map-tail proc lst '())) (define (%my-map-tail proc lst acc) (if (not (pair? lst)) (reverse acc) (%my-map-tail proc (cdr lst) (cons (proc (car lst)) acc))))
手続きの中では %my-map-tail
は末尾呼び出しされているので、
Scheme では呼び出した後に戻ってきません。
言語処理系はコントロールスタックを必要としません。
その代わりに acc
に対して cons
しています。
この acc
変数への cons
がスタックを積む代わりの操作となっています。
lst
が空になったときに 全部の計算結果が acc
に入ります。
my-map
のときは lst
が空になった後は、
「残りの計算」を開始しましたが、
%my-map-tail
では lst
が空になった時点で最後のステップとなります。
しかし、 acc
は期待しているリストとは順番が逆になるので、
リストは reverse
で反転させないといけません。
このとき acc
の長さ分のペアが作られます(cons
されます)。
lst
の要素数を n
として比較してみると、
my-map
ではコールスタックに積む操作が、
n
回で cons
が n
回なのに対し、
%my-map-tail
では cons
が 2n
回です。
my-map
の方が通常メモリ確保済みのスタックを使えるのに対して、
%my-map-tail
ではヒープ領域を確保しながら
メモリ割り当てしないといけないので遅そうです。
なお、 (srfi 1)
の線形更新版の reverse!
を使用すれば新規にペア作る必がない分 %my-map-tail
の方が有利になります。
(define (%my-map-tail/reverse! proc lst acc) (if (not (pair? lst)) (reverse! acc) (%my-map-tail/reverse! proc (cdr lst) (cons (proc (car lst)) acc)))) (define (my-map-tail/reverse! proc lst) (%my-map-tail/reverse! proc lst '()))
この場合 reverse!
では新規の cons
もしないし、
reverse!
は末尾再帰で実装できるのでスタックも使わないため最も速そうです。
一見問題なさそうではありますが、
Scheme だと継続安全(continuation-safe)ではなくなるという問題があります(
continuation-safe は安全はGuile のドキュメントの6.26.3.4 Stack Overflow から引用)。
my-map-tail
で reverse!
を使うと、
acc
が壊れます。Scheme だと proc の中の継続が外から呼ばれる可能性があり、
acc
の副作用が検出可能であり、
こういった破壊的な手続きの使用には注意が必要です。
また、Racket では変更不能なペアを使うため、
そもそも reverse!
を定義できないという問題があります。
5. そもそも「末尾再帰への書き換え」とはいえないケース
アルゴリズムが全然違うので、 本記事で解説している 「末尾再帰への書き換え」とは異なるケースについて説明します。
5.1. フィボナッチ数の計算
末尾再帰でないフィボナッチ数の計算を
(define (fib n) (cond ((<= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2))))))
として、末尾再帰版を
(define (fib-tail n a b) (if (<= n 0) a (fib-tail (- n 1) b (+ a b))))
とするものがあります。
一目瞭然ですが、両者では計算方法がまったく違います。
そもそも fib
は木構造的な再帰をしているのに、
fib-tail
は繰り返し処理になっています。
このように全然違うものについて比較して、 末尾再帰の方がよいとするのは 本記事の主題とは関係のない話です。
5.2. 非末尾再帰版の reverse
これは Lisp のリストに慣れていないとやってしまう 可能性のある大きな間違いです。 これは、アルゴリズムが致命的な欠陥を抱えているという問題であり、 「末尾再帰に書き換える」という話ではありません。
(define (heavy-reverse lst) (if (not (pair? lst)) '() (append (heavy-reverse (cdr lst)) (list (car lst)))))
この定義は論理的には問題がなく、
意図した通りに lst
を反転したリストを求めます。
しかし、リストの特性を考慮すると致命的な欠陥となります。
再帰手続きの帰納部に (append x (list e))
という構造がの式があるのはとてもよくないです。
cons
は一つペアを作る手続きなのに対し、
(append x y)
は (legnth x)
個のペアを作る操作です。
この操作を再帰的に適用してまうと、
大量のペアを作成することとなり大変なことになってしまいます。
Scheme のリストは左側に要素を追加するのと右側に要素を追加するのは、 まったく異なるので気をつけましょう。 右に要素を追加したいと思ったら、 回避する方法がないか検討することをおすすめします。
6. 末尾再帰が自然なケース
私はここまで末尾再帰への書き換えをしないように主張してきましたが、 末尾再帰そのものが悪いわけではありません。
処理の目的上必然的に末尾再帰になる場合も多々あり、 そのようなケースについては当然そのまま末尾再帰にするのがよいでしょう。
一例として reverse-append
を定義してみます。
これは (reverse-append x y)
は y
に
x
を反転したリストを連結する手続きです。
(define (reverse-append lst1 lst2) (if (not (pair? lst1)) (if (null? lst1) lst2 (error "reverse-append: 真リストを期待しています" lst1)) (reverse-append (cdr lst1) (cons (car lst1) lst2))))
reverse-append
ですが、 lst1
が空リストの場合とそうでない場合に分けて検討してみましょう。
((not (pair? lst1))
かつ (not (null? lst1))
の場合は省略)
(implies (and (not (pair lst)) (list? lst)) (equal? (reverse-append lst1 lst2) lst2)) ;; 2 (implies (pair lst) (equal? (reverse-append lst1 lst2) (reverse-append (cdr lst1) (cons (car lst1) lst2))))
これだと1番目は計算の目的から明らかに正しいですね。
問題は2番目ですが、
これは、「 lst2
に lst1
のリストの先頭要素を追加したものに、
lst1
の最初の要素を取り除いたリストを反転して連結したもの」と、
「 lst2
に lst1
を反転して連結したもの」が等しいと主張しています。
まあこれは正しいでしょう。
再帰手続きの説明の難しさに、
当然すぎてそれをどう説明すればいいのかよく分からないというのがありますが、
reverse-append
もその程度には美しい定義なのです。
%my-map-tail
のときとは何が違うのでしょうか。
再掲します。
(define (my-map-tail proc lst) (%my-map proc lst '())) (define (%my-map-tail proc lst acc) (if (not (pair? lst)) (reverse acc) (%my-map-tail proc (cdr lst) (cons (proc (car lst)) acc))))
比較すると、 reverse-append
の lst2
は
reverse-append
の機能に必然的に必要な変数なのに対し、
%my-map-tail
の acc
は my-map-tail
の
「リスト lst
を手続き proc
で写したリストを求める」
という主要な機能とは何ら関係のない変数です。
つまり acc
が手続きの機能と何ら関係ないゆえに分かりにくくなるのです。
それに対して reverse-append
の
「 lst2
に lst1
を反転して連結したリストを作る」という機能には
lst2
は必然的に必要な変数であり自然なのです。
それが %my-map-tail
と reverse-append
の違いであり、
末尾再帰による実装でも reverse-append
手続きにとって主要な意味を持っていれば自然と理解できます。
ちなみに、リストを反転する手続き reverse
は
reverse-append
の特別な場合だと考えられます。
(define (my-reverse lst) (reverse-append lst '()))
7. 末尾再帰にした方に効率がよいケース
スタックオーバーフローを起こさない処理系では、 スタックがあふれそうになったタイミングでスタックを拡張するため、 ヒープ領域のメモリを確保します。 この点でメモリ使用量が大きくなるため、可読性は下がりますが末尾再帰の方がよいです。 「末尾再帰への変換をやめよう」はスタックの替わりとなる構造を、 プログラマが明示的に扱わないといけない場合についてパフォーマンス的にも正当化されます。
そのため、末尾再帰に変換する際にコールスタックを積む分について、 替わりとなるスタックを用意しなくてよいような場合は末尾再帰にした方が効率がよくなります。
以下のようにリストの長さを求める手続き
my-length
を定義してみます。
(define (my-length lst) (if (not (pair? lst)) (if (null? lst) 0 (error "my-length: リストではありません" lst)) (+ 1 (my-length (cdr lst)))))
my-length
を求めるのに、
my-length
手続きが lst の長さの分だけ呼ばれるため、
無駄にスタックに積まれていき、
無駄に (+ 1 _)
の計算をするために戻っていかないとけません。
それに対して以下の my-length-tail
はどうでしょうか?
(define (my-length-tail lst acc) (if (not (pair? lst)) (if (null? lst) acc (error "my-length-tail: リストではありません" lst)) (my-length-tail (cdr lst) (+ 1 acc))))
my-length-tail
ではスタックに積む必要もなく、戻る処理もありません。
以上により、 my-length-tail
の方が効率的です。
8. 深い再帰がかけるのは言語機能である
スタックオーバーフローが起きるかどうかは 処理系に依存する問題だから避けた方がよいという 立場もあるかもしれません。
しかし、むしろ深くネストした再帰を書ける という言語機能を提供しているかいないかと考えるべきです。
たとえば、あなたが再帰下降パーサを実装して JSON 構文をパースするプログラムを書いているとします。
再帰手続きを使って自然に実装すると、 次のような深くネストした JSON をパースする場合に 再帰のネストも深くなるはずです。
[[ … [[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]] … ]]
このようなケースで、 スタックオーバーフローの懸念がある場合には、 シンプルで美しい実装するのを諦めて、 スタックを用意して明示的に状態管理をするはめになります。
コードは無駄に複雑化し、 最初の実装よりも可読性が 大幅に低下することは避けられません。 これは再帰に課せられた本質的な制約ではありません。 言語処理系が深くネストした再帰をサポートしていない ということが問題なのです。
末尾呼び出し最適化があるかどうかで、 プログラムの書き方を大きく変化させてしまうのと同様に、 深くネストした再帰が書けるのかどうかも、 プログラムの書き方を大幅に変えてしまうのです。
もしも、あなたが再帰を重視するのであれば、 簡単にスタックオーバーフローを引き起してしまう、 言語処理系を避けて、 シンプルな再帰手続きを書くことを推奨します。
9. 深くネストした再帰をサポートするScheme処理系
9.1. 検証方法
1千万回のネストでスタックオーバーフローすると仮定して、 テストして問題ないか検証しました。
下記のコードを実行して正常に返ってくるかを確認します。
(let f ((i 10000000)) (if (= i 0) 0 (+ i (f (- i 1)))))
OS は GNU Guix System です。
検証時の ulimit -s
の値は 9788
でした。
$ ulimit -s 9788
以下の通り、C言語のコードでは 100万回のネストでスタックオーバーフローしたため、 Scheme での検証では余裕を持って1000万回のネストに耐えられるかを検証します。
$ cat sum.c #include <stdio.h> #include <stdlib.h> long long sum(long long n) { if (n <= 0) { return 0; } else { return n + sum(n - 1); } } int main(int argc, char **argv) { long n = atol(argv[1]); printf("result: %ld\n", sum(n)); return 0; } $ guix shell gcc -- gcc sum.c -o sum $ ./sum 100000 result: 5000050000 $ ./sum 1000000 Segmentation fault $
9.2. それぞれの処理系での検証
検証した処理系についてですが、 2024/12/25 現在で GNU Guix で簡単にインストールして動かすことのできた処理系に限定して調査しました。
こちらのリストは今後更新していこうと思います。
9.2.1. GNU Guile
GNU Guile のドキュメントの6.26.3.4 Stack Overflow にGNU Guile にはスタックのリミットがないとの記載があります。 ドキュメントに明示的に記載があるため、 GNU Guile のこの振舞いは偶然のものではなくて、 処理系の仕様であると解釈できます。
また、 call-with-stack-overflow-handler
手続きを使うことで、
スタックに制限をかけてさらに、
制限にかかった場合にハンドリングすることもできます。
GNU Guile に閉じている限りは再帰のネストに制限がなく、 必要であれば制限をかけることができハンドリング可能ということで、 理想的なパターンといえます。
$ guix shell guile@3 -- guile GNU Guile 3.0.9 Copyright (C) 1995-2023 Free Software Foundation, Inc. Guile comes with ABSOLUTELY NO WARRANTY; for details type `,show w'. This program is free software, and you are welcome to redistribute it under certain conditions; type `,show c' for details. Enter `,help' for help. scheme@(guile-user)> (let f ((i 10000000)) (if (= i 0) 0 (+ i (f (- i 1))))) $1 = 50000005000000 scheme@(guile-user)>
9.2.2. Racket
Racket には 2.3 Lists, Iteration, and Recursion に記載があります。
$ guix shell racket -- racket
Welcome to Racket v8.14 [cs].
> (let f ((i 10000000)) (if (= i 0) 0 (+ i (f (- i 1)))))
50000005000000
9.2.3. Gauche
以下の検証コードを使って、スタックオーバーフローするか確認します。
(let f ((i 10000000)) (if (= i 0) 0 (+ i (f (- i 1)))))
スタックオーバーフローするなら、 1千万回ネストした再帰を実行すればさすがに溢れると仮定して、 検証します。
結果は以下の通りで、深いネストをサポートしています。
$ guix shell gauche -- gosh -V Gauche scheme shell, version 0.9.15 [utf-8,pthreads], x86_64-unknown-linux-gnu (version "0.9.15") (command "gosh") (scheme.id gauche) (languages scheme r5rs r7rs) (encodings utf-8) (website "https://practical-scheme.net/gauche") (build.platform "x86_64-unknown-linux-gnu") (build.configure "CONFIG_SHELL=/gnu/store/3jhfhxdf6v5ms10x5zmnl166dh3yhbr1-bash-minimal-5.1.16/bin/bash" "SHELL=/gnu/store/3jhfhxdf6v5ms10x5zmnl166dh3yhbr1-bash-minimal-5.1.16/bin/bash" "--prefix=/gnu/store/jawf840rbncdfrjc05fnf04lgd6bz2sm-gauche-0.9.15" "--enable-fast-install" "--build=x86_64-unknown-linux-gnu" "--with-slib=/gnu/store/sk1c72ffl712ky8rkkm6vv0wi4jshiqz-slib-3c1/lib/slib" "--with-tls=mbedtls" "build_alias=x86_64-unknown-linux-gnu") (scheme.path "/gnu/store/jawf840rbncdfrjc05fnf04lgd6bz2sm-gauche-0.9.15/share/gauche-0.98/site/lib" "/gnu/store/jawf840rbncdfrjc05fnf04lgd6bz2sm-gauche-0.9.15/share/gauche-0.98/0.9.15/lib") (threads pthreads) (gauche.net.tls mbedtls) $ guix shell gauche -- gosh gosh> (let f ((i 10000000)) (if (= i 0) 0 (+ i (f (- i 1))))) 50000005000000 gosh>
9.2.4. Chez Scheme
1000万回でもスタックオーバーフローしません。
$ guix shell chez-scheme -- scheme Chez Scheme Version 10.1.0 Copyright 1984-2024 Cisco Systems, Inc. > (let f ((i 10000000)) (if (= i 0) 0 (+ i (f (- i 1))))) 50000005000000 >
9.2.5. Chicken Scheme
Chicken Scheme ではインタプリタとコンパイラの両方を確認します。
- インタプリタ
$ guix shell chicken -- csi CHICKEN (c) 2008-2022, The CHICKEN Team (c) 2000-2007, Felix L. Winkelmann Version 5.4.0 (rev 1a1d1495) linux-unix-gnu-x86-64 [ 64bit dload ptables ] Type ,? for help. #;1> (let f ((i 10000000)) (if (= i 0) 0 (+ i (f (- i 1))))) 50000005000000 #;2>
- コンパイラ
$ cat sum.scm (display (let f ((i 10000000)) (if (= i 0) 0 (+ i (f (- i 1)))))) (newline) $ guix shell chicken -- csc sum.scm $ ./sum 50000005000000 $
9.2.6. Gambit-C
- インタプリタ
私の環境だと インタプリタで 1千万で試すと、 結果が返ってこなかったのですが、一桁少ない百万であれば大丈夫でした。
$ guix shell gambit-c -- gsi Gambit v4.9.5 > (let f ((i 1000000)) (if (= i 0) 0 (+ i (f (- i 1))))) 500000500000 >
- コンパイラ
gsc
でコンパイルしたところ、 1千万でも問題なく実行できました。$ guix show gambit-c name: gambit-c version: 4.9.5 outputs: + out: everything systems: x86_64-linux i686-linux dependencies: location: gnu/packages/scheme.scm:561:2 homepage: http://www.gambitscheme.org/ license: LGPL 2.1+, ASL 2.0 synopsis: Efficient Scheme interpreter and compiler description: Gambit consists of two + main programs: gsi, the Gambit Scheme + interpreter, and gsc, the Gambit Scheme + compiler. The interpreter contains the + complete execution and debugging + environment. The compiler is the + interpreter extended with the + capability of generating executable + files. The compiler can produce + standalone executables or compiled + modules which can be loaded at run + time. Interpreted code and compiled + code can be freely mixed. $ cat sum.scm (display (let f ((i 10000000)) (if (= i 0) 0 (+ i (f (- i 1)))))) (newline) $ guix shell gcc gambit-c -- gsc -exe sum $ ./sum 50000005000000 $
9.2.7. Chibi-Scheme
百万のネストでスタックオーバーフローしました。
$ guix shell chibi-scheme -- chibi-scheme -V chibi-scheme 0.11.0 "sodium" (chibi chibi-0.11.0 r7rs ratios complex mini-float uvector threads full-unicode modules dynamic-loading linux x86_64 little-endian) $ guix shell chibi-scheme -- chibi-scheme > (let f ((i 10000000)) (if (= i 0) 0 (+ i (f (- i 1))))) ERROR: out of stack space > (let f ((i 1000000)) (if (= i 0) 0 (+ i (f (- i 1))))) ERROR: out of stack space > (let f ((i 100000)) (if (= i 0) 0 (+ i (f (- i 1))))) 5000050000 >
9.2.8. Bigloo
セメンテーション違反が発生してエラーとなりました。
(出力にメールアドレスが含まれていたため @
を空白に置換しました)
$ guix shell bigloo -- bigloo ------------------------------------------------------------------------------ Bigloo (4.3g) ,--^, `a practical Scheme compiler' _ ___/ /|/ Thu 27 Feb 2020 07:59:49 AM CET ,;'( )__, ) ' Inria -- Sophia Antipolis ;; // L__. email: bigloo lists-sop.inria.fr ' \ / ' url: http://www-sop.inria.fr/indes/fp/Bigloo ^ ^ ------------------------------------------------------------------------------ 1:=> (let f ((i 10000000)) (if (= i 0) 0 (+ i (f (- i 1))))) *** ERROR:bigloo: `segmentation violation' exception -- raised 1. \@f toplevel, stdin:1 2. \@f toplevel, stdin:1 3. \@f toplevel, stdin:1 4. \@f toplevel, stdin:1 5. \@f toplevel, stdin:1 6. \@f toplevel, stdin:1 7. \@f toplevel, stdin:1 8. \@f toplevel, stdin:1 9. \@f toplevel, stdin:1 10. \@f toplevel, stdin:1 1:=> (let f ((i 1000000)) (if (= i 0) 0 (+ i (f (- i 1))))) *** ERROR:bigloo: `segmentation violation' exception -- raised 1. \@f toplevel, stdin:2 2. \@f toplevel, stdin:2 3. \@f toplevel, stdin:2 4. \@f toplevel, stdin:2 5. \@f toplevel, stdin:2 6. \@f toplevel, stdin:2 7. \@f toplevel, stdin:2 8. \@f toplevel, stdin:2 9. \@f toplevel, stdin:2 10. \@f toplevel, stdin:2 1:=> (let f ((i 100000)) (if (= i 0) 0 (+ i (f (- i 1))))) *** ERROR:bigloo: `segmentation violation' exception -- raised 1. \@f toplevel, stdin:3 2. \@f toplevel, stdin:3 3. \@f toplevel, stdin:3 4. \@f toplevel, stdin:3 5. \@f toplevel, stdin:3 6. \@f toplevel, stdin:3 7. \@f toplevel, stdin:3 8. \@f toplevel, stdin:3 9. \@f toplevel, stdin:3 10. \@f toplevel, stdin:3 1:=> (let f ((i 10000)) (if (= i 0) 0 (+ i (f (- i 1))))) 50005000 1:=>
9.2.9. MIT-Sceheme
最大の再帰の深さを越えたとエラーになりました。 10万なら大丈夫のようです。
$ guix shell mit-scheme -- mit-scheme MIT/GNU Scheme running under GNU/Linux Type `^C' (control-C) followed by `H' to obtain information about interrupts. Copyright (C) 2020 Massachusetts Institute of Technology This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. Image saved on Sunday March 7, 2021 at 3:24:56 PM Release 11.2 || SF || LIAR/x86-64 1 ]=> (let f ((i 10000000)) (if (= i 0) 0 (+ i (f (- i 1))))) ;Aborting!: maximum recursion depth exceeded 1 ]=> (let f ((i 1000000)) (if (= i 0) 0 (+ i (f (- i 1))))) ;Aborting!: maximum recursion depth exceeded 1 ]=> (let f ((i 100000)) (if (= i 0) 0 (+ i (f (- i 1))))) ;Value: 5000050000 1 ]=>
9.2.10. Scheme48
1000万だとエラーになりました。
10万なら大丈夫のようです。
(出力にメールアドレスが含まれていたため @
を空白に置換しました)
$ guix shell scheme48 -- scheme48 Welcome to Scheme 48 1.9.2 (made by *GOK* on 2024-06-18) See http://s48.org/ for more information. Please report bugs to scheme-48-bugs s48.org. Get more information at http://www.s48.org/. Type ,? (comma question-mark) for help. > (let f ((i 10000000)) (if (= i 0) 0 (+ i (f (- i 1))))) gc: Scheme 48 heap overflow (max heap size 4000000 cells) $ guix shell scheme48 -- scheme48 Welcome to Scheme 48 1.9.2 (made by *GOK* on 2024-06-18) See http://s48.org/ for more information. Please report bugs to scheme-48-bugs s48.org. Get more information at http://www.s48.org/. Type ,? (comma question-mark) for help. > (let f ((i 10000)) (if (= i 0) 0 (+ i (f (- i 1))))) 50005000 > (let f ((i 100000)) (if (= i 0) 0 (+ i (f (- i 1))))) 5000050000 > (let f ((i 1000000)) (if (= i 0) 0 (+ i (f (- i 1))))) gc: Scheme 48 heap overflow (max heap size 4000000 cells)
9.2.11. STklos
スタックサイズは固定のようですが、 起動時のオプションで拡張できるようです。
デフォルトで問題がありそうなので、
末尾再帰への変換が不要とはいえなそうです。
(出力にメールアドレスが含まれていたため @
を空白に置換しました)
$ guix shell stklos -- stklos \ STklos version 2.10 (stable) \ Copyright (C) 1999-2024 Erick Gallesio <eg stklos.net> / \ [Linux-6.10.14-gnu-x86_64/pthreads/readline/utf8] / \ Type ',h' for help stklos> (let f ((i 100000)) (if (= i 0) 0 (+ i (f (- i 1))))) Received a SIGSEGV signal. Try to augment stack size (--stack-size option). If the problem persists, fill an issue report on https://github.com/egallesio/STklos/issues $ guix shell stklos -- stklos --stack-size=10000000 \ STklos version 2.10 (stable) \ Copyright (C) 1999-2024 Erick Gallesio <eg stklos.net> / \ [Linux-6.10.14-gnu-x86_64/pthreads/readline/utf8] / \ Type ',h' for help stklos> (let f ((i 100000)) (if (= i 0) 0 (+ i (f (- i 1))))) 5000050000 stklos>
9.3. 検証結果のまとめ
それぞれの検証結果としては以下のようになりました。 スタックオーバーフローしないものについて、 ドキュメントでの記載があるか調べたのですが、 私が調査した限り見つけられなかったものは「不明」としています。
言語処理系 | 1000万ネストした再帰 | ドキュメント | 備考 |
---|---|---|---|
GNU Guile | 可能 | 記載あり | |
Racket | 可能 | 記載あり | |
Gauche | 可能 | 不明 | |
Chez Scheme | 可能 | 不明 | |
Chicken Scheme | 可能 | 不明 | |
Gambit-C | 可能 | 不明 | |
Chibi Scheme | 不可 | ||
Bigloo | 不可 | ||
MIT-Scheme | 不可 | ||
Scheme48 | 不可 | ||
STklos | 不可 | 起動時のオプションでスタックサイズを設定可能 |
以上から、Scheme では深くネストしても スタックオーバーフローしない処理系が多くあることを確認できました。
ドキュメントでの記載が確認できている状態であれば、 気にすることなく再帰手続きで実装しても問題なさそうです。
10. おわりに
再帰でスタックオーバーフローが起きるということを、 当然の前提として受け入れる必要はなく、 深くネストした再帰をサポートした処理系であれば、 「末尾再帰への変換」をせずにそのままの 美しさを保つことができます。
末尾再帰への変換には宣言的な記述を損なう弊害があり、 そのままの再帰の形を維持することの価値が伝わっていれば幸いです。
11. 変更履歴
- タイトルを『「末尾再帰への書き換え」をやめよう!』から『「末尾再帰への書き換え」の弊害について』に変更。強く主張しすぎたと深く後悔したため。
my-map-tail
で最後のreverse
をするとGC時間が増加してしまい結果的に実行時間が長くなるという事象は条件を変えても発生し、cons
のコストが実行時間に影響を与えるとはいえそうなのですが、これとmy-map
がスタックを多く消費している場合に実行時間に与える影響について公平に比較するのは難しく諦めました。拡張されたスタックが使い回されるためにmy-map
を繰り返すベンチマークはそもそもmy-map
が有利になるという問題もありそうです。 以上から、my-map
とmy-map-tail
については理屈上は時間計算量、空間計算量に大きな差はない(はず)と主張するだけに留めることにしました。
4章と7章でベンチマークをとって実行時間を測定して比較した計測結果を載せていたのですが削除しました。計測結果の評価の時点でGCの時間も含めて評価していたのと、GCの時間からメモリの使用量を推定する解釈の誤りがあり、これらを正して再評価しようとしたところ、結果をどう評価するのが適切なのかが難しく手に負えなかったため、セクション自体を削除しました。少なくとも Guile では 末尾再帰版の - 8章の例示が深くネストしたJSON配列の例示が深くネストしていることを適切に表現できていなかったのを修正しました。
- 7章の末尾再帰にした方が効率がよいケースで、実行時間をみて「わずか」にと記載していたのですが、空間計算量を考慮するとわずかとはいえない程度の計算量の差があるので修正しました。