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で2つの型の共通部分を、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}のように2つのパラメータがあります。要素型が不明な場合は、Array{T,2} where Tと書けます。これはTのすべての値にわたるArray{T,2}の和集合、すなわち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}) = 4Function 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: abstract type Any
body: UnionAll
var: TypeVar
name: Symbol N
lb: Union{}
ub: abstract type Any
body: mutable struct Array{T, N} <: DenseArray{T, N}
ref::MemoryRef{T}
size::NTuple{N, Int64}ここから、Arrayは実際にはUnionAll型の名前であることがわかります。パラメータごとに1つのUnionAll型があり、それらが入れ子になっています。Array{Int,2}という構文はArray{Int}{2}と等価です。内部では、各UnionAllが、最も外側から順に1つずつ、特定の変数値でインスタンス化されます。これにより、末尾の型パラメータの省略に自然な意味が与えられます。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
型システムでは、自由型変数という概念が非常に重要です。型Tにおいて変数Vが自由であるとは、Tが、変数Vを導入するUnionAllを含んでいないことをいいます。たとえば、型Array{Array{V} where V<:Integer}には自由変数がありませんが、その内部のArray{V}の部分には、自由変数Vがあります。
自由変数を含む型は、ある意味では、そもそも本当の型とはいえません。型Array{Array{T}} where Tを考えてみましょう。これは、配列を要素とする同種配列すべてを指します。内側の型Array{T}だけを見ると、あらゆる種類の配列を指しているように見えるかもしれません。しかし、外側の配列の各要素は同じ配列型でなければならないため、Array{T}は単に任意の配列を指すわけではありません。Array{T}は実質的に複数回「出現」しており、その「たびに」Tは同じ値でなければならない、ともいえます。
このため、C APIの関数jl_has_free_typevarsは非常に重要です。この関数がtrueを返す型については、部分型判定やその他の型関数から意味のある結果は得られません。
TypeNames
次の2つのArray型は、機能的には等価ですが、表示は異なります。
julia> TV, NV = TypeVar(:T), TypeVar(:N)
(T, N)
julia> Array
Array
julia> Array{TV, NV}
Array{T, N}これらは、型のnameフィールドを調べることで区別できます。このフィールドはTypeName型のオブジェクトです。
julia> dump(Array{Int,1}.name)
TypeName
name: Symbol Array
module: Module Core
singletonname: Symbol Array
names: SimpleVector
1: Symbol ref
2: Symbol size
atomicfields: Ptr{Nothing}(0x0000000000000000)
constfields: Ptr{Nothing}(0x0000000000000000)
wrapper: UnionAll
var: TypeVar
name: Symbol T
lb: Union{}
ub: abstract type Any
body: UnionAll
var: TypeVar
name: Symbol N
lb: Union{}
ub: abstract type Any
body: mutable struct Array{T, N} <: DenseArray{T, N}
Typeofwrapper: abstract type Type{Array} <: Any
cache: SimpleVector
...
linearcache: SimpleVector
...
hash: Int64 2594190783455944385
backedges: #undef
partial: #undef
max_args: Int32 0
n_uninitialized: Int32 0
flags: UInt8 0x02
cache_entry_count: UInt8 0x00
max_methods: UInt8 0x00
constprop_heuristic: UInt8 0x00ここで関係するのは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} @0x00007fcc7de64850Arrayのwrapperフィールドは自分自身を指しますが、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が必要です。つまり、このメソッドは、まったく同じ型の引数に対してのみ呼び出されるべきだということです。
2つの値が同じ型かどうかでディスパッチできることは、非常に便利です(たとえば、昇格システムで利用されています)。したがって、Tuple{T,T} where Tに別の解釈を求める理由は複数あります。これを実現するため、部分型判定に次の規則を加えます。変数が共変位置に複数回出現する場合、その変数が取り得る値は具象型のみに制限されます。(「共変位置」とは、変数の出現箇所と、その変数を導入するUnionAll型の間に、Tuple型とUnion型しか現れないことを意味します。)このような変数は「対角変数」または「具象変数」と呼ばれます。
したがって、たとえばTuple{T,T} where Tは、Tがすべての具象型を取り得るUnion{Tuple{Int8,Int8}, Tuple{Int16,Int16}, ...}と見なせます。これにより、部分型判定には興味深い結果が生じます。たとえば、Tuple{Real,Real}はTuple{T,T} where Tの部分型ではありません。2つの要素の型が異なるTuple{Int8,Int16}のような型を含むためです。Tuple{Real,Real}とTuple{T,T} where Tには、非自明な共通部分Tuple{T,T} where T<:Realがあります。一方、Tuple{Real}はTuple{T} where Tの部分型です。この場合、Tは1回しか出現せず、対角変数ではないためです。
次に、以下のようなシグネチャを考えてみましょう。
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が同じ型でなければならないかどうかを明確にするためです。この形式のシグネチャでは同じ型である必要があります。xとyに異なる型を許すのであれば、yの型に対して3つ目の変数を導入できます。
次に複雑になるのは、和集合と対角変数の相互作用です。たとえば、次のような場合です。
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}一般的な規則は次のとおりです。共変位置にある具象変数は、部分型判定アルゴリズムがそれを1回しか使用しない場合、具象変数ではないかのように振る舞います。xがNothing型の場合、Union{Nothing,T}内のTを使う必要はなく、2番目の位置でのみ使用します。これは、Tuple{T} where Tにおいて、Tを具象型に制限しても違いがないという事実から自然に導かれます。いずれにしても、その型はTuple{Any}に等しくなります。
ただし、不変位置に出現する変数は、その出現が使用されるかどうかにかかわらず、具象変数にはなれません。そうしないと、比較相手の型によって型の振る舞いが変わり、部分型関係の推移性が失われてしまいます。たとえば、次を考えてみましょう。
Tuple{Int,Int8,Vector{Integer}} <: Tuple{T,T,Vector{Union{Integer,T}}} where TUnion内のTを無視すると、Tは具象変数となり、最初の2つの型が同じではないため、答えは「false」になります。しかし、代わりに次を考えてみましょう。
Tuple{Int,Int8,Vector{Any}} <: Tuple{T,T,Vector{Union{Integer,T}}} where T今度は、Union内のTを無視できません(T == Anyでなければなりません)。そのため、Tは具象変数ではなく、答えは「true」になります。これでは、Tが具象変数かどうかが比較相手の型に依存してしまいます。型はそれ自体で明確な意味を持たなければならないため、これは認められません。したがって、どちらの場合も、Vector内でのTの出現を考慮します。
Subtyping diagonal variables
対角変数に対する部分型判定アルゴリズムは、(1) 変数の出現を特定することと、(2) 対角変数が具象型のみを取り得るようにすること、という2つの要素から成ります。
最初の処理は、環境内の変数ごとにカウンタoccurs_invとoccurs_covを(src/subtype.c内に)保持し、それぞれ不変位置と共変位置での出現回数を追跡することで実現します。occurs_inv == 0 && occurs_cov > 1のとき、その変数は対角変数です。
2番目の処理は、変数の下限に条件を課すことで実現します。部分型判定アルゴリズムは、実行中に各変数の範囲を狭めます(下限を上げ、上限を下げます)。これにより、部分型関係が成り立つ変数値の範囲を追跡します。変数が対角変数であるUnionAll型の本体を評価し終えたら、上限と下限の最終的な値を調べます。変数は具象型でなければならないため、その下限が具象型の部分型になり得なければ、矛盾が生じます。たとえば、AbstractArrayのような抽象型は具象型の部分型にはなれませんが、Intのような具象型や、空の型Bottomはなれます。下限がこの検査を通過しない場合、アルゴリズムはfalseという結果で停止します。
たとえば、Tuple{Int,String} <: Tuple{T,T} where Tという問題では、TがUnion{Int,String}の上位型であれば、これがtrueになると導かれます。しかし、Union{Int,String}は抽象型なので、この関係は成り立ちません。
この具象性の検査は、関数is_leaf_boundで行われます。この検査は、Bottomに対してもtrueを返すため、jl_is_leaf_typeとは少し異なることに注意してください。現在、この関数はヒューリスティックに基づいており、取り得るすべての具象型を検出できるわけではありません。難しいのは、下限が具象型かどうかが、ほかの型変数の上限や下限の値に依存する可能性があることです。たとえば、Vector{T}が具象型Vector{Int}と等価になるのは、Tの上限と下限がどちらもIntに等しい場合に限られます。このための完全なアルゴリズムは、まだ確立できていません。
Introduction to the internal machinery
型を扱う演算の大部分は、ファイルjltypes.cとsubtype.cにあります。まずは、部分型判定が実際に動作する様子を観察するとよいでしょう。make debugでJuliaをビルドし、デバッガ内で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}}より特異的です。
また、型の等価性判定において同一となるシグネチャを持つメソッドが2つ定義された場合は、代わりに追加された順序で比較され、後から追加されたメソッドのほうが先に追加されたメソッドより特異的と見なされます。