LoginSignup
4

More than 5 years have passed since last update.

mrubyで末尾再帰

Posted at

あまり知られていませんが(Googleとtwitterの検索を調べた結果)、mrubyには末尾再帰のための処理が入っています。でも、ほとんどテストされていないので基本的には動きません。昔ちょっと動かしたことがあるのでその話を書きます。

TAILCALL命令

mrubyのバイトコードインタプリタにはTAILCALLという命令があります。この命令はもちろん現状では使われていません。余談ですが、mrubyのインタプリタの命令には使われていないものがいくつかあります。NOPなんかもそうですね。
TAILCALLは、SENDに似たような処理なんですがメソッドの呼び出し情報を格納するcallinfoのエントリーを新しく追加するのではなく今実行中のメソッド呼び出し情報が入っているエントリーに上書きしてしまいます。また、レジスタも呼び出し元で使っているレジスタに上書きしてしまいます。詳しくはコード を読んでください。

コンパイラ

mrubyのバイトコードコンパイラ(mruby-compiler mrbgem)にはTAILCALL対応の処理が入っていますが、現状では無効化されています。
https://github.com/mruby/mruby/blob/master/mrbgems/mruby-compiler/core/codegen.c#L308
処理を読むと、RETURN命令の直前のSEND命令はTAILCALL命令に置き換えられるようです。

バグ

コンパイラの部分を有効にすれば動くのでは?って思うかもしれませんが動きません。昔、動かしたことがあるのですがいくつかのパッチ を当てるとao benchくらいなら動くようになります。興味のあればどうぞ
これ、本家に取り込まれていないんですよね。私もそれでいいと思っています。なぜなら make testが通らないからです。がんばればなんとかなるとかではなく、原理的に非互換が生じちゃうんですよね。そのテストは local_variables。本来あるはずのローカル変数の領域を潰しちゃう(だから再帰してもスタックが膨れない)のだから当然互換は取れないですよね。

おわりに

性能がそれほど上がるものでもなかったので、これっきりになっています。楽しかったので無駄だとは思っていませんが。将来、mrubyで関数型プログラミングが流行りだす未来があれば引っ張り出しましょう。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
4