类型系统是一组规则,用于为编程语言的各个组成部分赋予类型,并确定这些部分可以如何组合。类型描述值与计算的性质:表达式可能产生一个整数,函数可能接受字符串并返回布尔值,某项操作也可能要求独占访问某个资源。类型系统将这些区别精确定义,使编译器、解释器或其他检查机制能够据此实施约束。
类型系统在计算机科学和软件工程中有多种用途。它们能够检测某些编程错误、表达接口、支持抽象、指导程序变换,并为推理程序的正确性提供基础。不同类型系统提供的保证差异很大。常规类型系统可以防止将整数当作函数调用,而表达能力更强的系统则可以追踪数组长度、资源所有权或数学命题。任何普通的类型系统都无法确保每个程序都具备所有期望的性质。
类型可以在执行前接受检查,也可以在执行期间受到约束,或者结合这两种方式处理。因此,要理解类型系统,就需要区分其形式规则与具体实现,也需要区分它所排除的错误与仍有可能发生的故障。类型系统设计的核心问题是:如何在提供有用保证的同时,兼顾表达能力、易于理解的诊断信息,以及切实可行的检查成本。
历史起源与发展
类型系统在数学上的渊源,是为避免不受限制的自指所引发的悖论而进行的尝试。伯特兰·罗素于1908年提出类型论,将表达式划分为不同层级,限制哪些表达式可以用来述说哪些对象的性质。这项工作关注的是数学基础,而非编程,却确立了一个影响深远的思想:某些表达式组合应当被排除,因为它们的构造违反了分类规则。
阿隆佐·丘奇在20世纪30年代发展了λ演算,并于1940年提出简单类型论。在简单类型λ演算中,函数具有诸如 这样的类型,只有当实参具有所要求的类型时,才允许进行函数应用。这些系统为研究函数、计算和证明提供了一种简洁的数学语言,也揭示了一个至今仍然重要的区别:引入类型会改变哪些表达式可以写出来,而不只是为已有表达式添加说明。
早期编程语言使用类型,部分是为了区分不同的机器表示方式及其允许的操作。Fortran编程语言于1957年首次实现,区分了整数、浮点数等数值类别。ALGOL 60引入了声明以及对程序组成部分的结构化描述。后来的语言将类型的作用扩展到了机器层面的表示之外。约于1970年问世的Pascal强调结构化数据和编译期检查;Simula 67发展了类和继承机制,对面向对象编程产生了深远影响。
20世纪60年代和70年代的研究将编程语言中的类型与逻辑及自动推理联系起来。罗杰·欣德利于1969年发表了关于主类型的结果,罗宾·米尔纳则为ML开发了一套实用的多态类型规则,并在一篇发表于1978年、影响深远的论文中加以阐述。约翰·雷诺兹和让-伊夫·吉拉尔在20世纪70年代初各自独立发展了二阶多态λ演算的形式。这些进展解释了函数如何在不放弃静态检查的前提下,以统一的方式处理多种类型。
此后的工作既扩展了类型所能追踪的性质,也拓宽了类型系统的实际应用。模块系统支持大规模抽象;子类型机制将面向对象接口的某些方面形式化;依赖类型将程序与证明联系起来;线性类型和所有权规则则将资源使用纳入类型系统。近年来进入主流语言的特性包括对可空引用与非空引用的区分、代数数据类型、流敏感检查,以及静态类型与动态类型的结合。这段历史并非朝着某种普遍最强的单一设计不断演进的过程:各种语言仍在根据其应用领域、互操作性要求和实现约束作出不同的选择。
形式结构:判断、规则与语义
形式化的类型系统通常由类型语言、一组类型判断,以及用于确立这些判断的推理规则组成。一种常见的判断形式是
表示在假设 下,表达式 的类型为 。上下文 通常记录作用域内各变量的类型,不过,更丰富的系统还可能跟踪可用的能力、逻辑假设或资源所有权。类型判断是关于表达式的数学陈述;类型检查器则是尝试确立这类陈述的算法。
简单类型 λ 演算展示了这一基本结构。如果上下文中 的类型为 ,那么 就可以用作类型为 的表达式。如果在额外假设 的类型为 的条件下,函数体的类型为 ,那么函数抽象 的类型就是 。函数应用遵循以下规则:
这条规则体现了一项组合性原则:关于复合表达式的信息,可以从其直接组成部分的信息中推导出来。
类型可以包括布尔型、整数型等基本类别,以及用于构造更复杂类型的类型构造器。积类型 表示一个有序对;函数类型 描述一个可调用的值;列表类型则可以用元素类型作为参数。类型规则描述如何构造和消去这些值。例如,配对操作引入一个积,而投影操作则提取其中的一个分量。与存储表示相比,这些引入规则和消去规则往往能更清楚地揭示类型的本质含义。
类型判定必须与语言的语义相联系,也就是与语言对程序行为的描述相联系。操作语义通过求值步骤描述执行过程,这些步骤通常写作 。指称语义则在数学结构中解释表达式。这两种视角彼此相关,但不能互相替代。有时可以将类型近似理解为值的集合,但更精细的解释还会考虑行为、抽象、效应,或程序不同执行过程之间的关系。
实际语言还会引入小型演算中不存在的复杂因素。可变变量需要存储模型;异常需要控制转移规则;对象则需要对方法查找和继承作出描述。编译器可能会将便于使用的表层语法转换为规模更小的带类型中间语言,在其中显式呈现这些机制。因此,形式模型有两个用途:一是明确语言预期提供的保证,二是提供便于处理的研究对象,以证明这些保证在执行或转换后仍然成立。
类型安全及其保证的边界
类型安全关注类型判定与程序执行之间的关系。非正式地说,类型安全的语言会阻止将某些操作应用于不适当的值。不应把函数当作机器地址使用,布尔值也不应意外变成一个带有不相关字段的对象。具体禁止哪些行为,取决于语言的语义。如果不考虑特定语言将什么视为合法的值、操作或运行时失败,就无法给出有用的通用定义。
对于许多演算系统,类型健全性的论证围绕两个定理展开。保持性指出,求值会保持类型:如果 且 ,那么 的类型也为 ;涉及存储和其他状态时,需要对这一定理作适当扩展。进展性指出,类型正确的闭表达式要么是一个值,要么可以执行一步求值。两者共同确立:类型正确的程序在执行时,不会以模型所排除的特定方式陷入卡住状态。
“卡住”是一个技术概念,并不是所有不良结果的统称。一门语言可能明确允许除以零时抛出异常,因此抛出该异常并不违反其类型安全定理。无限循环在每一步都可能保持类型正确。程序也可能在遵守所有类型规则的同时,产生错误的业务结果。因此,通常意义上的类型安全并不意味着程序一定终止、功能正确、没有死锁,也不意味着能够防范所有安全漏洞。
内存安全与类型安全有所重叠,但两者并不相同。语言可以通过运行时检查、垃圾回收、所有权限制,或这些机制的组合,来防止越界访问和释放后使用。另一方面,C编程语言虽然具有静态类型,却允许一些操作在使用不当时引发未定义行为,包括无效指针解引用。整数运算究竟采用回绕、触发陷阱,还是产生未定义行为,同样由语言语义决定;仅有整数类型并不能消除整数溢出。
实际能够提供的保证,还取决于受检查系统的边界。外部函数接口、未经检查的类型转换、不安全的语言特性以及动态加载的代码,都可能引入常规检查器无法验证的假设。对健全性的主张必须明确这些假设,而不能将所有组件都视为受到同等保护。只有当不安全的实现代码维持了其接口所承诺的不变量时,安全代码才能依赖该实现。
最后,健全性是一种数学性质,并不意味着所有安全的程序都会被接受。健全的检查器可能拒绝某些执行时不会发生类型错误的程序。在表达能力足够强的语言中,要精确判定任意程序是否能够避免某种特定的不良行为,通常是不可能的。类型系统通过限制自身所进行的推理,得到可判定且实用的近似结果。
静态类型、动态类型与渐进类型
静态类型无需以实际输入执行程序,就能检查与类型有关的约束。检查可以发生在编译期间、编辑器中,或模块加载时。静态检查器根据程序结构、声明和推断出的信息进行推理。对于将整数与函数相加这样的表达式,即使某次执行根本不会运行到它,静态检查器也可能将其拒绝。静态类型并不要求每个变量都有显式的类型注解。
动态类型将类型上的区别关联到运行时的值,并在执行过程中检查操作。在 Python 和 JavaScript 等语言中,一个变量可以先后指向不同类别的值。这并不意味着值没有类型,也不意味着所有操作都被允许。调用不可调用的值,或尝试执行不受支持的操作,都可能引发运行时错误。尽管许多兼容性检查被推迟到执行时进行,动态类型语言仍然可以严格保障内存安全。
这些分类并不决定一种语言采用编译执行还是解释执行。静态类型语言可以由解释器执行,动态类型语言也可以编译成机器码。它们也不决定数据表示是否带有类型标签:静态类型语言可能保留运行时类型信息,以支持反射、类型转换或泛型操作。反过来,动态类型语言的优化实现也可能在确定特定执行路径上的某些性质后,消除冗余检查。
“强类型”和“弱类型”等术语则不够精确。它们可能指对隐式转换的限制、对数据表示重解释的防范,或运行时检查的覆盖程度。这些都是相互独立的设计问题。一种语言可以允许从整数到浮点数的隐式转换,同时拒绝一切未经检查的指针操作;另一种语言则可能要求显式进行数值转换,却开放底层操作。因此,准确的描述应指明相关的隐式转换、显式类型转换或安全规则,而不是依赖单一的强弱尺度。
渐进类型允许静态上精确的类型与动态类型或未知类型共存。例如,一个参数经过检查、要求为整数的函数,可能接收到来自动态类型代码的值,此时就需要进行边界检查。在形式化的渐进类型系统中,与未知类型的兼容性通常用一致性关系来表示,而不是普通的子类型关系。有些系统还会在边界契约检查失败时判定责任归属,帮助确定是哪个组件提供了不兼容的值。
并非所有支持可选类型注解的语言都提供相同的渐进类型保证。有些工具会擦除注解,不在运行时执行相应检查;另一些则会插入检查,或依赖显式的边界验证。宽松的逃逸类型可以抑制分析,却不能保证交互的健全性。关键问题在于:注解意味着什么,移除注解是否会改变行为,检查发生在何处,以及有类型组件与无类型组件交互时仍能保留哪些保证。
数据类型、抽象与接口设计
类型系统既提供了组织数据的概念体系,也限制了可执行的操作。基本类型表示基础类别,积类型组合多项信息,和类型则表示不同的可能情形。积类型 同时包含一个 和一个 ;和类型 包含其中一种情形,并通过标签加以区分。这些构造支持代数数据类型,其形态由不同情形、字段和递归定义的组合决定。
例如,可选值可以用两个构造器表示:None 和 Some(T)。二叉树既可以为空,也可以是一个包含元素和两棵子树的节点。模式匹配会检查一个值由哪个构造器生成,并使相应的字段可供使用。类型检查器通常能发现遗漏的情形,让数据的构造和使用都明确体现各种可能情形。因此,新增构造器后,所有处理不完整的位置都可能被揭示出来。
这种显式区分有助于分清那些在底层表示中会被混为一谈的状态。网络响应可以表示为 Success(Payload) 或 Failure(Error),而不是将载荷与一个独立的状态标志组合在一起。即使米和秒都存储为浮点数,为它们分别定义类型也能防止意外混用。这种保证的前提是类型之间的区别始终得到保留:如果一种语言仅将这两种声明视为同一底层类型的别名,就未必能强制执行这种区分。
抽象类型将接口与其表示方式分离。模块可以公开栈类型,以及创建栈、入栈和出栈的操作,同时隐藏实现究竟使用数组还是链式结构。对客户端代码的检查依据的是抽象接口,而不是实现的内部布局。在适当的语言限制下,更换表示方式不需要修改客户端代码。这是类型机制与模块化软件架构之间的一个核心联系。
递归类型描述的是其组成部分会引用同类结构的结构。递归类型与其展开形式之间的关系因语言而异:有些系统要求显式包装和解包,另一些则将二者视为等价。可变结构需要格外谨慎,因为其内容在构造后仍可能改变。构造器确立的不变式,只有在后续操作无法通过暴露的引用或不受控制的更新破坏它时,才有意义。
类型也会塑造应用程序编程接口。函数签名可以传达失败是否以结果值表示、参数是否可选,以及抽象句柄支持哪些操作。但仅凭函数签名,无法说明所有语义条件:排序函数通常具有从列表到列表的类型,而这一类型并未表明输出是有序的。因此,接口设计需要将可强制执行的类型区分,与针对所选类型语言无法表达的性质的规约结合起来。
多态、子类型与兼容性
多态使程序组件能够用于不止一种类型。多种机制都能提供这种能力,但各自带来的影响不同。参数多态对类型变量进行抽象:例如,一个函数可以具有类型 。特设多态针对不同类型选择不同的行为,重载的算术运算就是一例。子类型多态允许原本要求通用接口的组件接收更具体的实现。这些机制可以在同一种语言中共存。
参数多态支持对容器及其他结构编写可复用的操作,无须为每种元素类型分别提供实现。计算列表长度的函数不必知道元素是整数还是字符串。在满足适当纯性条件的语言中,类型为 的全函数,其行为受到极大限制:它无法凭空构造未知类型的任意值。这种一致性为称为“参数性”的推理原则提供了基础。不终止、异常、运行时类型检查等特性,则可能削弱仅凭类型就能得出的结论。
子类型关系通常写作 ,表示类型为 的值可以用在要求类型为 的值的地方。在结构化类型系统中,兼容性取决于类型的成员或结构。带有 name 和 age 字段的记录,可能可以用在只要求 name 字段的地方。在名义类型系统中,兼容性取决于具名类型之间显式声明的关系。即使不同类型的表示恰好相同,名义上的区分仍可保留它们在领域含义上的差异。
型变描述的是:将类型置于类型构造器中之后,兼容关系如何变化。当 时,只读的 生产者可能可以用作 生产者;这称为协变。消费者的方向则相反:能够消费任意 的对象也能消费 ,由此产生逆变。通常的函数子类型原则为
参数类型按逆变方向变化,而返回值类型按协变方向变化。
可变容器说明了这些区别为何重要。如果可以把猫的可变集合当作动物的可变集合来使用,那么从较宽泛的动物集合视角操作它的代码就可能向其中插入一只狗。随后,若仍按原先只包含猫的集合来读取,就会破坏这一假设。因此,这类容器通常是不变的。Java 则允许引用类型数组具有协变性,并在运行时检查不兼容的写入操作,这说明语言可以用动态检查来替代静态限制。
语言层面的兼容性也比完整的行为可替代性更有限。一个子类型可能提供了所有必需的方法,却以违背使用方预期的方式实现这些方法,例如不符合其对顺序、异常或状态变化的预期。常规类型检查通常验证的是签名和已声明的关系,而非所有行为法则。重载决议和泛型约束又引入了更多规则,因此,兼容性是整个语言设计的一项属性,而不是简单比较存储布局就能确定的。
类型检查、类型推断与计算极限
类型检查考察的是:在指定假设下,某个表达式是否符合给定类型。类型推断则尝试根据表达式及其上下文找出合适的类型。两者的区别是概念上的,而非绝对的:编译器可以推断局部变量的类型,根据类型标注检查函数签名,并求解将这两项活动联系起来的约束。类型推断减少了重复书写,但类型标注对于接口、诊断、文档,以及消除原本存在歧义的选择,仍然很有用。
一种常见的推断策略是先生成约束,再求解约束。对于函数应用 ,推断出的 的类型必须具有相容的参数类型和某个结果类型。如果一个变量用于整数加法,这种用法就会相应地约束其类型。在简单的系统中,未知类型用变量表示,而合一操作使类型表达式相等。因此,将函数应用于它自身的结果,可能会施加一些类型等式,由此得出一致的类型,或发现矛盾。
Hindley–Milner 类型系统将这种方法与受限的多态性结合起来。局部绑定可以对那些未被外围环境固定的类型变量进行泛化,从而产生类型方案。每次使用该绑定时,都会用新的类型变量对该方案进行实例化。因此,只需绑定一次的恒等函数,就可以同时应用于整数和布尔值。在这一基本系统中,可赋予类型的表达式具有主类型方案,其余类型方案都可以通过对它进行实例化得到。
可变状态使不受限制的泛化变得复杂。如果每次使用某个可变存储单元时,都将它视为可独立实例化的多态对象,那么一次使用可能向其中存入整数,而另一次使用却可能把同一份内容当作函数读取。因此,ML 家族语言会限制哪些绑定可以泛化,通常采用值限制或其改进形式。这说明了一个更普遍的原则:增加一项语言特性,可能会使原先可靠的推断规则失效,即便该特性看起来与类型无关。
表达能力更强的系统通常采用双向类型检查。一些表达式根据自身结构合成类型,另一些表达式则依据上下文提供的预期类型接受检查。函数参数的类型标注或预期的结果类型,可以帮助确定某些选择,否则就需要进行困难的推断。具有高秩多态、重载字面量、依赖类型或复杂子类型关系的语言,通常要求在关键位置提供类型标注,而不是尝试不受限制的类型重建。
检查本身的复杂度也是一项设计约束。尽管许多实际情形都能高效处理,简短的程序仍可能产生规模极大的推断类型,或求解代价高昂的约束问题。与基本 Hindley–Milner 系统的类型推断不同,System F 中不受限制的类型推断是不可判定的。更一般地,停机问题意味着,检查器不可能判定任意程序的所有重要语义性质。因此,语言实现需要在类型特性的表达能力与以下目标之间取得平衡:检查过程可预测、错误定位有用,以及程序演变过程中检查结果保持稳定。
依赖类型、精化类型与证明
依赖类型允许类型依赖于值。系统不必为所有数组赋予相同的元素容器类型,而是可以按长度区分向量,用 表示由 个 类型元素组成的向量。这样,拼接操作的类型就可以表达其结果长度等于输入长度之和:
在构造或使用该函数时,这一长度关系也就成为必须确立的条件之一。
这类系统使程序验证与日常编程更加紧密地结合。索引函数可以要求在提供索引的同时,附上该索引小于向量长度的证据。平衡树的实现可以在其构造器中附加结构不变量。由此得到的保证比简单容器类型所能提供的更强,但也带来了证明义务。自动推断并不总能找出所需的算术等式或证据变换。
精化类型提供了一种相关方法,即用谓词约束基础类型。例如,类型 描述的是正整数。函数可以要求除数的精化条件排除零,也可以返回一个受依赖于输入的界限约束的值。许多精化类型系统使用自动逻辑求解器来履行证明义务。为了使检查在计算上可行,它们通常会限制可用的谓词或推断形式,而不是在没有辅助的情况下接受任意数学命题。
柯里—霍华德对应将类型与命题、程序与证明联系起来。在一种基本解释下,积类型对应合取,和类型对应析取,函数类型对应蕴涵。从 的证明到 的证明的函数,构成了 的证明。表达能力更强的依赖积对应全称量化,而依赖对则可以将存在性断言及其见证一并表达出来。
这种联系是 Lean证明助手等证明助手以及其他基于构造性类型论的系统的基础。一个小型内核按照精确的规则检查证明项。精化器和自动化工具可以构造复杂的证明,但其结果要由内核验证。这种架构将寻找证明与检查证明区分开来,正如类型推断不同于检查给定的类型标注。
用于逻辑推理会带来一些普通编程语言不必满足的要求。如果不受限制的非终止计算能为每个类型提供一个项,那么将这些类型解释为命题就会破坏逻辑一致性。因此,面向证明的系统会对递归、终止性、宇宙以及其他可能导致不一致的因素加以控制。仅有依赖类型并不能保证一种语言构成可靠的逻辑。不过,在适当的逻辑基础之上,依赖类型能够支持形式验证,使可执行定义与正确性论证共用同一种形式语言。
效应、资源与实现
函数的输入和输出类型不一定能完整描述它所做的事情。两个类型均为 的函数可能有所不同:一个只计算长度,另一个则读取文件、修改全局状态或抛出异常。效应系统记录计算中除返回值之外的其他方面。例如,可以用如下判断形式表示:
其中, 描述状态访问、输入/输出等效应。语言可以利用这类信息限制效应出现的位置,并据此证明某些变换是合理的;如果可能存在隐含的交互,这些变换就可能不成立。
资源敏感的系统会跟踪值的使用方式。线性类型要求某些资源必须恰好使用一次;仿射类型规则则允许它们至多使用一次。这些思想适用于文件句柄、通信端点,以及那些无法安全复制的值。它们关注的是使用规则,而不一定要求物理上的唯一性:资源可以由一个小型句柄表示,而类型系统负责控制哪些操作可以消耗或转移该句柄。
所有权系统明确了资源的管理责任。Rust 将所有权转移、借用和生命周期约束结合起来,以控制内存访问。共享引用通常允许读取但不允许修改,而可变借用则施加独占性条件;受控的内部可变性机制还提供了其他使用模式。生命周期检查确保引用的存续时间不超过其所访问数据的存续时间。这些检查无需追踪式垃圾收集器,就能在安全代码中防止释放后使用以及许多数据竞争,但不能保证程序不会死锁或不存在任何逻辑错误。
其他专门的类型规则用于描述允许的操作顺序。会话类型可以规定,某个通信端点必须先发送请求,再接收响应,最后关闭。类型状态接口可以区分尚未打开的文件与已打开的文件,或尚未初始化的对象与已就绪的对象。这些系统将协议状态编码到类型中,从而在执行前阻止某些无效的状态转换。它们的实用性部分取决于能否在不引入过多记录和维护工作的情况下,表达实际的控制流和别名关系。
实现方式决定了类型检查完成后会保留什么。类型可以被擦除、保留以供反射使用,或转换成运行时描述符和字典参数。泛型函数可以编译为共享代码,也可以针对具体类型进行特化,后者通常称为单态化。特化可以改善数据表示并消除间接调用,但也可能增大代码体积。对于边界、类型转换、动态边界或未能静态证明的性质,运行时检查仍可能是必要的。
源语言具有类型系统,并不意味着后续的每个编译阶段都会自动安全。优化必须保留源语言的可观察行为;即使原始程序类型正确,变换过程也可能存在缺陷。带类型的中间表示有助于维护编译器内部的不变量;更强的方法则会验证变换本身,或要求提供证明证据。在部署边界处,序列化、外部代码和不可信输入仍需验证,因为外部数据不会仅仅因为被赋予某个声明类型,就获得语言层面的保证。