ろじかるんるんものがたり

病人が特に何も書かない。無駄だからだ。

JVM におけるメモリ効率の良い末尾再帰最適化の実装の紹介

やあやあ病人です。今日は特に予定もないので、最近読んだ論文の中から、適当にいくつかピックアップして紹介したいと思います。

Memory-efficient Tail Calls in the JVM with Imperative Functional Objects

JVM における TCE(Tail Call Elimination) については、長い間研究されてきています。六年前に JVM での TCE についての Odersky 先生の論文を紹介する記事を書いたりもしました。もう六年前…こちらの論文は TCE の実現における常套手段が JVM では通用しないよという話や、historical な話が面白くて、実際の提案手法は、まあダメでしょ…みたいなものだったのですが、今回の論文の手法はかなり良いと思います。

JVM で TCE というと、矢張り Trampoline です。Trampoline というと、Free モナドが数年前だかに流行った頃に、皆さん少しは齧っていると思うので説明は省略します。Trampoline で大体良いのですが、Trampoline はメソッド呼び出しの都度 memory allocation が生じるので、結局最後は OOM で死ぬという問題がありました。実際少なくともひと昔前の Scalaz の IO を真面目に使うと OOM で死にます。まあ Scalaz が footprint いくらなんでも気にしなさすぎというのもあると思いますが、そんな感じです。今は IO の実装とか諸々変わってるかもしれません。
話を戻して…今回の論文の提案手法では、general な TCE をメモリ使用量定数で実現することができます。実現方法は、言われてみればという感じで、特に難しくはなく、論文の主題としてはそれを利用することで FCore という System F の拡張を作れるよ(作ったよ)という部分だと思います。が、まあ System F なんて誰も興味ないと思うのでそこは飛ばします。

JVM での関数の representation は、Function as Object つまり Java8 の Functional Interfaces(aka SAM) が一般的です。というか他に知らないです。Scala も Kotlin も Clojure も Frege も Java との Interoperability を考えると、どうしてもそうなってしまいます。Functional Interfaces が加わった Java8 以降は特にそうです。論文では、Function as Object の頭文字をとってこれらを FAO と呼んでいます。
それに対して、FAO に代わるものとして、新しい関数の representation、Imperative Function Object 略して IFO と呼ばれるものが提案されています。これはどういうものかというと…見てもらうのが一番早いと思うので見てください。

public abstract class Function {
  Object arg, res;
  abstract void apply();
}

これだけです。引数や返り値を、フィールドとして持つようにしただけですね。本当にこれだけですが、色々と変わってきます。

Trampoline の問題点は、FAO の allocation がどうしても必要なので、メモリ使用量が定数にならないというところでした。一方で、IFO は関数を「使いまわす」ことで、これを回避します。FAO では使いまわせないのかというと、少し考えればわかると思うのですが、関数呼び出しには当然引数が必要になります。Trampoline を利用すると、引数が決定されるタイミングより、実際に関数を適用を行うタイミングの方が遅くなるので、bind 相当の処理が必要になり、結果として bind された FAO の allocation が発生します。
IFO では、引数をフィールドとして持っているので、bind の必要はありません。単純明快ですね。処理全体の流れとしては殆どトランポリンと同じで、IFO を保持する比較的スコープの大きい変数を用意しておき、関数適用したい場合は、代わりにその変数に IFO を渡して return。次に処理すべき IFO があるかどうかチェックして、あれば呼び、なければ最後の返り値をフィールドから返り値を取り出す。相互再帰の場合も問題なくいけます。

というわけで IFO いい感じなんですが、課題も色々あります。currying は必須、Object で持つと boxing/unboxing が生じる、mutable な外部スコープの変数を持つクロージャだと困る、thread-safety に実装するの大変、Java との Interoperability が下がる(IFO 版呼ぶ FAO 定義することで回避可能)、FAO と違い都度生成するのではなく、最初に生成しちゃうので部分適用とか使われるとだるい、と色々あります。

前述のとおり既に実装はあるので、試したい人はどうぞ。


もう一つ紹介したかったんですが、結構前に読んだ論文だったので間違いがないか読み直してたら大分疲れてしまったのでおしまい。