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 である代わりに :import です。

Numbers

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

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) の形式で表され、第三のコンポーネントはオプションです（現在の行番号が変わる場合は省略されますが、ファイル名は省略されません）。

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

Macros

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

Lowered form

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

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

• Expr

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

• スロット番号

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

• 引数

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

• コード情報

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

• GotoNode

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

• GotoIfNot

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

• ReturnNode

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

• QuoteNode

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

• グローバル参照

  モジュール 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] にあります）。

• 静的パラメータ

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

• =

  課題。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

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

• エンター

  例外ハンドラ（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の値を持ちます。

• ループ情報

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

• 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

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

ブールプロパティ:

• 推測された

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

• インライン可能

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

• プロパゲートインバウンズ

  この内容が @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の詳細については、ドキュメントを参照してください。