paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Affect: An Affine Type and Effect System

Affect:一种仿射类型与效应系统
POPL 9(POPL)2025匹配度 2/10 · 论文属于类型与效应系统、效应处理器及 Coq/Iris 形式化验证方向,与用户关注的 PL↔AI(静态分析用于 ML/Agentic 程序)、浮点程序分析、贝叶斯程序分析及 LLM 交叉均无直接关联;仅共享 PL 形式化背景。引用 11 inbox
Orpheas van Rooij, Robbert Krebbers
crossref: 2026-09-10

AI 速览

一句话:提出 Affect:用仿射类型与效应静态追踪续延的 one-shot/multi-shot 用法,并在 Coq/Iris 中证明其可靠性。

效应处理器的续延可被恢复一次(one-shot)或任意多次(multi-shot);multi-shot 会破坏关键推理规则,使某些标准变换与优化不再可靠,在含可变引用的语言(如 OCaml 5)中尤为明显。本文提出 Affect——用仿射类型追踪续延用法的类型与效应系统,使编译器能据此高效实现效应处理器并判定可执行的优化。为支持存储续延的引用、嵌套续延等高级特性,作者扩展了 Rust 的 Cell 类型与 Wadler 的 use types,并支持多态效应函数的一般类型签名。作者在 Coq 的 Iris 分离逻辑中用逻辑关系对类型与判定作语义建模,证明了 Affect 的可靠性。

问题
效应处理器的续延可以至多恢复一次或任意多次使用,但 multi-shot 用法会破坏关键推理规则,使某些标准变换与优化(尤其在含可变引用的语言中)不再可靠,因此需要静态区分两种使用纪律。
方法
设计 Affect 类型与效应系统,用仿射类型追踪续延使用;扩展 Rust 的 Cell 类型与 Wadler 的 use types 以处理存储续延的引用与嵌套续延,并支持多态效应函数的一般类型签名。
评估
在 Coq 的 Iris 分离逻辑框架中以逻辑关系语义化类型与判定,机器化证明了系统可靠性,并覆盖控制反转、协作式并发等效应文献中的挑战性例子。
原文摘要(Abstract)

Effect handlers form a powerful construct that can express complex programming abstractions. They are a generalisation of exception handlers, but allow resumption of the continuation from where the effect was raised. Allowing continuations to be resumed at most once ( one-shot ) or an arbitrary number of times ( multi-shot ) has far-reaching consequences. In addition to performance considerations, multi-shot effects break key rules of reasoning and thus render certain standard transformation/optimisations unsound, especially in languages with mutable references (such as OCaml 5). It is therefore desirable to statically track whether continuations are used in a one-shot or multi-shot discipline, so that a compiler could use this information to efficiently implement effect handlers and to determine what optimizations it may perform. We address this problem by developing a type and effect system–called Affect –which uses affine types to track the usage of continuations. A challenge is to soundly deal with advanced programming features—such as references that store continuations and nested continuations—which are crucial to support challenging examples from the effects literature (such as control inversion and cooperative concurrency ). Another challenge is to support generic type signatures of polymorphic effectful functions. We address these challenges by using and extending Rust's Cell type and Wadler's use types . To prove soundness of Affect we model types and judgements semantically via a logical relation in the Iris separation logic framework in Coq.

链接与引用

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

BibTeX
@article{RooijK25,
  title = {Affect: An Affine Type and Effect System},
  author = {Orpheas van Rooij and Robbert Krebbers},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {9},
  number = {POPL},
  year = {2025},
  doi = {10.1145/3704841}
}