Julia Functions

Этот документ объяснит, как работают функции, определения методов и таблицы методов.

Method Tables

Каждая функция в Julia является обобщенной функцией. Обобщенная функция концептуально представляет собой одну функцию, но состоит из множества определений или методов. Методы обобщенной функции хранятся в таблице методов. Таблицы методов (тип MethodTable) ассоциированы с TypeName. TypeName описывает семью параметризованных типов. Например, Complex{Float32} и Complex{Float64} разделяют один и тот же объект имени типа Complex.

Все объекты в Julia потенциально могут быть вызываемыми, потому что каждый объект имеет тип, который, в свою очередь, имеет TypeName.

Function calls

Дано вызов f(x, y), выполняются следующие шаги: сначала доступ к таблице методов осуществляется как typeof(f).name.mt. Во-вторых, формируется тип кортежа аргументов, Tuple{typeof(f), typeof(x), typeof(y)}. Обратите внимание, что тип самой функции является первым элементом. Это связано с тем, что тип может иметь параметры и, следовательно, должен участвовать в диспетчеризации. Этот тип кортежа ищется в таблице методов.

Этот процесс отправки выполняется функцией jl_apply_generic, которая принимает два аргумента: указатель на массив значений f, x и y, а также количество значений (в данном случае 3).

В системе есть два типа API, которые обрабатывают функции и списки аргументов: те, которые принимают функцию и аргументы отдельно, и те, которые принимают одну структуру аргументов. В первом типе 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);

Adding methods

Учитывая вышеописанный процесс диспетчеризации, концептуально все, что нужно для добавления нового метода, это (1) тип кортежа и (2) код для тела метода. jl_method_def реализует эту операцию. jl_method_table_for вызывается для извлечения соответствующей таблицы методов из того, что будет типом первого аргумента. Это гораздо сложнее, чем соответствующая процедура во время диспетчеризации, поскольку тип аргумента может быть абстрактным. Например, мы можем определить:

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

что работает, поскольку все возможные методы сопоставления будут принадлежать одной и той же таблице методов.

Creating generic functions

Поскольку каждый объект является вызываемым, ничего особенного не нужно для создания обобщенной функции. Поэтому jl_new_generic_function просто создает новый синглтон (размер 0) подтип Function и возвращает его экземпляр. Функция может иметь мнемоническое "имя для отображения", которое используется в отладочной информации и при печати объектов. Например, имя 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 содержит все определения конструкторов. Все подтипы Type (Type, UnionAll, Union и DataType) в настоящее время разделяют таблицу методов через специальное соглашение.

Builtins

Функции "builtin", определенные в модуле Core, это:

<: === _abstracttype _apply_iterate _apply_pure _call_in_world
_call_in_world_total _call_latest _compute_sparams _equiv_typedef _expr
_primitivetype _setsuper! _structtype _svec_ref _typebody! _typevar applicable
apply_type compilerbarrier current_scope donotdelete fieldtype finalizer
get_binding_type getfield getglobal ifelse invoke isa isdefined
memoryref_isassigned memoryrefget memoryrefmodify! memoryrefnew memoryrefoffset
memoryrefreplace! memoryrefset! memoryrefsetonce! memoryrefswap! modifyfield!
modifyglobal! nfields replacefield! replaceglobal! set_binding_type! setfield!
setfieldonce! setglobal! setglobalonce! sizeof svec swapfield! swapglobal! throw
tuple typeassert typeof

Это все одиночные объекты, типы которых являются подтипами Builtin, который является подтипом Function. Их цель - предоставить точки входа в среду выполнения, которые используют соглашение о вызовах "jlcall":

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

Методы таблиц встроенных функций пусты. Вместо этого у них есть единственная запись кэша для метода, охватывающая все (Tuple{Vararg{Any}}), чей указатель fptr jlcall указывает на правильную функцию. Это своего рода хак, но работает довольно хорошо.

Keyword arguments

Ключевые аргументы работают, добавляя методы к функции kwcall. Эта функция обычно является "сортировщиком ключевых аргументов" или "сортировщиком по ключевым словам", который затем вызывает внутреннее тело функции (определенное анонимно). Каждое определение в функции kwsorter имеет те же аргументы, что и некоторые определения в обычной таблице методов, за исключением того, что перед ним добавлен один аргумент NamedTuple, который дает имена и значения переданных ключевых аргументов. Задача kwsorter заключается в том, чтобы переместить ключевые аргументы в их канонические позиции на основе имени, а также оценить и подставить любые необходимые выражения значений по умолчанию. Результатом является обычный список позиционных аргументов, который затем передается еще одной сгенерированной компилятором функции.

Самый простой способ понять процесс — это посмотреть, как определяется метод с аргументами по ключевым словам. Код:

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

на самом деле создает три определения метода. Первое - это функция, которая принимает все аргументы (включая именованные аргументы) в качестве позиционных аргументов и включает код для тела метода. У нее автоматически сгенерированное имя:

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

