末尾再帰 - higepon blog

最近一部で盛り上がっている「末尾再帰」について自分の理解を確認するのも兼ねて書いてみます。
（そもそも自分がふったのがきっかけっぽいので）。
上級者の方は間違い等に厳しくつっこんでもらえると助かります:-)

背景

自分が末尾再帰を知ったのは多分Schemeの勉強を始めた頃だったと思います。
例えばSICPという本では20ページあたりにこっそりと出てきます。
そのころの理解はかなり浅いもので「ふーん。」程度でした。
さて後日Schemeの処理系を実装することになりR5RSというSchemeの仕様書を読んだところ

Scheme の実装は真正に末尾再帰的(properly tail-recursive)
であることが要求されている。これは，たとえ繰返し計算が
構文的に再帰的手続きで記述されているときでも，定数空間
でその繰返し計算を実行することを可能にする

とあり末尾再帰のことを詳しく知る必要性が出てきました。
そこであれこれ調べ出したのがきっかけです。

まずはじめに用語ですが似たようなものが3つくらいあります。

末尾再帰呼出し
末尾再帰最適化
真正に末尾再帰的(properly tail-recursive)

これらはそれぞれ意味が違うのでそれぞれ分けて説明しようと思います。

末尾再帰呼出しとは？

末尾再帰呼出しとは、関数の末尾（一番最後に値を返すところ）で自分自身を呼び出すことをいいます。
JavaScriptで例を書いてみました。

function sum(n) {
    return sum_iter(n, 0);
}
function sum_iter(n, a) {
    if (n < 1) {
        return a;
    }
    return sum_iter(n - 1, a + n); // 自分自身を呼び出して、それを値として返している。
}

例えば sum(3) は 3 + 2 + 1 を返しますが
sum_iter(3, 0) => sum_iter(2, 3) => sum_iter(1, 5) => sum_iter(0, 6) => 6 と sum_iter が再帰的に呼ばれて 6 が返ります。
このような形の呼出しを末尾再帰呼出しといいます。

末尾呼出し最適化とは？

「末尾呼出し」を最適化するのが末尾呼出し最適化です。
最適化というからには、効率が悪い部分があってそれを改善してくれそうですね。

ここで「効率が悪い状況」と「最適化する方法」は言語仕様や処理系によっていろいろと異なる話がありそうなのですが、一般的に紹介されるものを取りあげようと思います。
ひとつ前に書いた JavaScript関数のsum(5000)をFirefoxで実行すると

のように「再帰呼出ししすぎだよ」と怒られてしまいます。

これはいわゆる「スタックオーバーフロー」と呼ばれる現象で、関数の呼出し履歴（コールスタック）に保持しているデータがいっぱいにあふれてしまって実行がエラーで止まってしまっていることを示します。
sum_iter を5000回再帰的に呼ぶにはスタックが足りなかったということです。
スタックというのは一般的にメモリ上にあるものなので、末尾再帰呼出しをすると（この処理系では）メモリ=空間を消費していくことになります。

ここで注目すべき点は

再帰的に呼ぶとスタックが消費される
再帰呼出しの深さに比例してスタックの消費量が増えている

の2点です。

これを「再帰呼出しの深さに比例せず定数の空間消費量で済ませる」 goto を使った最適化というのが良く紹介されます。
コードは以下の通り。
※実際のJavaScriptには goto はありません。例をかき終わってから気づいた（ぉ。

function sum2(n) {
    return sum_iter2(n, 1);
}

function sum_iter2(n, a) {
retry:
    if (n < 1) {
        return a;
    }
    a += n;
    n = n -1;
    goto retry;
}

sum_iter2 関数の末尾呼出し(call) を goto に置き換えています。
再帰呼び出しが無くなったことにより、スタックを消費せずおなじ計算結果を返すことが出来ます。
これを人間がコードを書くときに意識するのは面倒だしありえないので、たいていの場合は処理系が裏で最適化をやってくれます。

真正に末尾再帰的(properly tail-recursive)とは？

Scheme の仕様書には

