More about types

Если вы использовали Julia некоторое время, вы понимаете основную роль, которую играют типы. Здесь мы пытаемся заглянуть под капот, сосредоточив внимание в частности на Parametric Types.

Types and sets (and Any and Union{}/Bottom)

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

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

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

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

julia> typeintersect(Int, Float64)
Union{}

julia> Union{Int, Float64}
Union{Float64, Int64}

julia> typejoin(Int, Float64)
Real

julia> typeintersect(Signed, Union{UInt8, Int8})
Int8

julia> Union{Signed, Union{UInt8, Int8}}
Union{UInt8, Signed}

julia> typejoin(Signed, Union{UInt8, Int8})
Integer

julia> typeintersect(Tuple{Integer, Float64}, Tuple{Int, Real})
Tuple{Int64, Float64}

julia> Union{Tuple{Integer, Float64}, Tuple{Int, Real}}
Union{Tuple{Int64, Real}, Tuple{Integer, Float64}}

julia> typejoin(Tuple{Integer, Float64}, Tuple{Int, Real})
Tuple{Integer, Real}

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

UnionAll types

Система типов 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} в этом примере).

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

f1(A::Array) = 1
f2(A::Array{Int}) = 2
f3(A::Array{T}) where {T<:Any} = 3
f4(A::Array{Any}) = 4

Подпись - как описано в Function calls - f3 имеет тип UnionAll, оборачивающий тип кортежа: Tuple{typeof(f3), Array{T}} where T. Все, кроме f4, могут быть вызваны с a = [1,2]; все, кроме f2, могут быть вызваны с b = Any[1,2].

Давайте рассмотрим эти типы немного подробнее:

julia> dump(Array)
UnionAll
  var: TypeVar
    name: Symbol T
    lb: Union{}
    ub: Any
  body: UnionAll
    var: TypeVar
      name: Symbol N
      lb: Union{}
      ub: Any
    body: Array{T, N} <: DenseArray{T, N}
      ref::MemoryRef{T}
      size::NTuple{N, Int64}

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

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

Можно вручную создать TypeVarы:

julia> TypeVar(:V, Signed, Real)
Signed<:V<:Real

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

Синтаксис Array{T} where T<:Integer преобразуется в

let T = TypeVar(:T,Integer)
    UnionAll(T, Array{T})
end

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

Free variables

Концепция свободной переменной типа чрезвычайно важна в системе типов. Мы говорим, что переменная 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 в C API очень важна. Типы, для которых она возвращает true, не дадут значимых ответов в подтипировании и других типовых функциях.

TypeNames

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

julia> TV, NV = TypeVar(:T), TypeVar(:N)
(T, N)

julia> Array
Array

julia> Array{TV, NV}
Array{T, N}

Эти можно различить,examining поле name типа, который является объектом типа TypeName:

julia> dump(Array{Int,1}.name)
TypeName
  name: Symbol Array
  module: Module Core
  names: empty SimpleVector
  wrapper: UnionAll
    var: TypeVar
      name: Symbol T
      lb: Union{}
      ub: Any
    body: UnionAll
      var: TypeVar
        name: Symbol N
        lb: Union{}
        ub: Any
      body: Array{T, N} <: DenseArray{T, N}
  cache: SimpleVector
    ...

  linearcache: SimpleVector
    ...

  hash: Int64 -7900426068641098781
  mt: MethodTable
    name: Symbol Array
    defs: Nothing nothing
    cache: Nothing nothing
    max_args: Int64 0
    module: Module Core
    : Int64 0
    : Int64 0

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

julia> pointer_from_objref(Array)
Ptr{Cvoid} @0x00007fcc7de64850

julia> pointer_from_objref(Array.body.body.name.wrapper)
Ptr{Cvoid} @0x00007fcc7de64850

julia> pointer_from_objref(Array{TV,NV})
Ptr{Cvoid} @0x00007fcc80c4d930

