Truffle Tutorial Slides (30～60p)の自分用翻訳メモです。

誤訳や省略については保障しません。

問題があれば削除します。

SL(A Simple Language)のハイライト

動的型付け
強い型付け
暗黙の型変換なし
任意精度の整数
第一級関数
動的な関数定義？(Dynamic function redefinition)
オブジェクトとは、キーと値を格納するデータ構造である
- キーと値は任意の型が使用可能
- キーは通常String型

型

SLの型	値	Javaにおける実装？(Java Type in Implementation)
Number	任意精度の整数	64 bit 以内ではlong オーバーフローしたら java.lang.BigInteger
Boolean	true または false	boolean
String	ユニコード文字列	java.lang.String
Function	関数への参照	SLFunction
Object	キーと値	DynamicObject
Null	null	SLNull.SINGLETON

Nullは自分自身を持つ型？(Null is its own type)
「Undefined」とも呼ばれる

ベストプラクティス

パフォーマンスのためになるべくプリミティブ型を利用する
自作(Guest)言語ではJavaのnullを使用しない

構文

Cに類似した制御構文

if, while, break, continue, return

演算子

+, -, *, /, ==, !=, <, <=, >, >=, &&, ||, ()
+ は文字列の連結演算子としても定義される
|| と && は短絡評価を持つ
プロパティへのアクセスは . または [] を用いる？(. or [] for property access)

リテラル

Number, String, Function

組み込み関数？(Builtin functions)

println, readln : 標準入出力
nanoTime : 時間測定？(to allow time measurements)
defineFunction : 動的な関数定義？(Dynamic function redefinition)
stacktrace, helloEqualsWorld : 「stack walking」 and 「stack frame」操作
new : プロパティなしで新しいオブジェクトを割り当てる

構文解析

略

SLの例

略

Getting Started

略

ASTインタプリタ

ごめんなさい省略します

Truffleのノードと木

Class Node

Truffleノードの基本クラス？(base class of all Truffle tree nodes)

親・子の管理
自身を新しいノードに置き換える？(Replacement of this node with a (new) node)
ノードのコピー
execute() メソッドはサブクラスで定義するため、ここでは定義しない？(No execute() methods: define your own in subclasses)

NodeUtilは便利なユーティリティメソッドを提供する。

public abstract class Node implements Cloneable {
    public final Node getParent() { ... }
    public final Iterable<Node> getChildren() { ... }
    public final <T extends Node> T replace(T newNode) { ... }
    public Node copy() { ... }
    public SourceSection getSourceSection();
}

If構文

public final class SLIfNode extends SLStatementNode {

    @Child private SLExpressionNode conditionNode;
    @Child private SLStatementNode thenPartNode;
    @Child private SLStatementNode elsePartNode;

    public SLIfNode(SLExpressionNode conditionNode, SLStatementNode thenPartNode, SLStatementNode elsePartNode) {
        this.conditionNode = conditionNode;
        this.thenPartNode = thenPartNode;
        this.elsePartNode = elsePartNode;
    }

    public void executeVoid(VirtualFrame frame) {
        if (conditionNode.executeBoolean(frame)) {
            thenPartNode.executeVoid(frame);
        }else{
            elsePartNode.executeVoid(frame);
        }
    }
}

子ノードのフィールドには@Childのアノテーションを付け、finalにしない。

プロファイリング付きIf構文

public final class SLIfNode extends SLStatementNode {

    @Child private SLExpressionNode conditionNode;
    @Child private SLStatementNode thenPartNode;
    @Child private SLStatementNode elsePartNode;
    private final ConditionProfile condition = ConditionProfile.createCountingProfile();

    public SLIfNode(SLExpressionNode conditionNode, SLStatementNode thenPartNode, SLStatementNode elsePartNode) {
        this.conditionNode = conditionNode;
        this.thenPartNode = thenPartNode;
        this.elsePartNode = elsePartNode;
    }

    public void executeVoid(VirtualFrame frame) {
        if (condition.profile(conditionNode.executeBoolean(frame))) {
            thenPartNode.executeVoid(frame);
        }else{
            elsePartNode.executeVoid(frame);
        }
    }
}

