DevoxxUSに参加した際、とてもおもしろかったセッションがありました。Oleg Šelajevの"How to create a new JVM language"というセッションです。
OlegはvJUG（virtual JUG: オンライン上の仮想Java User Group）のOrganiser、JRebelやXRebelを作っているZeroTurnaroundの人です。*1
このセッションでは、ANTLRとGraal（とくにTruffle）を使って四則演算する言語を作ろう！というものでした。とてもおもしろかったのですが、1つ問題がありました。
ソースが公開されていない！
OlegのGitHubにもありませんでした。
そこで僕は決めました。セッション動画を見ながら、表示されるコードを写して自分で実装しよう！と…
結果、できました！
ソースはこちらです。
ただ、動画では公開されていない部分もあり、いろいろ検索してTruffleのサンプルで簡易言語を実装したプロジェクトのソースを参考にしました。見た感じOlegもこれを元にしている気がします。
概要
簡易な言語として、以下の構成にします。
| Module | Takes | Returns |
|---|---|---|
| Lexer | Text(Code) | Tokens |
| Parser | Tokens | AST(Abstract Syntax Tree) |
| Compiler | AST | JVM bytecode |
つまり、Code -(Lexer)-> Tokens -(Parser)-> AST -(Compiler)-> JVM bytecodeとして、JVMで実行します。
今回Lexer/Parserの部分にANTLRを、それ以降の部分にGraal、Truffleを使います。
ANTLR
ANTLR (ANother Tool for Language Recognition) is a powerful parser generator for reading, processing, executing, or translating structured text or binary files. It’s widely used to build languages, tools, and frameworks. From a grammar, ANTLR generates a parser that can build and walk parse trees.
（適当訳）ANTLRはパワフルなジェネレータです。構造化されたテキストやバイナリファイルの読み込みや処理、実行、解釈のためのものです。言語やツール、フレームワーク構築に広く使われています。文法からANTLRはパースツリーを構築し巡回するパーサを生成します。
文法を定義してANTLRに渡せば、LexerやParserを生成します。
Graal、Truffle
GraalとTruffleが何か、まだ僕にはうまく説明できませんが…
Graal is a research compiler. Truffle is … well, that’s kind of hard to explain, because there’s not much to compare it to. The shortest summary I can think of is this: Truffle is a framework for implementing languages using nothing more than a simple abstract syntax tree interpreter.
https://blog.plan99.net/graal-truffle-134d8f28fb69
（適当訳）Graalはリサーチコンパイラだ。Truffleは…うーん、説明が難しい。比較するものがないから。僕が考え得るもっとも短い概要はこうだ。TruffleはASTインタプリタでしかないものを使って言語を実装するためのフレームワークだってことだ。
Graal is a new just-in-time compiler for the JVM focused on peak performance and multi-language support.
http://www.oracle.com/technetwork/oracle-labs/program-languages/overview/index.html
（適当訳）GraalはJVMのための新しいジャスト・イン・タイムコンパイラで、最高のパフォーマンスと多言語サポートに重点を置いています。
またGraalVMというものもあり、これはGraal（JITコンパイラ）やTruffleを持つJVMです。
GraalやGraalVMそのものについては、日本オラクルの西川さんのプレゼンテーション資料が大変わかりやすいです。
www.slideshare.net
今回作成する言語はANTLRで生成したコードが作るASTを、TruffleのAPIを使いインタープリットして、JVM上で処理を実行します。
ソース解説
ANTLR
今回は四則演算の構文をそのままプログラミング言語の文法とします。ANTLRを使ってBNFを定義します。
grammar Math;
prog
: expr (EOF | NEWLINE)
;
expr
: '(' expr ')' #parensExpr
| functionName '('argument? (',' argument)* ')' #invoke
| '->' expr #asyncExpr
| left=expr op=('*'|'/') right=expr #infixExpr
| left=expr op=('+'|'-') right=expr #infixExpr
| value=NUM #numberExpr
;
functionName: ID;
argument: expr;
ID
: ('a'..'z' | 'A'..'Z' | '_') ('a'..'z' | 'A'..'Z' | '_' | '0'..'9')*
;
OP_ADD: '+';
OP_SUB: '-';
OP_MUL: '*';
OP_DIV: '/';
NUM: [0-9]+ ('.' [0-9]+)?;
WS: [ \t]+ -> skip;
COMMA: ',';
NEWLINE: '\r'? '\n';
BNF？という人も、内容はつかみやすいと思います。Math.g4とします。
公式サイトANTLRを参考にセットアップしてください。macOSならbrewでインストールできます。
$ antlr4 ANTLR Parser Generator Version 4.7 $ antlr4 -package grammer Math.g4
このコマンドで、BNFからJavaソースコードを生成します。packageオプションはJavaのパッケージの指定です。
$ cd jvmmathlang/src/main/java/grammer $ ls -al -rw-r--r-- 1 jyukutyo staff 691 7 8 11:08 Math.g4 -rw-r--r-- 1 jyukutyo staff 145 7 8 11:09 Math.tokens -rw-r--r-- 1 jyukutyo staff 3548 7 8 11:09 MathBaseListener.java -rw-r--r-- 1 jyukutyo staff 4545 7 8 11:09 MathLexer.java -rw-r--r-- 1 jyukutyo staff 145 7 8 11:09 MathLexer.tokens -rw-r--r-- 1 jyukutyo staff 3234 7 8 11:09 MathListener.java -rw-r--r-- 1 jyukutyo staff 15288 7 8 11:09 MathParser.java
これらのソースはANTLRのクラスを利用しますので、依存ライブラリにANTLRを追加します。
<dependency> <groupId>org.antlr</groupId> <artifactId>antlr4-runtime</artifactId> <version>4.7</version> </dependency>
AST
ANTLRは生成したクラスにもあるようにLexerとParserの部分を担当します。処理した結果ASTを構築します。確認してみましょう。
$ mvn clean compile $ pwd jvmmathlang/target/classes $ grun grammer.Math prog -gui 1 + 2 ^D
こんな感じでASTが構築されたことがわかります。
IntelliJ Plugin
ANTLRでBNFを書くときは、プラグインを入れると書きやすいです。
ANTLR v4 grammar plugin :: JetBrains Plugin Repository
Truffle
Truffleを使うため、依存ライブラリに追加します。
<dependency> <groupId>com.oracle.truffle</groupId> <artifactId>truffle-api</artifactId> <version>0.26</version> </dependency> <dependency> <groupId>com.oracle.truffle</groupId> <artifactId>truffle-tck</artifactId> <version>0.26</version> </dependency> <dependency> <groupId>com.oracle.truffle</groupId> <artifactId>truffle-dsl-processor</artifactId> <version>0.26</version> </dependency>
やっとJavaコードです。
public class JvmMathLangMain { public static void main(String[] args) throws MissingNameException { PolyglotEngine engine = PolyglotEngine.newBuilder().setIn(System.in).setOut(System.out).build(); ... try(Scanner s = new Scanner(System.in)) { String program = null; while(true) { System.out.print("> "); program = s.nextLine().trim(); ... Source source = Source.newBuilder(program).name("<stdin>").mimeType(JvmMathLang.MIME_TYPE).build(); PolyglotEngine.Value result = engine.eval(source); ... } } } }
mainメソッドです。入力（今回の場合数式）を文字列でよみ、Truffle APIのSourceをビルド、それをエンジンのeval()に渡して数式を評価します。
ではこのエンジンから処理を委譲される部分を見ていきます。言語そのもののクラスです。
@TruffleLanguage.Registration(name = "JVMMATHLANG", version = "0.0.1", mimeType = JvmMathLang.MIME_TYPE) @ProvidedTags({StandardTags.CallTag.class, StandardTags.StatementTag.class, StandardTags.RootTag.class, DebuggerTags.AlwaysHalt.class}) public class JvmMathLang extends TruffleLanguage<JvmMathLangContext> { public static final String MIME_TYPE = "application/x-jvmmathlang";
TruffleLanguageを継承します。JvmMathLangContextは自分で作ったクラスで、コンテキスト、いわゆる入れ物のクラスです。
@TruffleLanguage.Registrationで言語名やバージョン、MIMEタイプを指定します。上のGIFにも表示されています。@ProvidedTagsはまだ理解していません。
@Override protected CallTarget parse(ParsingRequest request) throws Exception { Map<String, JvmMathLangRootNode> functions = parseSource(request.getSource()); JvmMathLangRootNode main = functions.get("main"); JvmMathLangRootNode evalMain = new JvmMathLangRootNode(this, main.getFrameDescriptor(), main.getBodyNode(), "main"); return Truffle.getRuntime().createCallTarget(evalMain); } private Map<String, JvmMathLangRootNode> parseSource(Source source) throws IOException { InputStream inputStream = source.getInputStream(); CharStream charStream = CodePointCharStream.fromBuffer(CodePointBuffer.withBytes(ByteBuffer.wrap(IOUtils.toByteArray(inputStream)))); MathLexer mathLexer = new MathLexer(charStream); CommonTokenStream tokenStream = new CommonTokenStream(mathLexer); MathParser mathParser = new MathParser(tokenStream); MathParser.ProgContext prog = mathParser.prog(); ParseTreeWalker treeWalker = new ParseTreeWalker(); MathParseTreeListener listener = new MathParseTreeListener(); treeWalker.walk(listener, prog); return listener.getFunctions(this); }
エンジンのeval()から処理が始まり、parse()メソッドが呼び出されます（Sourceに指定したMIMEタイプがこの言語のものであるため）。ParsingRequestにはeval()に渡したSourceあります。parseSourceの部分がポイントです。ここはANTLRが生成した処理を呼び出しています。Lexer、Parserを使いASTを作りました。このANTLRのASTをTruffleでのASTに変換しているのがMathParseTreeListenerです。ParseTreeWalkerが巡回したときにリスナーとして処理が呼び出されます。
public class MathParseTreeListener extends MathBaseListener { private Map<String, JvmMathLangRootNode> functions = new HashMap<>(); private JvmMathLangNode node; private LinkedList<JvmMathLangNode> mathLangNodes = new LinkedList<>(); ... @Override public void exitNumberExpr(MathParser.NumberExprContext ctx) { String text = ctx.value.getText(); try { mathLangNodes.push(new LongNode(Long.parseLong(text))); } catch(NumberFormatException e) { mathLangNodes.push(new BigDecimalNode(new BigDecimal(text))); } }
継承元のMathBaseListenerはANTLRで生成したクラスです。LinkedListはスタックとして使います。JvmMathLangRootNodeやJvmMathLangNodeはTruffleで使うASTのノードです。ツリーでNumberExprのとき、つまり単なる数値のノードならTruffleでの数値ノードを生成します。
@NodeInfo(language = "JVMMATHLANG", description = "") public class JvmMathLangRootNode extends RootNode { /** The function body that is executed, and specialized during execution. */ private JvmMathLangNode bodyNode;
Truffleのノードには@NodeInfoアノテーションを付与します。ルートノードなので、実行対象のノードを持っています。
@TypeSystemReference(JvmMathLangTypes.class) @NodeInfo(language = "JVMMATHLANG", description = "") public abstract class JvmMathLangNode extends Node { public abstract Object executeGeneric(VirtualFrame frame);
すべてのノードの親クラスです。この四則演算言語が利用する型をJvmMathLangTypesを通じて指定します。
@TypeSystem({long.class, BigInteger.class, JvmMathLangFunction.class}) public abstract class JvmMathLangTypes {}
longとBigDecimal、それに独自定義のJvmMathLangFunctionを利用します。Functionについては省略します。
で、数値ノードです。
@NodeInfo(shortName = "const") public class LongNode extends JvmMathLangNode { private final long value; public LongNode(long l) { this.value = l; } public long executeLong(VirtualFrame frame) { return this.value; } @Override public Object executeGeneric(VirtualFrame frame) { return this.value; } }
これはlongのノードですが、BigDecimalもほぼ同様です。
同様に、演算子のノードも作成します。
@NodeInfo(shortName = "+") public abstract class AddNode extends BinaryNode { @Specialization(rewriteOn = ArithmeticException.class) protected long add(long left, long right) { return Math.addExact(left, right); } @Specialization @TruffleBoundary protected BigDecimal add(BigDecimal left, BigDecimal right) { return left.add(right); } @Specialization @TruffleBoundary protected BigDecimal add(Object left, Object right) { BigDecimal l = left instanceof BigDecimal ? (BigDecimal) left : BigDecimal.valueOf((long) left); BigDecimal r = right instanceof BigDecimal ? (BigDecimal) right : BigDecimal.valueOf((long) right); return l.add(r); } }
これは加算演算子のノードです。BinaryNodeを継承しています。
@NodeChildren({@NodeChild("leftNode"), @NodeChild("righrNode")}) public abstract class BinaryNode extends JvmMathLangNode {
演算子ノードはすべてBinaryNodeを継承します。@NodeChildrenの内容は、演算子であればその左右にそれぞれノードがあるので、左のノードと右のノードを処理メソッドの引数として受け取れるようにします。
さて、加算に戻ります。メソッドに@Specializationをつけています。これでTruffleから呼び出される処理としてマークしている感じです。JavadocではDefines a method of a node subclass to represent one specialization of an operation.とありました。
@TruffleBoundaryは境界となるメソッドにつけます。longのadd()にはありません。これは、longのadd()でArithmeticExceptionが起こった場合、フォールバックのような感じでまた違うadd()が呼び出されるようにするためです。long以外のadd()は境界なので、フォールバックせず通常の例外処理となります。
AddNodeは抽象クラスです（抽象メソッドはありませんが）。具象クラスはどこにあるかというと、これは自分では実装しません。TruffleDSL annotation processorが具象クラスを生成します。
減算、乗算、除算もほぼ同様です。
またMathParseTreeListenerに戻ります。
public class MathParseTreeListener extends MathBaseListener { ... @Override public void exitInfixExpr(MathParser.InfixExprContext ctx) { JvmMathLangNode right = mathLangNodes.pop(); JvmMathLangNode left = mathLangNodes.pop(); JvmMathLangNode current = null; switch (ctx.op.getType()) { case MathLexer.OP_ADD: current = nodes.ops.AddNodeGen.create(left, right); break; case MathLexer.OP_DIV: current = nodes.ops.DivNodeGen.create(left, right); break; case MathLexer.OP_MUL: current = nodes.ops.MulNodeGen.create(left, right); break; case MathLexer.OP_SUB: current = nodes.ops.SubNodeGen.create(left, right); break; } mathLangNodes.push(current); } ... public Map<String,JvmMathLangRootNode> getFunctions(JvmMathLang jvmMathLang) { functions.put("main", new JvmMathLangRootNode(jvmMathLang, new FrameDescriptor(), node, "main")); return functions; } }
nodes.ops.AddNodeGenもannotation processorが生成するクラスです。このクラスを呼び出して、ノードを生成します。
最後にgetFunctions()を呼べば、全ノードを持つルートノードが取得できます。また言語クラスのparseに戻ります。
@TruffleLanguage.Registration(name = "JVMMATHLANG", version = "0.0.1", mimeType = JvmMathLang.MIME_TYPE) public class JvmMathLang extends TruffleLanguage<JvmMathLangContext> { @Override protected CallTarget parse(ParsingRequest request) throws Exception { Map<String, JvmMathLangRootNode> functions = parseSource(request.getSource()); JvmMathLangRootNode main = functions.get("main"); JvmMathLangRootNode evalMain = new JvmMathLangRootNode(this, main.getFrameDescriptor(), main.getBodyNode(), "main"); return Truffle.getRuntime().createCallTarget(evalMain); }
ルートノードを、TruffleランタイムのメソッドcreateCallTarget()に渡し、CallTargetを生成して戻り値として返せば完了です。
Truffle 0.25での変更点
Truffleは0.25で大きくAPIが変わったようです。Olegのプレゼンのコードのままではdeprecatedとなる部分があります。
- com.oracle.truffle.api.ExecutionContextがdeprecatedになりました
- TruffleLanguage#parse(Source code, Node context, String… argumentNames)がdeprecatedになりました
また実行時にエラーとなることもありました。
[ERROR] /Users/jyukutyo/code/jvmmathlang/src/main/java/nodes/ops/DivNode.java:[11,17] Element BinaryNode at annotation @NodeChild is erroneous: No generic execute method found with 0 evaluated arguments for node type JvmMathLangNode and frame types [com.oracle.truffle.api.frame.VirtualFrame, com.oracle.truffle.api.frame.Frame].
ノードに引数なしのexecuteGeneric()が必要なようです。JvmMathLangNodeクラスにメソッドを定義しました。
感想
プログラミング言語と言えるほどのものではないですが、文法に従ったテキストを解析して処理を実行するところまででき、非常に楽しかったです。ほとんどのことはANTLRとTruffleがやってくれるので、自分では何もしていないなと感じる部分もありますが…
文法をより作り込めば、メソッド呼び出しなどさまざまなことができるのだと思います（そこまでの意欲は今のところないですが…）。上述のsimplelanguageでさえ、内容は全然simpleじゃないですｗ
Graal/TruffleはJavaOneで聞いてからとてもおもしろそうに感じていました。少しだけ理解が深まってよかったです。今後も注目していきたいです。
*1:これらの製品はサムライズム社で！ http://samuraism.com/products/zeroturnaround/jrebel
