More about types

If you've used Julia for a while, you understand the fundamental role that types play. Here we try to get under the hood, focusing particularly onParametric Types.

Types and sets (andAny andUnion{}/Bottom)

It's perhaps easiest to conceive of Julia's type system in terms of sets. While programs manipulate individual values, a type refers to a set of values. This is not the same thing as a collection; for example aSet of values is itself a singleSet value. Rather, a type describes a set ofpossible values, expressing uncertainty about which value we have.

Aconcrete typeT describes the set of values whose direct tag, as returned by thetypeof function, isT. Anabstract type describes some possibly-larger set of values.

Any describes the entire universe of possible values.Integer is a subset ofAny that includesInt,Int8, and other concrete types. Internally, Julia also makes heavy use of another type known asBottom, which can also be written asUnion{}. This corresponds to the empty set.

Julia's types support the standard operations of set theory: you can ask whetherT1 is a "subset" (subtype) ofT2 withT1 <: T2. Likewise, you intersect two types usingtypeintersect, take their union withUnion, and compute a type that contains their union withtypejoin:

julia> typeintersect(Int, Float64)Union{}julia> Union{Int, Float64}Union{Float64, Int64}julia> typejoin(Int, Float64)Realjulia> typeintersect(Signed, Union{UInt8, Int8})Int8julia> Union{Signed, Union{UInt8, Int8}}Union{UInt8, Signed}julia> typejoin(Signed, Union{UInt8, Int8})Integerjulia> 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}

While these operations may seem abstract, they lie at the heart of Julia. For example, method dispatch is implemented by stepping through the items in a method list until reaching one for which the type of the argument tuple is a subtype of the method signature. For this algorithm to work, it's important that methods be sorted by their specificity, and that the search begins with the most specific methods. Consequently, Julia also implements a partial order on types; this is achieved by functionality that is similar to<:, but with differences that will be discussed below.

UnionAll types

Julia's type system can also express aniterated union of types: a union of types over all values of some variable. This is needed to describe parametric types where the values of some parameters are not known.

For example,Array has two parameters as inArray{Int,2}. If we did not know the element type, we could writeArray{T,2} where T, which is the union ofArray{T,2} for all values ofT:Union{Array{Int8,2}, Array{Int16,2}, ...}.

Such a type is represented by aUnionAll object, which contains a variable (T in this example, of typeTypeVar), and a wrapped type (Array{T,2} in this example).

Consider the following methods:

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

The signature - as described inFunction calls - off3 is aUnionAll type wrapping a tuple type:Tuple{typeof(f3), Array{T}} where T. All butf4 can be called witha = [1,2]; all butf2 can be called withb = Any[1,2].

Let's look at these types a little more closely:

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}

This indicates thatArray actually names aUnionAll type. There is oneUnionAll type for each parameter, nested. The syntaxArray{Int,2} is equivalent toArray{Int}{2}; internally eachUnionAll is instantiated with a particular variable value, one at a time, outermost-first. This gives a natural meaning to the omission of trailing type parameters;Array{Int} gives a type equivalent toArray{Int,N} where N.

ATypeVar is not itself a type, but rather should be considered part of the structure of aUnionAll type. Type variables have lower and upper bounds on their values (in the fieldslb andub). The symbolname is purely cosmetic. Internally,TypeVars are compared by address, so they are defined as mutable types to ensure that "different" type variables can be distinguished. However, by convention they should not be mutated.

One can constructTypeVars manually:

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

There are convenience versions that allow you to omit any of these arguments except thename symbol.

The syntaxArray{T} where T<:Integer is lowered to

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

so it is seldom necessary to construct aTypeVar manually (indeed, this is to be avoided).

Free variables

The concept of afree type variable is extremely important in the type system. We say that a variableV is free in typeT ifT does not contain theUnionAll that introduces variableV. For example, the typeArray{Array{V} where V<:Integer} has no free variables, but theArray{V} part inside of it does have a free variable,V.

A type with free variables is, in some sense, not really a type at all. Consider the typeArray{Array{T}} where T, which refers to all homogeneous arrays of arrays. The inner typeArray{T}, seen by itself, might seem to refer to any kind of array. However, every element of the outer array must have thesame array type, soArray{T} cannot refer to just any old array. One could say thatArray{T} effectively "occurs" multiple times, andT must have the same value each "time".

