“空语境良构;若 $\Gamma;\mathsf{ctx}$ 且 $\Gamma\vdash A;\mathsf{type}$,便可扩张为 $\Gamma,x:A;\mathsf{ctx}$。…”
形式陈述
在语境
引入规则把语境中的构造逐点抽象;消去规则把函数用于实参,并在余类型中实行同一次代入:
标准计算规则是判断式 β-等式
有些理论还采用判断式函数 η 规则
若
直觉
普通函数只保证“输入属于
在命题解释下,
例子与边界
令
若
第二次应用再由 β-计算给出
Π 类型本身不会自动比较任意两个函数。点态给出
推论与应用
Π 类型统一表达带索引 API、隐式参数、泛化定理和证明携带函数。例如安全数组索引可取
实现上,检查 λ 往往利用期望的 Π 类型,而检查应用先综合函数类型、再核对实参并把实参代入余类型。隐式参数与 metavariable 只改变表面信息如何补全,不改变核心规则中的代入义务。类型检查器若用规范形判定余类型相等,还必须证明该转换过程对所选 Π、η 与宇宙规则可靠且终止。
显式向量连接核心把这一应用义务落实到每个参数:先传元素类型与长度,再核对向量,最终用自然数消去子的计算规则验证余类型。其分层宇宙、motive和所有λ参数注解都已写出。
参考资料
- 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。