企业官网建设流程全解析

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 type）T描述的是"直接标签（direct tag）恰好为T"的值集合，其中标签由typeof返回；
• 抽象类型（abstract type）描述的是可能更大的值集合。

在全集与空集的端点处，有两个特殊类型：

• Any描述全部可能值的整个宇宙；
• Integer是Any的子集，包含Int、Int8等具体类型；
• Bottom（即Union{}）对应空集——没有任何值属于它。

Julia 的类型系统支持标准的集合运算：

官方文档给出的运算示例：

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}) = 4

f3的签名是一个包裹元组类型的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与ub），name符号纯粹是装饰性的。C 层定义见 src/julia.h：

typedef 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按地址比较，因此被定义为可变类型，以确保"不同的"类型变量能被区分；但按约定它们不应被改写。

可以手动构造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）：类型系统中最关键的概念之一

自由（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 0x00

C 层中jl_typename_t的完整定义见 src/julia.h，其注释点明了职责："表示一个DataType的 'name' 部分，描述类型的语法结构，并存储该类型不同实例化共享的全部数据，包括用于 hash-consing 分配DataType对象的缓存"。关键字段包括：

• wrapper：指向用于创建新Array类型的顶层类型的引用；
• cache（排序数组）与linearcache（未排序数组）：参数化类型实例化的缓存；
• hash：分配给每个类型的整数；
• max_args、max_methods、constprop_heuristic等：与方法表、常量传播启发式相关的属性。

本例中相关字段是wrapper：

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

Array的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带有一个相等约束。此时对角规则并非必要：数组确定了T，x与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的类型是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未被使用，只在第二个槽位用到一次。这自然源于：在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 == Any），T不是具体的，答案为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_morespecific

type_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