paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Effect handlers, evidently

效应处理器:证据翻译
ICFP 4(ICFP)2020匹配度 2/10 · 论文研究代数效应处理器的语义、证据翻译与编译实现,属于纯 PL/函数式编程理论,未涉及 LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析,与用户研究方向仅有宽泛的 PL 关联。引用 33 inbox
Ningning Xie, Jonathan Immanuel Brachthäuser, Daniel Hillerström, Philipp Schuster, Daan Leijen
dblp: 2026-09-10crossref: 2026-09-10

AI 速览

一句话:提出 scoped resumptions 限制与证据翻译,证明其可靠一致并实现高效效应处理器。

代数效应处理器能灵活表达效应,但通用形式过于强大,难以推理且实现开销高。本文将处理器限制为具有作用域恢复(scoped resumptions)的子集,论证仍可表达重要效应并改善推理。基于该保证,提出一种可靠且一致的证据翻译:将处理器作为证据直接传给每个操作,并证明到普通 λ 演算的完全可靠性(soundness)与一致性(coherence)。该翻译支持高效实现:尾恢复操作可就地执行而无需捕获求值上下文,并用常量偏移索引替代运行时处理器搜索。

问题
通用代数效应处理器表达力过强,程序难以推理,且运行时需搜索处理器导致实现效率低。
方法
将处理器限制为 scoped resumptions,并定义把处理器作为证据传给每个操作的 evidence translation,证明其到纯 lambda 演算的可靠性与一致性。
评估
通过语义证明评估翻译的正确性,并展示尾恢复操作原地执行、常量偏移索引处理器等高效实现技术。
原文摘要(Abstract)

Algebraic effect handlers are a powerful way to incorporate effects in a programming language. Sometimes perhaps even _too_ powerful. In this article we define a restriction of general effect handlers with _scoped resumptions_. We argue one can still express all important effects, while improving reasoning about effect handlers. Using the newly gained guarantees, we define a sound and coherent evidence translation for effect handlers, which directly passes the handlers as evidence to each operation. We prove full soundness and coherence of the translation into plain lambda calculus. The evidence in turn enables efficient implementations of effect operations; in particular, we show we can execute tail-resumptive operations _in place_ (without needing to capture the evaluation context), and how we can replace the runtime search for a handler by indexing with a constant offset.

链接与引用

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

BibTeX
@article{XieBHSL20,
  title = {Effect handlers, evidently},
  author = {Ningning Xie and Jonathan Immanuel Brachthäuser and Daniel Hillerström and Philipp Schuster and Daan Leijen},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {4},
  number = {ICFP},
  year = {2020},
  doi = {10.1145/3408981}
}