paperbot · PL 论文追踪

全部论文 待读 收藏

P2 The clocks are ticking: No more delays!

时钟在滴答:不再有延迟!
LICS 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2017匹配度 2/10 · 论文属于纯类型论与形式语义研究,讨论守卫递归的归约语义、合流性与强规范化,未涉及 LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析。虽然与形式化验证/类型系统基础有间接关联,但不在用户当前核心研究问题范围内。引用 43 inbox
Patrick Bahr, Hans Bugge Grathwohl, Rasmus Ejlers Mogelberg
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:提出 Clocked Type Theory,为守卫递归给出适合归约语义的类型论,并证明合流、强规范化与典范性。

守卫递归(Nakano 意义)允许在类型论中加入一般递归类型与项而不破坏一致性,并已用于余数据编程、余归纳类型推理以及高级语言特性的步进索引。本文旨在为其构造可直接归约、最终可机器检验的实现基础。作者提出 Clocked Type Theory:一种比现有守卫递归类型论更适合归约语义的新类型论,显式引入时钟以控制延迟与守卫。论文证明其归约语义满足合流性、强规范化与典范性,并展示如何编码以流为例的余归纳类型,进而推出该类型系统保证流定义的生产性。

问题
现有守卫递归类型论虽支持一般递归类型且保持一致性,但缺少适合归约语义、可支撑实现与机器检验的基础。
方法
提出 Clocked Type Theory,显式使用时钟组织守卫递归,并定义其归约语义;证明合流、强规范化与典范性。
评估
通过元理论证明建立归约语义的性质,并以流为例编码余归纳类型,证明类型系统保证流定义的生产性。
原文摘要(Abstract)

Guarded recursion in the sense of Nakano allows general recursive types and terms to be added to type theory without breaking consistency. Recent work has demonstrated applications of guarded recursion such as programming with codata, reasoning about coinductive types, as well as constructing and reasoning about denotational models of general recursive types. Guarded recursion can also be used as an abstract form of step-indexing for reasoning about programming languages with advanced features. Ultimately, we would like to have an implementation of a type theory with guarded recursion in which all these applications can be carried out and machine-checked. In this paper, we take a step towards this goal by devising a suitable reduction semantics. We present Clocked Type Theory, a new type theory for guarded recursion that is more suitable for reduction semantics than the existing ones. We prove confluence, strong normalisation and canonicity for its reduction semantics, constructing the theoretical basis for a future implementation. We show how coinductive types as exemplified by streams can be encoded, and derive that the type system ensures productivity of stream definitions.

链接与引用

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

BibTeX
@inproceedings{BahrGM17,
  title = {The clocks are ticking: No more delays!},
  author = {Patrick Bahr and Hans Bugge Grathwohl and Rasmus Ejlers Mogelberg},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005097}
}