paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A Modal Deconstruction of Löb Induction

Löb 归纳的模态解构
POPL 9(POPL)2025匹配度 1/10 · 该论文属于模态类型论与 guarded recursion/Löb 归纳的理论研究,与用户关注的 LLM/Agent 增强静态分析、浮点程序分析或贝叶斯程序分析均无直接交叉。虽属程序语言理论,但未涉及 AI、静态分析工具或工业落地,因此匹配度很低。引用 0 inbox
Daniel Gratzer
crossref: 2026-09-10

AI 速览

一句话:用模态类型论分解 Löb 归纳,提出捕获 topos of trees 模态结构且不排除 canonicity/normalization 的 guarded 类型论 Gatsby。

本文重新分析 guarded recursion 中的基本 Löb 归纳原理。既有方法通常将 Löb 归纳作为核心原语,本文则借助模态类型论与 univalent foundations 的近期进展,从一组更简单、概念上更清晰的原语推导出它。基于这一洞察,作者提出 Gatsby:首个在捕获 topos of trees 丰富模态结构的同时支持 Löb 归纳,且不直接排除 canonicity 或 normalization 的 guarded 类型论。作者表明 Gatsby 能恢复许多既有 guarded recursion 方法,并利用其额外表达力改进先前例子。该工作关键依赖同伦论洞察,也是 univalent foundations 在程序语言理论中的新应用。

问题
如何理解并推导 guarded recursion 中的基本 Löb 归纳原理,以及如何构造同时捕获 topos of trees 模态结构、支持 Löb 归纳且不排除 canonicity/normalization 的 guarded 类型论。
方法
借助模态类型论与 univalent foundations,对 Löb 归纳进行模态解构,从更简单、更概念化的原语推出它,并据此设计 guarded 类型论 Gatsby。
评估
展示 Gatsby 能恢复多种既有 guarded recursion 方法并改进先前例子;其类型论设计不直接排除 canonicity 或 normalization。
原文摘要(Abstract)

We present a novel analysis of the fundamental Löb induction principle from guarded recursion. Taking advantage of recent work in modal type theory and univalent foundations, we derive Löb induction from a simpler and more conceptual set of primitives. We then capitalize on these insights to present Gatsby, the first guarded type theory capturing the rich modal structure of the topos of trees alongside Löb induction without immediately precluding canonicity or normalization. We show that Gatsby can recover many prior approaches to guarded recursion and use its additional power to improve on prior examples. We crucially rely on homotopical insights and Gatsby constitutes a new application of univalent foundations to the theory of programming languages.

链接与引用

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

BibTeX
@article{Gratzer25,
  title = {A Modal Deconstruction of Löb Induction},
  author = {Daniel Gratzer},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {9},
  number = {POPL},
  year = {2025},
  doi = {10.1145/3704866}
}