paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Bialgebraic Reasoning on Higher-order Program Equivalence

高阶程序等价性的双代数推理
LICS Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science2024匹配度 2/10 · 论文研究高阶程序等价、逻辑关系与双代数语义,属于纯 PL 形式语义理论;与用户画像核心的 LLM/Agent 与静态分析/形式化验证交叉、浮点程序分析、贝叶斯程序分析均无直接关联。引用 6 inbox
Sergey Goncharov, Stefan Milius, Stelios Tsampas, Henning Urbat
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:提出高阶数学操作语义下逻辑关系的通用构造,并证明其对上下文等价自动可靠。

逻辑关系是证明高阶语言上下文等价的核心方法,但通常需针对每种语言或等价概念单独构建理论。本文将(步进索引)逻辑关系的构造提升到高阶数学操作语义(HOMOS)这一高度参数化的范畴框架中,给出通用构造。主要结果:若语言的弱操作模型构成 lax 双代数,则所构造的逻辑关系对上下文等价自动可靠。该抽象理论可实例化到组合逻辑、带递归类型的 λ 演算,以及不同风格的上下文等价。

问题
如何为高阶语言及其不同上下文等价概念提供统一、可复用的逻辑关系推理方法,避免逐例构建新理论。
方法
在高阶数学操作语义(HOMOS)框架中通用地构造步进索引逻辑关系,并用弱操作模型的 lax 双代数条件建立可靠性。
评估
通过范畴论证明给出一般可靠性定理,并将抽象理论实例化到组合逻辑、带递归类型的 λ 演算及多种上下文等价。
原文摘要(Abstract)

Logical relations constitute a key method for reasoning about contextual equivalence of programs in higher-order languages. They are usually developed on a per-case basis, with a new theory required for each variation of the language or of the desired notion of equivalence. In the present paper we introduce a general construction of (step-indexed) logical relations at the level of Higher-Order Mathematical Operational Semantics, a highly parametric categorical framework for modeling the operational semantics of higherorder languages. Our main result states that for languages whose weak operational model forms a lax bialgebra, the logical relation is automatically sound for contextual equivalence. Our abstract theory is shown to instantiate to combinatory logics and λ-calculi with recursive types, and to different flavours of contextual equivalence.

链接与引用

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

BibTeX
@inproceedings{0001M0U24,
  title = {Bialgebraic Reasoning on Higher-order Program Equivalence},
  author = {Sergey Goncharov and Stefan Milius and Stelios Tsampas and Henning Urbat},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662099}
}