「末尾再帰への書き換え」の弊害について

目次

投稿日: 2024-12-25 水

1. はじめに

Lisp Advent Calendar 2024 の25日目の記事です。

美しい再帰手続き(再帰関数)を 分かりにくい末尾再帰(反復アルゴリズム)に変換することなく、 そのままの美しさを保つことを推奨します。

深くネストした再帰に起因するスタックオーバーフローは、 プログラミング言語の処理系が課す厳しい制約であり、 無条件に認めるべき前提ではありません。

深くネストした再帰をサポートしている処理系であれば、 可読性に優れた美しい再帰手続きが書けます。

一般的なタイトルを付けましたが、 本記事では Scheme の処理系についてのみ調査しています。

本当は Scheme に限定した記事を書くつもりだったのですが、 主題自体は一般的な内容であり、 スタックオーバーフローするから末尾再帰にすることを推奨する書籍や記事が無数にあるため、 意図的に一般化したタイトルとしました。

本記事は過去記事の「Guile ではスタック溢れを気にせず再帰しよう」 を一般化したタイトルに変更し、再帰の美しさの説明を強化したバージョンです。

2. 再帰の何がよいのか

再帰手続きは再帰的な構造したデータを対象に 計算を行なうのに方法です。

再帰的なデータ構造の処理を再帰で扱うと、 宣言的な記述で処理を定義でき、 停止性の条件を満たしつつ、 正しく式を書き換えるだけで再帰関数を定義できます。

読む場合も式の書き換えが正しいことに 納得すればそれだけで再帰手続きを理解できます。

これが再帰の力であり美しさです。

再帰手続きの何がよいのかを説明している章であるため、 再帰が美しく分かりやすい記述であると納得している方は、 この章は飛ばしてしまって問題ありません。

2.1. 再帰的なデータ構造

まず再帰的なデータ構造について本記事で扱うものを紹介します。

2.1.1. リスト

Scheme におけるリストは次のように定義できます。

  • 空リストはリストである
  • cdr部がリストのペアはリストである
  1. ペアとは

    Scheme のペアには car 部と cdr 部があり、それぞれ手続き car, cdr で取り出すことができます。 car 部が xcdr 部が y のペアは (cons x y) で構成することができます。

    つまり (car (cons x y))x で、 (cdr (cons x y))y です。

    ペアがリストである場合は car は、 リストの最初の要素を求める手続きで、 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) をどのように置き換えるかということを記述しています。

ここでは、二つの式「 xy が等しい」を (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)))))

も先程と同じように以下のように、 リスト を carcdr に分けて確認すれば、 正しく定義できていることを確認できます。 ((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))))

いままでと同様に carcdr で分けてみましょう。

(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)))))

いままではこれで簡単に理解できたのに、 carcdr で場合分けしてみても何も分かりませんでした。 このアプローチは末尾再帰に変換したアルゴズムの前には無力です。

この手続きを理解するには、 引数の状態の変化に着目する必要があります。

再帰呼び出しのたびに、 引数の状態は次のように変化していきます。

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 回で consn 回なのに対し、 %my-map-tail では cons2n 回です。 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-tailreverse! を使うと、 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)yx を反転したリストを連結する手続きです。

(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番目ですが、 これは、「 lst2lst1 のリストの先頭要素を追加したものに、 lst1 の最初の要素を取り除いたリストを反転して連結したもの」と、 「 lst2lst1 を反転して連結したもの」が等しいと主張しています。 まあこれは正しいでしょう。 再帰手続きの説明の難しさに、 当然すぎてそれをどう説明すればいいのかよく分からないというのがありますが、 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-appendlst2reverse-append の機能に必然的に必要な変数なのに対し、 %my-map-tailaccmy-map-tail の 「リスト lst を手続き proc で写したリストを求める」 という主要な機能とは何ら関係のない変数です。 つまり acc が手続きの機能と何ら関係ないゆえに分かりにくくなるのです。

それに対して reverse-append の 「 lst2lst1 を反転して連結したリストを作る」という機能には lst2 は必然的に必要な変数であり自然なのです。

それが %my-map-tailreverse-append の違いであり、 末尾再帰による実装でも reverse-append 手続きにとって主要な意味を持っていれば自然と理解できます。

ちなみに、リストを反転する手続き reversereverse-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 ではインタプリタとコンパイラの両方を確認します。

  1. インタプリタ
    $ 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> 
    
  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. インタプリタ

    私の環境だと インタプリタで 1千万で試すと、 結果が返ってこなかったのですが、一桁少ない百万であれば大丈夫でした。

    $ guix shell gambit-c -- gsi
    Gambit v4.9.5
    
    > (let f ((i 1000000)) (if (= i 0) 0 (+ i (f (- i 1)))))
    500000500000
    > 
    
  2. コンパイラ

    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. 変更履歴

  • <2025-02-05 水> タイトルを『「末尾再帰への書き換え」をやめよう!』から『「末尾再帰への書き換え」の弊害について』に変更。強く主張しすぎたと深く後悔したため。
  • <2024-12-26 木> 4章と7章でベンチマークをとって実行時間を測定して比較した計測結果を載せていたのですが削除しました。計測結果の評価の時点でGCの時間も含めて評価していたのと、GCの時間からメモリの使用量を推定する解釈の誤りがあり、これらを正して再評価しようとしたところ、結果をどう評価するのが適切なのかが難しく手に負えなかったため、セクション自体を削除しました。少なくとも Guile では 末尾再帰版の my-map-tail で最後の reverse をするとGC時間が増加してしまい結果的に実行時間が長くなるという事象は条件を変えても発生し、 cons のコストが実行時間に影響を与えるとはいえそうなのですが、これと my-map がスタックを多く消費している場合に実行時間に与える影響について公平に比較するのは難しく諦めました。拡張されたスタックが使い回されるために my-map を繰り返すベンチマークはそもそも my-map が有利になるという問題もありそうです。 以上から、 my-mapmy-map-tail については理屈上は時間計算量、空間計算量に大きな差はない(はず)と主張するだけに留めることにしました。
  • <2024-12-26 木> 8章の例示が深くネストしたJSON配列の例示が深くネストしていることを適切に表現できていなかったのを修正しました。
  • <2024-12-26 木> 7章の末尾再帰にした方が効率がよいケースで、実行時間をみて「わずか」にと記載していたのですが、空間計算量を考慮するとわずかとはいえない程度の計算量の差があるので修正しました。

著者: Masaya Tojo

Mastodon: @tojoqk

RSS を購読する

トップページに戻る