julia> pointer_from_objref(Array{TV,NV}.name.wrapper)
Ptr{Cvoid} @0x00007fcc7de64850

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

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

julia> struct MyType{T,N} end

julia> MyType{Int,2}
MyType{Int64, 2}

julia> MyType{Float32, 5}
MyType{Float32, 5}

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

Tuple types

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

julia> Tuple
Tuple

julia> Tuple.parameters
svec(Vararg{Any})

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

julia> typeintersect(Tuple, Tuple{Int,Float64})
Tuple{Int64, Float64}

julia> typeintersect(Tuple{Vararg{Any}}, Tuple{Int,Float64})
Tuple{Int64, Float64}

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

julia> typeintersect(Tuple{Vararg{T} where T}, Tuple{Int,Float64})
Tuple{Int64, Float64}

julia> typeintersect(Tuple{Vararg{T}} where T, Tuple{Int,Float64})
Union{}

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

Наконец, стоит отметить, что Tuple{} является отличным:

julia> Tuple{}
Tuple{}

julia> Tuple{}.parameters
svec()

julia> typeintersect(Tuple{}, Tuple{Int})
Union{}

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

julia> pointer_from_objref(Tuple)
Ptr{Cvoid} @0x00007f5998a04370

julia> pointer_from_objref(Tuple{})
Ptr{Cvoid} @0x00007f5998a570d0

julia> pointer_from_objref(Tuple.name.wrapper)
Ptr{Cvoid} @0x00007f5998a04370

julia> pointer_from_objref(Tuple{}.name.wrapper)
Ptr{Cvoid} @0x00007f5998a04370

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

Diagonal types

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

f(x::T, y::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. Чтобы это работало, мы добавляем следующее правило к подтипированию: если переменная встречается более одного раза в ковариантной позиции, она ограничивается диапазоном только конкретных типов. ("Ковариантная позиция" означает, что только типы Tuple и Union встречаются между вхождением переменной и типом UnionAll, который ее вводит.) Такие переменные называются "диагональными переменными" или "конкретными переменными".

Итак, например, 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 встречается только один раз и, следовательно, не является диагональным.

Далее рассмотрим подпись, подобную следующей:

f(a::Array{T}, x::T, y::T) where {T} = ...

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

f(a::Array{T}, x::S, y::S) where {T, S<:T} = ...

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

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

f(x::Union{Nothing,T}, y::T) where {T} = ...

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

f(1, 1)
f("", "")
f(2.0, 2.0)
f(nothing, 1)
f(nothing, "")
f(nothing, 2.0)

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

(Tuple{Union{Nothing,T},T} where T) == Union{Tuple{Nothing,Any}, Tuple{T,T} where T}

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

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

Tuple{Int,Int8,Vector{Integer}} <: Tuple{T,T,Vector{Union{Integer,T}}} where T

Если T внутри Union игнорируется, то T является конкретным, и ответ "ложь", так как первые два типа не одинаковы. Но рассмотрим вместо этого

Tuple{Int,Int8,Vector{Any}} <: Tuple{T,T,Vector{Union{Integer,T}}} where T

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

Subtyping diagonal variables

Алгоритм подтипирования для диагональных переменных имеет два компонента: (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. Мы еще не разработали полный алгоритм для этого.

Introduction to the internal machinery

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

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

julia> function mysubtype(a,b)
           ccall(:jl_breakpoint, Cvoid, (Any,), nothing)
           a <: b
       end

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

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

mysubtype(Tuple{Int, Float64}, Tuple{Integer, Real})

Мы можем сделать это более интересным, попробовав более сложный случай:

mysubtype(Tuple{Array{Int,2}, Int8}, Tuple{Array{T}, T} where T)

Subtyping and method sorting

Функции 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}}.

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

type_morespecific(a, b) = ccall(:jl_type_morespecific, Cint, (Any,Any), a, b)

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