Julia の型

Julia をしばらく使ったなら、Julia で型が持つ重要な役割を理解しているはずです。ここでは型について、特にパラメトリック型について詳しく説明します。

型と集合 (Union{}/Bottom)

Julia の型システムは集合の言葉を使って考えるのがおそらく最も分かりやすいでしょう。プログラムが操作するのは個別の値であるのに対して、型が指すのは値の集合です。これはプログラムで使われるコレクションとは異なります: 例えば複数の値を Set にまとめたとしても、それは Set 型の値が一つあるだけです。そうではなく、型は可能な値の集合を表し、これによって値が取る値が正確には分からないもののある程度は分かることを表現します。

具象型 T は直接的なタグ (typeof が返す値) が T である値の集合を表します。抽象型はそれよりも大きな値の集合を表します。

例えば Any が表すのは全ての可能な値からなる集合であり、Integer が表すのは Int, Int8 などの具象型を含む Any の部分集合です。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 の心臓部に位置します。例えばメソッドのディスパッチは、メソッドリストの要素を一つずつ走査して、引数のタプルの型がシグネチャの部分型となっているメソッドを見つける処理として実装されます。このアルゴリズムが正しく高速に動作するには、メソッドが特定性specificityに関する順序でソートされ、探索が最も特定的なメソッドから始まることが重要です。このために、Julia には型に対する半順序も実装されています。型に対する半順序は <: と同様の機能で実現されますが、後述するように違いもあります。

UnionAll 型

Julia の型システムは型の反復和 (iterated union) も表現できます。反復和とは、ある変数が取り得る値のそれぞれで宣言される型を全て合併した型を意味します。これはパラメータのいずれかが定まっていないパラメトリック型を表すために必要です。

例えば Array を Array{Int,2} などとして使うことからも分かるように、Array は二つのパラメータを持ちます。要素型が分からないときは Array{T,2} where T と書けますが、これは任意の値を T に代入したときに得られる Array{T,2} 型を全て合併した型 Union{Array{Int,2}, Array{String,2}, ...} を表します。

こういった型は UnionAll オブジェクトとして表現されます。このオブジェクトは変数 (この型では TypeVar 型の T) とラップされた型 (この例では 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

Julia の関数呼び出しの章で説明されるように、f3 のシグネチャは Tuple{typeof(f3), Array{T}} where T というタプル型をラップした UnionAll 型です。f4 以外は a = [1,2] に対して呼び出すことができ、f2 以外は b = Any[1,2] に対して呼び出すことができます。

Array 型をもっと詳しく見てみましょう:

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}

この実行例から、Array が実際には UnionAll 型の値であることが分かります。一つのパラメータごとに一つの UnionAll 型があり、この例のようにパラメータが複数あるときは入れ子になります。Array{Int,2} という構文は Array{Int}{2} と等価であり、内部で UnionAll は変数ごとに一つずつインスタンス化されます。このため、最後にある型パラメータは自然に省略できます: 例えば Array{Int} は Array{Int,N} where N と等価な型を与えます。

TypeVar は型ではなく、UnionAll 型の一部分とみなされるべきです。型変数は可能な値の下界と上界 (それぞれ lb, ub フィールド) を持ちます。フィールド name のシンボルは本当は必要となりませんが、ユーザーに情報を与えるために存在します。内部で TypeVar はアドレスを使って比較されるので、"異なる" 型変数を区別するために可変型として定義されます。ただし慣習として 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) な型変数という概念は Julia の型システムにおいて非常に重要です。変数 V が型 T において自由であるとは、変数 V を持つ UnionAll が T に含まれないことを言います。例えば 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

次の二つの Array 型は機能的には同じですが、REPL 上での出力が異なります:

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
  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
    kwsorter: #undef
    module: Module Core
    : Int64 0
    : Int64 0

今関係あるフィールドは wrapper です。このフィールドは新しい Array 型を作るのに使われたトップレベルの型への参照を保持します。

julia> Array === Array.body.body.name.wrapper
true

julia> Array === Array{Int, 1}.name.wrapper
true

