Julia の関数呼び出し

この章では Julia の関数・メソッド定義・メソッドテーブルがどのように動作するかを説明します。

メソッドテーブル

Julia の関数は全て総称関数 (generic function) です。一つの総称関数は概念的には一つの関数ですが、複数の定義 (メソッド) から構成されます。総称関数のメソッドが格納されるのがメソッドテーブルです。メソッドテーブル (MethodTable 型のオブジェクト) は TypeName のタプルをキーに持ちます。TypeName はパラメータ化された型の族を表し、例えば Complex{Float32}Complex{Float64} はどちらも Complex という TypeName を持ちます。

Julia の全てのオブジェクトは呼び出し可能なオブジェクトになれます。なぜならオブジェクトは型を持ち、型は TypeName を持つからです。

関数呼び出し

f(x,y) という関数呼び出しが現れると、次のステップで処理が進みます:

引数を表すタプルの第一要素に関数の型が含まれることに注意してください。これは関数の型がパラメータを持つ可能性があり、ディスパッチで考慮される必要があるためです。このタプルを使ってメソッドテーブルが検索されます。

ディスパッチ処理は jl_apply_generic で行われます。jl_apply は引数 (f, x, y) からなる配列と配列の長さ (3) の二つを引数に受け取ります。

Julia のシステムには関数と引数リストを受け取る API に二つの種類があります。関数と引数を個別に受け取るものと、まとめて一つの引数として受け取るものです。前者では処理対象の関数が個別に渡されるので、その関数に対する引数には関数の情報が含まれません。後者では、API に対する引数の最初の要素が関数となります。

例えば関数呼び出しを行う次の関数は args ポインタだけを受け取るので、args の最初の要素は呼び出す関数となります:

jl_value_t *jl_apply(jl_value_t **args, uint32_t nargs)

次の関数は同じ処理を行いますが、呼び出す関数を別の引数に受け取ります。そのため args 配列に関数は含まれません:

jl_value_t *jl_call(jl_function_t *f, jl_value_t **args, int32_t nargs);

メソッドの追加

ディスパッチ処理は上記のようになっているので、新しいメソッドの定義に必要なのは次の二つだけです:

  1. タプル型の値
  2. メソッド本体のコード

jl_method_def がこの操作を実装します。jl_first_argument_datatype を通して第一引数の型からメソッドの追加先となるメソッドテーブルが取得されます。引数のタプル型が抽象型となる可能性があるので、この処理は対応するディスパッチ処理よりもずっと複雑になります。例えば次に示すような奇妙な関数定義が可能です:

(::Union{Foo{Int},Foo{Int8}})(x) = 0

この定義に適合するメソッドが全て同じメソッドテーブルに追加されるためです。

総称関数の作成

Julia では全てのオブジェクトが呼び出し可能なので、総称関数の作成に特別な処理は必要ありません。jl_new_generic_functionFunction の部分型であるシングルトン型 (サイズ 0 の型) を作って返すだけです。関数にはデバッグ情報やオブジェクトの出力で使う “表示用の” 名前を付けることができます。例えば Base.sin の名前は sin です。慣習により、総称関数を作成するときに作られるの名前は関数の名前の最初に # を付けたものとなります。例えば typeof(sin) の名前は Base.#sin です。

クロージャ

クロージャは単なる呼び出し可能なオブジェクトであり、フィールドにキャプチャされた変数を持ちます。例えば

function adder(x)
    return y->x+y
end

というコードは、(大まかに言って) 次の低水準形式に変換されます:

struct ##1{T}
    x::T
end

