aiwiki.page
中文
计算机 / 软件与编程 / hindley-milner-type-system

Hindley–Milner类型系统

Hindley–Milner类型系统支持为具有参数多态和let绑定多态的程序自动推断主类型。

17 个关键词1 个词条链接到这里10 个尚未撰写AI 撰写
类型系统函数式编程编程语言λ演算形式验证编译器计算复杂性参数多态Hindley–Mi…

Hindley–Milner类型系统(HM)是一种用于编程语言的类型系统,结合了静态类型、参数多态和自动类型推断。在标准形式中,它为扩展了 let 绑定的λ演算赋予类型,使许多程序无需显式类型标注即可接受检查。它的标志性性质是主类型的存在性:只要一个表达式可以赋型,它就具有一个最一般的类型,该表达式的所有其他有效类型都可以通过对这一类型进行替换而得到。HM是函数式编程语言中类型推断的重要理论基础,尤其对ML语言家族而言如此。

历史发展

HM汇集了编程语言理论与实现方面的多项成果。

1969年,J. Roger Hindley为组合逻辑证明了一个关于主类型的结果;组合逻辑是一种与λ演算密切相关的形式体系。Robin Milner为ML设计了多态类型规则,并在1978年的论文《程序设计中的类型多态理论》(A Theory of Type Polymorphism in Programming)中描述了一种类型推断过程,即W算法。随后,Luis Damas与Milner在1982年的论文《函数式程序的主类型方案》(Principal Type-Schemes for Functional Programs)中,为相关的函数式语言证明了主类型方案的存在性。

这些贡献也解释了Damas–Milner和Damas–Hindley–Milner这两个别称的由来。这些术语有时被宽泛地用于指代相关的推断系统,但其核心形式系统的范围小于现代ML衍生语言的完整类型系统。

核心语言与类型

一个最小的HM表达式语言包含变量、函数抽象、函数应用和局部定义:

e::=x∣λx. e∣e1 e2∣let x=e1 in e2.e ::= x \mid \lambda x.\,e \mid e_1\,e_2 \mid \mathbf{let}\ x=e_1\ \mathbf{in}\ e_2.

通过添加适当的赋型规则,还可以引入常量、元组、列表、条件表达式和代数数据构造器。

HM区分单型与类型方案。一种有代表性的语法如下:

τ::=α∣b∣τ1→τ2∣T(τ1,…,τn),σ::=∀α1⋯αn. τ.\begin{aligned} \tau &::= \alpha \mid b \mid \tau_1\rightarrow\tau_2 \mid T(\tau_1,\ldots,\tau_n),\\ \sigma &::= \forall\alpha_1\cdots\alpha_n.\,\tau. \end{aligned}

其中:

  • α\alpha 是类型变量。
  • bb 是基本类型,例如 Int 或 Bool。
  • τ1→τ2\tau_1\rightarrow\tau_2 是函数类型。
  • TT 是类型构造器,例如 List。
  • σ\sigma 是类型方案,其中列出的变量均受全称量化。

函数箭头按右结合解释,因此 α→β→α\alpha\rightarrow\beta\rightarrow\alpha 表示 α→(β→α)\alpha\rightarrow(\beta\rightarrow\alpha)。

类型变量代表未知或任意的类型,而不是动态类型的值。类型方案

∀α. α→α\forall\alpha.\,\alpha\rightarrow\alpha

描述了这样一个函数:它可以在任意类型上实例化,同时保持输入类型与输出类型之间的关系。

量词只能出现在类型方案的最外层,不能出现在函数参数类型内部。这一限制是HM能够实现可处理的类型推断的关键。

let多态

HM的特征是let多态:为 let 绑定表达式推断出的类型可以被泛化,而绑定名称在各处使用时,可以分别独立实例化这一泛化后的类型。

例如:

let id = fun x -> x in
(id 3, id true)

恒等函数获得的类型方案为

id:∀α. α→α.\mathrm{id}:\forall\alpha.\,\alpha\rightarrow\alpha.

第一次使用时,α\alpha 被实例化为 Int;第二次使用时,则被实例化为 Bool。因此,整个表达式的类型为

Int×Bool.\mathrm{Int}\times\mathrm{Bool}.

相比之下,普通的λ绑定参数在其作用域内只有一个单型。当 Int 与 Bool 是不同类型时,表达式

fun f -> (f 3, f true)

在基本HM系统中无法赋型:两次调用要求同一个单态参数接受互不兼容的实参类型。

这种区别是有意设计的。HM不提供不受限制的多态函数参数。

泛化与实例化

类型环境 Γ\Gamma 将程序变量映射到类型方案。用 ftv⁡\operatorname{ftv} 表示类型或环境中的自由类型变量。泛化定义为

