Julia ASTs

ジュリアにはコードの2つの表現があります。まず、パーサーによって返される表面構文AST（例えば、Meta.parse関数）があります。これはマクロによって操作されるもので、文字ストリームからjulia-parser.scmによって構築された、書かれたままのコードの構造化された表現です。次に、低下した形式、またはIR（中間表現）があります。これは型推論とコード生成に使用されます。低下した形式では、ノードの種類が少なく、すべてのマクロが展開され、すべての制御フローが明示的な分岐と文のシーケンスに変換されます。低下した形式はjulia-syntax.scmによって構築されます。

まず、マクロを書くために必要なASTに焦点を当てます。

Surface syntax AST

フロントエンドのASTはほぼ完全に Expr と原子（例：シンボル、数値）で構成されています。一般的に、視覚的に異なる各構文形式に対して異なる表現ヘッドがあります。例はs式構文で示されます。各括弧付きリストはExprに対応し、最初の要素がヘッドです。例えば、(call f x) はJuliaの Expr(:call, :f, :x) に対応します。

Calls

do 構文:

f(x) do a,b
    body
end

(do (call f x) (-> (tuple a b) (block body)))として解析されます。

Operators

ほとんどの演算子の使用は単なる関数呼び出しであるため、callというヘッドで解析されます。しかし、一部の演算子は特別な形式（必ずしも関数呼び出しではない）であり、その場合、演算子自体が式のヘッドとなります。julia-parser.scmでは、これらは「構文演算子」と呼ばれています。一部の演算子（+および*）はN-引数解析を使用し、連鎖した呼び出しは単一のN引数呼び出しとして解析されます。最後に、比較の連鎖には独自の特別な式構造があります。

Bracketed forms

Macros

Strings

ドキュメント文字列の構文:

"some docs"
f(x) = x

