Truffle Tutorial Slides 自分用翻訳メモ①

[Truffle Tutorial Slides](https://lafo.ssw.uni-linz.ac.at/pub/papers/2016_PLDI_Truffle.pdf) (30～60p)の自分用翻訳メモです。

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

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



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

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

  - キーと値は任意の型が使用可能

  - キーは通常String型



# 型

| SLの型   | 値                | Javaにおける実装？(Java Type in Implementation)              |
| -------- | ----------------- | ------------------------------------------------------------ |
| Number   | 任意精度の整数    | 64 bit 以内ではlong <br>オーバーフローしたら 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は便利なユーティリティメソッドを提供する。



```java
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構文

```java
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構文

```java
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);
        }
    }
}
```





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



# ブロック

```java
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構文 : ノード間の制御フロー

```java
public final class SLReturnNode extends SLStatementNode {
    
    @Child private SLExpressionNode valueNode;
    
    ...
    
    public void executeVoid(VirtualFrame frame) {
        throw new SLReturnException(valueNode.executeGeneric(frame));
    }
}
```



```java
public final class SLReturnException extends ControlFlowException {
    
    private final Object result;
    
    ...
}
```



```java
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)

 

```java
@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によって生成されたコード①

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

```java
@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によって生成されたコード②

```java
@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の型システム定義

```java
@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を使用する。



```java
@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クラスのファクトリメソッド



# フレーム管理

```java
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保管される。

+ フレームの割り当て・フレームの実装はしてはいけない。



# ローカル変数

```java
@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に切り替える。



```java
@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 )