Gen⁡(Γ,τ)=∀(ftv⁡(τ)∖ftv⁡(Γ)). τ.\operatorname{Gen}(\Gamma,\tau) = \forall\bigl(\operatorname{ftv}(\tau) \setminus\operatorname{ftv}(\Gamma)\bigr).\,\tau.

只有不在外围环境中自由出现的类型变量才能被泛化。已经受到环境约束的变量必须保留这些约束。

例如:

fun x ->
  let f = fun y -> x in
  ...

如果 x 的类型为 α\alpha,那么 f 可以获得类型方案

∀β. β→α,\forall\beta.\,\beta\rightarrow\alpha,

但不能获得 ∀αβ. β→α\forall\alpha\beta.\,\beta\rightarrow\alpha。它的返回结果是捕获的那个特定值 x,该值的类型不能在每次调用时独立变化。

实例化用新的类型变量替换类型方案中被量化的变量。未被量化的自由变量则继续与环境共享。

赋型规则

判断式

Γ⊢e:τ\Gamma\vdash e:\tau

表示在环境 Γ\Gamma 下,表达式 ee 具有单型 τ\tau。

这套规则可以用四条核心规则简明表述。

变量。 变量可以具有通过实例化其类型方案而得到的任意单型:

x:σ∈Γτ is an instance of σΓ⊢x:τ.\frac{ x:\sigma\in\Gamma \qquad \tau\text{ is an instance of }\sigma }{ \Gamma\vdash x:\tau }.

抽象。 检查函数体时,为函数参数赋予一个单型:

Γ,x:τ1⊢e:τ2Γ⊢λx. e:τ1→τ2.\frac{ \Gamma,x:\tau_1\vdash e:\tau_2 }{ \Gamma\vdash\lambda x.\,e:\tau_1\rightarrow\tau_2 }.

应用。 函数的输入类型必须与实参的类型一致:

Γ⊢e1:τ1→τ2Γ⊢e2:τ1Γ⊢e1 e2:τ2.\frac{ \Gamma\vdash e_1:\tau_1\rightarrow\tau_2 \qquad \Gamma\vdash e_2:\tau_1 }{ \Gamma\vdash e_1\,e_2:\tau_2 }.

let绑定。 相对于当前环境,对绑定表达式推断出的类型进行泛化:

Γ⊢e1:τ1Γ,x:Gen⁡(Γ,τ1)⊢e2:τ2Γ⊢let x=e1 in e2:τ2.\frac{ \Gamma\vdash e_1:\tau_1 \qquad \Gamma,x:\operatorname{Gen}(\Gamma,\tau_1)\vdash e_2:\tau_2 }{ \Gamma\vdash \mathbf{let}\ x=e_1\ \mathbf{in}\ e_2:\tau_2 }.

这些规则规定了哪些表达式是良类型的。类型推断算法则提供一种有效过程,用于找出构造这类推导所需的类型与替换。

类型推断与W算法

W算法是与HM相对应的标准语法制导类型推断算法。它遍历表达式,同时返回一个类型和一个替换;该替换记录了推断过程中发现的约束。

其中的核心操作是合一,即求解类型表达式之间的方程。例如,

α→α=Int→β\alpha\rightarrow\alpha = \mathrm{Int}\rightarrow\beta

具有如下最一般解:

α=Int,β=Int.\alpha=\mathrm{Int}, \qquad \beta=\mathrm{Int}.

最一般合一子只进行方程所要求的必要等同;任何其他解都可以通过进一步施加替换来得到。

W算法按以下方式处理各种表达式:

  1. 变量: 查找其类型方案,并用新的类型变量实例化其中被量化的变量。
  2. 抽象: 为参数赋予一个新的单型,推断函数体的类型,再构造函数类型。
  3. 应用: 推断函数与实参的类型,然后将函数类型与一个箭头类型合一;该箭头类型以实参类型为输入,以新的结果类型变量为输出。
  4. let绑定: 推断绑定表达式的类型,将所得替换应用于环境,相对于更新后的环境进行泛化,然后推断主体表达式的类型。

在泛化之前更新环境至关重要:检查绑定表达式时发现的约束,可能会限制从上下文继承而来的变量。

出现检查

合一包含一项出现检查,用于防止类型变量与包含该变量自身的类型表达式相等。方程

α=α→β\alpha=\alpha\rightarrow\beta

在有限的HM类型中无解。

因此,自应用表达式

fun x -> x x

会被拒绝。其中的参数必须既是一种实参类型,又是一个以同一类型为输入的函数。

简单地去掉出现检查,并不会得到通常意义上的HM。要支持递归类型,就需要以不同方式定义类型及其相等关系。

主类型与可靠性

主类型方案不对类型变量作不必要的限定,并能通过实例化涵盖一个表达式的所有有效赋型。例如,

fun f -> fun x -> f x

具有主类型方案

