2001-04-24 (Tue) [長年日記]
_ 末尾再帰
前もやったけど末尾再帰の最適化をRuby 1.7に実装してみた。
<URL:http://www.shugo.net/archive/ruby17-tail-recursive.diff>
末尾再帰の最適化とは、簡単にいうと、
def foo(...) ... return foo(...) end
のような末尾再帰でスタックを食い尽くさないようにすること。
どうやって実現しているかというと、あるメソッド(A)内の最後のメソッドコール(B)では、 Aに戻って来る必要がないことを利用して、Bの前にAの呼び出し前に戻ってしまう、という 方法を使っている。上記のコードでは、return foo(...)という部分でいったんfooの呼び 出し元に戻ってから再びfooを呼ぶので、何回fooを呼んでもスタックを食い尽くすことが ないってわけ。現状ではメソッドコールのたびにsetjmp()するので効率が悪いけど、上手 くやれば改善できると思う。
ところがmake testに通らない。原因は、
def foo
proc {
return "hello"
}.call
end
p foo
みたいなのが
-:3:in `call': return from proc-closure (LocalJumpError)
from -:3
というエラーになること。 最適化でProc#callの前にfooの呼び出し元に戻るので、Procがorphan (みなしご)になっちゃうわけですね。
これは難しいなあ。 orphanなProcからreturnした時は、例外を上げる代りにcontinuationで 元のメソッドに戻ることにするとかいうのは...だめだろうな。
_ 続き
上のバグの対処法を思いついたけど、上手く動かない。 うーん、今日はPC持って帰るか。
[ツッコミを入れる]