paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Adequacy for Algebraic Effects Revisited

代数效应的 Adequacy 再探
OOPSLA 9(OOPSLA1)2025匹配度 1/10 · 该论文属于纯形式语义/范畴论方向,研究代数效应在 CBPV 下的充分性定理,与用户关注的静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析均无直接关联。虽然涉及交互树与单子代数等理论工具,但既不涉及 LLM,也缺乏工程落地或 benchmark 驱动的动机。引用 6 inbox
G. A. Kavvos
crossref: 2026-09-10

AI 速览

一句话:为一般(含无穷)代数效应建立基于交互树与单子代数的 CBPV 充分性定理。

本文重新探讨代数效应的充分性(adequacy)定理,并将结果推广到包含无穷效应的一般代数效应类。所考虑的演算是 Call-by-Push-Value(CBPV)的一个版本,因此可覆盖包括按值调用在内的多种求值机制。作者为该演算给出基于交互树(interaction trees)的操作语义,以及基于单子代数(monad algebras)的指称语义。核心结果是指称等价蕴含观察等价,即建立充分性;证明采用传统的逻辑关系(logical relations)论证。该工作为不同求值策略下的代数效应语义提供统一框架。

问题
如何为一般代数效应(含无穷效应)在 CBPV 下建立充分性,使指称语义与操作语义一致并覆盖多种求值机制。
方法
以交互树定义操作语义,以单子代数定义指称语义,并通过传统逻辑关系证明指称等价蕴含观察等价。
评估
通过理论证明给出 adequacy 定理,覆盖包含无穷效应的一般代数效应类以及包括按值调用在内的多种求值机制;摘要未涉及实现或实证评估。
原文摘要(Abstract)

This paper proves an adequacy theorem for a general class of algebraic effects, including infinitary ones. The theorem targets a version of Call-by-Push-Value (CBPV), so that it applies to many possible evaluation mechanisms, including call-by-value. The calculus is given an operational semantics based on interaction trees, as well as a denotational semantics based on monad algebras. The main result, viz. that denotational equivalence implies observational equivalence, using a traditional logical relations argument.

链接与引用

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

BibTeX
@article{paperbot3177,
  title = {Adequacy for Algebraic Effects Revisited},
  author = {G. A. Kavvos},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {9},
  number = {OOPSLA1},
  year = {2025},
  doi = {10.1145/3720457}
}