jvmlang.daitokai 1.0.0 MinCamlJを作ってみた
- 2. 自己紹介 ? 上司 和善 (かみつかさ かずよし) ? @jou4 ? 広島のメーカーのIT部門に所属。Javaフレームワークや開発支援 ツールの整備を担当。 ? Javaは苦手。JVMは好き。 ? 最近とあるきっかけから広島JUGを立ち上げることに。
- 3. 本日の概要 ? MinCamlJを作ってみたら色々と大変だった、という話。 ? MinCamlJ (https://github.com/jou4/MinCamlJ) ? MinCamlコンパイラをJavaで書き直したもの。Javaバイトコードを出力。 ? MinCaml ? 住井英二郎さんが開発された教育目的のコンパイラ。言語仕様は OCamlのサブセット。
- 4. MinCamlの言語仕様 ? 型はbool, int, float, array, tuple。 ? 四則演算、条件分岐、変数定義、関数定義、クロージャを サポート。 ? 構文はOCamlを最小化したもの。 ? コンパイラの理解が目的なので言語仕様は最低限。 let rec f a b = a + b in print_int (f 1 2)
- 6. 動機 ? コンパイラ開発が趣味。MinCamlはバイブルの1つ。 ? 現在、JVMで動く言語とそのコンパイラを開発中。(全然人に見せ られるレベルではないが…) ? 時間ができたらMinCamlもJVMで動くようにしたかった。 ? 最近、広島JUGの立ち上げ準備とその宣伝活動中。 ? 2/14 広島オープンセミナーで広報したところ、本日のイベントを紹 介された。 ? 広岛闯鲍骋の宣伝活動を兼ねて参加してみるか。ネタはどうしよう。 ? 以前から温めていたMinCamlJで行こう。2週間あればいけ るはず。
- 7. 作戦 ? 基本はJavaへの焼き直し ? 単純作業化。ロジックを考える時間を省く。 ? 時間がないのでひとまずエイヤッで ? 体裁を整えるのはあとからで良い。 ? Java8のラムダを積極的に活用 ? MinCamlはOCamlで書かれているので高階関数など関数プログ ラミング要素がてんこ盛り。ラムダがないとやっとれん。 ? クロージャ周りはinvokedynamic ? それ以外は基本的なバイトコードでいけるはず。
- 11. ラムダとinvokedynamic ? 今回最も興味があった部分であり、かつ、苦労した部分。 ? クロージャ周りの実装に使った。今回は実装していないが部分適用にも 使える。クロージャの説明は分かりにくいのでここでは部分適用を例にとる。 ? MinCamlJでは、クロージャを、自由変数と呼ばれる変数を先に部分適 用することで実装しているので無関係ではない。 let rec f a b = a + b in let g = (f 1) in g 2 ? 通常invoke*を使ってメソッドを呼ぶときは全ての引数を渡すこと が前提。一部の引数だけを先に渡しておき、残りは後から渡したい。 どうすれば？
- 12. ラムダとinvokedynamic ? 前頁の例は、Java8のラムダを使うと次のように書ける。 int f(int a, int b) { return a + b; } IntFunction<IntUnaryOperator> f_curry = a -> b -> f(a, b); IntUnaryOperator g = f_curry.apply(1); g.applyAsInt(2); ? これがどのようなバイトコードになるか探れば良さそう。
- 13. ラムダとinvokedynamic ? 意味不明… static {}; descriptor: ()V flags: ACC_STATIC Code: stack=1, locals=0, args_size=0 0: invokedynamic #15, 0 // IntFunction; 5: putstatic #16 // Field f_curry 8: return … private static java.util.function.IntUnaryOperator lambda$0(int); descriptor: (I)Ljava/util/function/IntUnaryOperator; flags: ACC_PRIVATE, ACC_STATIC, ACC_SYNTHETIC Code: stack=1, locals=1, args_size=1 0: iload_0 1: invokedynamic #62, 0 // IntUnaryOperator; 6: areturn invokedynamicでラムダを得られるみたい 見知らぬラムダがある
- 14. ラムダとinvokedynamic ? Java8では、invokedynamicとLambdaMetafactory #metafactoryを使ってラムダを実行時に生成している。 ? この情報を元に、LambdaMetafactory#metafactoryは、「ラムダを 表すクラス(FunctionalInterfaceの実装クラス)」と「そのクラスをインス タンス化するためのメソッド(ハンドル)」を生成。 ? invokedynamicは、そのメソッドを実行しラムダのインスタンスを得る。 CallSite metafactory( MethodHandles.Lookup caller, // MethodHandleのルックアップ?コンテキスト String invokedName, // FunctionalInterfaceの抽象メソッド(SAM)の名前 MethodType invokedType, // invokedynamicで実行されるメソッドの型 MethodType samMethodType, // SAMの型 MethodHandle implMethod, // 目的のメソッド MethodType instantiatedMethodType // SAMの具体化した型 )
- 15. ラムダとinvokedynamic Invoke Dynamic Bootstrap CallSite Method Handle 目的の処理 Invoke Dynamic Bootstrap (metafactory) CallSite Method Handle ラムダをインスタン ス化し、返却する 処理 ラムダを表す クラス 基本的なinvokedynamic ラムダを得る場合 (生成) (生成) (生成) (使用) (初回呼出前) (ポインタ) (ポインタ) (初回呼出前) (呼出) (呼出)
- 16. ラムダとinvokedynamic ? LambdaMetafactoryについて自分はこう理解した。 ? 先ほどの例を再掲。 int f(int a, int b) { return a + b; } IntFunction<IntUnaryOperator> f_curry = a -> b -> f(a, b); IntUnaryOperator g = f_curry.apply(1); g.applyAsInt(2); IntFunction<IntUnaryOperator> f$(){ return a -> f$$(a); } IntUnaryOperator f$$(int a){ return b -> f(a, b); } IntUnaryOperator g = f$().apply(1); g.applyAsInt(2); ? ラムダを分解しメソッドに振り分け。 Javaコンパイラが作るクラスファイルを覗く と、ラムダ式から、lambda.0, lambda.1, …, lambda.N というメ ソッドが作られていることがわかる。
- 17. ラムダとinvokedynamic ? LambdaMetafactoryを使ってラムダを生成する。 int f(int a, int b) { … } IntFunction<IntUnaryOperator> f$(){ return a -> f$$(a); } IntUnaryOperator f$$(int a){ return b -> f(a, b); } IntUnaryOperator g = f$().apply(1); g.applyAsInt(2); このラムダを得るために、InvokeDyanmicと LambdaMetafactoryを用いる。 このラムダを得るために、InvokeDyanmicと LambdaMetafactoryを用いる。
- 18. ラムダとinvokedynamic ? LambdaMetafactoryは実行時にラムダを表すクラスを生成する。 class F$ implements IntFunction<IntUnaryOperator> { public IntUnaryOperator apply(int a){ return f$$(a); } } class F$$ implements IntUnaryOperator { private int a; public F$$(int a){ this.a = a; } public int applyAsInt(int b){ return f(a, b); } } IntFunction<IntUnaryOperator> f$(){ return new F$(); } IntUnaryOperator f$$(int a){ return new F$$(a); } IntUnaryOperator g = new f$().apply(1); g.applyAsInt(2); 先に渡された引数はフィールドに保持。 apply*が呼ばれたら次へ渡す。 ラムダの正体。匿名クラスとほぼ同じ。
- 19. ラムダとinvokedynamic ? MinCamlJでは、カリー化した関数を派生させて、 invokedynamicとLambdaMetafactoryによりラムダを 生成している。関数適用の種類により使い分けている。 ? 直接コールの場合は元々の関数を呼ぶ。 ? クロージャや部分適用(今回は実装していないが)の場合は、カリー 化した関数に順に1つずつ関数を渡す。 let rec f a b = a + b // f から f$, f$$ を派生 f 1 2 // f を呼ぶ let g = (f 1) in g 2 // f$を呼びラムダオブジェクトを取得、1 -> 2と引数を順番に渡す
- 20. バイトコード生成(参考) // f : int -> int -> int // f a b = a + b mv = cw.visitMethod(ACC_PUBLIC + ACC_STATIC, "f", "(II)I", null, null); mv.visitCode(); mv.visitVarInsn(ILOAD, 0); mv.visitVarInsn(ILOAD, 1); mv.visitInsn(IADD); mv.visitInsn(IRETURN); mv.visitMaxs(2, 2); mv.visitEnd(); int f(inta, int b) { return a + b; } IntFunction<IntUnaryOperator> f$(){ return a -> f$$(a); } IntUnaryOperator f$$(int a){ return b -> f(a, b); }
- 21. バイトコード生成(参考) // f$ : () -> (int -> (int -> int)) // f$ () = a -> f$$ a mv = cw.visitMethod(ACC_PUBLIC + ACC_STATIC, "f$", "()Ljava/util/function/IntFunction;", null, null); mv.visitCode(); // Functionを得るためのメソッドを動的に生成し、実行する mv.visitInvokeDynamicInsn("apply", "()Ljava/util/function/IntFunction;" , new Handle(H_INVOKESTATIC, "java/lang/invoke/LambdaMetafactory", "metafactory", MethodType.methodType( CallSite.class, MethodHandles.Lookup.class, String.class, MethodType.class, MethodType.class, MethodHandle.class, MethodType.class) .toMethodDescriptorString()) , Type.getType(MethodType.methodType(Object.class, int.class).toMethodDescriptorString()) , new Handle(H_INVOKESTATIC, className, "f$$", MethodType.methodType(IntUnaryOperator.class, int.class).toMethodDescriptorString()) , Type.getType(MethodType.methodType(IntUnaryOperator.class, int.class).toMethodDescriptorString())); mv.visitInsn(ARETURN); mv.visitMaxs(1, 0); mv.visitEnd();
- 22. バイトコード生成(参考) // f$$ : int -> (int -> int) // f$$ a = b -> f a b mv = cw.visitMethod(ACC_PUBLIC + ACC_STATIC, "f$$", "(I)Ljava/util/function/IntUnaryOperator;", null, null); mv.visitCode(); // apply実行時に実行するメソッドの引数 mv.visitVarInsn(ILOAD, 0); // Functionを得るためのメソッドを動的に生成し、実行する mv.visitInvokeDynamicInsn("applyAsInt", "(I)Ljava/util/function/IntUnaryOperator;" , new Handle(H_INVOKESTATIC, "java/lang/invoke/LambdaMetafactory", "metafactory", MethodType.methodType( CallSite.class, MethodHandles.Lookup.class, String.class, MethodType.class, MethodType.class, MethodHandle.class, MethodType.class) .toMethodDescriptorString()) , Type.getType(MethodType.methodType(int.class, int.class).toMethodDescriptorString()) , new Handle(H_INVOKESTATIC, className, "f", MethodType.methodType(int.class, int.class, int.class).toMethodDescriptorString()) , Type.getType(MethodType.methodType(int.class, int.class).toMethodDescriptorString())); mv.visitInsn(ARETURN); mv.visitMaxs(1, 1); mv.visitEnd();
- 24. Javaへの置き換えが面倒だった ? 代数的データ型やパターンマッチングをJavaに置き換えるのが 面倒。 ? 極力実装を急ぎたかったので細かいことは考えなかった ? Javaなりの書き方があるけど今回は… (* MinCaml *) | FNeg(e) -> FNeg(deref_term e) | FAdd(e1, e2) -> FAdd(deref_term e1, deref_term e2) // MinCamlJ } else if (e instanceof SFNeg) { SFNeg e1 = (SFNeg) e; return new SFNeg(derefTerm(e1.getExpr())); } else if (e instanceof SFAdd) { SFAdd e1 = (SFAdd) e; return new SFAdd(derefTerm(e1.getLeft()), derefTerm(e1.getRight()));
- 25. Stack Map Frames がよくわからなかった ? 条件分岐や例外送出によるジャンプが発生する場合に必要 ? ローカル変数とスタックの状態を効率良く検証するのに必要という 認識 ? 最初は頑張ってみたけど結構面倒、やれなくはない ? どのスロットにどの型が入っているか ? COMPUTE_FRAMES オプションで楽をすることにした ? オプションを使うとシミュレートにコストがかかるという記述を目にした が、自前でやってもそのコストは同じような気がするし、自前でやる メリットは何なのか ? 今後勉強したい
- 26. 型情報をJVMに与えるのが煩わしかった ? アセンブリならレジスタとメモリ操作だけなので型など不要 ? JVMが安全を確保してくれるゆえの制約と認識している ? あまり意識せずスタートしたが実際はかなり手間がかかった ? プリミティブが絡むと Function, IntFunction, IntFunction<IntUnaryOperator , IntToDoubleFunction などを使い分けなければいけない ? さらにこれらはInterfaceの定義するメソッドが異なる ? Functionならapply, IntToDoubleFunctionならapplyAsDoubleとか … ? ジェネリックな型の場合キャストが必須 ? 例えばFunction<T,R>だと戻り値の型がObjectなので、その後、他に 使う場合はキャストが必要 ? IntFunction<IntUnaryOperator>なら、引数にintを渡して戻って きたObjectをIntUnaryOperatorにキャストして引数intを適用
- 27. まとめ
- 28. まとめ ? MinCamlのJava版を作ってみて、バイトコードについて学ん だ。 ? バイトコードの扱いは難しいところもある。でも習熟すれば、JVMと いう優秀な実行環境を活用できる、のは魅力。 ? 今回は、invokedynamicとLambdaMetafactoryの使い方を 理解できて良かった。 ? MinCamlJは一応のところまでは実装?テストするつもり。機 能追加は考えていない。
- 29. 広岛闯鲍骋の宣伝
- 30. 広島JUG 第1回のご案内 時間 テーマ スピーカー 10:00-11:00 Java Day Tokyoフィードバック 寺田 佳央さん 11:00-12:00 未定 未定(調整中) 4月25日(土) 10:00-12:00 ＠グリーンアリーナ小会議室 http://hiroshima-jug.doorkeeper.jp/events/20660 タイムテーブル(調整中) 寺田さんにお越しいただきます！
Editor's Notes
- #10: 字句解析からクロージャ変換まで大体3日 Javaバイトコード生成に大体5日 テストと修正で大体5日
- #12: まだ理解しきれていない function make_adder(x) { function adder(y) { return x + y; } return adder; } 関数と自由変数(環境)の組(adder, x) = クロージャ adder’ (x, y) -> return adder -> return makecls(adder, y) -> return adder’.apply(x)
- #13: 1引数ずつ受け取る関数へ変换(肠耻谤谤测化)
- #15: 理解に苦しんだ
- #17: Javaでも、lambda.0, lambda.1, …, lambda.N というメソッドが派生する