Документация Engee

Функции в Julia

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

Таблицы методов

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

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

Вызовы функций

При вызове 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);

Добавление методов

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

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

будет работать, так как все возможные соответствующие ему методы будут входить в одну и ту же таблицу методов.

Создание универсальных функций

Так как вызвать можно любой объект, для создания универсальной функций не требуется ничего особенного. Поэтому jl_new_generic_function просто создает одинарный подтип Function (нулевого размера) и возвращает его экземпляр. У функции может быть мнемоническое отображаемое имя, которое применяется в отладочных данных и при выводе информации об объектах. Например, таким именем для 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 определены следующие встроенные функции.

<: === _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 arrayref arrayset arraysize compilerbarrier const_arrayref donotdelete
fieldtype finalizer get_binding_type getfield getglobal ifelse invoke isa
isdefined modifyfield! nfields replacefield! set_binding_type! setfield!
setglobal! sizeof svec swapfield! throw tuple typeassert typeof

Все это одинарные объекты, типы которых являются подтипами типа Builtin, который, в свою очередь, является подтипом Function. Их назначение — предоставлять во время выполнения точки входа, соответствующие соглашению о вызовах jlcall.

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

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

Именованные аргументы

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

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

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

В этом случае просто производится диспетчеризация в первый метод с передачей значений по умолчанию. Функция pairs применяется к именованному кортежу с остальными аргументами для итерации по парам «ключ — значение». Обратите внимание: если метод не принимает остальные именованные аргументы, данный аргумент отсутствует.

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

function (::Core.kwftype(typeof(circle)))(kws, circle, center, radius)
    if haskey(kws, :color)
        color = kws.color
    else
        color = black
    end
    # и т. д.

    # Остальные именованные аргументы помещаются в `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 (если его еще нет) и возвращает тип функции.

Такой подход имеет одну особенность: если в месте вызова не используются именованные аргументы, специальная процедура не требуется; все работает так, как если бы их вообще не было в языке. Однако, если в месте вызова используются именованные аргументы, происходит диспетчеризация в сортировщик 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 передается далее для обработки замыканий.

Проблемы, связанные с эффективностью компиляции

Создание нового типа для каждой функции может иметь серьезные последствия в плане потребления ресурсов компилятором в сочетании с принятым в Julia подходом «специализация по умолчанию по всем аргументам». И действительно, первоначальная реализация этого подхода страдала такими недостатками, как гораздо большая длительность сборки и тестирования, увеличенное потребление памяти и почти в два раза больший размер образа системы по сравнению с базовым. При примитивной реализации проблема усугубляется настолько, что системой становится практически невозможно пользоваться. Чтобы сделать такой подход практически применимым, требовался ряд существенных оптимизаций.

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

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

Интерфейсная часть генерирует объявления типов для всех замыканий. Изначально это было реализовано путем создания обычных объявлений типов. Однако в результате создавалось слишком много конструкторов, каждый из которых был крайне примитивен (все аргументы просто передавались в new). Так как методы упорядочены лишь частично, их добавление имеет алгоритмическую сложность O(n^2) и, кроме того, для их хранения требуются лишние ресурсы. Оптимизация была достигнута путем создания выражений struct_type напрямую (в обход создания конструкторов по умолчанию) и прямого использования new для создания экземпляров замыканий. Может быть, не самое элегантное решение, но что-то нужно было делать.

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