Julia の AST

Julia には二種類のコード表現があります。一つ目は表層構文 AST (surface syntax AST) で、これはパーサー (例えば Meta.parse) によって生成され、マクロによって操作される表現です。表層構文 AST は入力されたコードをそのまま構造的に表現したものであり、文字ストリームから julia-parser.scm によって生成されます。二つ目のコード表現は低水準形式 (lowered form) またの名を中間表現 (intermediate representation, IR) であり、これは型推論とコード生成で使われる表現です。低水準形式に含まれるノードの種類は表層構文 AST より少なく、マクロは全て展開され、制御構造は明示的な分岐と文の並びに変換されます。低水準形式は julia-syntax.scm によって構築されます。

マクロを書くには AST1 の理解が必要なので、こちらを先に説明します。

表層構文 AST

フロントエンド AST はほぼ全てが Expr と原子式 (atom/シンボル/数値など) からなります。一般に、視覚的に異なる形式の構文にはそれぞれ異なるヘッドが使われます。

以降の例は S 式の構文で示されます。括弧で囲われたリストが一つの Expr に対応し、最初の要素がヘッドに対応します。例えば (call f x) は Julia における Expr(:call, :f, :x) を表します。

関数呼び出し

入力 AST
f(x) (call f x)
f(x, y=1, z=2) (call f x (kw y 1) (kw z 2))
f(x; y=1) (call f (parameters (kw y 1)) x)
f(x...) (call f (... x))

do 構文

f(x) do a,b
    body
end

は、(do (call f x) (-> (tuple a b) (block body))) とパースされます。

演算子

ほとんどの演算子は関数呼び出しを表しているだけなので、ヘッドが call の式としてパースされます。ただし一部の演算子は (関数呼び出しとは限らない) 特殊形式であり、演算子がそのままヘッドとなります。そういった演算子は julia-parser.scm で「構文演算子 (syntactic operator)」と呼ばれています。また N-ary としてパースされる演算子 (+ と *) もあります。つまりこれらの演算子が続けて書かれると N 個の引数を持った関数呼び出しとしてパースされるということです。また続けて書かれた比較も特別な式構造を持ちます。

入力 AST
x+y (call + x y)
a+b+c+d (call + a b c d)
2x (call * 2 x)
a&&b (&& a b)
x += 1 (+= x 1)
a ? 1 : 2 (if a 1 2)
a:b (: a b)
a:b:c (: a b c)
a,b (tuple a b)
a==b (call == a b)
1 < i <= n (comparison 1 < i <= n)
a.b (. a (quote b))
a.(b) (. a (tuple b))

括弧を使った式

入力 AST
a[i] (ref a i)
t[i;j] (typed_vcat t i j)
t[i j] (typed_hcat t i j)
t[a b; c d] (typed_vcat t (row a b) (row c d))
a{b} (curly a b)
a{b;c} (curly a (parameters c) b)
[x] (vect x)
[x,y] (vect x y)
[x;y] (vcat x y)
[x y] (hcat x y)
[x y; z t] (vcat (row x y) (row z t))
[x for y in z, a in b] (comprehension x (= y z) (= a b))
T[x for y in z] (typed_comprehension T x (= y z))
(a, b, c) (tuple a b c)
(a; b; c) (block a (block b c))

マクロ

入力 AST
@m x y (macrocall @m (line) x y)
Base.@m x y (macrocall (. Base (quote @m)) (line) x y)
@Base.m x y (macrocall (. Base (quote @m)) (line) x y)

文字列

入力 AST
"a" "a"
x"y" (macrocall @x_str (line) "y")
x"y"z (macrocall @x_str (line) "y" "z")
"x = $x" (string "x = " x)
`a b c` (macrocall @cmd (line) "a b c")

docstring の構文

"some docs"
f(x) = x

