Julia Functions

このドキュメントでは、関数、メソッド定義、メソッドテーブルの仕組みを説明します。

Method Tables

Juliaの関数はすべてジェネリック関数です。ジェネリック関数は、概念的には1つの関数ですが、多数の定義、すなわちメソッドから構成されます。ジェネリック関数のメソッドは、メソッドテーブルに格納されます。グローバルなメソッドテーブルは1つで、型はMethodTable、名前はCore.methodtableです。メソッドに対する通常の操作(呼び出しなど)はすべて、このテーブルを使用します。

Function calls

f(x, y)という呼び出しでは、次の手順が実行されます。まず、タプル型Tuple{typeof(f), typeof(x), typeof(y)}が作られます。最初の要素が関数自体の型であることに注意してください。これは、関数自体もほかの引数と対等にメソッド検索に関与するためです。このタプル型を使って、グローバルなメソッドテーブルを検索します。ただし、システムは結果をキャッシュできるため、その後の同様の検索ではこれらの手順を省略できます。

このディスパッチ処理はjl_apply_genericによって実行されます。この関数は、値f、x、yを格納した配列へのポインターと、値の個数(この場合は3)の2つの引数を取ります。

システム全体を通して、関数と引数リストを扱うAPIには2種類あります。関数と引数を別々に受け取るものと、単一の引数構造体を受け取るものです。前者のAPIでは、関数が別に渡されるため、「引数」の部分に関数の情報は含まれません。後者のAPIでは、関数が引数構造体の最初の要素になります。

たとえば、呼び出しを実行する次の関数はargsポインターのみを受け取るため、args配列の最初の要素が呼び出す関数になります。

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

同じ機能を提供する次のエントリーポイントは、関数を別に受け取るため、args配列に関数は含まれません。

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

Adding methods

上記のディスパッチ処理を踏まえると、新しいメソッドを追加するために概念上必要なのは、(1) タプル型と、(2) メソッド本体のコードだけです。jl_method_defがこの操作を実装しています。

Creating generic functions

すべてのオブジェクトは呼び出し可能なので、ジェネリック関数の作成に特別な仕組みは必要ありません。そのため、jl_new_generic_functionは、Functionの新しいシングルトンサブタイプ(サイズ0)を作成し、そのインスタンスを返すだけです。関数には、覚えやすい「表示名」を付けることができ、デバッグ情報やオブジェクトの表示に使われます。たとえば、Base.sinの名前はsinです。慣例として、作成される型の名前は、関数名の先頭に#を付けたものになります。したがって、typeof(sin)はBase.#sinになります。

Closures

クロージャとは、キャプチャした変数に対応するフィールド名を持つ、呼び出し可能なオブジェクトにすぎません。たとえば、次のコードは、

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

Constructors

コンストラクター呼び出しは、型に対する呼び出し、つまりType{T}上に定義されたメソッドへの呼び出しにすぎません。

Builtins

Coreモジュールで定義されている「組み込み」関数は、次のとおりです。

<: === _abstracttype _apply_iterate _call_in_world_total _compute_sparams
_defaultctors _equiv_typedef _expr _import _primitivetype _setsuper! _structtype
_svec_len _svec_ref _typebody! _typevar _using applicable apply_type
compilerbarrier current_scope declare_const declare_global donotdelete fieldtype
finalizer get_binding_type getfield getglobal ifelse invoke invoke_in_world
invokelatest isa isdefined isdefinedglobal memorynew memoryref_isassigned
memoryrefget memoryrefmodify! memoryrefnew memoryrefoffset memoryrefreplace!
memoryrefset! memoryrefsetonce! memoryrefswap! modifyfield! modifyglobal! nfields
replacefield! replaceglobal! setfield! setfieldonce! setglobal! setglobalonce!
sizeof svec swapfield! swapglobal! throw throw_methoderror tuple typeassert
typeof

これらの大半はシングルトンオブジェクトであり、その型はすべてBuiltinのサブタイプです。また、この型はFunctionのサブタイプです。これらの目的は、次の「jlcall」呼び出し規約を使用するランタイムのエントリーポイントを公開することです。

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

Keyword arguments

キーワード引数は、kwcall関数にメソッドを追加することで実現されます。この関数は通常「キーワード引数ソーター」または「キーワードソーター」と呼ばれ、関数の内部本体(無名で定義されるもの)を呼び出します。kwsorter関数の各定義は、通常のメソッドテーブルにあるいずれかの定義と同じ引数を取りますが、その先頭にNamedTuple引数が1つ追加されます。この引数は、渡されたキーワード引数の名前と値を保持します。kwsorterの役割は、キーワード引数を名前に基づいて所定の位置に並べ替え、必要なデフォルト値の式を評価して補うことです。その結果、通常の位置引数リストが得られ、それがコンパイラーによって生成された別の関数へ渡されます。

