“检查一个函数 $f:\Pi(n:\mathbb N).\mathsf{Vec}(A,n)\to C(n)$ 时,匹配 会产生约束 $n\equiv0$,匹配 会产生 $n\equiv\mat…”
形式陈述 ​
定义相等是类型论的判断族,常写为
它通常包含反身、对称、传递、各语法构造的同余,以及选定的计算规则。函数的β-计算给出
归纳类型消去子遇到构造器时有相应 ι-rule;局部定义展开可形成 δ-rule,let 代入可形成 ζ-rule。是否把函数或记录 η、递归定义展开、证明擦除列入
因此它直接参与类型判断,并须满足代入与主体归约:若判断成立,施加良型替换后仍成立;若良型项计算一步,其类型不会改变。声明式
恒等类型
直觉
定义相等描述内核愿意“视为同一个程序”的表达式。它像编译器在核对接口前进行的透明计算:函数刚应用就代入,递归子刚遇到构造器就展开,类型中的算术也按同样规则化简。用户无需提交一份等式证书,因为这次识别属于判断过程自身。
把它限制在受控计算上非常重要。若每个数学上可证明的等式都自动进入转换,类型检查器为了判断一个函数调用是否合法,就可能被迫搜索任意证明。内涵理论把较大的相等空间留给恒等类型,只让稳定、可计算的一部分成为定义相等,从而在表达力与可判定内核之间划界。
例子与边界
设自然数加法按第一个参数递归:
若
定义相等也受透明度控制。若常量
推论与应用
定义相等让类型中的计算无需显式改写,支撑依赖函数应用、索引归纳和模块透明展开。实现通常先比较类型头部:遇到 Π、Σ 或构造器便结构递归,遇到中立项则比较头变量与 spine;需要时才继续求值,避免先完全正规化所有表达式。正确性要求算法接受恰好声明规则生成的等同,且不把运行时副作用或不终止计算带进内核转换。
在元理论中,定义相等的规范形唯一性可推出类型构造器的可辨识性,例如若两个 Π 类型定义相等,则其定义域与适当余类型也相等;这些引理又服务于类型检查可靠性。它还影响库设计:把定律做成判断计算可改善化简与执行,把定律只做成恒等证明则保持较小内核。两种选择没有通用优胜者,必须按正规化、可判定性和用户可见计算行为共同评估。
参考资料
- Per Martin-Löf, Intuitionistic Type Theory, Bibliopolis, 1984,judgmental equality、conversion 与 computation rules。
- Bengt Nordström, Kent Petersson, and Jan M. Smith, Programming in Martin-Löf’s Type Theory, Oxford University Press, 1990,equality judgments、evaluation 与类型检查。
- Andreas Abel, Thierry Coquand, and Peter Dybjer, “Normalization by Evaluation for Martin-Löf Type Theory with Typed Equality Judgements,” LICS 2007, pp. 3–12,typed conversion 的规范化与可判定性。