paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Refinement Composition Logic

精化组合逻辑(RCL)
ICFP 8(ICFP)2024匹配度 2/10 · 论文属于程序验证与精化组合逻辑,使用分离逻辑蕴涵和Coq形式化,但未涉及LLM/Agent、浮点程序分析或贝叶斯程序分析,与用户画像中PL与AI交叉的核心方向没有直接关联。引用 1 inbox
Youngju Song, Dongjae Lee
dblp: 2026-09-10crossref: 2026-09-10

AI 速览

一句话:将精化组合问题对应到分离逻辑蕴涵证明,提出RCL并揭示新验证策略。

程序验证中常用精化(refinement)来证明实现满足数学规约,而整体精化通常由多个小精化组合而成。本文关注如何组合这些精化。作者发现,组合精化与在现代分离逻辑中证明蕴涵之间存在新颖对应关系:该对应一方面可复用分离逻辑的工具与抽象构造,简化组合证明;另一方面揭示了新的验证策略。为建立这一对应,论文创新性地使用天使非确定性(angelic non-determinism)应对关键挑战。基于该对应,作者提出 RCL(Refinement Composition Logic),一个专门用于组合精化的逻辑。所有结果均在 Coq 中形式化。

问题
如何通过组合多个“小”精化来建立整体实现精化数学规约的证明。
方法
发现精化组合与分离逻辑蕴涵证明之间的对应,利用天使非确定性建立该对应,并提出专用逻辑 RCL。
评估
所有结果均在 Coq 中形式化;该对应可复用分离逻辑工具与抽象构造,简化组合证明并揭示新的验证策略。
原文摘要(Abstract)

One successful approach to verifying programs is refinement, where one establishes that the implementation ( e.g. , in C) behaves as specified in its mathematical specification. In this approach, the end result (a whole implementation refines a whole specification) is often established via composing multiple “small” refinements. In this paper, we focus on the task of composing refinements. Our key observation is a novel correspondence between the task of composing refinements and the task of proving entailments in modern separation logic. This correspondence is useful. First, it unlocks tools and abstract constructs developed for separation logic, greatly streamlining the composition proof. Second, it uncovers a fundamentally new verification strategy. We address the key challenge in establishing the correspondence with a novel use of angelic non-determinism . Guided by the correspondence, we develop RCL (Refinement Composition Logic) , a logic dedicated to composing refinements. All our results are formalized in Coq.

链接与引用

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

BibTeX
@article{SongL24,
  title = {Refinement Composition Logic},
  author = {Youngju Song and Dongjae Lee},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {8},
  number = {ICFP},
  year = {2024},
  doi = {10.1145/3674645}
}