paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Call-by-name extensionality and confluence

Call-by-name 外延性与合流
JFP vol.272017匹配度 1/10 · 该论文属于纯编程语言理论中的形式语义与重写系统研究,讨论 call-by-name 外延性、合流性与 sequent calculus,与用户关注的静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析等方向几乎无直接交集。引用 2 inbox
PHILIP JOHNSON-FREYD, PAUL DOWNEN, ZENA M. ARIOLA
dblp: 2026-09-10crossref: 2026-09-10

AI 速览

一句话:在 sequent calculus 中为带效应的 call-by-name 惰性外延函数给出合流规约系统,并揭示其边界。

本文研究带效应的 call-by-name 语言中函数外延性与重写系统合流性的冲突。作者指出,若简单地把 η 等外延律当作规约规则,合流性很容易被破坏。论文在 sequent calculus 中考察该问题,并借鉴 call-by-name 函数语言理论中的若干洞见,包括两个独立 control calculi 的合流重写以及可靠的 continuation-passing style(CPS)变换。基于这些思想,作者为惰性外延函数给出了一个合流的规约系统,从而在支持外延性的同时保持重写的一致性。最后,论文讨论了该方法在严格求值以及函数之外类型上的局限性。

问题
为带效应的 call-by-name 语言设计既尊重函数外延性又保持合流性的重写系统十分困难;直接将 η 等外延律视为规约规则会破坏合流。
方法
在 sequent calculus 框架下,借鉴 call-by-name 函数语言理论中两个独立 control calculi 的合流重写与可靠 CPS 变换等洞见,构造并分析规约系统。
评估
通过理论证明与论证给出惰性外延函数的合流规约系统,并分析该方法在严格求值和非函数类型上的局限。
原文摘要(Abstract)

Abstract Designing rewriting systems that respect functional extensionality for call-by-name languages with effects turns out to be surprisingly challenging. Simply interpreting extensional laws like η as reduction rules easily breaks confluence. We explore these issues in the setting of a sequent calculus. Building on an insight that appears in different aspects of the theory of call-by-name functional languages—confluent rewriting for two independent control calculi and sound continuation-passing style transformations—we give a confluent reduction system for lazy extensional functions. Finally, we consider limitations to this approach when used for strict evaluation and types beyond functions.

链接与引用

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

BibTeX
@article{Johnson-FreydDA17,
  title = {Call-by-name extensionality and confluence},
  author = {PHILIP JOHNSON-FREYD and PAUL DOWNEN and ZENA M. ARIOLA},
  journal = {Journal of Functional Programming},
  volume = {27},
  year = {2017},
  doi = {10.1017/s095679681700003x}
}