For this reason, the functionjl_has_free_typevars in the C API is very important. Types for which it returns true will not give meaningful answers in subtyping and other type functions.

TypeNames

The following twoArray types are functionally equivalent, yet print differently:

julia> TV, NV = TypeVar(:T), TypeVar(:N)(T, N)julia> ArrayArrayjulia> Array{TV, NV}Array{T, N}

These can be distinguished by examining thename field of the type, which is an object of typeTypeName:

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

In this case, the relevant field iswrapper, which holds a reference to the top-level type used to make newArray types.

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

Thewrapper field ofArray points to itself, but forArray{TV,NV} it points back to the original definition of the type.

What about the other fields?hash assigns an integer to each type. To examine thecache field, it's helpful to pick a type that is less heavily used than Array. Let's first create our own type:

julia> struct MyType{T,N} endjulia> MyType{Int,2}MyType{Int64, 2}julia> MyType{Float32, 5}MyType{Float32, 5}

When you instantiate a parametric type, each concrete type gets saved in a type cache (MyType.body.body.name.cache). However, instances containing free type variables are not cached.

Tuple types

Tuple types constitute an interesting special case. For dispatch to work on declarations likex::Tuple, the type has to be able to accommodate any tuple. Let's check the parameters:

julia> TupleTuplejulia> Tuple.parameterssvec(Vararg{Any})

Unlike other types, tuple types are covariant in their parameters, so this definition permitsTuple to match any type of tuple:

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

However, if a variadic (Vararg) tuple type has free variables it can describe different kinds of tuples:

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

Notice that whenT is free with respect to theTuple type (i.e. its bindingUnionAll type is outside theTuple type), only oneT value must work over the whole type. Therefore a heterogeneous tuple does not match.

Finally, it's worth noting thatTuple{} is distinct:

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

What is the "primary" tuple-type?

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

soTuple == Tuple{Vararg{Any}} is indeed the primary type.

Diagonal types

Consider the typeTuple{T,T} where T. A method with this signature would look like:

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

According to the usual interpretation of aUnionAll type, thisT ranges over all types, includingAny, so this type should be equivalent toTuple{Any,Any}. However, this interpretation causes some practical problems.

First, a value ofT needs to be available inside the method definition. For a call likef(1, 1.0), it's not clear whatT should be. It could beUnion{Int,Float64}, or perhapsReal. Intuitively, we expect the declarationx::T to meanT === typeof(x). To make sure that invariant holds, we needtypeof(x) === typeof(y) === T in this method. That implies the method should only be called for arguments of the exact same type.

It turns out that being able to dispatch on whether two values have the same type is very useful (this is used by the promotion system for example), so we have multiple reasons to want a different interpretation ofTuple{T,T} where T. To make this work we add the following rule to subtyping: if a variable occurs more than once in covariant position, it is restricted to ranging over only concrete types. ("Covariant position" means that onlyTuple andUnion types occur between an occurrence of a variable and theUnionAll type that introduces it.) Such variables are called "diagonal variables" or "concrete variables".

So for example,Tuple{T,T} where T can be seen asUnion{Tuple{Int8,Int8}, Tuple{Int16,Int16}, ...}, whereT ranges over all concrete types. This gives rise to some interesting subtyping results. For exampleTuple{Real,Real} is not a subtype ofTuple{T,T} where T, because it includes some types likeTuple{Int8,Int16} where the two elements have different types.Tuple{Real,Real} andTuple{T,T} where T have the non-trivial intersectionTuple{T,T} where T<:Real. However,Tuple{Real}is a subtype ofTuple{T} where T, because in that caseT occurs only once and so is not diagonal.

Next consider a signature like the following:

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

In this case,T occurs in invariant position insideArray{T}. That means whatever type of array is passed unambiguously determines the value ofT – we sayT has anequality constraint on it. Therefore in this case the diagonal rule is not really necessary, since the array determinesT and we can then allowx andy to be of any subtypes ofT. So variables that occur in invariant position are never considered diagonal. This choice of behavior is slightly controversial – some feel this definition should be written as

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

to clarify whetherx andy need to have the same type. In this version of the signature they would, or we could introduce a third variable for the type ofy ifx andy can have different types.

The next complication is the interaction of unions and diagonal variables, e.g.

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

Consider what this declaration means.y has typeT.x then can have either the same typeT, or else be of typeNothing. So all of the following calls should match:

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

