Javaを出力するトランスレータ言語 gomaj
この記事は JVM Advent Calendar 3日目 の記事です。
gomajとは
gomajとはOCamlで書いた、Javaを出力するオモチャのトランスレータ言語です。AltJSに対抗するならば、AltJと言えるような言語です。名前は忘れたのですけど(ほんとに忘れたのですいません)、トランスレータ書く技術が欲しいですとtwitterで言っている人がいたので書いてみました。ちょうどgomaというC++のトランスレータを書いていたので、勢いで書いてみたわけです。
gomaという、c++を出力する型システムがGoLangに似た言語を作って遊んでいたのですが、そのJava番です。 gomajを使えばぁ、あんな事やこんな事が簡単に出来ます。多分。＜どんな事だ？笑
JVM関係ないじゃないか！っと思うかもしれませんが、大きな目で見れば、JVM上で動く言語で、Javaでもないのでここで紹介させていただきます。
ビルド方法
あらかじめ、OCamlとmakeが使える環境を用意します。ググってインストールしてください。 git cloneしてmakeするだけです。
$ make
ハローワールド
package example
Hello class {
+ ^ main():void = {
System.out.println("hello world")
}
}
こんなファイルを作って、Hello.gomajで保存します。
見た目、;がなくて何か変な、+とか^がついている、型を後ろにかくような言語になってますね。
Scalaっぽいけど、Scalaではありません。
+は実はpublicです。^はstaticの意味です。そういわれてもう一度見れば、ああ、単なるマクロみたいなもんかと思えるかもしれません。-はprivateで*はprotectedです。
このプログラムをコンパイルしてjavaに変換し、javacでコンパイルして実行します。
$ ./gomajc example/hello.gomaj example/Hello.java $ javac example/Hello.java $ ./java example.Hello hello world!
動きました。出力されたHello.javaは以下のようになります:
package example;
class Hello {
static public void main(String[] argv) {
System.out.println("hello world");
}
}
奇麗なJavaが出力されてますね。
フィボナッチをオブジェクト指向を使ったケースと、スタティックなケースで書いてみましょう。
package example
+ Fib class {
^ fib(a:int):int =
if (a == 0)
return 0
else if (a == 1)
return 1
else
return fib(a - 2) + fib(a - 1);
^ + main(argv:Array[String]):void = {
System.out.println("fib 10 = " + fib(10))
System.out.println("Int.fib 10 = " + new Int(10).fib())
}
^ Int class (x:int) {
+ fib():int =
if (@x == 0) {
return 0
} else if (@x == 1)
return 1
else
return new Int(@x - 1).fib()
+ new Int(@x - 2).fib()
}
}
変換されたJavaは以下のようになります:
package example;
public class Fib {
static int fib(int a) {
if (a==0)
return 0;
else if (a==1)
return 1;
else
return fib(a-2)+fib(a-1);
}
static public void main(String[] argv) {
System.out.println("fib 10 = "+fib(10));
System.out.println("Int.fib 10 = "+ new Int(10).fib());
}
static class Int {
Int(int x) {
this.x=x;
}
int x;
public int fib() {
if (this.x==0) {
return 0;
} else if (this.x==1)
return 1;
else
return new Int(this.x-1).fib()+ new Int(this.x-2).fib();
}
}
}
Intクラスのコンストラクタはありませんが、Int class (x:int) {...}と書くだけで自動生成されています。また、ブロックの省略もできてます。this.xは@xとRubyのように書けています。アノテーションは、、、考慮に入れてません＜え”、、、っということで、@は@@にすると良いでしょう。@@は@@@にすれば、、、。
他にも以下のような色々な機能を付けてみました:
package example + Test class { - a:int; - b:int = 1; - c():int = return 1; + ^ main(argv:Array[String]):void = { System.out.println("c()="+new Test().c()) a:int=0 b:int=0 System.out.println("1+2+3="+(a=b=1+2+3)) System.out.println("1+2+3="+(a=(b=1)+2+3)) System.out.println("1*2+3="+(1*2+3)) System.out.println("(1+2)*3="+((1+2)*3)) System.out.println("-(1+2*3)="+ -(1+2*3)) System.out.println("(-1+2*3)="+ (-1+2*3)) System.out.println("eq="+new Test().eval(new Int(1))) System.out.println("eq="+new Test().eval(new Add(new Int(1),new Int(2)))) } - eval(e:E):int = { e match { | Int => return $._1 | Add => a:int = eval($._1) b:int = eval($._2) return a + b } return 0 } ^ Point class(x:int, y:int); ^ Point3D class(x:int, y:int, z:int); ^ E class(); ^ E :> Int class(int); ^ E :> Add class(E,E); }
Test.gomaj
match構文はswitchの変わりですが、instanceofでの分岐を短く書く事が可能です。
値のバインディングはないですけど、まぁ、単純なトランスレータだとこれくらいが限界です。
^ Point class(x:int, y:int);
と書くと、いい感じのクラスが出来たり、
^ E :> Int class(int);
って書くと、Eクラスを継承したIntクラスが出来たり、名前の指定が無い場合は、_1というフィールド名になったりします。
変換結果
package example; public class Test { private int a; private int b = 1; private int c() { return 1; } public static void main(String[] argv) { System.out.println("c()="+ new Test().c()); int a = 0; int b = 0; System.out.println("1+2+3="+(a=b=1+2+3)); System.out.println("1+2+3="+(a=(b=1)+2+3)); System.out.println("1*2+3="+(1*2+3)); System.out.println("(1+2)*3="+(1+2)*3); System.out.println("-(1+2*3)="+ -(1+2*3)); System.out.println("(-1+2*3)="+( -1+2*3)); System.out.println("eq="+ new Test().eval( new Int(1))); System.out.println("eq="+ new Test().eval( new Add( new Int(1), new Int(2)))); } private int eval(E e) { if (e instanceof Int) { Int $ = (Int)e; return $._1; } if (e instanceof Add) { Add $ = (Add)e; int a = eval($._1); int b = eval($._2); return a+b; } return 0; } static class Point { Point(int x, int y) { this.x=x; this.y=y; } int x; int y; } static class Point3D { Point3D(int x, int y, int z) { this.x=x; this.y=y; this.z=z; } int x; int y; int z; } static class E { E() { } } static class Int extends E { Int(int _1) { this._1=_1; } int _1; } static class Add extends E { Add(E _1, E _2) { this._1=_1; this._2=_2; } E _1; E _2; } }
Test.java
内部の構成
ここからは、大ざっぱなgomajの内部構造を説明して行きます。
gomajは以下の5つのファイルで構成されています。
- ast.ml 構文木を表すデータを定義します。
- parser.mly パーサの定義です。OCamlYaccでparser.mlを生成します。
- lexer.mli 字句解析の定義です。OCamlLexでlexer.mlを生成してコンパイルします。
- gen_java.ml Javaの出力を行います。
- main.ml メイン関数です。コマンドライン引数を見てファイルを開いてパースし、
gen_javaでjavaを出力します。
それでは、より詳細に見て行きましょう。
ast.ml
まずは構文のデータを作ります。astはAbstract Syntax Treeの抽象構文木略です。 こういう場合は、代数データ型がとても便利です。Scalaだとcase classを使う所ですね。
- t 型
- e 式
- a アクセス属性
- s 文
- prog プログラム
という5つの型を作ります。なんで、１文字なんだって？いうと、短い方が慣れると見やすいからです。 普通は意味分かるような名前にすべきですが、何回も同じ物を書くので省略しています。
type t = | Ty of string | TGen of string * t
まずは、型を表すt型を作ります。Tyがintとか、Stringといった型が入るデータの型です。
Ty("int")
のようにして型を書けます。便利ですね。 TGenのほうは、ジェネリックスです。配列もTGenを使い出力する所で特別扱いします。
TGen("int",Ty("Array"))
で、intの配列という意味にしました。
type e = | EInt of int | EBin of e * string * e | EPre of string * e | EPost of e * string | ECall of e * e list | EArr of e * e list | EVar of string | EString of string | EEmpty | ECast of t * e
eは式を表してます。EIntがint,EBinが2項演算子,EPreが前置演算子,EPostが後置演算子,ECallが関数呼び出し，EArrが配列演算子、EVarが変数等の識別子、EStringが文字列、EEmptyは空、ECastはキャスト演算子を表します。Javaで書くと10個のクラスで10ファイルで、コンストラクタを書いてウンタラで大変な所がたった、11行で書けるあたりが関数型言語の強みです。
type a = | APublic | AProtected | APrivate | AStatic | AFinal
aは属性accessのaで属性です。APublicがpublicでAProtectedがprotectedで、、、。後はわかりますよね。
type s = | SBlock of s list | SIf of e * s * s | SEmpty | SExp of e | SRet of e | SFun of t * string * (t * string) list * s | SPackage of string | SLet of t * e * e | SClass of string * string * s list | SCon of string * (t * string) list * s | STrait of string * s list | SAccess of a list * s | SMatch of e * (string * s list) list
ここからは早口で行きます。
sはステートメント(文)を表します。SBlockは{}です。中に更に文のリストが入ります。SIfはif文、SEmptyは空の文、SExpは式の文、SRetはreturn文、SFunは関数、そうこれ文じゃないんですけど、文としてます。手抜きです。ちゃんと分析出来てないジャンって所。リファクタリングするポイントでしょう。ただ、パーサ等でチェックをしっかりやれば大丈夫でしょう。
SPackageはpackageを表します。SLetは変数定義です。Letという名前は、SML、Haskell、OCaml、Swift等の関数型言語で良く表れるので、使っています。SClassはクラス、SConはコンストラクタ、STraitはインターフェイスだけど、Scalaっぽくtraitとしました。SAccessはアクセス属性、SMatchはswitch文をScalaに似せてmatchとしました。
ゼーゼー。長いですね。マジメに目を通す必要もないかもしれません。目を通したかた、ありがとうございました。
type prog = | Prog of s list
さぁ最後です。progがプログラムを表してて、sつまり、文のリストになってます。ホントは宣言部分をわけるといいんだろうけどまぁ、勢いで作った物なのでお許しを。宣言(declare)を略してdに分けると良いでしょう。
さらっと大量のデータオブジェクトが定義出来ました。 こういうところは関数型言語は強いですね。単純にJavaでまじめに書いたら恐ろしい量になるはずです。
parser.mly
次はパーサを書きましょう。 OCamlは標準で、OCamlYaccというコンパイラコンパイラがついてきます。 yaccという文法定義からパーサのC言語を吐き出すプログラムがあります。コンパイラをコンパイルするのでコンパイラコンパイラと呼ばれているわけですが、OCamlYaccはそのYaccのOCaml版です。 Yaccの作り方は直感的に理解するのは難しいです。理解せずに使うのは気持悪いけど、ま、便利だし速いので使っちゃいましょう。
ocamlyaccはコマンドラインから、
$ ocamlyacc parser.mly
等と書くと、parser.mlyからparser.mlというパーサのコードを出力してくれます。 便利です。
使っていると、文法の定義の衝突が起きて、コンフリクトのメッセージが表示されます。 コンフリクトとか気になると思いますけど、気にしないのが初心者の心構えとして重要です。 コンフリクトがあるから、駄目だみたいな批判もあると思うけど、とりあえずは、動けば良いんです。 そう思うとずっと楽に使えます。時間とコストをかければ、コンフリクトは消せるので、無い方がよいです。 コンフリクトはerrorではなくwarningと思えば、warningあっても動くみたいに思うとよいでしょう。
大ざっぱにソースを見てみましょう。体裁はよろしくないかも知れませんが、バラバラに書くのもと思いまして、ソースのコメントに文章を書いてみましたので、そのまま読んでください。
%{ (* %{と%}の間にyaccで出力されたファイルの先頭に書きたいプログラムをここに書きます *) (* Astモジュールを読み込んだり、 *) open Ast (* 関数定義も書けます。 *) let addBlock = function | (SBlock _ as b) -> b | b -> SBlock [b] %} /* 次にトークンの定義を%tokenの後ろにずらずらと書きます。１行に複数かけます */ %token STATIC PUBLIC PRIVATE PROTECTED FINAL %token CLASS THIS TRAIT EXTENDS REXTENDS : : /* トークンには様々なデータを含める事が出来て、<>の中に型を指定出来ます。 */ %token <string> PACKAGE %token <string> IMPORT %token <string> STRING %token <int> INT %token <string> ID : : /* 演算子の結合の優先順位を指定します。優先順位の順番は上が高くなります。 使えるのは、%left,%right,%noassocの3つです。 */ %right ASSIGN %right CAST %left EQ NE %left LT GT LE GE : : /* パーサの開始位置と型を書きます。この場合はprogのみ定義していてますが、複数書く事が出来ます。 */ %type <Ast.prog> prog %start prog %% /* ここから文法定義です */ /* progという名前の文法を定義します。 */ prog: | defs { Prog($1) } /* defsからprogは出来ています。 */ /* {}の中で、defsに対してアクションを記述します。$1は1個目の要素defsで、それをProgで包んでます */ /* defsの文法要素 */ defs: /* adefか、adefの連続かで、要するに、adefのリストとして返します []はリストを生成し::はリストの結合を表しています */ | adef { [$1] } | adef defs { $1 :: $2 } /* adefは アクセス属性のリストが付けられて、セミコロンを後ろに書けます */ adef: | accesses def { SAccess($1, $2) } | def { $1 } | adef SEMICOLON { $1 } : :
筆者は最初、このyaccの文法がなんか汚いなぁと思っていました。%{ %}の間にプログラム書くとか、%%の後ろが文法定義とか気持悪いなんて思ったのですけど、伝統的にこういう物なのです。受け入れましょう。短く書ければどうだっていいんです。重要なのは文法を気軽に定義出来る事なのですから。
文法定義を作る練習をする場合は、1+2*3みたいな計算式を作ってみて、それから、徐々に育てて行くのが楽しいです。Javaっぽい物であれば、最小限のコードを作ってそれをパースするのがよいわけです。
Test class { public static main(argv:Array[String]):void = { System.out.println("hello world\n") } }
をパースする事だけ出来る物を作ってそれを徐々に育てて行けば良いかんじです。 いきなりデカい例があると辛いでしょうけどw より細かい例は、ご要望があれば書きたいと思います。
参考文献は、ググってください。
lexer.mll
字句解析を作ります。コンパイラの本では字句解析が先に書かれてますけど、lexerがparserを参照する形になるので、順番逆に書いてます。 字句解析は、テキストデータをトークン列として返すのが仕事です。 正規表現を使う事で、短く定義出来て、高速に動作する字句解析器を作る事が出来ます。
{ (* ここにプログラムを書く *) open Parser } /* 変数定義 */ let space = [' ' '\t' '\n' '\r'] let digit = ['0'-'9'] /* 字句解析ルール */ rule token = parse | space+ { token lexbuf } | .. and comment = parse | "*/" { token lexbuf }
構造としてはこんな感じで、先頭の{}の中にプログラムを書いて、letで変数を定義して、ruleで字句解析のルールを書けます。ルール内のspace+ とかは正規表現で、+は1個以上の連続です。で、{}の中にルールを書きます。 ま、たぶん、習うより、慣れろです。最初はどこかの例を拾って来て修正してみる。 修正の数が多くなれば、なるほど分かって来ている事になります。
参考文献は、やっぱりググってください。
main.ml
パーサ作ったら、残すは変換部分のgen_java.mlと、main.mlだけです。 先にmain.mlを覗いてみましょう。
let trans input output = let inp = open_in input in let lexbuf = Lexing.from_channel inp in let ast = Parser.prog Lexer.token lexbuf in close_in inp; let out = open_out output in Gen_java.print_prog out ast; close_out out let gomaj2java src = let len = String.length src in if String.sub src (len - 6) 6 = ".gomaj" then String.sub src 0 (len - 6) ^ ".java" else failwith "filename is bad." let _ = let gomaj = Sys.argv.(1) in let java = gomaj2java(gomaj) in trans gomaj java
一番最後のlet _ = ... という箇所が、javaでいうstatic {} で、プログラムが読み込まれたときに動きます。メイン関数みたいな物です。
で、コマンドライン引数を取り出し、gomaj2javaで原始的な方法で、ファイル名の拡張子を.gomajから.javaに変換し、transでファイルを読み込みパースして、結果をGen_javaのprint_progに渡してファイルに出力してるだけです。簡単ですねw。なに？OCamlが分からないって？それは、失礼しましたー。
gen_java.ml
さて、最後はJavaを出力する所です。いくつかのポイントに絞って説明します。
ポイント1 block
奇麗にネストをつけて出力するためにspっていう変数に先頭の空白を用意しときます。 そして、blockっていう高階関数でその空白を上げ、blockを抜ければ下がるみたいに作っておきます。
そうすると、
block begin fun () -> fprintf !fp "\n"; print_s e; fprintf !fp "%s" ed end
等と書くだけで、ネストを書けるようになります。 高階関数使う嬉しさは、まるで構文を作っているように書ける事です。
ポイント2 print_ls
blockもそうですが、複数の出力を間に指定された文字列で区切って出力する高階関数、print_lsを作っておきます。これさえあれば、同じような事を何度も書かなくて済みます。
ポイント3 演算子の優先順位を管理して無駄な括弧を出力しない
面倒なら、全部かっこをつけて出力すればいいのですが、出力したjavaファイルの可読性が下がってしまいます。 人間なら脳内で演算子の優先順位を色々考えていい感じに書いてくれますが、プログラムは指示した事しかやってくれないので、優先順位を考慮して出力する必要があります。
構文木をトラバースして出力して行くのですが、そのときに優先順位を上から降らせて行く感じで書くとうまくいきます。アルゴリズムの詳細についてはOCamlのドキュメントのどこかに書いてあったので、探して見てください。＜参考文献書けよって？お金くれたら書きますw
infixs,prefixs,postfixsという演算子の表に、それぞれ、中置、前置、後置演算子の演算子名と、優先順位、左結合か右結合か等を入れておき、それぞれのトラバースの際にその優先順位を参照して、括弧が必要そうで左結合なら、優先順位がp1 <= pなら括弧を付け、右結合なら優先順位がp1 < pなら括弧を付けます。
以下のプログラムを見て下さい:
| EBin(e1, op, e2) -> let (p1,l) = (M.find op infixs) in let paren = paren && (if l then p1 <= p else p1 < p) in if paren then fprintf !fp "("; print_e e1 ~p:(if l then p1 - 1 else p1 + 1); fprintf !fp "%s" op; print_e e2 ~p:p1; if paren then fprintf !fp ")"
降らせる優先順位は、左結合ならp1 - 1で右結合ならp1 + 1とします。
トラバースして出力
さ、ここまで分かれば後はトラバースするだけです。
また早口ですw
print_progでprog(プログラム)をprintし、print_sでs(文)をprintし、print_aでa(アクセス属性)をプリントし、print_tでt(型)をプリントし、print_eでe(式)をプリントします。疲れた。プリントプリントって言ってるだけじゃんw
コード量の少ないprint_tを見てみましょう:
let rec print_t = function
| Ty(s) -> fprintf !fp "%s" s
| TGen(s, t) ->
begin match s with
| "Array" ->
print_t t;
fprintf !fp "[]"
| _ ->
fprintf !fp "%s<" s;
print_t t;
fprintf !fp ">"
end
Tyは型の名前が入っているのでそれを取り出してfprintfで出力するだけです。
TGenの場合は、Arrayなら特別で配列の表記にして書き出し、それ以外はジェネリックスの型として出力します。
それ以外の型はないので、ここに書き加えれば言い訳です。
まとめ
OCamlを使って、Javaに別シンタックスを与えるトランスレータ言語を作ってみました。
それほどたくさんの量を書かずに、トランスレータを書く事が出来ることが分かっていただけたかと思います。（馬鹿に出来る程、簡単ではない事も）
パターンマッチングに似た機能を追加したり、publicやstaticを記号で書く事で短く書けるようにしたり、Scalaのようなコンストラクタの自動生成が出来るようにしたりする事が出来ました。
今回作成したトランスレータに型チェック等がありません。 型チェックを入れたり、全、Javaの機能を含めてはいませんので、オモチャレベルの物ですが、拡張して遊んでみてはいかがでしょうか？
明日は @jyukutyo さんの「JITWatchについて」です！
