paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A Relational Theory of Monadic Rewriting Systems, Part I

单子重写系统的关系理论(第一部分)
LICS 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2021匹配度 2/10 · 该论文属于纯形式语义与重写理论研究,讨论单子重写系统、代数效应以及CBV λ演算的标准化与合流,未涉及LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析等用户核心方向;仅与函数式/效应语言的PL理论基础有间接关联。引用 3 inbox
Francesco Gavazzo, Claudia Faggian
crossref: 2026-09-12

AI 速览

一句话:提出单子重写的关系理论,识别弱笛卡尔单子与线性方程条件,并给出带代数效应的 CBV λ 演算的标准化与合流定理。

本文研究带效应程序语言的计算与重写语义:将归约本身视为具有单子效应的重写,提出单子重写系统的关系理论。作者指出,对分布、幂集、reader、全局状态等单子,直接定义有意义的重写并不平凡,因此追问何种条件下单子重写可行。方法上,他们识别出弱笛卡尔单子可保证单子重写具有良好性质;当单子由等式理论(如代数效应)给出时,证明所有等式线性是充分条件。最后将该抽象理论应用于带代数效应的 CBV λ 演算,得到带效应的表面标准化与合流定理。

问题
在带效应语言中,如何定义具有良好行为的单子重写,以及哪些单子允许这种重写?
方法
引入单子重写系统的关系理论,识别弱笛卡尔单子,并对由等式理论给出的单子给出线性等式的充分条件,再应用于带代数效应的 CBV λ 演算。
评估
以理论定理证明为主:证明弱笛卡尔单子和线性等式条件下的良行为,并在 CBV λ 演算上导出带效应的表面标准化与合流定理。
原文摘要(Abstract)

Motivated by the study of effectful programming languages and computations, we introduce a relational theory of monadic rewriting systems. The latter are rewriting systems whose notion of reduction is effectful, where effects are modelled as monads. Contrary to what happens in the ordinary operational semantics of monadic programming languages, defining meaningful notions of monadic rewriting turns out to problematic for several monads, including the distribution, powerset, reader, and global state monad. This raises the question of when monadic rewriting is possible. We answer that question by identifying a class of monads, known as weakly cartesian monads, that guarantee monadic rewriting to be well-behaved. In case monads are given as equational theories, as it is the case for algebraic effects, we also show that a sufficient condition to have a well-behaved notion of monadic rewriting is that all equations in the theory are linear. Finally, we apply the abstract theory of monadic rewriting systems to the call-by-value λ-calculus with algebraic effects, this way obtaining effectful (surface) standardisation and confluence theorems.

链接与引用

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

BibTeX
@inproceedings{paperbot6157,
  title = {A Relational Theory of Monadic Rewriting Systems, Part I},
  author = {Francesco Gavazzo and Claudia Faggian},
  booktitle = {LICS},
  year = {2021},
  doi = {10.1109/lics52264.2021.9470633}
}