trampoline
Windows update を実行したらパソコンが壊れてしまった。
パソコンが壊れたことは過去に 3 回あるがいずれも Windows update 中と直後。
今回はグラフィックボードが壊れただけ*1で助かったので続きを。
前回調べたのは TCO を実装するためで、何故実装したいのかというと Groovy 1.8 の新機能である Closure#trampoline の理解を深めるため。TCO -> trampoline の順に実装する。
TCO
wasabiz 氏の http://d.hatena.ne.jp/wasabiz/20110118/1295335821 が元ネタ。
athos 氏が Ruby で実装されて いろいろな言語で実装できると言われているので Groovy で実装してみた。
def sum(Integer n, Integer acc) { if (n == 0) { assert false:"sum($n, $acc)" acc } else { sum(n-1, acc+n) } } def tco(obj, name) { def continue_ = new Object() def first = true def arguments = null def original = obj.&"$name" obj.metaClass."$name" = new Closure(original.owner, original.thisObject) { @Override Class[] getParameterTypes() { original.parameterTypes } @Override int getMaximumNumberOfParameters() { original.getMaximumNumberOfParameters } def doCall(Object... args) { if (first) { first = false try { while (true) { def result = original(*args) if (result.is(continue_)) args = arguments else return result } } finally { first = true } } else { arguments = args continue_ } } } } // assert 55 == sum(10,0) assert 55 == tco(this, "sum")(10,0)
Groovy 1.8 でしか動作しない*2。
1.8 の機能を用いているからではなくて Groovy ではメソッドのオーバーロードがあるがどうやって対象のメソッドを呼ぶか理解していないため*3。
1.8 でも Integer でなく int にすると動作しないし、デフォルト引数を付けても動作しない。
仕組みは元のメソッドを loop するように置き換えるだけ。
original を呼び出すと元の sum が呼ばれ、その中の sum の呼び出しは置き換えた loop 用の定義が呼ばれる。例外を投げてみると再帰していないことを確認できる。
Caught: java.lang.AssertionError: sum(0, 55). Expression: false at tco_method.sum(tco_method.groovy:3) at tco_method$1.doCall(tco_method.groovy:27) at tco_method.run(tco_method.groovy:45)
http://jira.codehaus.org/browse/GROOVY-246 を見ると誰も AST変換実装してくれないから trampoline 使ってねってことになってしまった。
Groovy++ の http://code.google.com/p/groovypptest/wiki/TailRecursion は 0.4.248 で試してみたが動作しなかった。
MOPで
仕組みが分かれば他のやり方でも実装できる。
memoize のときに使った方法で。
def sum = { int n, int acc = 0 -> if (n == 0) { assert false:"sum($n, $acc)" acc } else { call(n-1, acc+n) } } class TcoInterceptor implements Interceptor { int nest = 0 @Override Object beforeInvoke(Object object, String methodName, Object[] arguments) { nest++ if (nest == 2) return new ParameterArray(arguments) } @Override Object afterInvoke(Object object, String methodName, Object[] arguments, Object result) { nest-- result } @Override boolean doInvoke() { nest == 1 } } def tco(Closure recursion) { { Object... args -> def proxy = ProxyMetaClass.getInstance(recursion.class) proxy.interceptor = new TcoInterceptor() proxy.use(recursion) { def result = recursion(*args) for (;;) { if (result instanceof ParameterArray) { result = recursion(*result.get()) } else return result } } } } assert 55 == tco(sum)(10)
Closure の呼び出しが再帰したら引数を ParameterArray に包んで返すようにする。
groovy.lang.ParameterArray は使い道がないクラスなので使い道があった。
何かで包むとモナドや bind っぽい感じがするが result を返す場合があるので型がだめだ。
trampoline
trampoline はどうなっているか？
trampoline は引数でなく引数を部分適用したクロージャを返している。クロージャごと返すので相互再帰できる。
Closure#trampoline の呼び出しが部分適用*4で、TrampolineClosure#call が loop の呼び出しになっている。
terazzo 氏が実装されている Java 版 がこの実装になっている気がする。
def even, odd even = { int n -> if (n == 0) return true else return odd(n - 1) } odd = { int n -> if (n == 0) return false else return even(n - 1) } class TrampolineInterceptor implements Interceptor { int nest = 0 LinkedList stack = [] @Override Object beforeInvoke(Object object, String methodName, Object[] arguments) { stack.addLast(methodName) nest++ if (nest == 2) return object.curry(*arguments) } @Override Object afterInvoke(Object object, String methodName, Object[] arguments, Object result) { stack.removeLast() nest-- result } @Override boolean doInvoke() { stack.last() != "call" || nest == 1 } } def trampoline(Closure... recursions) { return { Object... args -> def interceptor = new TrampolineInterceptor() def loop = { // call first of recursions def result = recursions.first()(*args) for (;;) { if (result instanceof Closure) { result = result.call() } else return result } } recursions.inject(loop) { acc, v -> def proxy = ProxyMetaClass.getInstance(v.class) proxy.interceptor = interceptor return { proxy.use(v, acc) } }.call() } } assert true == trampoline(even, odd)(3000) assert false == trampoline(odd, even)(3000)
この実装では戻り値が Closure の間 loop するようにしているので Closure を返すクロージャは最適化できない。逆に言えば trampoline は TrampolineClosure を返している間ループしてくれる。
追記
1.8 から Closure の戻り値の型が追加されていたがやはり Java から使うためのようだ。Groovy の trampoline も Java から使える。
groovy.ClosureJavaIntegrationTest.java
... public void testTrampoline() { final Reference<Closure<BigInteger>> ref = new Reference<Closure<BigInteger>>(); ref.set(new Closure<BigInteger>(null) { public Object doCall(Integer n, BigInteger total) { return n > 1 ? ref.get().trampoline(n - 1, total.multiply(BigInteger.valueOf(n))) : total; } }.trampoline()); Closure<BigInteger> factorial = new Closure<BigInteger>(null) { public BigInteger doCall(Integer n) { return ref.get().call(n, BigInteger.ONE); } }; assertEquals(BigInteger.valueOf(479001600), factorial.call(12)); } ...
2011-06-05 追記
interceptor の回数のカウントは適当。
def sum = { ... call(...) }
と
def sum sum = { ... sum(...) }
で呼ばれるメソッドが違ったりする。
class TcoInterceptor implements Interceptor { int nest = 0 LinkedList stack = [] boolean isCall(methodName) { methodName == "call" || methodName == "doCall" } @Override Object beforeInvoke(Object object, String methodName, Object[] arguments) { stack.addLast(methodName) if (isCall(methodName) && ++nest == 2) return new ParameterArray(arguments) } @Override Object afterInvoke(Object object, String methodName, Object[] arguments, Object result) { stack.removeLast() if (isCall(methodName)) --nest result } @Override boolean doInvoke() { !isCall(stack.last()) || nest == 1 } }
とりあえず call と doCall の回数を数えても動作した。
やりたかったのは回数を数えて再帰した場合は引数を返すということ。
もし再帰ではなく Y combinator のときのように maker の形であればもっと簡単に実装できる。
def tco(G) { def recursion = G { Object... args -> new ParameterArray(args) } return { Object... args -> def result = recursion(*args) for (;;) { if (result instanceof ParameterArray) { result = recursion(*result.get()) } else return result } } } def sum_maker = { Closure f -> return { n, acc=0 -> n == 0 ? acc : f(n-1, acc+n) } } assert (0..10000).sum() == tco(sum_maker)(10000)
