形式陈述
在语境 Γ 中,若 A 是类型且 B 是以 x : A 为参数的类型族,依赖类型 公理库 依赖类型 Dependent type 类型表达式可依赖项值的类型系统构造。 的 Π-formation 规则为
Γ ⊢ A type Γ , x : A ⊢ B type Γ ⊢ Π ( x : A ) . B type . 引入规则把语境中的构造逐点抽象;消去规则把函数用于实参,并在余类型中实行同一次代入:
Γ , x : A ⊢ b : B Γ ⊢ λ x . b : Π ( x : A ) . B , Γ ⊢ f : Π ( x : A ) . B Γ ⊢ a : A Γ ⊢ f a : B [ a / x ] . 标准计算规则是判断式 β-等式
( λ x . b ) a ≡ b [ a / x ] : B [ a / x ] . 有些理论还采用函数 η 规则 f ≡ λ x . f x ,前提是 x 对 f 新鲜;另一些理论只证明命题式函数外延性,或根本不接受 η 为判断相等,因此定义 Π 类型时必须列明这一选择。替换稳定性要求若 σ : Δ → Γ 是良型替换,则 ( Π ( x : A ) . B ) [ σ ] 与 Π ( x : A [ σ ] ) . B [ σ + ] 按定义相等,其中 σ + 把替换提升到扩张语境。
若 x 不自由出现于 B ,Π 类型退化为非依赖函数类型 A → B 。这是规则的边界特例:应用后的结果类型恰好不发生可见变化,并不意味着每个普通函数都暗中携带有信息量的索引证明。
直觉
普通函数只保证“输入属于 A ,输出属于固定的 B ”;Π 类型把许多不同的输出类型 B ( a ) 绑成一个逐点选择。拥有 f : Π ( x : A ) . B ( x ) ,就意味着对每个具体 a 都能产出恰好属于那一纤维 B ( a ) 的结果。输入不仅参与计算,也参与说明结果应落在哪里。
在命题解释下,Π ( x : A ) . B ( x ) 对应“对每个 x : A ,B ( x ) 成立”,而 λ 抽象把含任意 x 的证明封装为全称证明。这是Curry–Howard 对应 公理库 Curry–Howard 对应 Curry–Howard correspondence · Propositions as types 把命题对应为类型、证明对应为程序、证明化简对应为程序求值。 层面的规则同构,不是把一个运行时函数与一阶逻辑公式宣称为无条件的对象等价;擦除、证明无关性与计算语义仍取决于具体系统。
例子与边界
令 Vec ( A , n ) 为长度为 n 的向量族。保持长度的恒等程序具有类型
keep : Π ( n : N ) . Vec ( A , n ) → Vec ( A , n ) , keep = λ n . λ v . v . 若 v 2 : Vec ( A , 2 ) ,第一次应用把 n 代为 2 ,所以
keep 2 : Vec ( A , 2 ) → Vec ( A , 2 ) , 第二次应用再由 β-计算给出 keep 2 v 2 ≡ v 2 。若误把参数写成 v 3 : Vec ( A , 3 ) ,失败发生在第二次应用的前提判断,而不是等到函数体访问越界元素。与“把长度存在一个整数栏位里”的记录相比,索引替换直接决定调用后的静态类型。
Π 类型本身不会自动比较任意两个函数。点态给出 Π x . f ( x ) = g ( x ) 通常只能得到恒等类型中的函数相等,且需要函数外延性;它不必成为判断相等 f ≡ g 。若允许 B ( x ) 含有不终止计算,甚至判断 B ( a ) 与另一个类型可转换都可能不可判定。空定义域上的 Π 类型在逻辑上可居留,也不能据此推出程序已枚举某个运行时集合:构造它只需在假设 x : A 下给出分支。
推论与应用
Π 类型统一表达带索引 API、隐式参数、泛化定理和证明携带函数。例如安全数组索引可取 i : Fin ( n ) ,返回 A ;矩阵转置可写成 Π ( m , n ) . Mat ( A , m , n ) → Mat ( A , n , m ) ,让维度交换出现在余类型而非文档注释。定理证明中,假设引入与全称引入都由 λ 完成,实例化则由应用完成。
实现上,检查 λ 往往利用期望的 Π 类型,而检查应用先综合函数类型、再核对实参并把实参代入余类型。隐式参数与 metavariable 只改变表面信息如何补全,不改变核心规则中的代入义务。类型检查器若用规范形判定余类型相等,还必须证明该转换过程对所选 Π、η 与宇宙规则可靠且终止。
参考资料
Per Martin-Löf, Intuitionistic Type Theory , Bibliopolis, 1984,dependent function formation、application 与 computation rules。
Bengt Nordström, Kent Petersson, and Jan M. Smith, Programming in Martin-Löf’s Type Theory , Oxford University Press, 1990,function sets 与依赖程序构造。
The Univalent Foundations Program, Homotopy Type Theory: Univalent Foundations of Mathematics , Institute for Advanced Study, 2013,§1.4,dependent function types。