Skip to content

依赖函数类型

Dependent function type · Pi type · Π-type

让函数结果类型随实参变化,并以逐点构造和依赖应用给出其规则的 Π 类型。

条目类型
定义

形式陈述

在语境 Γ 中,若 A 是类型且 B 是以 x:A 为参数的类型族,依赖类型的 Π-formation 规则为

ΓAtypeΓ,x:ABtypeΓΠ(x:A).Btype.

引入规则把语境中的构造逐点抽象;消去规则把函数用于实参,并在余类型中实行同一次代入:

Γ,x:Ab:BΓλx.b:Π(x:A).B,Γf:Π(x:A).BΓa:AΓfa:B[a/x].

标准计算规则是判断式 β-等式

(λx.b)ab[a/x]:B[a/x].

有些理论还采用函数 η 规则 fλx.fx,前提是 xf 新鲜;另一些理论只证明命题式函数外延性,或根本不接受 η 为判断相等,因此定义 Π 类型时必须列明这一选择。替换稳定性要求若 σ:ΔΓ 是良型替换,则 (Π(x:A).B)[σ]Π(x:A[σ]).B[σ+] 按定义相等,其中 σ+ 把替换提升到扩张语境。

x 不自由出现于 B,Π 类型退化为非依赖函数类型 AB。这是规则的边界特例:应用后的结果类型恰好不发生可见变化,并不意味着每个普通函数都暗中携带有信息量的索引证明。

直觉

普通函数只保证“输入属于 A,输出属于固定的 B”;Π 类型把许多不同的输出类型 B(a) 绑成一个逐点选择。拥有 f:Π(x:A).B(x),就意味着对每个具体 a 都能产出恰好属于那一纤维 B(a) 的结果。输入不仅参与计算,也参与说明结果应落在哪里。

在命题解释下,Π(x:A).B(x) 对应“对每个 x:AB(x) 成立”,而 λ 抽象把含任意 x 的证明封装为全称证明。这是Curry–Howard 对应层面的规则同构,不是把一个运行时函数与一阶逻辑公式宣称为无条件的对象等价;擦除、证明无关性与计算语义仍取决于具体系统。

例子与边界

Vec(A,n) 为长度为 n 的向量族。保持长度的恒等程序具有类型

keep:Π(n:N).Vec(A,n)Vec(A,n),keep=λn.λv.v.

v2:Vec(A,2),第一次应用把 n 代为 2,所以

keep2:Vec(A,2)Vec(A,2),

第二次应用再由 β-计算给出 keep2v2v2。若误把参数写成 v3:Vec(A,3),失败发生在第二次应用的前提判断,而不是等到函数体访问越界元素。与“把长度存在一个整数栏位里”的记录相比,索引替换直接决定调用后的静态类型。

Π 类型本身不会自动比较任意两个函数。点态给出 Πx.f(x)=g(x) 通常只能得到恒等类型中的函数相等,且需要函数外延性;它不必成为判断相等 fg。若允许 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。
关系图谱9 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系

被这些条目使用