julia> Array === Array{TV, NV}
false

julia> Array === Array{TV, NV}.name.wrapper
true

この例から分かるように1、Array の 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) に保存されます。 ただし自由変数を含むインスタンスはキャッシュされません。

タプル型

タプル型は興味深い特別なケースです。ディスパッチが x::Tuple のような宣言でも動作できるように、タプル型は任意の型を保持できなければなりません。タプル型のパラメータを確認してみましょう:

julia> Tuple
Tuple

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

他の型と異なり、タプル型はパラメータについて共変 (covariant) です。そのため、上の定義により任意のタプル型と 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 型に関して自由なとき (言い換えると、T を束縛する UnionAll 型が Tuple 型の外にあるとき)、タプル型に含まれる T は全て同じである必要があることに注意してください。そのため二つ目の例では Tuple{Vararg{T}} where T が異なる型を持つタプル Tuple{Int,Float64} とマッチしていません。

最後に、Tuple{} は単一の型となります:

julia> Tuple{}
Tuple{}

julia> Tuple{}.parameters
svec()

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

タプル型の "元の" 型は何でしょうか2？

julia> Tuple === Tuple{}
false

julia> Tuple === Tuple.name.wrapper
true

julia> Tuple === Tuple{}.name.wrapper
true

julia> Tuple === Tuple{Int, Float64}.name.wrapper
true

つまり Tuple == Tuple{Vararg{Any}} が元の型となります。

対角型

Tuple{T,T} where T 型を考えます。このシグネチャを持つメソッドは例えば次のような形をしています:

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

UnionAll 型の通常の解釈によれば、この T は Any を含む全ての型となれます。よって Tuple{T,T} where T は Tuple{Any,Any} と等価なはずです。しかし、このような解釈は実際的な問題をいくつか引き起こします。

第一に、T の値はメソッド定義の内部で利用できなければなりませんが、f(1, 1.0) のような呼び出しで T が取るべき値は明らかではありません。T は Union{Int,Float64} になることも、Real になることもできます。しかし私たちが x::T と宣言するとき、直感的には T === typeof(x) を意図するはずです。この条件を成り立たせるには、前述のメソッド定義が typeof(x) === typeof(y) === T を含意する必要があります。これは正確に同じ型を持つ引数に対してだけ f が呼び出せることを意味します。

さらに二つの値が同じ型を持つかどうかに応じてディスパッチできると (型の昇格システムなどで) 非常に便利なことも判明しているので、Tuple{T,T} where T に異なる解釈を用意する理由が複数存在することになります。これを実現するために、私たちは部分型付け規則に次の規則を加えました: 「特定の変数が共変な場所に複数回現れるなら、その変数がなれるのは具象型だけ」というものです (変数が「共変な位置に現れる」とは、変数とそれを導入した UnionAll の間に Tuple と Union だけが現れることを意味します)。共変の場所にある変数を「対角変数 (diagonal variable)」あるいは「具象変数 (concrete variable)」と呼びます。

例えば Tuple{T,T} where T が表すのは Union{Tuple{Int8,Int8}, Tuple{Int16,Int16}, ...} であり、T は任意の具象型となれます。ここから興味深い部分型付け規則がいくつか生まれます。例えば Tuple{Real,Real} は Tuple{T,T} where T の部分型ではありません。なぜなら、Tuple{Real,Real} には Tuple{Int8,Int16} のような異なる二つの実数型からなるタプル型が含まれるからです。また Tuple{Real,Real} と Tuple{Int8,Int16} は非自明な交差 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 は等価制約 (equality constraint) を持つと言います。このときは配列が T を定めて x と y はそれぞれ T の任意の部分型となれるので、対角型の規則は適用されません。つまり不変な位置に表れた変数は対角型とみなされないということです。この振る舞いの選択は多少の議論を呼ぶものです ──中には、このシグネチャは次のように書かれるべきだと感じる人もいます:

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

