paperbot · PL 论文追踪

全部论文 待读 收藏

P2 The fire triangle: how to mix substitution, dependent elimination, and effects

火三角:如何混合替换、依赖消去与效应
POPL 4(POPL)2019匹配度 2/10 · 该论文属于纯类型论与函数式编程基础研究,讨论替换、依赖消去与效应的不相容,并给出 ∂CBPV 演算;这与用户画像中 PL 与 AI/LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析的核心交叉方向没有直接关系。引用 42 inbox
Pierre-Marie Pédrot, Nicolas Tabareau
crossref: 2026-09-10

AI 速览

一句话:提出类型论中替换、依赖消去与效应不相容的 no-go 定理,并给出依赖 CBPV 演算 ∂CBPV 以调和三者。

论文指出,在类型论中替换、依赖消去与效应之间存在根本性张力,并将其凝练为一个 no-go 定理,称为类型论的“火三角”。为解除该限制,作者提出 ∂CBPV:将 call-by-push-value(CBPV)这一通用效应演算扩展到依赖类型。通过把 call-by-name 和 call-by-value 的经典分解推广到 ∂CBPV,论文解释了为何在效应存在时,call-by-name 必须限制依赖消去,而 call-by-value 必须限制替换。最后,作者给出从 ∂CBPV 到 Martin-Löf 类型论的多种带效应语法翻译(reader、weaning、forcing),以说明该演算足以解释多种效应。

问题
在类型论中,替换、依赖消去与效应三者能否同时无限制共存?论文将这一张力形式化为 no-go 定理。
方法
提出依赖类型版本的 CBPV 演算 ∂CBPV,并将 call-by-name/call-by-value 分解推广到该演算以分析三者冲突;再通过到 Martin-Löf 类型论的效果化语法翻译解释效应。
评估
以 no-go 定理证明限制不可避免,并构造 reader、weaning、forcing 等翻译,展示 ∂CBPV 可解释多种效应。
原文摘要(Abstract)

There is a critical tension between substitution, dependent elimination and effects in type theory. In this paper, we crystallize this tension in the form of a no-go theorem that constitutes the fire triangle of type theory. To release this tension, we propose ∂CBPV, an extension of call-by-push-value (CBPV) —a general calculus of effects—to dependent types. Then, by extending to ∂CBPV the well-known decompositions of call-by-name and call-by-value into CBPV, we show why, in presence of effects, dependent elimination must be restricted in call-by-name, and substitution must be restricted in call-by-value. To justify ∂CBPV and show that it is general enough to interpret many kinds of effects, we define various effectful syntactic translations from ∂CBPV to Martin-Löf type theory: the reader, weaning and forcing translations.

链接与引用

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

BibTeX
@article{paperbot522,
  title = {The fire triangle: how to mix substitution, dependent elimination, and effects},
  author = {Pierre-Marie Pédrot and Nicolas Tabareau},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {4},
  number = {POPL},
  year = {2019},
  doi = {10.1145/3371126}
}