paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Logical relations for coherence of effect subtyping

效应子类型一致性的逻辑关系
LMCS vol.Volume 14, Issue 12018匹配度 1/10 · 该论文属于纯形式语义与定理证明(逻辑关系、效应子类型、Coq 机器化验证),未涉及 LLM/Agent、静态分析在 ML/Agentic 程序中的应用、浮点程序分析或贝叶斯程序分析,与当前研究画像的核心交叉方向几乎无关。引用 0 inbox
Dariusz Biernacki, Piotr Polesiuk
crossref: 2026-09-10

AI 速览

一句话:提出异构双正交步进索引逻辑关系,证明效应子类型下强制语义的一致性,并机器化验证选择性 CPS 翻译。

带子类型的编程语言的强制(coercion)语义通常定义在类型推导而非类型判断上,因此必须保证一致性:同一判断的不同推导得到相同语义。本文提出异构、双正交、步进索引的逻辑关系,用于证明这类强制语义的一致性。为展示方法有效性,作者研究带定界续延与控制效应子类型的按值调用 lambda 演算,给出类型导向的选择性 CPS 翻译,并用该逻辑关系证明其强制语义一致。文章还包含 Coq 形式化,依赖一种用于步进索引推理的新型浅嵌入逻辑。

问题
带子类型的强制语义定义在类型推导上,可能因推导不同而产生语义歧义;核心问题是证明其一致性(coherence)。
方法
提出异构、双正交、步进索引的逻辑关系,并用于证明类型导向选择性 CPS 翻译的强制语义一致。
评估
在带定界续延和控制效应子类型的按值调用 lambda 演算上进行案例研究,并提供基于新步进索引浅嵌入逻辑的 Coq 形式化。
原文摘要(Abstract)

A coercion semantics of a programming language with subtyping is typically defined on typing derivations rather than on typing judgments. To avoid semantic ambiguity, such a semantics is expected to be coherent, i.e., independent of the typing derivation for a given typing judgment. In this article we present heterogeneous, biorthogonal, step-indexed logical relations for establishing the coherence of coercion semantics of programming languages with subtyping. To illustrate the effectiveness of the proof method, we develop a proof of coherence of a type-directed, selective CPS translation from a typed call-by-value lambda calculus with delimited continuations and control-effect subtyping. The article is accompanied by a Coq formalization that relies on a novel shallow embedding of a logic for reasoning about step-indexing.

链接与引用

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

BibTeX
@article{paperbot429,
  title = {Logical relations for coherence of effect subtyping},
  author = {Dariusz Biernacki and Piotr Polesiuk},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 14, Issue 1},
  year = {2018},
  doi = {10.23638/lmcs-14(1:11)2018}
}