インタプリタでプロファイリングすると、コンパイラはより良いコードを生成できる。

ブロック

public final class SLBlockNode extends SLStatementNode {

    @Children private final SLStatementNode[] bodyNodes;

    public SLBlockNode(SLStatementNode[] bodyNodes) {
        this.bodyNodes =  bodyNodes;
    }

    @ExplodeLoop public void executeVoid(VirtualFrame frame) {
        for (SLStatementNode statement : bodyNodes) {
            statement.executeVoid(frame);
        }
    }
}

複数のノードを表すフィールドは、＠Childrenをつけたfinal配列で表します。
子要素の繰り返しを行う時は、@ExplodeLoopを付ける必要があります？(The iteration of the children must be annotated with @ExplodeLoop)

return構文 : ノード間の制御フロー

public final class SLReturnNode extends SLStatementNode {

    @Child private SLExpressionNode valueNode;

    ...

    public void executeVoid(VirtualFrame frame) {
        throw new SLReturnException(valueNode.executeGeneric(frame));
    }
}

public final class SLReturnException extends ControlFlowException {

    private final Object result;

    ...
}

public final class SLFunctionBodyNode extends SLExpressionNode {

    @Child private SLStatementNode bodyNode;

    ...

    public Object executeGeneric(VirtualFrame frame) {
        try {
            bodyNode.executeVoid(frame);
        }catch (SLReturnException ex){
            return ex.getResult();
        }
        return SLNull.SINGLETON;
    }
}

ノード間の制御フローに例外を使用する。
制御フローに利用する例外はControlFlowExceptionを継承する。

例外を用いたノード間制御？(Exceptions for Inter-Node Control Flow)

例外はすべてのスタックフレームを巻き戻します？(Exception unwinds all the interpreter stack frames of the method (loops, conditions, blocks, ...))

加算？(Addition)

@NodeChildren({@NodeChild("leftNode"), @NodeChild("rightNode")})
public abstract class SLBinaryNode extends SLExpressionNode {
}

public abstract class SLAddNode extends SLBinaryNode {

    @Specialization(rewriteOn = ArithmeticException.class)
    protected final long add(long left, long right) {
        return ExactMath.addExact(left, right);
    }

    @Specialization
    protected final BigInteger add(BigInteger left, BigInteger right) {
        return left.add(right);
    }

    @Specialization(guards = "isString(left, right)")
    protected final String add(Object left, Object right) {
        return left.toString() + right.toString();
    }

    protected final boolean isString(Object a, Object b) {
        return a instanceof String || b instanceof String;
    }
}

@Specializationメソッドの順序は重要です。最初に一致した要素が選択されます。
他のすべてのspecializationでは、ガードはメソッドのシグネチャに基づいて暗黙的に行われます。

Truffle DSLによって生成されたコード①

ファクトリメソッドで生成されたコード

@GeneratedBy(SLAddNode.class)
public final class SLAddNodeGen extends SLAddNode {

    public static SLAddNode create(SLExpressionNode leftNode, SLExpressionNode rightNode) {
        ... 
    }

    ...
}

The parser uses the factory to create a node that is initially in the uninitialized state.
The generated code performs all the transitions between specialization states.

Truffle DSLによって生成されたコード②

@GeneratedBy(methodName = "add(long, long)", value = SLAddNode.class)
private static final class Add0Node_ extends BaseNode_ {

    @Override public long executeLong(VirtualFrame frameValue) throws UnexpectedResultException {
        long leftNodeValue_;
        try {
            leftNodeValue_ = root.leftNode_.executeLong(frameValue);
        }catch (UnexpectedResultException ex){
            Object rightNodeValue =  executeRightNode_(frameValue);
            return SLTypesGen.expectLong(getNext().execute_(frameValue,  ex.getResult(), rightNodeValue));
        }
        long rightNodeValue_;
        try {
            rightNodeValue_ = root.rightNode_.executeLong(frameValue);
        }catch (UnexpectedResultException ex){
            return SLTypesGen.expectLong(getNext().execute_(frameValue,  leftNodeValue_, ex.getResult()));
        }
        try {
            return root.add(leftNodeValue_, rightNodeValue_);
        } catch (ArithmeticException ex) {
            root.excludeAdd0_ = true;
            return SLTypesGen.expectLong(remove("threw rewrite exception", frameValue, leftNodeValue_, rightNodeValue_));
        }
    }