Второй метод — это обычное определение для оригинальной функции circle, которая обрабатывает случай, когда не передаются аргументы ключевого слова:

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

Это просто вызывает первый метод, передавая значения по умолчанию. pairs применяется к именованному кортежу оставшихся аргументов для обеспечения итерации пар ключ-значение. Обратите внимание, что если метод не принимает оставленные именованные аргументы, то этот аргумент отсутствует.

Наконец, есть определение kwsorter:

function (::Core.kwftype(typeof(circle)))(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

Функция Core.kwftype(t) создает поле t.name.mt.kwsorter (если оно еще не было создано) и возвращает тип этой функции.

Этот дизайн имеет такую особенность, что места вызова, которые не используют именованные аргументы, не требуют специальной обработки; все работает так, как будто они вообще не являются частью языка. Места вызова, которые используют именованные аргументы, напрямую передаются в kwsorter вызываемой функции. Например, вызов:

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

снижено до:

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

kwcall (также в Core) обозначает сигнатуру и диспетчеризацию kwcall. Операция распаковки ключевых слов (записанная как other...) вызывает функцию merge именованного кортежа. Эта функция дополнительно распаковывает каждый элемент other, ожидая, что каждый из них будет содержать два значения (символ и значение). Естественно, более эффективная реализация доступна, если все распакованные аргументы являются именованными кортежами. Обратите внимание, что оригинальная функция circle передается дальше, чтобы обрабатывать замыкания.

Compiler efficiency issues

Генерация нового типа для каждой функции имеет потенциально серьезные последствия для использования ресурсов компилятора, когда это сочетается с дизайном Julia "специализироваться по всем аргументам по умолчанию". Действительно, первоначальная реализация этого дизайна страдала от значительно более длительного времени сборки и тестирования, более высокого использования памяти и системного образа, почти в 2 раза большего, чем базовый. В наивной реализации проблема настолько серьезна, что делает систему почти непригодной для использования. Для того чтобы сделать дизайн практичным, потребовалось несколько значительных оптимизаций.

Первая проблема заключается в чрезмерной специализации функций для различных значений аргументов, представляющих функции. Многие функции просто "передают" аргумент куда-то еще, например, в другую функцию или в место хранения. Таким функциям не нужно специализироваться для каждого замыкания, которое может быть передано. К счастью, этот случай легко отличить, просто рассматривая, вызывает ли функция один из своих аргументов (т.е. аргумент появляется в "головной позиции" где-то). Функции высшего порядка, критичные к производительности, такие как map, определенно вызывают свою аргумент-функцию и, следовательно, будут специализированы, как и ожидалось. Эта оптимизация реализована путем записи, какие аргументы вызываются во время прохода analyze-variables на фронтэнде. Когда cache_method видит аргумент в иерархии типов Function, переданный в слот, объявленный как Any или Function, он ведет себя так, как будто аннотация @nospecialize была применена. Эта эвристика, похоже, оказывается чрезвычайно эффективной на практике.

Следующий вопрос касается структуры хеш-таблиц кэша методов. Эмпирические исследования показывают, что подавляющее большинство динамически вызываемых вызовов включает один или два аргумента. В свою очередь, многие из этих случаев можно разрешить, рассматривая только первый аргумент. (К слову: сторонники единственного диспетчеризации не будут удивлены этим вовсе. Однако этот аргумент означает "многократная диспетчеризация легко оптимизируется на практике", и поэтому мы должны использовать ее, а не "мы должны использовать единственную диспетчеризацию"!) Таким образом, кэш методов использует тип первого аргумента в качестве своего основного ключа. Обратите внимание, однако, что это соответствует второму элементу кортежа типа для вызова функции (первый элемент - это тип самой функции). Обычно вариация типов в главной позиции крайне низка – действительно, большинство функций принадлежат синглетонным типам без параметров. Однако это не так для конструкторов, где одна таблица методов содержит конструкторы для каждого типа. Поэтому таблица методов Type специально обрабатывается, чтобы использовать первый элемент кортежа типа вместо второго.

Фронтенд генерирует объявления типов для всех замыканий. Изначально это было реализовано путем генерации обычных объявлений типов. Однако это привело к созданию чрезвычайно большого количества конструкторов, все из которых были тривиальными (просто передавали все аргументы в new). Поскольку методы частично упорядочены, вставка всех этих методов имеет сложность O(n²), плюс их просто слишком много, чтобы их можно было держать. Это было оптимизировано путем генерации выражений struct_type напрямую (обходя генерацию конструктора по умолчанию) и использования new напрямую для создания экземпляров замыканий. Не самое красивое решение, но приходится делать то, что нужно.

Следующая проблема заключалась в макросе @test, который генерировал замыкание с 0 аргументами для каждого теста. Это не совсем необходимо, так как каждый тест просто выполняется один раз на месте. Поэтому @test был изменен, чтобы развернуться в блок try-catch, который записывает результат теста (истина, ложь или возникшее исключение) и вызывает обработчик тестового набора для этого.