paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Canonicity for Indexed Inductive-Recursive Types

索引归纳-递归(IIR)类型的典范性
POPL 10(POPL)2026匹配度 2/10 · 该论文属于纯类型论与形式语义,研究索引归纳-递归类型的典范性,与用户关注的静态分析、LLM/Agent、浮点程序分析及贝叶斯程序分析等方向没有直接关联。引用 2 inbox
András Kovács
crossref: 2026-09-10

AI 速览

一句话:为支持可数宇宙层级与索引归纳-递归(IIR)类型的 Martin-Löf 类型论证明典范性,并给出将 IIR 归约到 IR 的构造。

本文为带有可数宇宙层级、且每个宇宙都支持索引归纳-递归(IIR)类型的 Martin-Löf 类型论证明 canonicity。作者分两步进行:首先利用归纳-递归(IR)类型及其他基本类型构造子构造 IIR 类型,使后续证明更简单,并说明所构造的 IIR 类型支持与 Agda 原生 IIR 实现相同的定义计算规则;其次,基于沿全局截面函子(global sections functor)的 gluing 方法,给出 IR 类型的 canonicity 证明。核心思想是用元理论中的 IIR 类型编码每个 IR 类型的 canonicity 谓词。该工作将 IIR 的 canonicity 问题归约到 IR,并扩展了 gluing 方法在依赖类型论元理论中的应用。

问题
研究带可数宇宙层级并支持索引归纳-递归(IIR)类型的 Martin-Löf 类型论是否具有 canonicity(典范性)。
方法
先将 IIR 类型由 IR 类型和基本类型构造子构造出来,再用沿全局截面函子的 gluing 方法证明 IR 类型的 canonicity;关键是用元理论中的 IIR 类型编码 canonicity 谓词。
评估
通过构造性元理论证明完成,展示所构造 IIR 类型与 Agda 原生实现具有相同定义计算规则,从而得到目标理论的 canonicity。
原文摘要(Abstract)

We prove canonicity for a Martin-Löf type theory with a countable universe hierarchy where each universe supports indexed inductive-recursive (IIR) types. We proceed in two steps. First, we construct IIR types from inductive-recursive (IR) types and other basic type formers, in order to simplify the subsequent canonicity proof. The constructed IIR types support the same definitional computation rules that are available in Agda’s native IIR implementation. Second, we give a canonicity proof for IR types, building on the established method of gluing along the global sections functor. The main idea is to encode the canonicity predicate for each IR type using a metatheoretic IIR type.

链接与引用

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

BibTeX
@article{Kovacs26,
  title = {Canonicity for Indexed Inductive-Recursive Types},
  author = {András Kovács},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {10},
  number = {POPL},
  year = {2026},
  doi = {10.1145/3776685}
}