Closure クラスの API を使ってみる (6) ：トランポリン trampoline()

今回はクロージャのトランポリンに関するメソッドを見ていきます。　前回見たカリー化（部分適用）と同じく、トランポリンも関数型プログラミングでは大抵サポートされている機能なようで、それを Groovy に取り入れたって感じのようです。　主な解説は書きのリンク先にあります：

参考 URL

これらの記事から解説や注意点を拝借して列挙してしておきましょう。

Closure#trampoline() とは「明示的な末尾再帰の指定」を行うためのもの
trampoline() メソッドの呼び出しに実質的に2つの意味がある
書き換え手順は
1. クロージャ内の call(...) を trampoline(...) に書きかえる
2. そのクロージャを呼び出すところに trampoline() をはさむ
クロージャ内の最後の部分で引数あり trampoline() のみを呼び出す
内部で trampoline() しているクロージャを使う場合は、引数なし trampoline() メソッドを呼び出して、トランポリンできるようにしてから使う
trampoline() で相互再帰もできる

詳しくは上記のリンク先を参照のこと。

このトランポリン機能は Clojure から移植されたものらしいですが、『プログラミングClojure』を読んでみると Clojure の recur 関数と trampoline 関数をまとめて（Groovy の） Closure クラスの trampoline() メソッドにした、みたいな感じじゃないかと（違うかもしれませんが）。　というより、あまり Clojure の trampoline 関数を意識しない方がよさそうではあります。

トランポリン関連のメソッド

Closure クラスに定義されているトランポリン関連のメソッドは以下の2つ：

    Closure trampoline()
    Closure trampoline(Object... args)

この2つのメソッドは引数があるかないかだけの違いで、API ドキュメントにも同じ記述がされているのですが、自分で使う際には別物と思っておいた方がよいかと思います。　それぞれのシグニチャの trampoline() メソッドの使い方は

引数なし・・・Closure オブジェクトに対して外部から呼び出して、トランポリン機能をもった Closure オブジェクトを取得する
引数あり・・・クロージャの内部から呼び出して、再帰処理を記述する

まぁ、拝借した解説に書いてることと同じですがね。　末尾再帰呼び出しでだけ trampoline() メソッドを呼び出すようにするのは、クロージャ評価の返り値をトランポリン機能を持った Closure オブジェクトにしたいということなんでしょう。　結果（？）、引数のあるなしに関わらず trampoline() メソッドの機能は同じでよくなっているのかと。

サンプル・コード

trampoline() メソッドのサンプルとしてよく載っているのはフィボナッチ数列ですが（階乗を計算するのもありますが）、あまり同じサンプルってのも書いてて勉強にならないので、ちょっと別のサンプルを書いてみました。　数学っぽい例になってしまうので本筋とは別の点で分かりにくくなっているかもしれません。

サンプル・コードのための数学

元ネタの数学を少々。　使う数学は連分数で
　　 $\frac{1+\sqrt{5}}{2} = 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \cdots}}}$
という関係があることを使います。　これ、黄金比ですけどね*1。　これを念頭に置いて、漸化式
　　 $a_{n+1} = 1 + \frac{1}{a_n}$
で定められる数列 a_n を考えると（初項は正の数ならたぶん何でも OK）、その極限が黄金比になります。

本題へ

ではまずスタックオーバーフローするコード。

import static java.math.MathContext.*

def goldenRatio = { x, n ->
    if(n == 0) return x
    else return 1.0 + 1.0.divide(call(x, n-1), DECIMAL128)    // 1 + 1/x    call() が自己再帰
}

println goldenRatio(1.0, 100)    // 1.6180339887498948482045868343656381
println goldenRatio(1.0, 10000)    // StackOverflowError