こうすれば x と y が同じ型にならなければならないことがはっきりします。このバージョンのシグネチャで x と y が異なる型を持てるようにするには、新しく導入した三つ目の変数を 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 のとき Union{Nothing,T} の T は使われず、T はタプルの二番目のスロットでのみ使われます。この規則は Tuple{T} where T で T を具象型に制限しても違いが生まれないという観察から自然に得られます: いずれにせよ Tuple{T} where T は Tuple{Any} に等しいからです。

一方で、もし変数が不変な場所に現れたなら、その変数は使われるかどうかに関係なく具象型に制限されなくなります。この規則が存在しないと、型の比較において同一の型が比較相手によって異なる振る舞いをするようになり、部分型関係が推移律を満たさなくなります。例として次の比較を考えます:

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

右辺の Union に含まれる T を無視できると仮定すれば、T は具象変数となり、最初の二つの T は同じ型となるので、比較の結果は false となります。さらに次の比較を考えます:

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

ここでは Union に含まれる T を無視できません (部分型関係を成り立たせるには T == Any が必要だからです)。すると T は具象変数とならず、比較の結果は true となります。つまり不変な場所に現れる変数を無視できるようにすると、T が具象変数かどうかが比較相手に依存してしまうのです。型はそれ自身で明確な意味を持っているべきであり、これは容認できません。これが理由で、両方の場合で Vector に含まれる T は考えに入れられます。

対角変数の部分型付け

対角変数に対する部分型付けアルゴリズムは二つの部分からなります:

  1. 対角変数の出現を見つける。
  2. 対角変数が具象型の値を取ることを保証する。

一つ目のタスクは環境内の各変数に対して occurs_inv と occurs_cov という二つのカウンターを使って不変および共変な位置での出現回数を数えることで行われます (参照: 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 関数が行います。この関数は Bottom に対して true を返すので、jl_is_leaf_type とは同じでないことに注意してください。なお現在この関数はヒューリスティックを使っており、全ての具象型を捕捉できるわけではありません。難しいのは下界が具象型かどうかが他の型変数の上界または下界に依存する場合がある点です。例えば Vector{T} が具象型 Vector{Int} と等価になるのは T の上界と下界が Int に等しいときだけです。私たちはこの問題に対する完全なアルゴリズムをまだ実装していません。

型の内部機構への入門

型を扱う操作の多くは jltypes.c と subtype.c で見つかります。まずは部分型付けが動作する様子を実際に見てみるのがよいでしょう。make debug として Julia をビルドして、Julia をデバッガの中から起動してください。gdb デバッグ 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)

部分型付けとメソッドのソート

type_morespecific 関数がメソッドテーブル内の関数に半順序を定めます。この特定性specificityは狭義です: a が b よりも特定的で a と b が等しくないなら、b は a より特定的ではありません。

a が b の狭義部分型のとき、a は b より特定的だと自動的にみなされます。ただしそれ以外にも type_morespecific には形式性の劣る規則がいくつかあります。例えば subtype は引数の個数を区別しますが、type_morespecific は区別しない場合があります: Tuple{Int,AbstractFloat} は Tuple{Integer} の部分型ではありませんが、前者は後者より特定的とみなされます (これに対して Tuple{Int,AbstractFloat} と Tuple{Integer,Float64} では、どちらも相手より特定的ではありません)。同様に Tuple{Int,Vararg{Int}} は Tuple{Integer} の部分型ではありませんが、前者は後者より特定的だとみなされます。ただし type_morespecific は長さに関してボーナスを与えます: 例えば Tuple{Int,Int} は Tuple{Int,Vararg{Int}} より特定的です。

メソッドのソート方法をデバッグするときは、次の関数が便利です3:

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

この関数を使うとタプル型 a がタプル型 b より特定的かどうかを判定できます。

  1. 訳注: 現在のバージョンでは pointer_from_objref を可変オブジェクトに対して呼び出せないので、実行例を変更した。[return]

  2. 訳注: 現在のバージョンでは pointer_from_objref を可変オブジェクトに対して呼び出せないので、実行例を変更した。[return]

  3. 訳注: この関数は現在のバージョンで Base.morespecific として定義されている (エクスポートはされていない)。[return]

広告