    @Override public Object execute(VirtualFrame frameValue) {
        try {
            return executeLong(frameValue);
        } catch (UnexpectedResultException ex) {
            return ex.getResult();
        }
    } //元記事ではこの閉じ括弧はない
}

Truffle DSLの型システム定義

@TypeSystem({long.class, BigInteger.class, boolean.class,              String.class, SLFunction.class, SLNull.class})
public abstract class SLTypes {
    @ImplicitCast
    public BigInteger castBigInteger(long value) {
        return BigInteger.valueOf(value);
    }
}

型変換をカスタマイズするには、@TypeCheckと@TypeCastを使用する。

@TypeSystemReference(SLTypes.class)
public abstract class SLExpressionNode extends SLStatementNode {

    public abstract Object executeGeneric(VirtualFrame frame);

    public long executeLong(VirtualFrame frame) throws UnexpectedResultException {
        return SLTypesGen.SLTYPES.expectLong(executeGeneric(frame));
    }

    public boolean executeBoolean(VirtualFrame frame)　...
}

SLTypesGen is a generated subclass of SLTypes.
abstractなexecuteGeneric()に加え、specialization毎のexecute()メソッド

UnexpectedResultException

型に特化したexecute()メソッドは特殊な戻り型を持ちます
- オートボクシングを避けるために、プリミティブな戻り型を許可する。
- キャストなしで結果を使用できる。(Allows to use the result without type casts)
- Speculation types are stable and the specialization fits.
But what to do when speculation was too optimistic?
- 戻り値よりも一般的な型で値を返す必要がある。
- UnexpectedResultExceptionで "boxed"という値を返す。
Exception handler performs node rewriting
- 例外は一度しかスローされないので、パフォーマンスのボトルネックはない。

Truffle DSL ワークフロー

略

フレームレイアウト

フレームはヒープ上のオブジェクトである。
- 関数はプロローグに割り当てられる？(Allocated in the function prologue)
- execute()メソッドへのパラメータとして渡される？(Passed around as parameter to execute() methods)
コンパイラは割り当てを削除する。
- No object allocation and object access.
- 自作(Guest)言語のローカル変数は、Javaのものと同じパフォーマンスを発揮する。
FrameDescriptor: describes the layout of a frame.
- 識別子(通常は変数名)から型付きスロットへのマッピング？(A mapping from identifiers (usually variable names) to typed slots.)
- すべてのスロットはフレームオブジェクトへのユニークなインデックスを持っている？(Every slot has a unique index into the frame object.)
- 解析中に作成および入力(Created and filled during parsing.)
フレーム
- 呼び出された自作(Guest)言語の関数ごとに作成。

フレーム管理

Truffle APIはフレームインターフェースのみを公開している。
- 実装クラスは最適化システムに依存する。
仮想フレーム
- コンパイラによって自動的に最適化される。
- フィールドに代入したり、解釈された関数から抜けたりしてはいけない。
実体化フレーム(MaterializedFrame)
- 制限なく保管できるフレーム？(A frame that can be stored without restrictions)
- 例 : 他の関数に渡す必要があるクロージャのフレーム？(frame of a closure that needs to be passed to other function)
フレームの割り当て
- TruffleRuntimeクラスのファクトリメソッド

フレーム管理

public interface Frame {

    FrameDescriptor getFrameDescriptor();
    Object[] getArguments();
    boolean isType(FrameSlot slot);

    Type getType(FrameSlot slot) throws FrameSlotTypeException;

    void setType(FrameSlot slot, Type value);

    Object getValue(FrameSlot slot);

    MaterializedFrame materialize();
}

フレームはすべてのJavaプリミティブ型とオブジェクトをサポートする。
SLのString・SLFunction・SLNullはObject保管される。
フレームの割り当て・フレームの実装はしてはいけない。

ローカル変数