この処理を理解するには、キーワード引数を持つメソッド定義がどのように低水準の表現へ変換されるかを見るのが最も簡単です。次のコードは、

function circle(center, radius; color = black, fill::Bool = true, options...)
    # draw
end

実際には3つのメソッド定義を生成します。1つ目は、すべての引数(キーワード引数を含む)を位置引数として受け取り、メソッド本体のコードを含む関数です。この関数には、自動生成された名前が付けられます。

function #circle#1(color, fill::Bool, options, circle, center, radius)
    # draw
end

2つ目のメソッドは、元のcircle関数に対する通常の定義で、キーワード引数が渡されない場合を処理します。

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

これは、デフォルト値を渡して1つ目のメソッドへディスパッチするだけです。残りの引数を格納する名前付きタプルにpairsを適用することで、キーと値のペアとして反復できるようにします。なお、メソッドが残りのキーワード引数を受け取らない場合、この引数は存在しません。

最後に、kwsorterの定義があります。

function (::Core.kwcall)(kws, circle, center, radius)
    if haskey(kws, :color)
        color = kws.color
    else
        color = black
    end
    # etc.

    # put remaining kwargs in `options`
    options = structdiff(kws, NamedTuple{(:color, :fill)})

    # if the method doesn't accept rest keywords, throw an error
    # unless `options` is empty

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

Compiler efficiency issues

関数ごとに新しい型を生成することは、Juliaの「デフォルトですべての引数に対して特殊化する」という設計と組み合わさると、コンパイラーのリソース使用量に深刻な影響を及ぼす可能性があります。実際、この設計の初期実装では、ビルド時間とテスト時間が大幅に延び、メモリ使用量が増え、システムイメージは従来のほぼ2倍の大きさになりました。素朴な実装では、システムがほとんど使いものにならないほどの問題になります。この設計を実用的なものにするには、いくつかの重要な最適化が必要でした。

最初の問題は、関数を値とする引数の値ごとに、関数が過剰に特殊化されることです。多くの関数は、引数を別の場所、たとえば別の関数や保存先へ単に「受け渡す」だけです。このような関数は、渡される可能性のあるすべてのクロージャに対して特殊化する必要はありません。幸い、このケースは、関数が自身の引数のいずれかを呼び出すかどうか(つまり、その引数がどこかで「先頭位置」に現れるかどうか)を調べるだけで簡単に見分けられます。mapのように性能が重要な高階関数は、確かに引数の関数を呼び出すため、引き続き期待どおりに特殊化されます。この最適化は、フロントエンドのanalyze-variablesパスで、どの引数が呼び出されるかを記録することで実装されています。cache_methodは、Functionの型階層に属する引数が、AnyまたはFunctionとして宣言されたスロットに渡されるのを検出すると、@nospecializeアノテーションが適用されているかのように動作します。このヒューリスティックは、実際にきわめて効果的なようです。

次の問題は、メソッドテーブルの構造に関するものです。実証的な調査によると、動的ディスパッチによる呼び出しの大半は、引数が1つか2つです。さらに、その多くは最初の引数だけを考慮すれば解決できます。(余談ですが、単一ディスパッチの支持者にとって、これはまったく意外ではないでしょう。しかし、この議論が意味するのは「多重ディスパッチは実際には最適化しやすい」ので採用すべきだということであり、「単一ディスパッチを使うべきだ」ということではありません!)そこで、メソッドテーブルとキャッシュは、左から右へ判定する決定木に基づいて構造を分割し、効率的な最近傍探索を可能にしています。

フロントエンドは、すべてのクロージャに対して型宣言を生成します。当初は、通常の型宣言を生成することで実装していました。しかし、これにより膨大な数のコンストラクターが生成され、そのすべてが単純なもの(すべての引数をそのままnewへ渡すだけ)でした。メソッドには半順序があるため、これらすべてのメソッドの挿入にはO(n²)の時間がかかり、そもそも保持しておくには数が多すぎます。そこで、struct_type式を直接生成してデフォルトコンストラクターの生成を回避し、newを直接使用してクロージャのインスタンスを作成するよう最適化しました。あまり美しい方法ではありませんが、必要なことはやらなければなりません。

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