Дополнительные сведения о типах

Возможно, проще всего представить себе систему типов Julia с точки зрения наборов. В то время как программы работают с отдельными значениями, тип относится к набору значений. Это не то же самое, что коллекция. Например, набор (Set) значений сам по себе является одним значением Set. Скорее, тип описывает набор возможных значений, выражая неопределенность относительно того, какое значение есть у нас.

Конкретный тип T описывает набор значений, чья прямая метка, возвращаемая функцией typeof, выглядит как T. Абстрактный тип описывает некоторый возможно больший набор значений.

Any описывает всю совокупность возможных значений. Integer — это подмножество Any, которое содержит Int, Int8 и другие конкретные типы. Внутри Julia также активно использует другой тип, известный как Bottom, который также может быть записан как Union{}. Он соответствует пустому набору.

Типы Julia поддерживают стандартные операции теории множеств: вы можете спросить, является ли T1 «подмножеством» (подтипом) T2 с T1 <: T2. Точно так же вы пересекаете два типа с помощью функции typeintersect, берете их объединение с помощью типа Union и вычисляете тип, который содержит их объединение, с помощью функции typejoin:

Хотя эти операции могут показаться абстрактными, они лежат в основе Julia. Например, диспетчеризация метода осуществляется путем пошагового прохода по элементам в списке методов до тех пор, пока не будет достигнут тот, для которого тип кортежа аргументов является подтипом сигнатуры метода. Для работы этого алгоритма важно, чтобы методы были отсортированы по их специфичности и поиск начинался с наиболее специфичных методов. Следовательно, Julia также реализует частичный порядок типов. Для этого используется функциональность, похожая на <:, но с различиями, которые будут рассматриваться ниже.

Система типов Julia также может выражать итерируемое объединение типов: объединение типов по всем значениям некоторой переменной. Это необходимо для описания параметрических типов, у которых значения некоторых параметров неизвестны.

Например, тип Array имеет два параметра, как показано в Array{Int,2}. Если бы мы не знали тип элемента, мы могли бы написать Array{T,2} where T, который является объединением Array{T,2} для всех значений T: Union{Array{Int8,2}, Array{Int16,2}, ...}.

Такой тип представлен объектом UnionAll, который содержит переменную (в данном примере — T, имеющую тип TypeVar) и заключенный в оболочку тип (в данном примере — Array{T,2}).

Рассмотрим следующие методы.

Сигнатура (как описано в разделе Вызовы функций) f3 является типом UnionAll, инкапсулирующим тип кортежа: Tuple{typeof(f3), Array{T}} where T. Все, кроме f4, можно вызвать с помощью a = [1,2]. Все, кроме f2, можно вызвать с помощью b = Any[1,2].

Рассмотрим эти типы подробнее.

Это указывает на то, что Array на самом деле именует тип UnionAll. Для каждого параметра существует один вложенный тип UnionAll. Синтаксис Array{Int,2} эквивалентен Array{Int}{2}. Внутренне экземпляр каждого типа UnionAll создается с определенным значением переменной, по одному за раз, начиная с самого внешнего. В этом случае опускание конечных параметров типа приобретает естественное значение. Array{Int} выдает тип, эквивалентный Array{Int,N} where N.

TypeVar сам по себе не является типом, а скорее должен рассматриваться как часть структуры типа UnionAll. Переменные типа имеют нижнюю и верхнюю границы для своих значений (в полях lb и ub). Символьное имя name является чисто декоративным. Внутренне типы TypeVar сравниваются по адресу, поэтому они определены как изменяемые, чтобы можно было различать переменные «разных» типов. Однако по соглашению они не должны быть изменяемыми.

Типы TypeVar можно построить вручную:

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

Синтаксис Array{T} where T<:Integer понижается до следующего:

поэтому TypeVar редко требуется создавать вручную (более того, этого следует избегать).

Понятие переменной свободного типа является чрезвычайно важным в системе типов. Мы говорим, что переменная V имеет свободный тип T, если T не содержит тип UnionAll, который представляет переменную V. Например, тип Array{Array{V} where V<:Integer} не имеет свободных переменных, но часть Array{V} внутри него имеет свободную переменную V.

Тип со свободными переменными в некотором смысле вообще не является типом. Рассмотрим тип Array{Array{T}} where T, который относится ко всем однородным массивам массивов. Может показаться, что внутренний тип Array{T}, рассматриваемый сам по себе, относится к любому виду массива. Однако каждый элемент внешнего массива должен иметь тот же тип массива, поэтому Array{T} не может относиться к любому старому массиву. Можно сказать, что Array{T} фактически «возникает» несколько раз, и T должен иметь одно и то же значение каждый «раз».

По этой причине функция jl_has_free_typevars в API для C очень важна. Типы, для которых она возвращает значение true, не дадут вразумительных ответов в подтипизации и других функциях типа.

