paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Handling delimited continuations with dependent types

用依赖类型处理定界延续
ICFP 2(ICFP)2018匹配度 1/10 · 该论文属于纯类型论与形式语义研究,讨论依赖类型语言中的 shift/reset 与 CPS 翻译,未涉及静态分析、ML/Agentic 程序、LLM 辅助验证、浮点程序分析或贝叶斯程序分析,与用户研究画像基本无关。引用 10 inbox
Youyou Cong, Kenichi Asai
crossref: 2026-09-10

AI 速览

一句话:为依赖类型语言引入 shift/reset,限制类型依赖并用答案类型多态给出可靠类型系统与保类型 CPS 翻译。

本文关注在依赖类型语言中集成定界控制操作 shift 和 reset 时遇到的两个难题:控制算子的动态性可能破坏逻辑一致性与主体归约等基本性质,而常用于定义控制算子语义的 CPS 翻译也难以直接扩展到依赖类型。作者通过限制类型的依赖关系,并对纯项采用答案类型多态来解决这些问题。论文的主要贡献是给出该语言的一个可靠类型系统,以及一个保持类型的 CPS 翻译,从而在保留依赖归纳类型的同时支持定界延续。文章还讨论了若干可扩展方向,使语言更接近全谱证明助手,但这些扩展带来非平凡的挑战。

问题
如何将 shift/reset 定界控制安全地融入具有依赖归纳类型的语言,同时避免破坏逻辑一致性和主体归约,并解决 CPS 翻译在依赖类型下的扩展困难。
方法
通过限制类型中的依赖,并利用纯项的答案类型多态,设计可靠类型系统与保持类型的 CPS 翻译。
评估
以形式化性质为主要论证,包括类型可靠性与 CPS 翻译保持类型,并讨论若干扩展方向及其开放问题;摘要未报告实现或实验评估。
原文摘要(Abstract)

Dependent types are a powerful tool for maintaining program invariants. To take advantage of this aspect in real-world programming, efforts have been put into enriching dependently typed languages with missing constructs, most notably, effects. This paper presents a language that has two practically interesting ingredients: dependent inductive types, and the delimited control constructs shift and reset. When integrating delimited control into a dependently typed language, however, two challenges arise. First, the dynamic nature of control operators, which is the source of their expressiveness, can break fundamental language properties such as logical consistency and subject reduction. Second, CPS translations, which we often use to define the semantics of control operators, do not scale straightforwardly to dependently typed languages. We solve the former issue by restricting dependency of types, and the latter using answer-type polymorphism of pure terms. The main contribution of this paper is to give a sound type system of our language, as well as a type-preserving CPS translation. We also discuss various extensions, which would make our language more like a full-spectrum proof assistant but pose non-trivial issues.

链接与引用

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

BibTeX
@article{paperbot276,
  title = {Handling delimited continuations with dependent types},
  author = {Youyou Cong and Kenichi Asai},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {2},
  number = {ICFP},
  year = {2018},
  doi = {10.1145/3236764}
}