uehaj's blog

Grな日々 - GroovyとかGrailsとかElmとかRustとかHaskellとかReactとかFregeとかJavaとか -

Closure#trampoline()とは何か

Closure#trampoline()はGroovy 1.8の新機能の1つです。

何かっていうと、「明示的な末尾再帰の指定*1」を行うためのものです。これを使うと実際には再帰じゃなくなります。ループになります。スタックを消費しなくなります。

だから正確に言うと、「いっけん再帰呼び出しの様に見えるループ」の指定です。ただ、「再帰呼び出しのように見える」というのも疑わしい話ですが。見えますか? 私には見えない。まあ単純に「trampoline()はループだ」と理解すれば良いでしょう。

なお、Clojureの同名の影響を大きく受けた機能のようです。移植といっても良いでしょう。しかし、ClojureとGroovyの言語の違いから、現状のGroovyでの表象(メソッド構成、メソッド名など)はある程度ズレてる気がします。

Clojureはともかく、Groovyにおいてforやwhileなどのループ構文を使わないでtrampoline()を使うべき理由は、「つい癖で末尾再帰で書いちゃった*2けど、スタックオーバーフローした! 急いで直したいけどforやwhile使ってる暇ない!」という人でしょうか。いねーよそんなやつ?いまいち利点が見えませんよね。まあ頭がschemeになっちゃった人用でしょうかね。手続き型言語においてそこまで再帰にこだわる理由は正直わからん。あるいはGParsとかで利点があるのかな。

以下サンプル。

def fact = { n, total ->
             n == 0 ? total : trampoline(n - 1, n * total) } // (1)


def factorial = { n ->
                  fact.trampoline().call(n, 1G) // (2)
}
  
println factorial(5000) // 再帰呼び出しだったらStackOverFlowするところが計算できるのでうれしいYO!

あとは愚痴っぽくなりますが、trampoline()はややわかりにくいと思うのですが、その理由の一つは、思うに、trampoline()メソッドの呼び出しに実質的に2つの意味があるということです。

上の場合、(2)のtrampoline()の意味は「既存クロージャのループ呼び出し可能化」です。Trampolinezationとでも呼びたい。Clojureの「(trampoline xx ..)」がGroovyでは(2)の「xx.trampoline().call(..)」に対応します。Groovyでは、可能化したうえで、callするんですね。2ステップになってる。

これに対して、(1)のtrampoline()の意味は、Clojureでいう#( ... )で関数呼び出しを返すところなのですが、Groovyでは、「引数をcurryして固定化したTrampolineClosureのインスタンスをかえします」。意味わかんないっすよね。ソース嫁です。

仕組みはともかく、実用的には、trampoline()を使う前に、

def fact = { n, total ->
             n == 0 ? total : call(n - 1, n * total) } // (3)

というクロージャを書いていたとします。(3)でのcall()は自己再帰呼び出し*3の意味です。Groovyのイディオムですね。

んで、このfactはスタックをnに比例して消費するので、やめたい。ならば、まずは、callのところを何も考えずにtrampoline()に置き替えます。それだけでじゃなくて、呼び出し方も特殊になって、(2)のようにtrampoline()を呼び出す必要があります。

まとめると、末尾再帰のクロージャをClosure#trampoline()を使って手動でループにするには以下の手順を踏めばよい。

  • クロージャ内のcall(..)をtrampoline(..)に書きかえる
  • そのクロージャを呼び出すところにtrampoline()をはさむ。c(...)だったらc.trampoline()(...)とか。もちろん、c.trampoline().call(...)でも良いです。

私の考えですが、Groovyのtrampoline()をややこしくしてるのはtrampoline()メソッドが2つの意味で使われることと、Clojureからそのまま用語を持ってきたことです。あと(1)のcallをtrampoline()に置きかえるのは本来不要だろうと思います。んじゃ書きかえたろ!と思ってソースを見るとcall,doCallが特別扱いされてるので難しいな。

それはともかく、AST変換でメソッドをTCOできたらいいのに、と思った。

@TailCall
def fact(n, total) {
     n == 0 ? total : fact(n - 1, n * total)
} 

こんな感じ。実際のテクニックとしては、ここらへんを参考にして、ラッパーを生成すればいいと思うのだ。

*1:「明示的な末尾再帰最適化の指定」とは呼びたくない。これは特定のシンタックスで特定の機能を呼び出すというものなので最適化ではない、と思いたい。

*2:なお、末尾再帰であるためには厳密に条件を満たす必要があります。末尾再帰を知らない人が適当に再帰呼び出しを書いてそれが偶然に末尾再帰になっている可能性はあんまりない。条件とは具体的には末尾の再帰関数呼び出しの結果に演算を加えてはならないということ。

*3:「自己再帰呼び出し」というのは、俗に言う「再帰呼び出し」のことです。なぜ俗かというと、「再帰呼び出し」だと「相互再帰呼び出し」を含んでしまうからです。関数からその関数自身を直接呼び出す場合は「自己再帰呼び出し」と呼ぶのが正確です。