Truffle Tutorial Slides 自分用翻訳メモ①

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 )