これは高知工科大 Advent Calendar 2018の8日目の記事です．
最近私の中で話題になっている，Graal/Truffle について書く． すごく抽象的なことしか述べない．
JavaScript や Ruby ， Python などといった，動的なプログラミング言語の高速化が難しいことは よく知られている． 例えば，型がないので，式の実行時にデータの種類をチェックし，言語セマンティクスに従って処理を振り分ける （型ディスパッチ）必要がある． また，関数の定義を実行中に変えることができたりするため，関数呼び出しの際は，その前にどの関数を 実行するのかを調べてからその関数に処理をとばす必要がある． このような，処理の振り分け（ディスパッチ）にかかる実行コストはかなり大きく， パフォーマンスを下げる原因になる．
太古の昔に，バイトコードインタプリタという実行方式が考案された． これは，プログラムをまずバイトコードと呼ばれる命令列に変換し，その命令列を逐次実行するというものである． この方式は動的なプログラミング言語と親和性が高く，現在でも多くの言語処理系が採用している． しかし，上で述べたような問題の解決にはならない．
動的なプログラミング言語の高速化という人類の悲願を達成するべくして， 誰もが一度は聞いたことがあるであろう，実行時コンパイル（Just-In-Time Compilation, JIT）の技術が発明・研究された．
アイデアは以下のようなものである．
- プログラムのある個所を一度実行したとき，そこで現れた変数（レジスタでも何でもよいが）のもつデータの性質は， 次に同じところを実行したときも同じ性質を持っている可能性が高い
- データの性質がどのようなものかを予想できるのであれば（時々外れるにしても），予想ができた時点でそれに特化した コードを生成してこれを実行した方が，全体でみると高速になる
例えば，ある関数呼び出しにおいて，引数に与えられる値が数値であれば，次に同じ関数が呼び出されたとき， その引数の値は数値であることが予想できる． 最初の呼び出しの時点で，その関数を，引数が数値であることを仮定して特化したものを作り， 次回以降の呼び出しではこちら側を呼び出すようにする．
「特化」と一口に書いてはいるが，長い JIT 研究の歴史によって，様々な手法が考案されている． そして，それらの成果は多くの言語処理系に適用されている．
JIT の技術は，動的なプログラミング言語を大幅に高速化することに成功した． 人類の悲願は達成され，皆の幸福は約束された，はずだった．
1990年代後半，闇の時代が訪れた．
そう，JavaScript の誕生と Web の普及による，JavaScript エンジン開発戦争である．
ブラウザを開発する各国は，自国の JavaScript エンジンを高速化することによって，自国の配下を増やそうとした． しかしながら，まともに動作 し，JIT コンパイラによって高速に動作する言語処理系を開発するのは大変難しい． そもそも，JIT コンパイラを含まずとも，インタプリタや，GC を含むランタイムシステムをまともに動作できるようにするだけでも大変である．
この不毛な大戦によって，各国の JavaScript エンジンの開発者は疲弊しきっていた． JavaScript エンジン開発者に限ったことではない． 他のプログラミング言語に関しても，独自に高速な処理系を開発を試みているが，これらも多くの犠牲者を出している．
生き残った開発者たちは，このような惨劇を繰り返してはならない，そう心に誓った． そのために，彼らは高速なプログラミング言語の処理系を犠牲者を出さずに楽に開発できるようにするためのシステムが必要であると考えた．
彼らは，高速なプログラミング言語の処理系を犠牲者を出さずに楽に開発できるようにするためのシステムを実現するために， まず第1二村射影（First Futamura Projection）というものに着目した．
第1二村射影は，一言で説明すると，ある言語のインタプリタとその言語で書かれたプログラムから，そのプログラムの実行バイナリを生成できる というものである．
インタプリタへの入力は，プログラムとプログラムへの入力であり，インタプリタの出力はプログラムの出力である． ここでのプログラムは静的なデータであると考えることができる． インタプリタとプログラムを部分評価を行うことができれば，それによってできるものはプログラムの実行バイナリである．
現実にそのようなシステムが存在しないことからわかるように，これを完全に行うことは現実的に不可能である （できたとしても実行バイナリが爆発的に大きくなる）． しかし，Hot なコードだけ部分的に，ならば可能である．
第1二村射影を現実的な範囲で実現したのが Graal/Truffle である． Graal は，Oracle が開発している JIT コンパイラ，Truffle は高速な言語処理系を開発するためのフレームワークである． Truffle を使って開発された言語処理系は， Graal と連携してプログラムを高速に実行する．
Truffle を使う言語処理系開発者は，Truffle が提供する言語開発用 DSL （Java に近いシンタックス）で， インタプリタ（とランタイムシステム）を記述する． Graal/Truffle は，自動で入力のプログラムとインタプリタを部分評価し，それによって得られたコードを使ってプログラムを実行する． ただし，どこまで部分評価をするかは言語処理系開発者の責任で管理する必要はある（部分評価する範囲を広げると プログラムが高速になる可能性が高まる反面，メモリを圧迫する）． そうはいっても，それは DSL で書いた処理系の中にアノテーションを挿入するだけで調整することができる．
言語処理系開発者は，DSL を使って JIT の最適化技術を簡単に実現することができる（インラインキャッシング等）． 更に，プロファイルの収集や，部分評価を行うタイミングを言語処理系開発者の側で制御する，といったことも可能である． これによって，例えば，ループを一定数回ったら，部分評価を行う，といったことができる．
PLDI2017 で発表された論文では，性能を証明するために以下の実行速度の比較が行われた．
- Graal/Truffle による JavaScript の実装 vs. V8
- Graal/Truffle による Ruby の実装 vs. JRuby
- Graal/Truffle による R の実装 vs. GNU R
V8戦に関しては勝てたとは言い難い結果ではあったが，他の JRuby戦，GNU R戦においては完全勝利を収めたようだ． V8戦に関しても，十分に戦える程度の差であり，一部のベンチマークでは勝利を収めているものもあった．
Graal/Truffle を使えば，楽に動的なプログラミング言語の，高速な言語処理系を開発できる． 要するにやばい． 今後も期待ができるプロジェクトであることは間違いない．
- Practical Partial Evaluation for High-Performance Dynamic Language Runtime
- Wikipedia:部分評価
- Graal
- Truffle
PyPy の話も絡めたかった．その前に力尽きた． Graal/Truffle までが長すぎたのは反省している． 深夜テンションで書いたからおかしいところがあるがお願いだから真に受けないで．