Следующие два типа Array функционально эквивалентны, но выводятся по-разному:

Их можно отличить, изучив поле name типа, которое является объектом типа TypeName:

В данном случае соответствующим полем является wrapper, которое содержит ссылку на тип верхнего уровня, используемый для создания новых типов Array.

Поле wrapper в Array указывает на себя, но для Array{TV,NV} оно указывает на исходное определение типа.

А как насчет других полей? hash присваивает целочисленное значение каждому типу. Для изучения поля cache рекомендуется выбрать тип, который используется менее активно, чем Array. Сначала создадим собственный тип:

При создании экземпляра параметрического типа каждый конкретный тип сохраняется в кэше типов (MyType.body.body.name.cache). Однако экземпляры, содержащие переменные свободного типа, не кэшируются.

Типы кортежей представляют собой интересный частный случай. Чтобы диспетчеризация работала с объявлениями, подобными x::Tuple, тип должен быть способен вмещать любой кортеж. Проверим параметры:

В отличие от других типов, типы кортежей ковариантны по своим параметрам, поэтому это определение позволяет Tuple соответствовать любому типу кортежа:

Однако, если тип кортежа с переменным количеством аргументов (Vararg) имеет свободные переменные, он может описывать различные типы кортежей:

Обратите внимание, что когда тип T свободен по отношению к типу Tuple (т. е. его тип UnionAll привязки находится вне типа Tuple), со всем типом должно работать только одно значение T. Поэтому разнородные кортежи не совпадают.

Наконец, стоит заметить, что Tuple{} является другим:

Что такое «основной» тип кортежа?

поэтому Tuple == Tuple{Vararg{Any}} действительно является основным типом.

Рассмотрим тип Tuple{T,T} where T. Метод с такой сигнатурой будет выглядеть следующим образом:

Согласно обычной интерпретации типа UnionAll, этот тип T распространяется на все типы, включая Any, поэтому он должен быть эквивалентен Tuple{Any,Any}. Однако такая интерпретация приводит к возникновению ряда практических проблем.

Во-первых, значение T должно быть доступно внутри определения метода. Для такого вызова, как f(1, 1.0), неясно, каким должен быть тип T. Это может быть Union{Int,Float64}, или, возможно, Real. Интуитивно мы ожидаем, что объявление x::T будет означать T === typeof(x). Чтобы убедиться в том, что инвариант сохраняется, нам требуется typeof(x) === typeof(y) === T в этом методе. Это означает, что метод должен вызываться только для аргументов точно такого же типа.

Оказывается, возможность отправлять данные о том, имеют ли два значения одинаковый тип, очень полезна (она используется, например, в системе продвижения), поэтому у нас есть несколько причин, чтобы получить другую интерпретацию Tuple{T,T} where T. Для этого мы добавляем следующее правило к подтипизации: если переменная встречается более одного раза в ковариантной позиции, она ограничивается диапазоном только конкретных типов. («Ковариантная позиция» означает, что между вхождением переменной и вводимым ею типом UnionAll встречаются только типы Tuple и Union.) Такие переменные называются «диагональными переменными» или «конкретными переменными».

Так, например, Tuple{T,T} where T можно рассматривать как Union{Tuple{Int8,Int8}, Tuple{Int16,Int16}, ...}, где тип T охватывает все конкретные типы. Это приводит к некоторым интересным результатам подтипизации. Например, Tuple{Real,Real} не является подтипом типа Tuple{T,T} where T, поскольку он включает некоторые типы, такие как Tuple{Int8,Int16}, где два этих элемента имеют разные типы. Tuple{Real,Real} и Tuple{T,T} where T имеют нетривиальное пересечение Tuple{T,T} where T<:Real. Однако Tuple{Real} является подтипом типа Tuple{T} where T, потому что в этом случае тип T встречается только один раз и поэтому не является диагональным.

Далее рассмотрим сигнатуру следующего вида:

В этом случае тип T появляется в инвариантной позиции внутри Array{T}. Это означает, что какой бы тип массива ни был передан, он однозначно определяет значение типа T — мы говорим, что тип T имеет ограничение равенства. Поэтому в данном случае правило диагонали не является необходимым, так как массив определяет тип T, и можно разрешить x и y быть любыми подтипами типа T. Поэтому переменные, которые встречаются в инвариантной позиции, никогда не считаются диагональными. Этот выбор поведения является несколько спорным — некоторые считают, что это определение должно быть записано как

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

Следующей сложностью является взаимодействие объединений и диагональных переменных, например:

Рассмотрим, что означает это объявление. y имеет тип T. Тогда x может иметь либо тот же тип T, либо тип Nothing. Таким образом, все следующие вызовы должны совпадать:

Эти примеры говорят о следующем: когда x имеет значение nothing::Nothing, для y нет никаких дополнительных ограничений. Это как если бы в сигнатуре метода было y::Any. На самом деле мы имеем следующую эквивалентность типов:

