[科普中国]-依赖类型

在计算机科学和逻辑中，依赖类型（或依存类型，dependent type）是指依赖于值的类型，其理论同时包含了数学基础中的类型论和计算机编程中用以减少程序错误的类型系统两方面。在 Per Martin-Löf 的直觉类型论中，依赖类型可对应于谓词逻辑中的全称量词和存在量词；在依赖类型函数式编程语言如 ATS、Agda、Dependent ML、Epigram、F* 和 Idris 中，依赖类型系统通过极其丰富的类型表达能力使得程序规范得以借助类型的形式被检查，从而有效减少程序错误。

简介依赖类型1的两个常见实例是依赖函数类型（又称依赖乘积类型、Π-类型）和依赖值对类型（又称依赖总和类型、Σ-类型）。一个依赖类型函数的返回值类型可以依赖于某个参数的具体值，而非仅仅参数的类型，例如，一个输入参数为整型值n的函数可能返回一个长度为n的数组；一个依赖类型值对中的第二个值可以依赖于第一个值，例如，依赖类型可表示这样的类型：它由一对整数组成，其中的第二个数总是大于第一个数。

依赖类型增加了类型系统的复杂度。由于确定两个依赖于值的类型的等价性需要涉及具体的计算，若允许在依赖类型中使用任意值的话，其类型检查将会成为不可判定问题；换言之，无法确保程序的类型检查一定会停机。

由于Curry-Howard同构揭示了程序语言的类型论与证明论的直觉逻辑之间的紧密关联性，以依赖类型系统为基础的编程语言大多同时也作为构造证明与可验证程序的辅助工具而存在，如 Coq 和 Agda（但并非所有证明辅助工具都以类型论为基础）；近年来，一些以通用和系统编程为目的的编程语言被设计出来，如 Idris。

一些以证明辅助为主要目的的编程语言采用强函数式编程（total functional programming），这消除了停机问题，同时也意味着通过它们自身的核心语言无法实现任意无限递归，不是图灵完全的，如 Coq 和 Agda；另外一些依赖类型编程语言则是图灵完全的，如 Idris、由ML派生而来的 ATS 和 由F#派生而来的 F*。

Lambda 立方Henk Barendregt 提出了 Lambda 立方模型，用于对不同的类型系统的表达能力加以区分。Lambda 立方的八个顶点分别对应各自的类型系统，简单类型lambda演算位于表达能力最低的顶点上，而构造演算（calculus of constructions）则位于表达能力最强的顶点上。

一阶依赖类型一阶依赖类型 ，对应于逻辑框架LF，是通过把简单类型lambda演算的函数空间一般化为依赖乘积类型而获得的。

二阶依赖类型二阶依赖类型 ，通过允许对 类型构造子的量化得到。此时，依赖乘积类型涵括了简单类型lambda演算中的 与System F中的 。

高阶依赖类型多态 lambda 演算高阶类型系统 扩充了 ，使之支持 Lambda 立方中的全部四种表达形式：从项到项的函数、从类型到类型的函数、从项到类型的函数、以及从类型到项的函数。这对应于构造演算（calculus of constructions），而构造演算则是证明辅助器Coq所基于的构造归纳演算（calculus of inductive constructions）理论的基础。

本词条内容贡献者为:

王慧维 - 副研究员 - 西南大学