(macrocall (|.| Core '@doc) (line) "some docs" (= (call f x) (block x))) を解析します。

Imports and such

using は import と同じ表現を持ちますが、式の先頭が :using である点が異なります。

Numbers

Juliaは多くのScheme実装よりも多くの数値型をサポートしているため、すべての数値がAST内で直接Scheme数値として表現されるわけではありません。

Block forms

ブロックのステートメントは (block stmt1 stmt2 ...) として解析されます。

If ステートメント:

if a
    b
elseif c
    d
else
    e
end

解析として：

(if a (block (line 2) b)
    (elseif (block (line 3) c) (block (line 4) d)
            (block (line 6 e))))

while ループは (while condition body) として解析されます。

for ループは (for (= var iter) body) として解析されます。イテレーション仕様が複数ある場合、それらはブロックとして解析されます: (for (block (= v1 iter1) (= v2 iter2)) body)。

break と continue は、0引数の式 (break) と (continue) として解析されます。

let は (let (= var val) body) または (let (block (= var1 val1) (= var2 val2) ...) body) として解析されます。これは for ループのようなものです。

基本的な関数定義は (function (call f x) body) として解析されます。より複雑な例：

function f(x::T; k = 1) where T
    return x+1
end

解析として：

(function (where (call f (parameters (kw k 1))
                       (:: x T))
                 T)
          (block (line 2) (return (call + x 1))))

型定義:

mutable struct Foo{T<:S}
    x::T
end

解析されます:

(struct true (curly Foo (<: T S))
        (block (line 2) (:: x T)))

最初の引数は、型が可変かどうかを示すブール値です。

try ブロックは (try try_block var catch_block finally_block) として解析されます。catch の後に変数がない場合、var は #f です。finally 節がない場合、最後の引数は存在しません。

Quote expressions

Juliaのソース構文形式は、コード引用（quoteおよび :( )）に対して $ を使った補間をサポートしています。Lispの用語で言うと、これは実際には「バッククォート」または「準クォート」形式です。内部的には、補間なしのコード引用の必要性もあります。Juliaのスキームコードでは、補間しない引用は式のヘッド inert で表されます。

inert 表現は Julia の QuoteNode オブジェクトに変換されます。これらのオブジェクトは任意の型の単一の値をラップし、評価されると単にその値を返します。

アトムを引数とする quote 式も QuoteNode に変換されます。

Line numbers

ソース位置情報は (line line_num file_name) の形式で表され、3 番目のコンポーネントはオプションです（現在の行番号が変更される場合は省略されますが、ファイル名は省略されません）。

これらの表現は、JuliaのLineNumberNodeとして表されます。

Macros

マクロの衛生状態は、escape と hygienic-scope というヘッドペアの表現を通じて示されます。マクロ展開の結果は自動的に (hygienic-scope block module) でラップされ、新しいスコープの結果を表します。ユーザーは呼び出し元からコードを補間するために、内部に (escape block) を挿入することができます。

Lowered form

低い形式（IR）はコンパイラにとってより重要です。なぜなら、型推論、インライン化のような最適化、コード生成に使用されるからです。また、入力構文の大幅な再配置から生じるため、人間にはあまり明白ではありません。

Symbolやいくつかの数値型に加えて、以下のデータ型が低下した形式で存在します：

• Expr

  headフィールドによって示されるノードタイプと、サブ式のVector{Any}であるargsフィールドを持っています。表面ASTのほぼすべての部分はExprで表されますが、IRは主に呼び出しと一部のトップレベル専用の形式のために、限られた数のExprのみを使用します。

• スロット番号

  引数とローカル変数を連続番号で識別します。スロットインデックスを示す整数値の id フィールドがあります。これらのスロットの型は、それらの CodeInfo オブジェクトの slottypes フィールドで確認できます。

• 引数

  SlotNumberと同じですが、最適化後のみ表示されます。参照されているスロットが囲んでいる関数の引数であることを示します。

• コード情報

  一連のステートメントのIRをラップします。そのcodeフィールドは実行する式の配列です。

• GotoNode

  無条件分岐。引数は分岐先であり、ジャンプするコード配列内のインデックスとして表されます。

• GotoIfNot

  条件分岐。cond フィールドが false に評価される場合、dest フィールドによって識別されるインデックスに移動します。

• ReturnNode

  引数（valフィールド）を囲む関数の値として返します。valフィールドが未定義の場合、これは到達不可能なステートメントを表します。

• QuoteNode

  任意の値をデータとして参照するためにラップします。例えば、関数 f() = :a は、value フィールドがシンボル a である QuoteNode を含んでおり、評価するのではなくシンボル自体を返すために使用されます。

• GlobalRef

  モジュール mod のグローバル変数 name を参照します。

• SSA値

  コンパイラによって挿入された、連続番号（1から始まる）の静的単一割り当て（SSA）変数を指します。SSAValueの番号（id）は、それが表す値の式のコード配列インデックスです。

• NewvarNode

  変数（スロット）が作成されるポイントを示します。これにより、変数が未定義にリセットされる効果があります。

Expr types

これらの記号は、Exprのheadフィールドに小文字で表示されます。

• コール

  関数呼び出し（動的ディスパッチ）。 args[1] は呼び出す関数で、 args[2:end] は引数です。

• 呼び出す

  関数呼び出し（静的ディスパッチ）。 args[1] は呼び出す MethodInstance であり、args[2:end] は引数です（呼び出されている関数は args[2] にあります）。

• static_parameter

  静的パラメータをインデックスで参照します。

• =

  課題。IRでは、最初の引数は常にSlotNumberまたはGlobalRefです。

• メソッド

  汎用関数にメソッドを追加し、必要に応じて結果を割り当てます。

  1引数形式と3引数形式があります。1引数形式は、構文 function foo end から生じます。1引数形式では、引数はシンボルです。このシンボルが現在のスコープ内で既に関数の名前として使われている場合、何も起こりません。シンボルが未定義の場合、新しい関数が作成され、そのシンボルで指定された識別子に割り当てられます。シンボルが定義されているが非関数の名前を持つ場合、エラーが発生します。「関数の名前を持つ」という定義は、バインディングが定数であり、シングルトン型のオブジェクトを参照することを意味します。これは、シングルトン型のインスタンスがメソッドを追加する型を一意に識別するためです。型にフィールドがある場合、メソッドがインスタンスに追加されるのか、その型に追加されるのかは明確ではありません。

  3引数形式には以下の引数があります：

  • args[1]

    関数名、または不明または不要な場合は nothing。シンボルの場合、最初の式は上記の1引数形式のように振る舞います。この引数はその後無視されます。メソッドが厳密に型によって追加される場合は nothing であることができます、(::T)(x) = x、または既存の関数にメソッドが追加される場合、MyModule.f(x) = x。

  • args[2]

    SimpleVector の引数タイプデータ。 args[2][1] は引数タイプの SimpleVector であり、 args[2][2] はメソッドの静的パラメータに対応する型変数の SimpleVector です。

  • args[3]

    メソッド自体の CodeInfo。スコープ外のメソッド定義（異なるスコープで定義されたメソッドを持つ関数にメソッドを追加する）に対しては、:lambda 式に評価される式です。

• 構造体型

  7つの引数を持つ新しい struct を定義する式：

  • args[1]

    structの名前

  • args[2]

    SimpleVectorのパラメータを指定して作成するcall式

  • args[3]

    fieldnamesを指定してSimpleVectorを作成するcall式

  • args[4]

    Symbol、GlobalRef、またはExprは、スーパタイプを指定します（例：:Integer、GlobalRef(Core, :Any)、または:(Core.apply_type(AbstractArray, T, N))）

  • args[5]

    SimpleVectorのフィールドタイプを指定するcall式

  • args[6]

    mutableの場合はtrueのBool

  • args[7]

    初期化に必要な引数の数。これはフィールドの数、または内部コンストラクタの new ステートメントによって呼び出される最小限のフィールドの数になります。

• 抽象型

  3つの引数を持つ式で、新しい抽象型を定義します。引数は、struct_type式の引数1、2、および4と同じです。

• プリミティブ型

  4引数の式は、新しいプリミティブ型を定義します。引数1、2、および4はstruct_typeと同じです。引数3はビット数です。

  Julia 1.5

  struct_type、abstract_type、および primitive_type はJulia 1.5で削除され、新しいビルトイン関数への呼び出しに置き換えられました。

• グローバル

  グローバルバインディングを宣言します。

• const

  定数として（グローバル）変数を宣言します。

• 新しい

  新しい構造体のようなオブジェクトを割り当てます。最初の引数は型です。new 擬似関数はこれに変換され、型は常にコンパイラによって挿入されます。これは非常に内部専用の機能であり、チェックは行われません。任意の new 式を評価すると、簡単にセグメンテーションフォルトが発生する可能性があります。

• splatnew

  newと似ていますが、フィールド値は単一のタプルとして渡されます。newが第一級関数であった場合のsplat(new)と同様に機能します。そのため、この名前が付けられています。

• isdefined

  Expr(:isdefined, :x) は、x が現在のスコープで既に定義されているかどうかを示す Bool を返します。

• the_exception

  jl_current_exception(ct)によって返される、catchブロック内で捕捉された例外を返します。

• エンター

  例外ハンドラ（setjmp）に入ります。args[1]は、エラー時にジャンプするキャッチブロックのラベルです。pop_exceptionによって消費されるトークンを生成します。

• 休暇

  ポップ例外ハンドラー。 args[1] はポップするハンドラーの数です。

• pop_exception

  キャッチブロックを出るときに、現在の例外のスタックを関連する enter の状態に戻します。 args[1] には関連する enter からのトークンが含まれています。

  Julia 1.1

  pop_exception は Julia 1.1 で新しく追加されました。

• インバウンズ

  境界チェックをオンまたはオフにするコントロール。スタックが維持され、もしこの式の最初の引数が真または偽（trueは境界チェックが無効であることを意味します）であれば、それがスタックにプッシュされます。最初の引数が:popの場合、スタックがポップされます。

• 境界チェック

  @inboundsでマークされたコードのセクションにインライン化された場合はfalseの値を持ち、それ以外の場合はtrueの値を持ちます。

• ループ情報

  ループの終了を示します。LowerSimdLoopに渡されるメタデータを含み、@simd式の内部ループをマークするか、LLVMループパスに情報を伝播させるために使用されます。

• copyast

  クォジクォートの実装の一部です。引数は表層構文ASTであり、単純に再帰的にコピーされ、実行時に返されます。

• メタ

  メタデータ。 args[1] は通常、メタデータの種類を指定するシンボルであり、残りの引数は自由形式です。以下の種類のメタデータが一般的に使用されます：

  • :inline と :noinline：インラインヒント。

• foreigncall

  ccall 情報のための静的に計算されたコンテナ。フィールドは次のとおりです：

  • args[1] : 名前

    外国関数のために解析される式。

  • args[2]::Type : RT

    含まれているメソッドが定義されたときに静的に計算される（リテラル）戻り値の型。

  • args[3]::SimpleVector (の型) : AT

    含まれているメソッドが定義されたときに静的に計算された引数の型の（リテラル）ベクター。

  • args[4]::Int : nreq

    varargs関数定義に必要な引数の数。

  • args[5]::QuoteNode{Symbol} : 呼び出し規約

    呼び出しの規約。

  • args[6:5+length(args[3])] : 引数

    すべての引数の値（各引数の型は args[3] に示されています）。

  • args[6+length(args[3])+1:end] : gc-ルーツ

    呼び出しの間にgc-rootedされる必要がある追加のオブジェクト。これらがどこから派生し、どのように処理されるかについては、Working with LLVMを参照してください。

• new_opaque_closure

  新しい不透明なクロージャを構築します。フィールドは次のとおりです：

  • args[1] : 署名

    不透明クロージャの関数シグネチャ。不透明クロージャはディスパッチに参加しませんが、入力タイプは制限できます。

  • args[2] : isva

    クロージャが可変長引数を受け入れるかどうかを示します。

  • args[3] : lb

    出力タイプの下限。 (デフォルトは Union{})

  • args[4] : ub

    出力タイプの上限。（デフォルトは Any）

  • args[5] : メソッド

    opaque_closure_method 表現としての実際のメソッド。

  • args[6:end] : キャプチャ

    不透明クロージャによってキャプチャされた値。

  Julia 1.7

  ジュリア1.7で不透明クロージャが追加されました。

Method

一意のコンテナが、単一のメソッドに対する共有メタデータを説明します。

• 名前, モジュール, ファイル, 行, シグ

  メタデータは、コンピュータと人間のためにメソッドを一意に識別するためのものです。

• あいまい

  このメソッドと曖昧な可能性のある他のメソッドのキャッシュ。

• 専門分野

  このメソッドのために作成されたすべての MethodInstance のキャッシュで、ユニーク性を確保するために使用されます。ユニーク性は、特にインクリメンタルプリコンパイルやメソッドの無効化の追跡において効率のために必要です。

• ソース

  元のソースコード（利用可能な場合、通常は圧縮されています）。

• ジェネレーター

  特定のメソッドシグネチャに対して専門的なソースを取得するために実行可能な呼び出し可能オブジェクト。

• ルーツ

  ASTに補間された非ASTのものへのポインタで、ASTの圧縮、型推論、またはネイティブコードの生成に必要です。

• nargs、isva、called、is_for_opaque_closure、

  このメソッドのソースコードに対する説明的ビットフィールド。

• プライマリーワールド

  このメソッドを「所有する」世界の年齢。

MethodInstance

ユニークなコンテナで、メソッドの単一の呼び出し可能なシグネチャを説明します。特に Proper maintenance and care of multi-threading locks を参照して、これらのフィールドを安全に変更する方法に関する重要な詳細を確認してください。

• specTypes

  このMethodInstanceの主キー。ユニーク性はdef.specializationsのルックアップを通じて保証されます。

• def

  この関数が記述するMethodの特化版。あるいは、これはモジュール内で展開されたトップレベルのラムダであり、メソッドの一部ではない場合のModule。

• sparam_vals

  specTypesの静的パラメータの値。Method.unspecializedのMethodInstanceでは、これは空のSimpleVectorです。しかし、MethodTableキャッシュからのランタイムMethodInstanceの場合、これは常に定義されており、インデックス可能です。

• 未推論

  トップレベルのサンクのための未圧縮ソースコード。さらに、生成された関数の場合、これはソースコードが見つかる多くの場所の1つです。

• バックエッジ

  キャッシュ依存関係の逆リストを保存して、新しいメソッド定義後に必要となる可能性のあるインクリメンタル再解析/再コンパイル作業を効率的に追跡します。これは、他の MethodInstance のリストを保持することによって機能し、これらはこの MethodInstance への可能な呼び出しを含むように推論または最適化されています。これらの最適化結果は、cache のどこかに保存されているか、定数伝播のようにキャッシュしたくない何かの結果である可能性があります。したがって、ここでさまざまなキャッシュエントリへのすべてのバックエッジをマージします（ほとんどの場合、適用可能なキャッシュエントリは1つだけで、最大ワールドのためのセンチネル値があります）。

• キャッシュ

  このテンプレートインスタンスを共有する CodeInstance オブジェクトのキャッシュ。

CodeInstance

• def

  このキャッシュエントリが派生した MethodInstance。

• オーナー

  この CodeInstance の所有者を表すトークンです。jl_egal を使用して一致させます。

• rettype/rettype_const

  specFunctionObject フィールドの推測される戻り値の型は、一般的に関数全体の計算された戻り値の型でもあります。

• 推測された

  この関数の推測されたソースのキャッシュを含む可能性があるか、単に rettype が推測されていることを示すために nothing に設定される可能性があります。

• ftpr

  汎用のjlcallエントリーポイント。

• jlcall_api

  fptrを呼び出す際に使用するABI。いくつかの重要なものには以下が含まれます：

  • 0 - まだコンパイルされていません
  • 1 - JL_CALLABLE jl_value_t *(*)(jl_function_t *f, jl_value_t *args[nargs], uint32_t nargs)
  • 2 - 定数（rettype_constに格納された値）
  • 3 - 静的パラメータを転送した jl_value_t *(*)(jl_svec_t *sparams, jl_function_t *f, jl_value_t *args[nargs], uint32_t nargs)
  • 4 - インタープリタで実行 jl_value_t *(*)(jl_method_instance_t *meth, jl_function_t *f, jl_value_t *args[nargs], uint32_t nargs)

• min_world / max_world

  このメソッドインスタンスが呼び出されるのに有効な世界の年齢の範囲。もし max_world が特別なトークン値 -1 であれば、その値はまだ知られていません。再考を必要とするバックエッジに遭遇するまで、引き続き使用される可能性があります。

CodeInfo

ソースコードを格納するための（通常は一時的な）コンテナ。

• コード

  Any ステートメントの配列

• スロット名

  スロット（引数またはローカル変数）ごとの名前を付けるシンボルの配列。

• スロットフラグ

  スロットプロパティの UInt8 配列で、ビットフラグとして表現されています：

  • 0x02 - 割り当て済み（この変数の左側に割り当て文がない場合のみ偽）
  • 0x08 - 使用済み（スロットの読み取りまたは書き込みがある場合）
  • 0x10 - 一度静的に割り当てられた
  • 0x20 - 割り当て前に使用される可能性があります。このフラグは型推論の後のみ有効です。

• ssavaluetypes

  配列またはInt。

  Intの場合、関数内のコンパイラによって挿入された一時的な場所の数（code配列の長さ）を示します。配列の場合、各場所の型を指定します。

• ssaflags

  関数内の各式に対するステートメントレベルの32ビットフラグ。詳細については、julia.hのjl_code_info_tの定義を参照してください。

• リネーテーブル

  ソースロケーションオブジェクトの配列

• codelocs

  linetableに関連付けられた各ステートメントの位置を示す整数インデックスの配列。

オプションフィールド:

• スロットタイプ

  スロットのための型の配列。

• rettype

  低下形式（IR）の推測される戻り値の型。デフォルト値は Any です。

• 推論制限ヒューリスティクスのためのメソッド

  method_for_inference_heuristics は、推論中に必要に応じて与えられたメソッドのジェネレーターを拡張します。

• 親

  このオブジェクトを「所有する」MethodInstance（該当する場合）。

• エッジ

  メソッドインスタンスを無効にする必要があるフォワードエッジ。

• min_world/max_world

  このコードが推測された時点で有効だった世界の年齢の範囲。

ブールプロパティ:

• 推測された

  これは型推論によって生成されたものですか。

• インライン可能

  この内容がインライン化の対象となるべきかどうか。

• propagate_inbounds

  この内容が、@boundscheck ブロックを省略する目的でインライン化されたときに @inbounds を伝播させるべきかどうか。

UInt8 設定:

• constprop

  • 0 = ヒューリスティックを使用する
  • 1 = 攻撃的
  • 2 = なし

• purity 5ビットフラグから構成されています：

  • 0x01 << 0 = このメソッドは一貫して返すか終了することが保証されています (:consistent)
  • 0x01 << 1 = このメソッドは外部から意味的に見える副作用がない（:effect_free）
  • 0x01 << 2 = このメソッドは例外をスローしないことが保証されています（:nothrow）
  • 0x01 << 3 = このメソッドは終了することが保証されています (:terminates_globally)
  • 0x01 << 4 = このメソッド内の構文制御フローは終了することが保証されています（:terminates_locally）

  Base.@assume_effectsの詳細については、ドキュメントを参照してください。