paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A contextual formalization of structural coinduction

结构余归纳的上下文形式化
JFP vol.352025匹配度 2/10 · 该论文属于程序语言形式语义与结构余归纳证明方法,重点在余递归程序的等式推理和观察等价,与用户画像核心关注的静态分析、LLM/Agent、浮点程序分析及贝叶斯程序分析没有直接交叉;仅与形式化验证主题有非常边缘的关联。引用 0 inbox
PAUL DOWNEN, ZENA M. ARIOLA
crossref: 2026-09-10

AI 速览

一句话:提出结构余归纳的上下文形式化,为余递归程序的等式推理提供直观且相对观察等价可靠的证明方法。

结构归纳被函数式程序员和研究者广泛用于非形式推理及程序验证与语义的形式方法。本文推广其对偶——结构余归纳,用以仅依据余递归程序上下文的逻辑结构来理解它们。作者提出一种基于上下文的非形式证明方法,其风格与结构归纳证明类似,便于检查所有情况是否覆盖以及余归纳假设是否正确使用。随后,这一直观方法被形式化为一个推导程序等式的句法理论,其合理性完全依据抽象机器的计算行为建立,并相对于观察等价被证明是可靠的。

问题
余递归程序缺少像结构归纳那样直观且可靠的推理方法。
方法
将结构余归纳作为基于上下文的非形式证明技术,并形式化为由抽象机器计算行为驱动的程序等式句法理论。
评估
相对于观察等价证明该句法理论的可靠性,并说明非形式证明风格便于检查案例覆盖与余归纳假设。
原文摘要(Abstract)

Abstract Structural induction is pervasively used by functional programmers and researchers for both informal reasoning as well as formal methods for program verification and semantics. In this paper, we promote its dual—structural coinduction—as a technique for understanding corecursive programs only in terms of the logical structure of their context. We illustrate this technique as an informal method of proofs which closely match the style of informal inductive proofs, where it is straightforward to check that all cases are covered and the coinductive hypotheses are used correctly. This intuitive idea is then formalized through a syntactic theory for deriving program equalities, which is justified purely in terms of the computational behavior of abstract machines and proved sound with respect to observational equivalence.

链接与引用

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

BibTeX
@article{DownenA25,
  title = {A contextual formalization of structural coinduction},
  author = {PAUL DOWNEN and ZENA M. ARIOLA},
  journal = {Journal of Functional Programming},
  volume = {35},
  year = {2025},
  doi = {10.1017/s0956796825100026}
}