paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Bisimulations for Delimited-Control Operators

定界控制算子的互模拟
LMCS vol.Volume 15, Issue 22019匹配度 2/10 · 该论文研究 shift/reset 等分隔控制算子的上下文等价与互模拟,属于纯形式语义理论,与用户关注的静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析均无直接关联,仅在 PL 形式化方法层面有非常间接的联系。引用 0 inbox
Dariusz Biernacki, Sergueï Lenglet, Piotr Polesiuk
crossref: 2026-09-10

AI 速览

一句话:为带 shift/reset 的无类型 λ 演算定义上下文等价,并在统一框架中用多种互模拟刻画其行为理论。

论文系统研究带定界控制算子 shift 和 reset 的无类型 λ 演算的行为理论。作者首先为该演算定义上下文等价,并试图用余归纳定义的互模拟关系来刻画它。文章在一个统一框架内考察 applicative、normal-form 和环境式(environmental)三种互模拟风格,通过实例比较它们各自的表达能力、优点与局限。该工作为定界控制算子的程序等价与行为推理提供语义基础,并讨论如何将方法扩展到其他定界控制算子。

问题
如何为带 shift/reset 的无类型 λ 演算建立上下文等价,并找到能刻画它的互模拟关系?
方法
定义上下文等价,引入余归纳互模拟,并在统一框架中比较 applicative、normal-form 与环境式三种风格。
评估
通过若干例子分析三种互模拟的强弱与适用场景,并讨论向其他定界控制算子的推广;工作以理论刻画和案例说明为主。
原文摘要(Abstract)

We present a comprehensive study of the behavioral theory of an untyped $\lambda$-calculus extended with the delimited-control operators shift and reset. To that end, we define a contextual equivalence for this calculus, that we then aim to characterize with coinductively defined relations, called bisimilarities. We consider different styles of bisimilarities (namely applicative, normal-form, and environmental) within a unifying framework, and we give several examples to illustrate their respective strengths and weaknesses. We also discuss how to extend this work to other delimited-control operators.

链接与引用

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

BibTeX
@article{paperbot789,
  title = {Bisimulations for Delimited-Control Operators},
  author = {Dariusz Biernacki and Sergueï Lenglet and Piotr Polesiuk},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 15, Issue 2},
  year = {2019},
  doi = {10.23638/lmcs-15(2:18)2019}
}