论文标题
效率的效果：一流控制的渐近加速
Effects for Efficiency: Asymptotic Speedup with First-Class Control
论文作者
论文摘要
我们研究分隔控制的基本效率。具体而言，我们表明效果处理程序可以为某些类别的功能实现运行时复杂性的渐近改善。我们考虑使用纯PCF的基本语言$λ_b$及其带有效果处理程序的扩展名$λ_H$的通用计数问题。我们表明，$λ_H$与任何$λ_b$实现相比，渐近地实现通用计数的效率更高。我们还表明，当$λ_b$以可变状态扩展时，此效率差距仍然存在。据我们所知，这个结果是控制运营者的第一个结果。
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 the generic count problem using a pure PCF-like base language $λ_b$ and its extension with effect handlers $λ_h$. We show that $λ_h$ admits an asymptotically more efficient implementation of generic count than any $λ_b$ implementation. We also show that this efficiency gap remains when $λ_b$ is extended with mutable state. To our knowledge this result is the first of its kind for control operators.