call() が自己再帰のメソッド呼び出し。　ここでは BigDecimal の割り算に精度（を指定する MathContext オブジェクト）を指定する必要があるので divide() メソッド（/ 演算子ではなく）を使っています。　2つ目の引数が100の場合は例外が投げられず終了しますが、10000の場合は StackOverflowError が投げられます。　ただし、このコードは末尾再帰呼び出しになっていないので、まずアルゴリズムの修正が必要。　末尾再帰呼び出しにするには以下のようにします：

import static java.math.MathContext.*

def goldenRatio = { x, n ->
    if(n == 0) return x
    else return call(1.0 + 1.0.divide(x, DECIMAL128), n-1)    // 末尾再帰呼び出しに修正
}

println goldenRatio(1.0, 100)    // 1.6180339887498948482045868343656381
println goldenRatio(1.0, 10000)    // StackOverflowError

これでトランポリンの準備が完了。　ではトランポリン機能をつけましょう。　手順は

クロージャの中の自己再帰のメソッド呼び出し call() の部分を引数あり trampoline() メソッドに変更
作成したClosure オブジェクトに対して引数なし trampoline() メソッドを呼び出して、トランポリン機能つき Closure オブジェクトを取得する

です：

import static java.math.MathContext.*

def goldenRatio = { x, n ->
    if(n == 0) rturn x
    else return trampoline(1.0 + 1.0.divide(x, DECIMAL128), n-1)    // call() を引数あり trampoline() に
}.trampoline()    // 引数なし trampoline() でトランポリン機能を持ったクロージャに

println goldenRatio(1.0, 10000)    // 1.6180339887498948482045868343656381

これでスタックオーバーフローなしに計算が完了。　めでたしめでたし。

ちょっとイジってみる

一応トランポリン機能を付加したコードは動くようになりましたが、もう少し API をイジってみましょう。　goldenRatio 変数には外部からの trampoline() 呼び出しを行っていない Closure オブジェクトを代入しておいて、このオブジェクトに対して幾つかのメソッド呼び出しを行ってみましょう：

import static java.math.MathContext.*

def goldenRatio = { x, n ->
    if(n == 0) return x
    else return trampoline(1.0 + 1.0.divide(x, DECIMAL128), n-1)
}

println goldenRatio    // Closure オブジェクト
println goldenRatio()    // 例外 MissingMethodException が投げられる
println goldenRatio(1.0, 10000)    // TrampolineClosure オブジェクト
println goldenRatio.trampoline()    // TrampolineClosure オブジェクト
println goldenRatio.trampoline()(1.0, 10000)    // 1.6180339887498948482045868343656381

// 外部からの trampoline() メソッド呼び出しを行わずに実行
goldenRatio = goldenRatio(1.0, 10000)
println goldenRatio()    // 1.6180339887498948482045868343656381

意外だったのは3つ目の「goldenRatio(1.0, 10000)」で、goldenRatio 変数に対して引数ありの call() メソッド（もしくは「()」）を呼び出すと TrampolineClosure オブジェクト（トランポリン機能をもった Closure オブジェクト）を返すところです。　クロージャ内部で呼ばれている、引数ありの trampoline() メソッドの返り値である TrampolineClosure オブジェクトが返されてるようですね。　これを利用すると、最後の2行のように外部から trampoline() メソッドを呼ばずに実行を行えます。　まぁ、敢えてこの方法を用いる必要がある場合があるのかどうか知りませんが。

相互再帰のサンプルも

連分数を使った相互再帰を行うサンプルも書いてみたんですが、思ったより記事が長くなったのでコードだけ：

import static java.math.MathContext.*

def one, two

one = { x, n ->
    return n == 0 ? x : two.trampoline(1.0 + 1.0.divide(x, DECIMAL128), n-1)
}

two = { x, n ->
    return n == 0 ? x : one.trampoline(1.0 + 2.0.divide(x, DECIMAL128), n-1)
}

def sqrt2 = two(1.0, 10000)
def sqrt2plus1 = one(1.0, 10000)

println sqrt2()    // √2
println sqrt2plus1()    // √2 + 1