paperbot · PL 论文追踪

全部论文 待读 收藏

P2 An effectful way to eliminate addiction to dependence

一种消除依赖成瘾的效应化方法
LICS 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2017匹配度 2/10 · 论文研究依赖类型论中引入异常、非终止等计算效应的单子翻译,属于类型系统/函数式编程的理论工作,与用户关注的静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析等核心方向没有直接关联,仅同属程序语言与形式化方法的大领域。引用 38 inbox
Pierre-Marie Pedrot, Nicolas Tabareau
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:提出 weaning 翻译,首次在依赖类型论 CIC 中安全引入异常、非终止、非确定性等计算效应。

论文研究如何在依赖类型论中引入计算效应(如异常、非终止、非确定性、写操作)这一长期难题。作者指出,传统的单子翻译在存在类型依赖时会失效,并借助 call-by-push-value 分解说明其失败的根源:类型依赖于项,而效应会改变项的计算行为。为此他们提出 weaning 翻译,其关键条件是单子的代数宇宙自身必须构成一个代数。该翻译适用于带受限依赖消去的归纳构造演算(CIC),随后作者将参数化(parametricity)技术与 weaning 翻译相结合,把结果推广到完整 CIC,从而给出首个带效应的 CIC 版本。

问题
传统单子式翻译无法在依赖类型论中引入效应,因为类型可以依赖项,而效应会破坏类型与项之间的这种依赖关系。
方法
通过 call-by-push-value 分解分析失败原因,提出 weaning 翻译,要求单子的代数宇宙自身构成代数;先应用于带受限依赖消去的 CIC,再用参数化技术扩展到完整 CIC。
评估
以理论构造与证明为主:给出 weaning 翻译及其在受限 CIC 上的适用性论证,并通过与参数化技术结合得到完整 CIC 的带效应版本。
原文摘要(Abstract)

We define a monadic translation of type theory, called the weaning translation, that allows for a large range of effects in dependent type theory-such as exceptions, non-termination, non-determinism or writing operations. Through the light of a call-by-push-value decomposition, we explain why the traditional approach fails with type dependency and justify our approach. Crucially, the construction requires that the universe of algebras of the monad forms itself an algebra. The weaning translation applies to a version of the Calculus of Inductive Constructions (CIC) with a restricted version of dependent elimination. Finally, we show how to recover a translation of full CIC by mixing parametricity techniques with the weaning translation. This provides the first effectful version of CIC.

链接与引用

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

BibTeX
@inproceedings{PedrotT17,
  title = {An effectful way to eliminate addiction to dependence},
  author = {Pierre-Marie Pedrot and Nicolas Tabareau},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005113}
}