は、(macrocall (|.| Core '@doc) (line) "some docs" (= (call f x) (block x))) とパースされます。

インポートとエクスポート

入力 AST
import a (import (. a))
import a.b.c (import (. a b c))
import ...a (import (. . . . a))
import a.b, c.d (import (. a b) (. c d))
import Base: x (import (: (. Base) (. x)))
import Base: x, y (import (: (. Base) (. x) (. y)))
export a, b (export a b)

using の表現は import と同じですが、ヘッドが :import ではなく :using となります。

数値

Julia は普通の scheme 実装より多くの数値型をサポートします。そのため AST 内で scheme の数値として表せない Julia の数値も存在します。

入力 AST
11111111111111111111 (macrocall @int128_str (null) "11111111111111111111")
0xfffffffffffffffff (macrocall @uint128_str (null) "0xfffffffffffffffff")
1111...たくさんの桁... (macrocall @big_str (null) "1111....")

ブロック形式

文のブロックは (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 5 e))))

while ループは (while condition body) とパースされます。

for ループは (for (= var iter) body) とパースされます。反復するオブジェクトがいくつか指定されたときは、ブロックを使って (for (block (= v1 iter1) (= v2 iter2)) body) とパースされます。

break と continue はゼロ引数の式としてパースされ、それぞれ (break) および (continue) となります。

let のパースは for ループと同様であり、(let (= var val) body) または (let (block (= var1 val1) (= var2 val2) ...) body) となります。

単純な関数定義は (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 節が存在しなければ最後の引数は省略されます。

クオート式

Julia ソースでコードをクオートする構文 (quote と :(...)) は $ のよる補間をサポートします。これは Julia のクオートが Lisp 用語で言うところの「バッククオート (backquote)」またの名を「準クオート (quasiquote)」であることを意味します。また Julia 内部では補間を行わないコードのクオートも必要になるので、Julia 内部の scheme コードは補間を行わないクオートを表すときにヘッドが inert の式を使います。

inert 式は Julia の QuoteNode オブジェクトに変換されます。このオブジェクトは任意の型の値を一つラップしたものであり、評価するとその値がそのまま返ります。

引数に原子式を持つ quote 式も QuoteNode に変換されます。

行番号

ソースの位置情報は (line line_num file_name) と表されます。第三要素は省略可能です (ファイル名が変わらないまま現在の行番号だけが変わると省略されます)。

行番号を表す式は Julia で LineNumberNode として表されます。

マクロ

マクロの健全性はヘッドに escape あるいは hygienic-scope を持つ式を使って処理されます。マクロ展開の結果は自動的に (hygienic-scope block module) で包まれ、結果が新しくできたスコープに存在することが表されます。ユーザーは (escape block) を内側に挿入することで呼び出し側からコードを補間できます。

低水準形式

低水準形式 (IR) は型推論・最適化 (インライン化など)・コード生成で使われるので、コンパイラにとって AST より重要です。一方で、低水準形式は入力された構文を大幅に組み替えることで生成されるので、人間にとっては AST より読みにくくなります。

Symbol と数値型に加えて、低水準形式には次のデータ型が現れます:

Expr 型

Expr 型の head フィールドに使われるシンボルとその意味は次の通りです:

Method 型

単一のメソッドを曖昧さなく記述する共有メタデータからなるコンテナです3。

MethodInstance 型

Method に対する呼び出し可能な単一のシグネチャを表す曖昧性が取り除かれたコンテナです。マルチスレッディングにおけるロックの適切な管理と対処の章に MethodInstance 型のフィールドを安全な形で変更するときの重要な注意点があります。

CodeInstance 型

CodeInfo 型

低水準化されたソースコードを保持する (通常は一時的な) コンテナです。

省略可能なフィールド:

真偽値プロパティ:

  1. 訳注: 「AST」「表層構文 AST」「フロントエンド AST」は全て同じ意味で使われている。[return]

  2. 訳注: 英語版では MethodInstance となっていたのを修正した。[return]

  3. 訳注: これ以降の Method, MethodInstance, CodeInstance, CodeInfo の説明には現在のバージョンに存在しないフィールドの説明が含まれる。[return]

広告