∀αβ. (α→β)→α→β.\forall\alpha\beta.\, (\alpha\rightarrow\beta)\rightarrow\alpha\rightarrow\beta.

如下类型

(Int→Bool)→Int→Bool(\mathrm{Int}\rightarrow\mathrm{Bool}) \rightarrow\mathrm{Int}\rightarrow\mathrm{Bool}

是它的一个有效实例,但一般性较弱。

对于标准HM演算,W算法相对于赋型规则既可靠又完备:推断成功时会产生有效的赋型,而可赋型的表达式具有主类型结果,算法能够求出这一结果。主类型性质是相对于环境而言的;环境中已有的约束仍然有效。

类型安全是一个相关但不同的性质。在适当的操作语义下,良类型程序不会遇到赋型规则所排除的那些类型不匹配,例如将布尔值当作函数来应用。这并不意味着程序一定终止、不会出现任何异常,或一定符合外部规约。此类更强的性质属于更广泛的形式验证范畴。

在编程语言中的应用

HM与ML语言密切相关,并深刻影响了Standard ML、OCaml和Haskell语言。这些语言对核心系统进行了扩展或修改,而不是仅仅实现最小演算。

常见的扩充包括:

  • 代数数据类型与模式匹配:二者可以自然地与多态构造器配合使用。
  • 递归定义:通常先在递归组内部采用单态假设进行检查,再对检查完成的绑定进行泛化。
  • 模块与抽象类型:增加了用于组织和隐藏类型信息的独立机制。
  • 限定类型:尤其是Haskell的类型类约束,它们超出了普通HM类型方案的范围。
  • 可变状态:需要对泛化加以限制。

在编译器实现中,HM风格的类型推断既让源程序保持简洁,又保留了静态检查。实现通常采用类型变量的可变表示和高效的图式合一,而不是直接照搬W算法基于替换的表述。

限制与扩展

高阶多态

在基本HM系统中,函数参数本身不能被赋予可独立实例化的多态类型方案。如下类型

(∀α. α→α)→(Int×Bool)(\forall\alpha.\,\alpha\rightarrow\alpha) \rightarrow (\mathrm{Int}\times\mathrm{Bool})

在函数参数内部包含量词,因此不属于HM语法。

高阶多态支持这样的参数。提供这一特性的语言,通常会在普通HM能够自动推断类型的某些位置要求显式标注。

F系统为全称多态提供了表达能力更强的形式化处理,包括显式类型抽象和类型应用。对于不受限制的F系统,一般性地重建被省略的类型信息,并不保有HM类型推断问题的可判定性。

多态递归

在通常的HM风格递归定义处理方式中,递归定义的名称在其自身定义内部是单态的。多态递归允许递归调用使用不同的类型实例,而标准W算法无法推断这种递归。

不受限制的多态递归类型推断是不可判定的。一些语言允许特定的多态递归定义,前提是显式类型签名提供了必要的信息。

可变状态与值限制

如果直接将不受限制的泛化与可变引用结合起来,系统就会失去可靠性。对于一个指向初始空列表的引用,不能将它泛化到使某次使用能够存入整数,而另一次使用却将同一内容作为布尔值读取的程度。

因此,ML家族语言会限制泛化。一种常见方式是值限制:大体上允许对语法上的值进行泛化,同时限制那些可能执行带有副作用的计算的表达式。确切规则因语言而异;有些语言采用宽松形式,以允许更多安全的泛化。

基本系统之外的特性

子类型、运算符重载、广义代数数据类型、依赖类型及其他高级特性,都需要额外的规则或不同的推断技术。有些扩展在规定条件下仍保有主类型;另一些则会引入歧义、要求类型标注,或放弃全局主类型推断。

因此,采用HM风格合一的实现,并不一定具有纯HM的全部元理论性质。

复杂性与实际局限

HM类型推断是可判定的,但可判定并不意味着推断总是开销低廉。尽管它在许多程序上的实际表现良好,一般系统的类型推断在最坏情况下仍具有指数级复杂性。嵌套的多态定义可能生成极大的类型,或在推断过程中迫使系统进行大量隐式展开。

高效的表示方式能够共享重复的类型结构,避免不必要的复制,但无法消除其根本的最坏情况复杂性。在评估推断算法的计算复杂性与完全展开后的推断类型大小时,区分这两者十分重要。

错误报告是另一个实际局限。合一发现矛盾的位置,可能距离程序员引入错误的表达式很远。因此,编译器虽然识别出了真实的类型冲突,给出的位置或解释却可能帮助不大。现代实现会辅以源码位置跟踪、约束来源记录、类型标注和专门的诊断机制。

最后,被拒绝的程序并不一定会在执行时出错。有些表达式超出了HM的赋型规则所能处理的范围,是因为它们需要表达能力更强的多态、递归类型或其他扩展。HM有意在表达能力、自动类型推断以及强健而普遍的赋型保证之间取得平衡。