paperbot · PL 论文追踪

全部论文 待读 收藏

P2 No value restriction is needed for algebraic effects and handlers

代数效应与处理器不需要值限制
JFP vol.272017匹配度 2/10 · 该论文属于纯 PL 类型论,研究代数效应与处理器的 HM 多态类型系统及可靠性证明,与用户画像中 PL↔AI、静态分析、浮点程序分析、贝叶斯程序分析或 LLM/Agent 等核心方向没有直接关联。引用 21 inbox
OHAD KAMMAR, MATIJA PRETNAR
crossref: 2026-09-10

AI 速览

一句话:提出可对任意计算泛化的 HM 多态类型系统,证明代数效应与处理器的可靠性,无需值限制。

本文研究 call-by-value 下代数效应与处理器的多态类型安全性,尤其是值限制的必要性。传统 Hindley–Milner 多态在存在引用单元、续延等计算效应时,若泛化任意计算会破坏可靠性,因此通常只泛化值。作者给出一个直接、可靠的 HM 多态类型系统,允许对任意计算做类型变量泛化,并证明其可靠性;证明在 Twelf 中机器化验证。随后分析效应处理器相对于状态效应的表达能力:作者猜想仅靠处理器无法表达引用单元,但证明它能模拟动态作用域状态,表明动态绑定也不需值限制。

问题
在 call-by-value 语言中,带计算效应的 HM 多态通常需要值限制;本文追问代数效应与处理器是否也必须限制泛化。
方法
构建带代数效应与处理器的 CBV 演算及 HM 多态类型系统,证明类型可靠性,并在 Twelf 中形式化;通过编码分析处理器对状态效应的表达力。
评估
可靠性证明经 Twelf 机器检查;并给出动态作用域状态的模拟,论证处理器无法表达引用单元的猜想。
原文摘要(Abstract)

Abstract We present a straightforward, sound, Hindley–Milner polymorphic type system for algebraic effects and handlers in a call-by-value calculus, which, to our surprise, allows type variable generalisation of arbitrary computations, and not just values. We first recall that the soundness of unrestricted call-by-value Hindley–Milner polymorphism is known to fail in the presence of computational effects such as reference cells and continuations, and that many programming examples can be recast to use effect handlers instead of these effects. After presenting the calculus and its soundness proof, formalised in Twelf, we analyse the expressive power of effect handlers with respect to state effects. We conjecture handlers alone cannot express reference cells, but show they can simulate dynamically scoped state, establishing that dynamic binding also does not need a value restriction.

链接与引用

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

BibTeX
@article{paperbot81,
  title = {No value restriction is needed for algebraic effects and handlers},
  author = {OHAD KAMMAR and MATIJA PRETNAR},
  journal = {Journal of Functional Programming},
  volume = {27},
  year = {2017},
  doi = {10.1017/s0956796816000320}
}