Computing/Truffle言語の実装例KinokoMLをつくった
この記事は、言語実装 Advent Calendar 2020の15日目の記事だ。
言語実装フレームワークTruffleを使って、ML風言語のKinokoMLを作り始め、動作するようになったので紹介する。
GraalとTruffle
TruffleはJava言語で書かれた自己最適化ASTインタプリタを実装するためのフレームワークである。 普通に書いたASTインタプリタは非常に遅いわけだが、TruffleベースのASTインタプリタを書いて、GraalというJITコンパイラと組み合わせると高速に実行できる。 Truffleについては過去の言語実装Advent Calendarに説明が出ているのでそちらも読んでみてほしい。
たいていの場合は、中間言語にコンパイルしないASTインタプリタの方が実装・読解しやすいはずだ（実行をデバッガで追えるし）。 言語を実装するときに言語機能と実行性能を同時に気にするのは大変だ。Truffleを使うことにより、比較的少ない労力で性能のある処理系を実装できると良さそう……というわけで本稿では以下を行う。
- 既存の処理系が言語実装の参考になるので、Truffleで実装された言語処理系を紹介。
- Truffleの使い方の参考用に、ML風言語KinokoMLを実装し始めたので紹介。
- KinokoMLのコードの解説を書いていたが分量が多くて一旦中断したので、副産物としてTruffleのAPIをいくつか選んで紹介。
Truffle言語の紹介
Truffleで言語処理系を実装するにあたって、既存のTruffle言語の実装が大いに参考になる。 そこで、言語実装者の観点で軽く既存の言語処理系を紹介する。
- SimpleLanguage
- Truffle学習用のシンプルな言語。シンプルと言ってもTruffleのいろんな機能が使われている。ここから出発すると良い。
- TRegex
- 正規表現エンジン。Graal.jsで使われている。TRegexがサポートしている正規表現であればTRegexを使い、だめならJoni（OnigurumaのJavaポート。Nashornでも使われていた）にフォールバックするらしい。
- NFI
- 他のTruffle言語から使うための、C FFIするための言語。現状はlibffiのラッパーのよう。
- Sulong
- LLVM IR（テキストとビットコード）のインタプリタ。 テキストまたはビットコードをパースして、ASTを実行する。 LLVMならできることをTruffle上でどう実装したら良いかの参考にすると良いかもしれない（ただしtail/musttailは実装されていなさそう。mustとは……）。
- GraalWasm
- WebAssemblyの実装。 ブロックをバイトコードインタプリタで実行しており、Truffleにバイトコードインタプリタ向けの最適化をさせるためのアノテーション BytecodeInterpreterSwitch の使用例となっている。
- Graal.js
- ECMAScript 2020を実装済みらしい（ただし末尾呼び出しはなし）。 たぶん最も力を入れて開発されているTruffle言語だろう。 動的オブジェクト・ジェネレータ・JVM連携など参考になる。 ちなみにNode.js互換の実装がついている。充分にウォームアップすれば性能的にも悪くないらしい？
- GraalPython
- Python 3.8の実装。まだ実験的な段階らしい。
- TruffleRuby
- Rubyの実装。Railsはまだ動かないらしい。
- FastR
- R言語の実装。Rはよく知らないのでわからない。逆にRの勉強に使うか……。
- Morzart-Graal
- Oz言語の実装。Oz言語もよく知らない。
- TruffleSqueak
- Squeak/Smalltalkの実装。Squeakを使ったことがないので本家との違いは知らないが、普通にSmalltalk環境っぽいものが動いているようだ。
- TruffleSOMとSOMns
- 別のSmalltalk環境の実装らしいがよく知らない。Newspeakという仕様があって（すごい名前だな……）、SOMnsはTruffleSOMベースのNewspeakの実装らしい。
- GraalPHP
- PHPの実験的な実装らしい。
- Espresso
- まだオープンソース化されていないが、Espressoという名前のTruffle上に実装されたJVMがあるらしい。
他にもTruffleClojureとかTruffleLuaとかshen-truffleとかTrufflePascalなどたくさんがあるが古そうなので省略。
こうしてみると、従来の実装方法だとASTインタプリタでは遅すぎて、証明をつけたいなどの強い動機がないと開発が続きにくいのだろうが、Truffleによってその状況が改善されるかもしれない。いろんな言語のASTインタプリタが、実用レベルの互換性を目指して実装されているのは良いことだ。
Truffle言語の実装例KinokoML
Truffleの使用例として、別途実装中の自作言語に似た、より単純な言語KinokoMLを実装し始めた。 名前の通りTruffle上で動作するML風言語だが、実行に型は使っていない。 型検査を通りそうなコードであれば、型検査で得られる情報なしに実行している（通らなさそうなコードは未定義動作とする）。 まだ実装初期で混迷を極めているが以下のようなテストコードが動いている。
100 // => 100
true // => true
false // => false
if true then 2 else 3 // => 2
if false then 2 else 3 // => 3
"test" // => test
"" // =>
(1) // => 1
(1 + 1) + 1 // => 3
1 + 1 // => 2
9223372036854775807 + 1 // => 9223372036854775808
let a = 1 in a // => 1
let a = 1 in let a = 2 in a // => 2
let a = 1 in let a = a + 1 in a // => 2
let a = 1 in let b = a + 1 in a // => 1
(fn a -> a) 1 // => 1
(fn a -> fn b -> b) 1 2 // => 2
(fn a -> fn b -> a) 1 2 // => 1
(fn a -> fn b -> a + b) 1 2 // => 3
let add = fn a -> fn b -> a + b in add 1 2 // => 3
let rec f = fn a -> fn b -> if a then f false b else b in f true 1 // => 1
let rec fib = fn n ->
if n < 1 then -1
else if n == 1 then 1
else if n == 2 then 1
else fib (n - 2) + fib (n - 1)
in fib 10 // => 55
let xs = { a = 10; b = 20; } in xs.b // => 20
let xs = { a = 10; b = 20; } in let ys = { xs with c = 30; } in ys.c // => 30
let xs = { a = 10; b = 20; } in let ys = { xs with c = 30; } in ys.b // => 20
ビルドとテスト実行
コードは https://github.com/orphos/kinokoml （記事を書いている時点のタグはv1.0.0-m.1）にある。 GraalVM（デフォルトでGraalをJITコンパイラとして使うようになってたりGraal/Truffle関連のいろいろが同梱されてたりするJDK）とMavenをインストールしておく。 ぼくはJava関連のものはSDKMANでインストールしているが、それによって手元にインストールされているバージョンは以下のようになっていた。
java: 20.3.0.r11-grl maven: 3.6.3
あとはmvn testすればビルドして実行されるはず。
Truffleの機能をいくつか解説
KinokoMLのコードの解説を書いていたが分量が多くて一旦中断した。そのうち書くが、今回は副産物としてTruffleのAPIをいくつか選んで紹介。
@CompilationFinal
フィールドアノテーションとして@CompilationFinal（または@Child/@ChlidrenのようなCompilationFinalを含意するアノテーション）をつけると、インタプリタにおいては非定数、コンパイルされたコードでは定数であるように扱われる。前提が崩れて更新したくなった場合は、CompilerDirectives.transferToInterpreterAndInvalidate()を呼んでコードを破棄しインタプリタに戻ってから更新すれば良い。dimensionを指定することで配列の要素まで定数扱いにできる。
@ExplodeLoop
メソッドに@ExplodeLoopをつけるとコンパイル時にループをアンロールしてくれる。 ループ対象が@CompilationFinalになっていれば完全に展開してくれるというわけ。
@Specialization
メソッドに@Specializationをつけると、abstractかつ名前がexecuteから始まるメソッドの特殊化されたバージョンとして扱われ、アノテーションプロセッサによってそのabstractメソッドの実装がつくられる。 @Specializationを使うとインラインキャッシュを実装したり、最初は64bit整数で数値演算してオーバーフローしたら無限精度に拡張するみたいなことができる。
VirtualFrameとMaterializedFrame
Truffle言語のRootNode（要は関数のノード）を実行すると、フレームがつくられてVirtualFrameとして渡ってくる。 VirtualFrameはフィールドに割り当てたりObjectにキャストできないが、その子インターフェースであるMaterializedFrameは可能。 そしてVirtualFrameはmaterialize()を呼ぶことでMatetializedFrameに変換できる。 つまりスタックからヒープへの移動を行ってくれるということかな。 Graal.jsではジェネレータの実装にMaterializedFrameが使われているようだ。
ControlflowException
ControlflowExceptionを継承した例外クラスを使ってフロー制御すると、（うまくいけば）Truffleによって高速なジャンプにコンパイルされるようだ。 Graal.jsではジェネレータの実装に、TrufflePascalではgotoの実装に使われている。
KinokoMLではこれを使って末尾呼び出しを実装しているが、Morzart-Graalの作者によればエスケープ解析が効かなくなるなどの性能問題があるらしい（自分で確認したわけではない）。
BlockNode
ノードの列（の指定したインデックス以降）を順に実行してくれるノード。 それ自体は自分で実装することもできるが、BloockNodeはTruffleコンパイラによって特別扱いされるとドキュメントにあるので、ノードの列を実行する場合はこれを使ったほうが良いだろう。 ControlflowExceptionを組み合わせることで実行の中断再開を実装できる（がKinokoMLには入れてない）。
DynamicObject
動的にスロットを追加削除できるオブジェクト。 要はECMAScriptのオブジェクトみたいなやつ。 Shapeと組み合わせて使うことで動的にレイアウトを処理系が把握して高速化してくれる。 Graal.jsで使われているので、充分ウォームアップすればモダンなJavaScript処理系並みに最適化してくれるだろう。
KinokoMLではレコードの実装に使っている。単相レコードならMaterializedFrameが使えるが、多相レコードを実装しやすいようにDynamicObjectを選択した。
Truffle Library
Truffle Libraryは多相ディスパッチのための仕組みらしい。 ホスト側のJVM言語や他のTruffle言語から値が見えるようにするにはInteropLibrary、DynamicObjectを操作するためにはDynamicObjectLibraryを使う必要があるので、KinokoMLでも使っている。
その他
以下はKinokoMLではまだ使ってない。