@NodeChild("valueNode")
@NodeField(name = "slot", type = FrameSlot.class)
public abstract class SLWriteLocalVariableNode extends SLExpressionNode {

    protected abstract FrameSlot getSlot();

    @Specialization(guards = "isLongOrIllegal(frame)")
    protected long writeLong(VirtualFrame frame, long value) {
        getSlot().setKind(FrameSlotKind.Long);
        frame.setLong(getSlot(), value);
        return value;
    }

    protected boolean isLongOrIllegal(VirtualFrame frame) {
        return getSlot().getKind() == FrameSlotKind.Long || getSlot().getKind() == FrameSlotKind.Illegal;
    }

    ...

    @Specialization(contains = {"writeLong", "  writeBoolean"})
    protected Object write(VirtualFrame frame, Object value) {
        getSlot().setKind(FrameSlotKind.Object);
        frame.setObject(getSlot(), value);
        return value;
    }
}

kind?がlongの場合にはsetKind()は何もしません。
単一のプリミティブ型に特化できない場合は、すべての読み書きをObjectに切り替える。

@NodeField(name = "slot", type = FrameSlot.class)
public abstract class SLReadLocalVariableNode extends SLExpressionNode {

    protected abstract FrameSlot getSlot();

    @Specialization(guards = "isLong(frame)")
    protected long readLong(VirtualFrame frame) {
        return FrameUtil.getLongSafe(frame, getSlot());
    }

    protected boolean isLong(VirtualFrame frame) {
        return getSlot().getKind() == FrameSlotKind.Long;
    }

    ...

    @Specialization(contains = {"readLong", "readBoolean"})
    protected Object readObject(VirtualFrame frame) {
        if (!frame.isObject(getSlot())) {
            CompilerDirectives.transferToInterpreter();
            Object result = frame.getValue(getSlot());
            frame.setObject(getSlot(), result);
            return result;
        }
        return FrameUtil.getObjectSafe(frame, getSlot());
    }
} //原文中にはこの閉じ括弧はない

guardは、フレームスロットがlong値を含むことを保証する。
ローカル変数をObject型に切り替える前に、まだプリミティブ値を持つフレームを書くことができます？(we can still have frames with primitive values written before we switched the local variable to the kind Object.)

コンパイル？(Compilation)

抽象構文木の自動部分評価。
- 関数の実行回数により、自動的に起動する。
コンパイルは抽象構文木が安定していると仮定します
- すべての@Childおよび@Childrenフィールドはfinalのように扱われる。
後からのノード書き換えはマシンコードを無効にする？(Later node rewriting invalidates the machine code)
- インタプリタに「最適化解除」と送り返す？(Transfer back to the interpreter: “Deoptimization”)
- ノード書き換えのための複雑なロジックはコンパイルされたコードの一部ではない？(Complex logic for node rewriting not part of compiled code)
- 優れたピークパフォーマンスに不可欠？(Essential for excellent peak performance)
コンパイラの最適化はインタプリタのオーバーヘッドを排除する。
- ノード間でこれ以上ディスパッチしない？(No more dispatch between nodes)
- VirtualFrameのこれ以上の割り当てはしない？(No more allocation of VirtualFrame objects)
- ノード間制御フローのためのこれ以上の例外はない？(No more exceptions for inter-node control flow )

Truffle Tutorial Slides 自分用翻訳メモ①

SL(A Simple Language)のハイライト

型

ベストプラクティス

構文

Cに類似した制御構文

演算子

リテラル

組み込み関数？(Builtin functions)

構文解析

SLの例

Getting Started

ASTインタプリタ

Truffleのノードと木

Class Node

If構文

プロファイリング付きIf構文

ブロック

return構文 : ノード間の制御フロー

例外を用いたノード間制御？(Exceptions for Inter-Node Control Flow)

加算？(Addition)

Truffle DSLによって生成されたコード①

Truffle DSLによって生成されたコード②

Truffle DSLの型システム定義

UnexpectedResultException

Truffle DSL ワークフロー

フレームレイアウト

フレーム管理

フレーム管理

ローカル変数

コンパイル？(Compilation)