paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Computation focusing

计算聚焦
ICFP 4(ICFP)2020匹配度 2/10 · 论文属于纯 PL 证明论与形式语义/类型系统研究,核心是聚焦演算、上下文等价和完全抽象,不涉及静态分析、ML/Agent 系统、LLM 辅助验证、浮点程序分析或贝叶斯程序分析;仅与形式化方法有间接关联。引用 4 inbox
Nick Rioux, Steve Zdancewic
dblp: 2026-09-10crossref: 2026-09-10

AI 速览

一句话:提出聚焦多态 CBPV 演算,证明计算完备性,并用聚焦语境建立上下文等价与完全抽象。

聚焦是证明论中利用类型信息剪除证明搜索非必要非确定性的技术;经 Curry-Howard 对应,聚焦推导对应正规形式的项。本文研究如何用聚焦推理上下文等价与完全抽象。作者提出聚焦的多态 call-by-push-value(CBPV)演算,证明计算完备性:每个良类型项都存在 βη 等价的聚焦项。该结果精化了建立上下文等价所需的情境引理,只须考虑聚焦语境。文章展示了聚焦在程序等价(含自由定理)证明中的应用,并证明纯全 CBPV 到带发散与简单效应类型语言的翻译是完全抽象的,给出一个陈述简单但此前难解问题的新解法。

问题
如何利用证明论中的聚焦技术来推理语言中的上下文等价与完全抽象。
方法
提出聚焦的多态 call-by-push-value 演算,证明每个良类型项都有 βη 等价的聚焦项,并据此精化情境引理、限定聚焦语境。
评估
通过证明程序等价(包括自由定理)以及纯全 CBPV 到含发散和简单效应类型语言翻译的完全抽象来演示方法。
原文摘要(Abstract)

Focusing is a technique from proof theory that exploits type information to prune inessential nondeterminism from proof search procedures. Viewed through the lens of the Curry-Howard correspondence, a focused typing derivation yields terms in normal form. This paper explores how to exploit focusing for reasoning about contextual equivalences and full abstraction. We present a focused polymorphic call-by-push-value calculus and prove a computational completeness result: for every well-typed term, there exists a focused term that is βη-equivalent to it. This completeness result yields a powerful way to refine the context lemmas for establishing contextual equivalences, cutting down the set that must be considered to just focused contexts. The paper demonstrates the application of focusing to establish program equivalences, including free theorems. It also uses focusing to prove full abstraction of a translation of the pure, total call-by-push-value language into a language with divergence and simple effect types, yielding a novel solution to a simple-to-state, but hitherto difficult to solve problem.

链接与引用

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

BibTeX
@article{RiouxZ20,
  title = {Computation focusing},
  author = {Nick Rioux and Steve Zdancewic},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {4},
  number = {ICFP},
  year = {2020},
  doi = {10.1145/3408977}
}