paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Effectful applicative bisimilarity: Monads, relators, and Howe's method

带效应的应用性互模拟:单子、relator 与 Howe 方法
LICS 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2017匹配度 1/10 · 该论文属于纯形式语义与程序等价理论,研究代数效应下应用性互模拟与Howe方法,未涉及LLM、Agent、静态分析、浮点程序分析或贝叶斯程序分析,与用户研究方向仅有非常间接的PL理论关联。引用 61 inbox
Ugo Dal Lago, Francesco Gavazzo, Paul Blain Levy
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:在带代数效应的 call-by-value λ-演算中,用 monad 和 relator 抽象推广应用性互模拟,并刻画其成为同余的条件。

论文研究带代数效应的 call-by-value λ-演算中的程序等价性。作者首先为计算 λ-演算配备 monadic 操作语义,将代数效应封装在 monad 中;随后引入 relator 理论,把 Abramsky 的应用性互模拟从纯演算抽象地推广到该设定。核心问题是:对于哪些 monad 与 relator,应用性互模拟仍是同余关系,从而可作为可靠的程序等价方法。为此,论文在抽象层面研究 Howe 方法,并给出保证同余性的条件。该工作提供了一个统一语义框架,使应用性互模拟可适用于多种效应与等价概念,并为带效应语言的共归纳等价证明奠定方法论基础。

问题
如何将 Abramsky 的应用性互模拟推广到带代数效应的 call-by-value λ-演算,并确定在何种 monad 与 relator 条件下它保持同余,从而成为可靠的程序等价性方法。
方法
为计算 λ-演算建立 monadic 操作语义,并借助 relator 理论抽象定义应用性互模拟;同时在抽象层面发展 Howe 方法以证明同余性。
评估
以抽象定义和定理证明为主要评估手段,刻画使应用性互模拟成为同余的 monad 与 relator 条件。
原文摘要(Abstract)

We study Abramsky's applicative bisimilarity abstractly, in the context of call-by-value λ-calculi with algebraic effects. We first of all endow a computational λ-calculus with a monadic operational semantics. We then show how the theory of relators provides precisely what is needed to generalise applicative bisimilarity to such a calculus, and to single out those monads and relators for which applicative bisimilarity is a congruence, thus a sound methodology for program equivalence. This is done by studying Howe's method in the abstract.

链接与引用

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

BibTeX
@inproceedings{LagoGL17,
  title = {Effectful applicative bisimilarity: Monads, relators, and Howe's method},
  author = {Ugo Dal Lago and Francesco Gavazzo and Paul Blain Levy},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005117}
}