paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Galois connecting call-by-value and call-by-name

Galois 连接关联 call-by-value 与 call-by-name
LMCS vol.Volume 20, Issue 12024匹配度 2/10 · 该论文属于纯编程语言形式语义研究,讨论 call-by-value/call-by-name 的可观察行为与 Galois 连接,虽与 PL 理论相关,但不涉及用户核心关注的静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析。引用 1 inbox
Dylan McDermott, Alan Mycroft
crossref: 2026-09-10

AI 速览

一句话:用 call-by-push-value 与 Galois 连接刻画传值与传名的可观察行为关系。

论文研究带计算效应的语言中 call-by-value 与 call-by-name 执行的可观察行为关系。作者以 Levy 的 call-by-push-value 演算为统一框架,将表达式分别翻译为传值与传名解释,并识别使两者行为相关的效应条件。基于这些条件,他们在类型的传值与传名解释之间构造映射,并给出效应应满足的额外性质,使这些映射构成 Galois 连接。该性质对发散等效应成立,但对可变状态等效应不成立,从而得到一个通用的推理原则。作者将该原则应用于发散与非确定性等计算效应,说明何时可从一种求值策略的终止或结果推断另一种策略。

问题
在带计算效应的语言中,call-by-value 与 call-by-name 的可观察行为常不同但相关;论文旨在给出统一条件与证明技术来刻画这种关系。
方法
以 Levy 的 call-by-push-value 为中介,将表达式翻译到 CBPV,构造类型在传值与传名解释之间的映射,并识别使映射成为 Galois 连接的效应性质。
评估
通过理论证明及发散、非确定性等示例效应展示推理原则;可变状态等反例表明这些性质并非对所有效应成立。
原文摘要(Abstract)

We establish a general framework for reasoning about the relationship between call-by-value and call-by-name. In languages with computational effects, call-by-value and call-by-name executions of programs often have different, but related, observable behaviours. For example, if a program might diverge but otherwise has no effects, then whenever it terminates under call-by-value, it terminates with the same result under call-by-name. We propose a technique for stating and proving properties like these. The key ingredient is Levy's call-by-push-value calculus, which we use as a framework for reasoning about evaluation orders. We show that the call-by-value and call-by-name translations of expressions into call-by-push-value have related observable behaviour under certain conditions on computational effects, which we identify. We then use this fact to construct maps between the call-by-value and call-by-name interpretations of types, and identify further properties of effects that imply these maps form a Galois connection. These properties hold for some computational effects (such as divergence), but not others (such as mutable state). This gives rise to a general reasoning principle that relates call-by-value and call-by-name. We apply the reasoning principle to example computational effects including divergence and nondeterminism.

链接与引用

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

BibTeX
@article{paperbot2778,
  title = {Galois connecting call-by-value and call-by-name},
  author = {Dylan McDermott and Alan Mycroft},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 20, Issue 1},
  year = {2024},
  doi = {10.46298/lmcs-20(1:13)2024}
}