paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Bimodels and Biorthogonality for Abstract Machines

抽象机器的双模型与双正交
ICFP 10(ICFP)2026匹配度 2/10 · 该论文属于程序语言形式语义与定理证明,研究抽象机器的双模型、双正交语义与Agda机械化,未涉及LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析。虽然与形式化验证有理论背景关联,但并非用户画像中‘AI→PL’或‘PL→AI’的核心交叉方向。引用 0 inbox
April Tune, G. A. Kavvos
crossref: 2026-09-10

AI 速览

一句话:为抽象机器提出双模型与双正交语义框架,统一证明 CK/CEK 机器的重要性质与模拟关系。

论文为抽象机器建立组合式语义,以 call-by-push-value 的 CK/CEK 机器为主要操作语义。作者引入 bimodel,为程序和栈分别提供指称,并进一步提出 environment bimodel 以处理闭包。每个模型都有句法实例(由机器构造)和集合论实例(作为指称语义)。借助双正交(biorthogonality),论文在模型上定义逻辑关系,并证明对模型与观察方式参数化的基本引理。不同实例化可导出 canonicity、adequacy、操作外延性、内部完全抽象,以及关联 CK 与 CEK 机器的一阶模拟定理。全部结果在 Agda 中机器化验证。

问题
如何以抽象机器作为主要操作语义,为其提供组合式指称语义,并统一导出可靠性与不同机器之间的关系。
方法
引入 bimodel 与 environment bimodel,分别指称程序、栈和闭包;构造句法与集合论实例,并利用双正交定义逻辑关系,证明参数化基本引理。
评估
通过不同实例化证明 canonicity、adequacy、操作外延性、内部完全抽象及 CK/CEK 一阶模拟定理;全部结果在 Agda 中机器化。
原文摘要(Abstract)

We develop a compositional semantics for abstract machines, focusing on CK/CEK machines for call-by-push-value. Taking abstract machines as the primary operational semantics, we introduce bimodels, which give denotations to both programs and stacks, and environment bimodels, which extend the construction to closures. Each has a syntactic instance, built from the machine itself, and a set-theoretic instance that serves as a denotational semantics. Using biorthogonality, we define logical relations over these models and prove fundamental lemmata that are parametric in the choice of model and observation. Different instantiations yield canonicity, adequacy, operational extensionality, internal full abstraction, and a first-order simulation theorem relating the CK and CEK machines. All results are mechanized in Agda.

链接与引用

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

BibTeX
@article{TuneK26,
  title = {Bimodels and Biorthogonality for Abstract Machines},
  author = {April Tune and G. A. Kavvos},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {10},
  number = {ICFP},
  year = {2026},
  doi = {10.1145/3828686}
}