These examples are telling us something: whenx isnothing::Nothing, there are no extra constraints ony. It is as if the method signature hady::Any. Indeed, we have the following type equivalence:

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

The general rule is: a concrete variable in covariant position acts like it's not concrete if the subtyping algorithm onlyuses it once. Whenx has typeNothing, we don't need to use theT inUnion{Nothing,T}; we only use it in the second slot. This arises naturally from the observation that inTuple{T} where T restrictingT to concrete types makes no difference; the type is equal toTuple{Any} either way.

However, appearing ininvariant position disqualifies a variable from being concrete whether that appearance of the variable is used or not. Otherwise types can behave differently depending on which other types they are compared to, making subtyping not transitive. For example, consider

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

If theT inside theUnion is ignored, thenT is concrete and the answer is "false" since the first two types aren't the same. But consider instead

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

Now we cannot ignore theT in theUnion (we must haveT == Any), soT is not concrete and the answer is "true". That would make the concreteness ofT depend on the other type, which is not acceptable since a type must have a clear meaning on its own. Therefore the appearance ofT insideVector is considered in both cases.

Subtyping diagonal variables

The subtyping algorithm for diagonal variables has two components: (1) identifying variable occurrences, and (2) ensuring that diagonal variables range over concrete types only.

The first task is accomplished by keeping countersoccurs_inv andoccurs_cov (insrc/subtype.c) for each variable in the environment, tracking the number of invariant and covariant occurrences, respectively. A variable is diagonal whenoccurs_inv == 0 && occurs_cov > 1.

The second task is accomplished by imposing a condition on a variable's lower bound. As the subtyping algorithm runs, it narrows the bounds of each variable (raising lower bounds and lowering upper bounds) to keep track of the range of variable values for which the subtype relation would hold. When we are done evaluating the body of aUnionAll type whose variable is diagonal, we look at the final values of the bounds. Since the variable must be concrete, a contradiction occurs if its lower bound could not be a subtype of a concrete type. For example, an abstract type likeAbstractArray cannot be a subtype of a concrete type, but a concrete type likeInt can be, and the empty typeBottom can be as well. If a lower bound fails this test the algorithm stops with the answerfalse.

For example, in the problemTuple{Int,String} <: Tuple{T,T} where T, we derive that this would be true ifT were a supertype ofUnion{Int,String}. However,Union{Int,String} is an abstract type, so the relation does not hold.

This concreteness test is done by the functionis_leaf_bound. Note that this test is slightly different fromjl_is_leaf_type, since it also returnstrue forBottom. Currently this function is heuristic, and does not catch all possible concrete types. The difficulty is that whether a lower bound is concrete might depend on the values of other type variable bounds. For example,Vector{T} is equivalent to the concrete typeVector{Int} only if both the upper and lower bounds ofT equalInt. We have not yet worked out a complete algorithm for this.

Introduction to the internal machinery

Most operations for dealing with types are found in the filesjltypes.c andsubtype.c. A good way to start is to watch subtyping in action. Build Julia withmake debug and fire up Julia within a debugger.gdb debugging tips has some tips which may be useful.

Because the subtyping code is used heavily in the REPL itself – and hence breakpoints in this code get triggered often – it will be easiest if you make the following definition:

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

and then set a breakpoint injl_breakpoint. Once this breakpoint gets triggered, you can set breakpoints in other functions.

As a warm-up, try the following:

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

We can make it more interesting by trying a more complex case:

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

Subtyping and method sorting

Thetype_morespecific functions are used for imposing a partial order on functions in method tables (from most-to-least specific). Specificity is strict; ifa is more specific thanb, thena does not equalb andb is not more specific thana.

Ifa is a strict subtype ofb, then it is automatically considered more specific. From there,type_morespecific employs some less formal rules. For example,subtype is sensitive to the number of arguments, buttype_morespecific may not be. In particular,Tuple{Int,AbstractFloat} is more specific thanTuple{Integer}, even though it is not a subtype. (OfTuple{Int,AbstractFloat} andTuple{Integer,Float64}, neither is more specific than the other.) Likewise,Tuple{Int,Vararg{Int}} is not a subtype ofTuple{Integer}, but it is considered more specific. However,morespecific does get a bonus for length: in particular,Tuple{Int,Int} is more specific thanTuple{Int,Vararg{Int}}.

If you're debugging how methods get sorted, it can be convenient to define the function:

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

which allows you to test whether tuple typea is more specific than tuple typeb.