paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A Type Theory for Defining Logics and Proofs

定义逻辑与证明的类型理论
LICS 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2019匹配度 2/10 · 该论文属于纯类型论与逻辑框架的基础研究,核心是 Cocon、HOAS、Kripke 模型和规范化证明,不涉及 LLM/Agent、ML/Agentic 程序静态分析、浮点程序分析或贝叶斯程序分析等用户核心方向,仅在形式化验证与 PL 理论大背景上有微弱交叉。引用 0 inbox
Brigitte Pientka, David Thibodeau, Andreas Abel, Francisco Ferreira, Rebecca Zucchini
crossref: 2026-09-12

AI 速览

一句话:提出依赖类型理论 Cocon,融合 HOAS 与可计算函数空间,并用 Kripke 模型证明规范化与一致性。

论文提出 Martin-Löf 风格的依赖类型理论 Cocon,目标是在逻辑框架中把用于表示高阶抽象语法(HOAS)的内涵函数空间与描述递归计算的外延函数空间结合起来。Cocon 借助上下文模态类型在 HOAS 表示与计算之间进行中介,并支持无限宇宙层级,从而提供类型级计算、元编程和小规模反射。作者的核心贡献是为 Cocon 构造 Kripke 风格语义模型并证明规范化;由该证明进一步推出主体归约(subject reduction)与一致性。该工作为将逻辑框架方法融入 Agda 等系统、弥合逻辑框架与依赖类型编程语言之间的鸿沟奠定了基础。

问题
如何在依赖类型理论中同时支持用于 HOAS 的内涵函数空间与用于递归计算的外延函数空间,并为该理论建立规范化、主体归约和一致性等元理论保证。
方法
定义 Martin-Löf 风格依赖类型理论 Cocon,引入上下文模态类型来连接 HOAS 表示与计算,并支持无限宇宙层级与类型级计算;进而构造 Kripke 风格语义模型。
评估
通过 Kripke 风格模型证明 Cocon 的规范化,并由规范化证明推导主体归约与一致性;属于理论证明评估,未涉及实现或实验基准。
原文摘要(Abstract)

We describe a Martin-Lof-style dependent type theory, called Cocon, that allows us to mix the intensional function space that is used to represent higher-order abstract syntax (HOAS) trees with the extensional function space that describes (recursive) computations. We mediate between HOAS representations and computations using contextual modal types. Our type theory also supports an infinite hierarchy of universes and hence supports type-level computation thereby providing metaprogramming and (small-scale) reflection. Our main contribution is the development of a Kripke-style model for Cocon that allows us to prove normalization. From the normalization proof, we derive subject reduction and consistency. Our work lays the foundation to incorporate the methodology of logical frameworks into systems such as Agda and bridges the longstanding gap between these two worlds.

链接与引用

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

BibTeX
@inproceedings{paperbot4973,
  title = {A Type Theory for Defining Logics and Proofs},
  author = {Brigitte Pientka and David Thibodeau and Andreas Abel and Francisco Ferreira and Rebecca Zucchini},
  booktitle = {LICS},
  year = {2019},
  doi = {10.1109/lics.2019.8785683}
}