paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Observational equality: now for good

观察性相等:这次一劳永逸
POPL 6(POPL)2022匹配度 1/10 · 该论文属于纯依赖类型论与证明论研究,关注 observational equality、规范化与可判定性,未涉及 LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析,与用户核心研究方向几乎无交叉。引用 24 inbox
Loïc Pujet, Nicolas Tabareau
crossref: 2026-09-10

AI 速览

一句话:提出 TTobs,为依赖类型论中每个类型配备满足函数外延、命题外延和 UIP 的同一关系,并证明规范化、正则性与可判定性。

依赖类型论若加入函数外延、命题外延和 UIP 等原则,常会破坏归约与判定性。本文在带定义性证明无关类型宇宙的依赖类型论基础上,提出基于集合式(setoidal)解释的类型论 TTobs。它为每个类型配备同一关系,并满足函数外延、命题外延及定义性 UIP。相比已有方案,TTobs 的归约可规范化,并具有算法性正则性;作者利用 Abel 等人的逻辑关系框架在 Agda 中形式化证明。还给出转换与类型检查可判定性及一致性,并说明如何加入商类型,以及引入 Swan Id 类型的集合式版本,使其成为带归纳等式的 MLTT 扩展。

问题
如何为依赖类型论加入函数外延、命题外延与 UIP 等原则,同时保持归约可规范化、类型检查可判定并具有计算内容。
方法
基于定义性证明无关类型宇宙与集合式语义解释,构造类型论 TTobs,并借助 Abel 等人的逻辑关系框架在 Agda 中证明其元理论性质。
评估
证明转换与类型检查可判定、系统一致及算法性正则性;并展示商类型扩展和 Swan Id 类型的集合式版本,说明其是带归纳等式的 MLTT 的真扩展。
原文摘要(Abstract)

Building on the recent extension of dependent type theory with a universe of definitionally proof-irrelevant types, we introduce TTobs, a new type theory based on the setoidal interpretation of dependent type theory. TTobs equips every type with an identity relation that satisfies function extensionality, propositional extensionality, and definitional uniqueness of identity proofs (UIP). Compared to other existing proposals to enrich dependent type theory with these principles, our theory features a notion of reduction that is normalizing and provides an algorithmic canonicity result, which we formally prove in Agda using the logical relation framework of Abel et al. Our paper thoroughly develops the meta-theoretical properties of TTobs, such as the decidability of the conversion and of the type checking, as well as consistency. We also explain how to extend our theory with quotient types, and we introduce a setoidal version of Swan's Id types that turn it into a proper extension of MLTT with inductive equality.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot1537,
  title = {Observational equality: now for good},
  author = {Loïc Pujet and Nicolas Tabareau},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {6},
  number = {POPL},
  year = {2022},
  doi = {10.1145/3498693}
}