Julia 类型系统深入解析：从集合论到 UnionAll 与对角变量的内部机制

Julia 类型系统深入解析从集合论到 UnionAll 与对角变量的内部机制【免费下载链接】juliaThe Julia Programming Language项目地址: https://gitcode.com/gh_mirrors/ju/julia本文是 Julia 官方开发者文档 More about types 的深度技术指南面向已熟悉 Julia 基本类型用法的开发者揭开类型系统引擎盖之下的运作原理如何用集合论理解类型、UnionAll与TypeVar的表示、自由变量的意义、TypeName与类型缓存以及支配方法分派dispatch的对角变量子类型规则。读完本文你将能读懂subtype.c与jltypes.c的核心算法思路理解f(x::T, y::T) where T这类签名为何如此特殊并掌握在调试器中跟踪子类型计算的方法。类型与集合Any与Union{}Bottom理解 Julia 类型系统最自然的视角是集合论程序操作的是单个值而一个类型描述的是一个值的集合set of values。这不同于集合对象——例如一个Set值本身只是一个Set值而类型表达的是一种不确定性我们有一个值但不确定具体是哪一个。具体类型concrete typeT描述的是直接标签direct tag恰好为T的值集合其中标签由typeof返回抽象类型abstract type描述的是可能更大的值集合。在全集与空集的端点处有两个特殊类型Any描述全部可能值的整个宇宙Integer是Any的子集包含Int、Int8等具体类型Bottom即Union{}对应空集——没有任何值属于它。Julia 的类型系统支持标准的集合运算运算语法/函数语义子集判断subtypeT1 : 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 的心脏方法分派dispatch就是遍历方法列表找到参数元组类型是其签名子类型的那个方法。为了让这一算法正确工作方法必须按特异性specificity排序且搜索从最特异的开始。因此 Julia 在类型上实现了一个偏序partial order其功能与:类似但存在下文将讨论的差异。UnionAll 类型表示变量取遍所有值的类型并Julia 的类型系统还能表达一个迭代并iterated union某个变量取遍所有值时的类型并集。当参数化类型的某些参数取值未知时就需要它。例如Array有两个参数Array{Int,2}。若元素类型未知可写成Array{T,2} where T它是T取遍所有值时Array{T,2}的并集Union{Array{Int8,2}, Array{Int16,2}, ...}。这样的类型由一个UnionAll对象表示它包含一个变量如T类型为TypeVar一个被包裹的类型如Array{T,2}。C 层面的定义见 src/julia.h// UnionAll type (iterated union over all values of a variable in certain bounds) // written body where lb:var:ub typedef struct { JL_DATA_TYPE jl_tvar_t *JL_NONNULL var; jl_value_t *JL_NONNULL body; } jl_unionall_t;考虑如下四个方法f1(A::Array) 1 f2(A::Array{Int}) 2 f3(A::Array{T}) where {T:Any} 3 f4(A::Array{Any}) 4f3的签名是一个包裹元组类型的UnionAll类型Tuple{typeof(f3), Array{T}} where T。所有方法除了f4都能以a [1,2]调用除了f2都能以b Any[1,2]调用。用dump观察Array的内部结构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类型每个参数嵌套一个UnionAll。Array{Int,2}等价于Array{Int}{2}内部每个UnionAll依次以某个变量值实例化从最外层开始逐一进行。这赋予了省略尾部类型参数以自然语义Array{Int}等价于Array{Int,N} where N。TypeVar不是类型而是 UnionAll 结构的组成部分一个TypeVar本身不是类型应被视为UnionAll类型的结构的一部分。类型变量带有取值的下界与上界字段lb与ubname符号纯粹是装饰性的。C 层定义见 src/julia.htypedef struct { JL_DATA_TYPE jl_sym_t *JL_NONNULL name; jl_value_t *JL_NONNULL lb; // lower bound jl_value_t *JL_NONNULL ub; // upper bound } jl_tvar_t;内部TypeVar按地址比较因此被定义为可变类型以确保不同的类型变量能被区分但按约定它们不应被改写。可以手动构造TypeVarjulia 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类型系统中最关键的概念之一自由free类型变量的概念在类型系统中极其重要。若类型T中不包含引入变量V的那个UnionAll则称V在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的类型子类型及其他类型函数无法给出有意义的结果。该函数在运行时中被广泛用于保护各种类型操作例如 src/builtins.c 中的has_free_typevars内建函数以及 src/codegen.cpp 中对含自由变量值的处理。TypeNames区分同一名字的不同类型下面两个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 0x00C 层中jl_typename_t的完整定义见 src/julia.h其注释点明了职责表示一个DataType的 name 部分描述类型的语法结构并存储该类型不同实例化共享的全部数据包括用于 hash-consing 分配DataType对象的缓存。关键字段包括wrapper指向用于创建新Array类型的顶层类型的引用cache排序数组与linearcache未排序数组参数化类型实例化的缓存hash分配给每个类型的整数max_args、max_methods、constprop_heuristic等与方法表、常量传播启发式相关的属性。本例中相关字段是wrapperjulia 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}的wrapper指回类型的原始定义。关于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})与大多数类型不同元组类型在参数上是**协变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类型是自由的即绑定它的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即只接受两个参数类型完全相同的调用。能否按两个值类型相同进行分派非常有用例如 promotion 系统就用到了它。为了让Tuple{T,T} where T有不同解释子类型规则加入了一条如果某个变量在协变位置出现多次则它被限制为只取具体类型。协变位置指从变量出现处到引入它的UnionAll类型之间只经过Tuple和Union类型。这类变量被称为对角变量diagonal variables或具体变量concrete variables。于是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只出现一次不是对角的。不变位置的相等约束equality constraint再看这个签名f(a::Array{T}, x::T, y::T) where {T} ...这里T出现在Array{T}的不变invariant位置。这意味着传入的数组类型无歧义地决定了T的值——我们说T带有一个相等约束。此时对角规则并非必要数组确定了Tx与y可以是T的任意子类型。因此出现在不变位置的变量永不被视为对角变量。这一行为选择略有争议——有人主张应写成f(a::Array{T}, x::S, y::S) where {T, S:T} ...以澄清x与y是否需要相同类型此写法下它们需要若允许不同则应引入第三个变量。并集与对角变量的交互下一个复杂点是对角变量与并集的交互f(x::Union{Nothing,T}, y::T) where {T} ...y的类型是Tx可以是同类型的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未被使用只在第二个槽位用到一次。这自然源于在Tuple{T} where T中限制T为具体类型没有任何差别——无论哪种方式该类型都等于Tuple{Any}。然而出现在不变位置会取消变量的具体性无论该出现是否被使用。否则类型的行为会随比较对象不同而不同使子类型失去传递性。例如Tuple{Int,Int8,Vector{Integer}} : Tuple{T,T,Vector{Union{Integer,T}}} where T如果忽略Union内的T则T是具体的答案为false前两个类型不同。但考虑Tuple{Int,Int8,Vector{Any}} : Tuple{T,T,Vector{Union{Integer,T}}} where T此时不能忽略Union中的T必须T AnyT不是具体的答案为true。若如此T的具体性将取决于另一个类型——这不可接受因为一个类型必须有自身明确的意义。因此两种情况下Vector内的T都被计入。对角变量的子类型算法源码实现对角变量的子类型算法由两部分组成(1) 识别变量出现(2) 确保对角变量只取具体类型。第一部分通过为环境中每个变量维护计数器occurs_inv与occurs_cov定义于 src/subtype.c 的jl_varbinding_t结构实现typedef struct jl_varbinding_t { jl_tvar_t *var; // store NULL to delete this from env (temporarily) jl_value_t *JL_NONNULL lb; jl_value_t *JL_NONNULL ub; int8_t existential; // whether this variable should be treated as existential int8_t occurs_inv; // occurs in invariant position int8_t occurs_cov; // # of occurrences in covariant position within the // current consistency-check scope ... int8_t cov_diag; // max value occurs_cov reached in any (already-closed) // consistency-check scope. The diagonal-rule test is // max(occurs_cov, cov_diag) 1, so a variable is // diagonal iff it occurred 2 times in some single // scope ... int8_t concrete; // 1 if another variable has a constraint forcing this one to be concrete ... } jl_varbinding_t;一个变量是对角的当occurs_inv 0 occurs_cov 1。计数在 src/subtype.c 附近递增occurs_inv与occurs_cov均饱和于 2。第二部分通过对变量**下界lower bound**施加条件实现。子类型算法运行时会不断收窄各变量的界提高下界、降低上界以跟踪子类型关系成立时变量可取的范围。当完成某个对角变量的UnionAll主体求值后检查界的最终值变量必须具体因此若其下界不可能是某个具体类型的子类型就产生矛盾。例如抽象类型AbstractArray不可能是具体类型的子类型但具体类型Int可以空类型Bottom也可以。若下界未通过检验算法以false终止。例如在Tuple{Int,String} : Tuple{T,T} where T中若T是Union{Int,String}的超类型则成立但Union{Int,String}是抽象类型故关系不成立。这一具体性检验由函数is_leaf_bound完成见 src/subtype.c// check that a type is concrete or quasi-concrete (Type{T}). // this is used to check concrete typevars: // issubtype is false if the lower bound of a concrete type var is not concrete. int is_leaf_bound(jl_value_t *v) JL_NOTSAFEPOINT { if (v jl_bottom_type) return 1; if (jl_is_intersecttype(v)) // internal meet node (see #61917), not a concrete leaf return 0; if (jl_is_some_Type(v)) return 1; if (jl_is_datatype(v)) { if (((jl_datatype_t*)v)-name-abstract) { return 0; } return ((jl_datatype_t*)v)-isconcretetype; } return !jl_is_type(v) !jl_is_typevar(v); }注意该检验与jl_is_leaf_type略有不同它对Bottom也返回true。目前该函数是启发式的并不能捕获所有可能的具体类型。难点在于一个下界是否具体可能依赖其他类型变量界的取值。例如Vector{T}只有在T的上下界都等于Int时才等价于具体类型Vector{Int}——官方文档明确说明完整算法尚未研究清楚。内部机制导览在调试器中观察子类型处理类型的大多数操作位于jltypes.c与subtype.c两个文件中。最好的入门方式是从观察子类型入手用make debug构建 Julia然后在调试器中启动 Julia。gdb 调试技巧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)后者同时涉及UnionAll、协变出现与对角规则是理解整个算法相互作用的好案例。子类型与方法排序type_morespecifictype_morespecific系列函数用于在方法表中对函数施加偏序从最特异到最不特异。特异性是严格的若a比b更特异则a ! b且b不比a更特异。如果a是b的严格子类型则自动认为a更特异。在此基础上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}}更特异此外若两个方法签名完全相同类型相等则按添加顺序比较后添加的方法更特异。这些规则在 src/subtype.c 的jl_type_morespecific与jl_method_morespecific中实现。后者明确处理了签名类型相等时比较方法添加顺序的语义JL_DLLEXPORT int jl_method_morespecific(jl_method_t *ma, jl_method_t *mb) { jl_value_t *a (jl_value_t*)ma-sig; jl_value_t *b (jl_value_t*)mb-sig; if (obviously_disjoint(a, b, 1)) return 0; if (jl_has_free_typevars(a) || jl_has_free_typevars(b)) return 0; if (jl_subtype(b, a)) { if (jl_types_equal(a, b)) return jl_atomic_load_relaxed(ma-primary_world) jl_atomic_load_relaxed(mb-primary_world); return 0; } if (jl_subtype(a, b)) return 1; return type_morespecific_(a, b, a, b, 0, NULL); }方法分派正是在 src/gf.c 中借助jl_type_morespecific对候选方法排序如 src/gf.c 中对方法签名与参数类型的特异性比较从而保证搜索从最特异的方法开始。这与文档开头方法分派 遍历按特异性排序的方法表的论述形成了完整的闭环。总结从集合论的视角出发Julia 的类型系统可以被系统地拆解Union{}Bottom与Any构成空集与全集UnionAll与TypeVar表达参数化类型的迭代并TypeName承载同一名字下的类型缓存与元信息元组的协变性与Vararg规则支撑了分派的灵活性而对角变量规则则保证了同型约束这一实用能力与子类型传递性之间的平衡。这些机制最终汇聚于jltypes.c与subtype.c两个 C 文件——前者负责类型的表示与缓存后者实现了is_leaf_bound、occurs_inv/occurs_cov计数以及type_morespecific等方法排序逻辑。理解这一层你不仅能解释f(x::T, y::T) where T的行为更能为深入 Julia 运行时与编译器源码打下坚实基础。【免费下载链接】juliaThe Julia Programming Language项目地址: https://gitcode.com/gh_mirrors/ju/julia创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考