Fight the Future

Java言語とJVM、そしてJavaエコシステム全般にまつわること

プレゼン、ボランティアコーチします!

勉強会でスピーカーをやりたいけど、プレゼンが初めて、苦手という方に無償でコーチします!資料レビューや録画リハへアドバイスします。Twitter@jyukutyoまでメンションでもDMでも。

私はデブサミやJJUG CCCなど200人規模で登壇経験ありです。海外での登壇も短いながらあり。デブサミ2017では公募スピーカー1位でした!

オレオレJVM言語を作ろう! How to create a new JVM language #Graal #Truffle

DevoxxUSに参加した際、とてもおもしろかったセッションがありました。Oleg Šelajevの"How to create a new JVM language"というセッションです。

www.youtube.com

OlegはvJUG(virtual JUG: オンライン上の仮想Java User Group)のOrganiser、JRebelやXRebelを作っているZeroTurnaroundの人です。*1

このセッションでは、ANTLRとGraal(とくにTruffle)を使って四則演算する言語を作ろう!というものでした。とてもおもしろかったのですが、1つ問題がありました。

ソースが公開されていない!

OlegのGitHubにもありませんでした。

そこで僕は決めました。セッション動画を見ながら、表示されるコードを写して自分で実装しよう!と…

結果、できました!

f:id:jyukutyo:20170712062605g:plain

ソースはこちらです。

github.com

ただ、動画では公開されていない部分もあり、いろいろ検索してTruffleのサンプルで簡易言語を実装したプロジェクトのソースを参考にしました。見た感じOlegもこれを元にしている気がします。

github.com

概要

簡易な言語として、以下の構成にします。

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.

http://www.antlr.org/

(適当訳)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

f:id:jyukutyo:20170708122317p:plain

こんな感じでASTが構築されたことがわかります。

IntelliJ Plugin

ANTLRBNFを書くときは、プラグインを入れると書きやすいです。

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じゃないですw

Graal/TruffleはJavaOneで聞いてからとてもおもしろそうに感じていました。少しだけ理解が深まってよかったです。今後も注目していきたいです。

*1:これらの製品はサムライズム社で! http://samuraism.com/products/zeroturnaround/jrebel