もし無制限個数のアクティブな末尾呼出しをScheme の実装がサポートしているならば，その実装は真正に末尾再帰的である。
呼出しがアクティブであるとは，呼び出した手続きから戻る可能性がまだあるということである。

と書いてあります。
要は処理系が、がんばって無制限個数のアクティブ末尾呼出しをサポートをすれば良いということになります。
なので処理系が上で説明したようなコールスタックを使っていればgotoの最適化が使えるかもしれません。

末尾呼出し最適化を処理系に実装するには？

ここからは自分のScheme処理系に末尾呼出し最適化を実装する話で、あまり役に立たない情報へと突入していきます:D
僕の処理系は普通のインタプリタで、手続きの呼出しに nativeスタックをそのまま使っているものなのですが、実際に最適化を入れるとなると躓いてしまいました。
例えば疑問として goto の方法は分かったけど

インタプリタに存在するいくつかのフェーズのどこに最適化処理をはさむのか
今の構造で最適化できるのか。（設計を大幅に変えないといけないのか？）

など分からないことだらけです。
足りない頭をしぼって考えると構文木を末尾再帰呼出しパターンマッチにかけて、むりやりそこを goto に書き換えるのかなとか。

そこで既存の処理系のコードを読むということで SigScheme のコードリーディングをして研究しました。
それでも分からなかったので SigScheme の作者のid:kzkさんからヒント(答え?)をいただきました。

Scheme にはいくつか構文がある(ifとか)のですが、特定の構文が手続きの末尾で呼ばれている場合に工夫をすればうまくいくみたいです。
begin を例にとって説明します。
begin は引数を左から順に評価(eval)して、右端の引数の eval の結果を返します。
下のコードであれば 4 が返ります。

(begin 1 2 (begin 3 4))

僕の今の実装ではこの外側の begin を eval する場合

(begin 1 2 (begin 3 4)) を evalしようとする
- 1を eval
- 2を eval
- (begin 3 4) をevalしようとする
  - 3 を eval
  - 4 を eval
  - 4 を返す
- 4 を返す

と native スタックを消費して eval を call していきます。（インデントはスタックの消費だと思ってください。）

これを

(begin 1 2 (begin 3 4)) を evalしようとする
- 1を eval
- 2を eval
- (begin 3 4) をeval せずに返す(needEvalフラグをたてておく)
- 3 を eval
- 4 ををeval せずに返す(needEvalフラグをたてておく)
4をeval
4を返す

という形にすると、自分のスタックフレームを破棄して、呼出元に eval を任せることでスタックの消費を抑えることがでできるのです。
ちょっと理解するのが難しいと思うのでノートにコールスタックの様子を書いていくと良いかもしれません。
begin の他に、if/cond/and/or/let などなどがこのような最適化が可能です。
任意の合成手続きの末尾再帰呼出しは、これらの最適化を行ったプリミティブな構文によって組み立てられるので末尾呼出しでスタックの消費が抑えられるようになります。（ここはちょっと自信が無い）。

この方法は nativeスタックではなく独自のコールスタックをもつ処理系にも有効です。
その一例として僕とMさんだけ(?)で盛り上がっていた「ese-eval3 - begin (was 写経)」あたりで begin の最適化と最適化しない版のコールすタックの使いかたの違いを見ることが出来ます。

というわけで現在この方法で最適化を実装中なのですが、きっと他にも良い最適化方法があるのだろうなと思いつつ調べ方が良く分からないという。

雑談

末尾再帰最適化ですがデメリットとかってあるのでしょうか。
予想されるものとしては、処理系の実装が複雑になるとか？
Emacs Lisp はなぜ末尾再帰呼出し最適化をしてないのかとか思うよなあ。

雑談2

Mさん/id:kzkさん色々親切に教えてくれてありがとうございました。
.mjt さん合格おめでとう。
yossy さん大きな決断をしましたね。応援してます!
次は Gauche のコードを読むぜ。
妻と旅に出たいです。

雑談3

といったようなことを人に教わったりコードを書いたりで学んだのですが、とりあえずこの本読んでおけ的なモノがあればぜひ教えてください。

末尾再帰リンク集

より深い議論が知りたい場合は以下をどうぞ。