(_::##1)(y) = _.x + y

function adder(x)
    return ##1(x)
end

コンストラクタ

コンストラクタの呼び出しは型を呼び出しているだけです。Type のメソッドテーブルには全てのコンストラクタの定義が含まれます。現在 Type の部分型 (Type, UnionAll, Union, DataType) は特別な処理を通してメソッドテーブルを共有します。

組み込み関数

Core モジュールに定義される「組み込みの」関数は次の通りです:

=== typeof sizeof <: isa typeassert throw tuple getfield setfield! fieldtype
nfields isdefined arrayref arrayset arraysize applicable invoke apply_type _apply
_expr svec

これらは全てシングルトンオブジェクトであり、型は Function の部分型 Builtin の部分型です。こうなっている理由は、“jlcall” の呼び出し規約を使うエントリーポイントをランタイムに公開するためです:

jl_value_t *(jl_value_t*, jl_value_t**, uint32_t)

組み込み関数のメソッドテーブルは空です。その代わり全てを捕まえるメソッドキャッシュエントリ (Tuple{Vararg{Any}}) が一つだけ存在し、このエントリの jlcall fptr が正しい関数を指します。これはハックの一種と言えますが、十分上手く行きます。

キーワード引数

キーワード引数は、キーワード引数を持つメソッドが定義される関数のメソッドテーブルに外からは見えない特別な関数オブジェクトをそれぞれ関連付けることで動作します。この特別な関数は “キーワード引数ソーター” (keyword argument sorter)・“キーワードソーター” (keyword sorter)・“kwsorter” などと呼ばれ、MethodTable オブジェクトの kwsorter フィールドに格納されます。キーワードソーター関数の各メソッドの引数は、通常のメソッドテーブルにある対応する定義が持つ引数の最初に NamedTuple 型の引数を加えたものです。この新しい引数が渡されたキーワード引数の名前と値を表します。キーワードソーター関数の仕事はキーワード引数を名前に従って正準な位置に移動させ、必要なデフォルト値の式を評価して置換することです。結果は通常の位置引数リストであり、これがコンパイラによって生成されるさらに別の関数に渡されます。

この処理を理解するには、例を使ってキーワード引数を持つメソッドの定義がどのような低水準形式になるのかを見るのが一番でしょう。次のコード

function circle(center, radius; color = black, fill::Bool = true, options...)
    # 描画する
end

は、三つのメソッド定義を生成します。一つ目のメソッドはキーワード引数を含んだ全ての引数を位置引数として受け取り、メソッド本体のコードを持ちます。この関数には自動生成された名前が付きます:

function #circle#1(color, fill::Bool, options, circle, center, radius)
    # 描画する
end

二つ目のメソッドは元の circle 関数と同じ通常の定義を持ち、キーワード引数が一つも与えられなかった場合を処理します:

function circle(center, radius)
    #circle#1(black, true, pairs(NamedTuple()), circle, center, radius)
end

このメソッドはデフォルト値を使って一つ目のメソッドにディスパッチしているだけです。

最後がキーワードソーター関数です:

function (::Core.kwftype(typeof(circle)))(kws, circle, center, radius)
    if haskey(kws, :color)
        color = kws.color
    else
        color = black
    end
    # 同様の処理

    # 残りの kwargs を options に入れる
    options = structdiff(kws, NamedTuple{(:color, :fill)})

    # メソッドが可変長キーワード引数を受け取らないなら、
    # options が空でないときここでエラーを出す。

    #circle#1(color, fill, pairs(options), circle, center, radius)
end

関数 Core.kwftype(t) はフィールド t.name.mt.kwsorter を (まだ作られていないなら) 作成し、その関数の型を返します。

この設計にはキーワード引数を使わない呼び出しで特別な処理が必要ないという特徴があります。そういった関数はキーワード引数が言語に全く存在しないかのように動作します。一方キーワード引数が使われる呼び出しは、呼び出される関数のキーワードソーター関数に直接ディスパッチします。例えば関数の呼び出し

circle((0,0), 1.0, color = red; other...)

は、低水準形式において次のように変換されます:

kwfunc(circle)(merge((color = red,), other), circle, (0,0), 1.0)

Core に含まれる kwfunc が呼び出されている関数 circle のキーワードソーター関数を取得しています。キーワードの splat (上の例における other...) は名前付きタプルの merge 関数を呼び出し、この関数が other の各要素をシンボルと値からなる二要素のコレクションとみなして名前付きタプルを構築します。splat の引数が全て名前付きタプルであれば当然高速な実装が利用できます。クロージャを処理するために元の circle 関数も渡されていることにも注目してください。

コンパイラの効率

Julia は「デフォルトでは全ての引数について関数を特殊化する」という設計を持つので、全ての関数に対して新しい型を生成するとコンパイラリソース的に大きな問題となります。実際、この設計を最初に実装したときはビルドとテストに長い時間がかかり、メモリ使用量は多く、システムイメージはベースラインよりも二倍近く大きくなっていました。この設計の持つ問題はナイーブな実装においてシステムをほぼ使えない状態にするのに十分だったのです。この設計を実用的にするには大幅な最適化がいくつか必要になりました。

最初の問題は、引数に関数が渡される関数で異なる引数の値に対してそれぞれ特殊化を行っていたことです。多くの関数は引数を他の場所、例えば他の関数や格納場所に “受け渡す” だけであり、そういった関数を渡される可能性のある全てのクロージャに対して特殊化する必要はありません。幸いにもこの場合には、関数が引数を呼び出しているかどうか (言い換えると、その引数が “ヘッド” の位置に表れるかどうか) で簡単に特殊化の必要性を判定できます。map のようなパフォーマンスクリティカルな高階関数は明らかに引数の関数を呼び出すので、この判定基準を使ったとしても期待通り特殊化されます。この最適化は呼び出された引数をフロントエンドの analyze-variables パスで記録するという方法で実装されます。cache_methodAny もしくは Function と宣言されたスロットに Function 型の型階層に含まれる引数が渡されたことを検出すると、@nospecialize 注釈が付与されたものとして扱います。このヒューリスティックは実際のプログラムにおいて非常に効果的と見られます。

次の問題はメソッドキャッシュで使われるハッシュテーブルの構造に関するものです。実証研究によると、動的ディスパッチの呼び出しは圧倒的多数が一つか二つの引数を使っており、そういった呼び出しの多くは最初の引数だけを考えることで解決できることが判明しています。(余談: 単一ディスパッチの支持者はこの事実を見ても全く驚かないでしょう。ただしここから得られる指針は「実際のプログラムに対して多重ディスパッチを最適化するのは簡単なので、私たちは多重ディスパッチを使うべきだ」であり、「単一ディスパッチでいいじゃないか!」ではありません。) そのためメソッドキャッシュは第一引数の型をプライマリキーとして使っています。ただしここで、第一引数の型は関数呼び出しで使われる型タプルの第二要素に対応することに注意してください (第一要素は関数自身の型です)。ヘッドの位置にある型が変わることは通常まずありません ──実際ほとんどの関数はパラメータを持たないシングルトン型に属します。しかしコンストラクタでは単一のメソッドテーブルが全ての型のコンストラクタを保持するので、この仮定は成り立ちません。そのため Type 型のメソッドテーブルは特別扱いされ、型タプルの (第二要素ではなく) 第一要素がプライマリキーとして使われるようになっています。

フロントエンドは全てのクロージャに対する型宣言を生成します。最初これは通常の型宣言を生成することで実装されていたのですが、これによって途方もない数の自明なコンストラクタ (全ての引数を new に渡すもの) が生成されていました。メソッドの間には半順序が定義されるので、こういったメソッドを全て挿入する処理は \(O(n^2)\) であり、\(n\) は非常に多くなります。この問題は struct_type 式を直接生成し、クロージャインスタンスを作るときに new を直接使うことで最適化されました。美しい解決法とは言えませんが、こうするほかありません。

次の問題は @test マクロで、このマクロは各テストケースに対してゼロ引数のクロージャを生成していました。実はテストケースはその場で一度実行されるだけなので、クロージャは必要ありません。そのため @test はテストの結果 (true, false または例外) を記録する try-catch ブロックに展開されるように変更され、テストスイートハンドラの内側で呼び出すよう定められました。