NL 名古屋で Frege の評価戦略について話してきました
先日の 歌舞伎座.tech に引き続き、NL名古屋 - connpass で Haskell 風 JVM 言語 Frege について発表してきました。
今回の発表では、Frege の持つ Haskell 的特徴である非正格評価に焦点を当て、正格評価を行うはずの Java 上でなぜ評価を遅延させられるのか、その内幕を解説しています。
www.slideshare.net
なお当日の様子は NL名古屋 -NLとはなんだったのか- #nlnagoya - Togetterまとめ にまとめられています。長丁場でしたが、各々さまざまなテーマの発表があり、楽しめるイベントだったと思います。
Java のコード生成を試してみよう！
発表中に述べている通り、Frege のコンパイラはバイトコードではなく Java のソースコードを出力します。ただしスライド中で言及されているコードは Frege が生成した Java コードそのものではなく、今回の内容との関連が薄い部分をわかりやすく改変したものです。ここでは実際にどのようなコンパイル結果が得られるのかを見てみましょう。
コンパイラとコードの準備
Frege の Java 生成ロジックは、最新バージョン v3.24 から大きく変更になりました。今回の発表で述べられているのはこの新しい方のロジックです。
最新のコンパイラはまだ α 版で、各種ビルドツールではまだ使用できないようなので、直接バイナリをダウンロードします。
$ wget -O fregec.jar https://github.com/Frege/frege/releases/download/3.24alpha/frege3.24.61.jar $ chmod +x fregec.jar
次に、スライド中で登場した竹内のたらい回し関数をサンプルとして使用します。以下の Frege コードを Tarai.fr として保存してください。
module Tarai where tarai :: Int -> Int -> Int -> Int tarai x y z = if x <= y then y else tarai (tarai (x - 1) y z) (tarai (y - 1) z x) (tarai (z - 1) x y)
ビルド結果が散らからないように、出力先として build ディレクトリを作成しておきましょう。
$ mkdir build
コンパイル結果の確認
以下のコマンドでコンパイルを実行します。
$ java -Xss1m -jar fregec.jar -d build Tarai.fr
しばらく待つと build 以下に Tarai.java と Tarai.class が生成されます。
今回の目的である build/Tarai.java を確認してみましょう。ファイルの前半はボイラープレートなので無視して、以下の部分が tarai 関数の変換結果です。
final public static int tarai(int arg$1, int arg$2, Lazy<Integer> arg$3) { tailrecursion: while (true) { final int arg$1f = arg$1; final int arg$2f = arg$2; final Lazy<Integer> arg$3f = arg$3; if (arg$1f <= arg$2f) { return arg$2f; } else { arg$1 = Tarai.tarai(arg$1f - 1, arg$2f, arg$3f); arg$2 = Tarai.tarai(arg$2f - 1, (int)arg$3f.call(), Thunk.<Integer>lazy(arg$1f)); arg$3 = Thunk.<Integer>shared( (Lazy<Integer>)(() -> Tarai.tarai((int)arg$3f.call() - 1, arg$1f, Thunk.<Integer>lazy(arg$2f))) ); continue tailrecursion; } } }
まず気づくこととして、Frege 側の tarai 関数は再帰の形で定義されていましたが、末尾再帰最適化の結果ループ tailrecursion に変換されています。このままだと本題が見えづらいので、Tarai.fr を以下のように書き換えてあえて最適化しないようにしてみましょう。
module Tarai where tarai :: Int -> Int -> Int -> Int tarai x y z = if x <= y then y else 0 + tarai (tarai (x - 1) y z) (tarai (y - 1) z x) (tarai (z - 1) x y)
生成される build/Tarai.java は以下のように変化します。
final public static int tarai(final int arg$1, final int arg$2, final Lazy<Integer> arg$3) { if (arg$1 <= arg$2) { return arg$2; } else { return 0 + Tarai.tarai( Tarai.tarai(arg$1 - 1, arg$2, arg$3), Tarai.tarai(arg$2 - 1, (int)arg$3.call(), Thunk.<Integer>lazy(arg$1)), Thunk.<Integer>shared( (Lazy<Integer>)(() -> Tarai.tarai((int)arg$3.call() - 1, arg$1, Thunk.<Integer>lazy(arg$2))) ) ); } }
ここから、識別子をわかりやすく x y z に変更して不要な修飾子も削ったものがスライド中に登場したコードです。
static int tarai(int x, int y, Lazy<Integer> z) { if (x <= y) { return y; } else { return tarai( tarai(x - 1, y, z), tarai(y - 1, (int)z.call(), Thunk.<Integer>lazy(x)), Thunk.<Integer>shared( (Lazy<Integer>)(() -> tarai((int)z.call() - 1, x, Thunk.<Integer>lazy(y)))) ); } }
まとめ
本記事では、発表中に端折り気味だった Java のコード生成部分について、実際のたらい回し関数のコンパイル結果を挙げて補足しました。スライドも合わせて確認してもらえると幸いです。
ちなみに、今回のたらい回し関数は単純に int をとって int を返すだけの関数でした。しかし実際の Frege コードにはもっと複雑な言語機能がいくらでも登場し、
などを Java 上で再現するために語るべきことは尽きません。いずれこのブログのネタにでもしますが、それはまた別の話。
