paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Effects for efficiency: asymptotic speedup with first-class control

效应换效率：一等控制带来渐近加速
ICFP 4(ICFP)2020匹配度 2/10 · 该论文属于纯 PL 理论/语言设计方向（delimited control 与 effect handlers 的渐近效率分析），与用户的核心方向（PL↔AI 交叉、静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析）几乎没有交集，也未涉及工业落地或 benchmark 失效分析。仅在 effect handlers 这一语言机制上可能间接关联到概率/Bayesian 编程的实现技术，但论文本身并未触及。引用 6 inbox
Daniel Hillerström, Sam Lindley, John Longley
语言设计与特性函数式编程
dblp: 2026-09-10crossref: 2026-09-10arxiv: 2026-09-10

AI 速览

一句话：证明效应处理器能为 generic count 带来渐近运行时加速，且该优势无法由可变状态弥补。

论文研究分隔控制与效应处理器的根本效率问题，而非仅关注其表达力或编程便利性。作者以一个类 PCF 的纯函数式基础语言 λ_b 和其加入效应处理器扩展的语言 λ_h 为对象，考察 generic count 问题。结果表明，λ_h 可以实现渐近复杂度更优的 generic count，而任何 λ_b 实现都无法达到该复杂度；即便给 λ_b 加入可变状态，这一渐近效率差距仍然存在。该结果据作者所知是控制操作符领域的首个同类型结论。

问题
效应处理器和分隔控制是否能在运行时复杂度层面带来本质性的渐近加速，而不仅仅是表达力或编程风格上的优势。
方法
在类 PCF 的纯语言 λ_b 与加入效应处理器的 λ_h 中形式化比较 generic count 的实现，并进一步分析 λ_b 扩展可变状态后的可实现复杂度。
评估
通过理论证明给出渐近复杂度分离，说明 λ_h 相比 λ_b 及其可变状态扩展的严格效率优势，而非基于实验基准。
原文摘要（Abstract）

We study the fundamental efficiency of delimited control. Specifically, we show that effect handlers enable an asymptotic improvement in runtime complexity for a certain class of functions. We consider thegeneric countproblem using a pure PCF-like base language λband its extension with effect handlers λh.We show that λhadmits an asymptotically more efficient implementation of generic count than any λbimplementation.We also show that this efficiency gap remains when λbis extended with mutable state.To our knowledge this result is the first of its kind for control operators.

链接与引用

DOI 原文 · arXiv · PDF（开放获取） · DBLP

BibTeX 
@article{abs-2007-00605,
  title = {Effects for efficiency: asymptotic speedup with first-class control},
  author = {Daniel Hillerström and Sam Lindley and John Longley},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {4},
  number = {ICFP},
  year = {2020},
  doi = {10.1145/3408982}
}