Общее правило таково: конкретная переменная в ковариантной позиции ведет себя как неконкретная, если алгоритм подтипизации использует ее только один раз. Когда x имеет тип Nothing, не нужно использовать тип T в Union{Nothing,T}, он используется только во втором слоте. Это обусловлено тем, что в Tuple{T} where T ограничение типа T конкретными типами не имеет никакого значения. Тип равен Tuple{Any} в любом случае.

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

Если тип T внутри Union игнорируется, то тип T будет конкретным, и ответ будет false, так как первые два типа не одинаковы. Теперь рассмотрим следующее.

Сейчас мы не можем игнорировать тип T в Union (у нас должно быть T == Any), поэтому тип T не является конкретным и ответ — true. В этом случае конкретность T будет находиться в зависимости от другого типа, что недопустимо, поскольку тип должен иметь четкое значение сам по себе. Поэтому появление T внутри Vector рассматривается в обоих случаях.

Алгоритм подтипизации для диагональных переменных состоит из двух компонентов: (1) определение вхождений переменных и (2) обеспечение того, чтобы диагональные переменные охватывали только конкретные типы.

Первая задача решается путем ведения счетчиков occurs_inv и occurs_cov (в файле src/subtype.c) для каждой переменной в среде с отслеживанием количества инвариантных и ковариантных вхождений, соответственно. Переменная является диагональной, когда occurs_inv == 0 && occurs_cov > 1.

Вторая задача решается путем наложения условия на нижнюю границу переменной. По мере работы алгоритма подтипизации происходит сужение границ каждой переменной (с повышением нижних и понижением верхних границ) в целях отслеживания диапазона значений переменной, для которых будет выполняться соотношение подтипа. Завершив вычисление тела типа UnionAll, переменная которого является диагональной, посмотрим на конечные значения границ. Поскольку переменная должна быть конкретной, возникает противоречие, если ее нижняя граница не может быть подтипом конкретного типа. Например, абстрактный тип, подобный AbstractArray, не может быть подтипом конкретного типа, но конкретный тип, подобный Int, может, и пустой тип Bottom тоже может. Если нижняя граница не проходит этот тест, алгоритм останавливается с ответом false.

Например, в задаче Tuple{Int,String} <: Tuple{T,T} where T мы получаем, что соотношение было бы верным, если бы T был супертипом Union{Int,String}. Однако Union{Int,String} является абстрактным типом, поэтому соотношение не выполняется.

Этот тест на конкретность проводится с помощью функции is_leaf_bound. Обратите внимание, что этот тест немного отличается от функции jl_is_leaf_type, поскольку он также возвращает true для нижней границы (Bottom). В настоящее время эта функция является эвристической и не перехватывает все возможные конкретные типы. Сложность в том, что конкретность нижней границы может зависеть от значений границ других переменных типа. Например, Vector{T} эквивалентен конкретному типу Vector{Int}, только если верхняя и нижняя границы T равны Int. Мы еще не разработали полный алгоритм действий в этой ситуации.

Большинство операций для работы с типами находятся в файлах jltypes.c и subtype.c. Лучше всего начать с изучения типизации в действии. Выполните сборку Julia с помощью make debug и запустите Julia в отладчике. В главе Советы по отладке gdb вы найдете полезные советы.

Поскольку код подтипизации активно используется в самом REPL, и, следовательно, точки останова в этом коде срабатывают часто, будет проще, если вы создадите следующее определение:

и затем установите точку останова в функции jl_breakpoint. После того как эта точка сработает, вы можете установить точки останова в других функциях.

В качестве разминки попробуйте сделать следующее.

Повысим уровень и рассмотрим более сложный случай:

Функции type_morespecific используются для задания частичного порядка для функций в таблицах методов (от наиболее специфичных до наименее). Специфичность является строгой; если a более специфично, чем b, то a не равно b и b не более специфично, чем a.

Если a является строгим подтипом b, то оно автоматически считается более специфичным. Исходя из этого, type_morespecific использует некоторые менее формальные правила. Например, subtype зависит от количества аргументов, а type_morespecific может не зависеть. В частности, Tuple{Int,AbstractFloat} является более специфичным, чем Tuple{Integer}, даже если он не является подтипом. (Ни Tuple{Int,AbstractFloat}, ни Tuple{Integer,Float64} не является более специфичным, чем другой.) В частности, Tuple{Int,Vararg{Int}} не является подтипом Tuple{Integer}, но считается более специфичным. Однако morespecific получает бонус за длину: в частности, Tuple{Int,Int} более специфичен, чем Tuple{Int,Vararg{Int}}.

Если вы отлаживаете способы сортировки методов, может быть целесообразно определить функцию:

которая позволяет проверять, является ли тип кортежа a более конкретным, чем тип кортежа b.