paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Recursive Subtyping for All

面向所有类型的递归子类型
POPL 7(POPL)2023匹配度 1/10 · 该论文研究递归类型与有界量化的子类型理论及 Coq 形式化,属于程序语言类型论基础,与用户关注的 LLM/Agent 结合静态分析、浮点程序分析、贝叶斯程序分析等方向无直接关联。虽然涉及形式化验证,但并非利用 LLM/Agent 改进验证或静态分析。引用 8 inbox
Litao Zhou, Yaoda Zhou, Bruno C. d. S. Oliveira
crossref: 2026-09-10

AI 速览

一句话:提出 F≤μ,将 iso-recursive 类型与有界量化结合,证明子类型可判定、传递且保守,并在 Coq 中形式化。

递归类型与有界量化广泛存在于 Java、C#、Scala 和 TypeScript 等语言中,但二者与子类型的交互长期难以同时获得可判定性、传递性、保守性以及可靠完备的算法化。本文提出 kernel F≤ 的扩展 F≤μ,加入 iso-recursive 类型,并采用新近提出的 nominal unfolding 规则扩展子类型关系。此外,F≤μ 还泛化了 kernel F≤ 的有界量化规则以接受等价边界,并引入受 Abadi、Cardelli 和 Viswanathan 启发的 structural folding/unfolding 规则,从而增强表达力并支持更多应用。作者给出了类型可靠性、子类型的传递性与可判定性、F≤μ 对 F≤ 的保守性,以及可靠完备的算法化子类型判定。文章还研究了带下界量化的扩展 F≤≥μ,且所有结果均已在 Coq 定理证明器中形式化。

问题
递归类型、有界量化与子类型的交互长期缺乏一个同时具有可判定性、子类型传递性、保守性和可靠完备算法化的简单基础演算。
方法
在 kernel F≤ 上加入 iso-recursive 类型与 nominal unfolding 子类型规则,并泛化有界量化以接受等价边界,同时引入 structural folding/unfolding 规则,给出算法化子类型判定并扩展到下界量化。
评估
证明类型可靠性、子类型传递性与可判定性、F≤μ 对 F≤ 的保守性及算法化子类型关系的可靠完备性,并用 Coq 对所有结果进行机器化验证。
原文摘要(Abstract)

Recursive types and bounded quantification are prominent features in many modern programming languages, such as Java, C#, Scala or TypeScript. Unfortunately, the interaction between recursive types, bounded quantification and subtyping has shown to be problematic in the past. Consequently, defining a simple foundational calculus that combines those features and has desirable properties, such as decidability , transitivity of subtyping, conservativity and a sound and complete algorithmic formulation has been a long time challenge. This paper presents an extension of kernel ‍ F ≤ , called F ≤ µ , with iso-recursive types. F ≤ is a well-known polymorphic calculus with bounded quantification. In F ≤ µ we add iso-recursive types, and correspondingly extend the subtyping relation with iso-recursive subtyping using the recently proposed nominal unfolding rules. We also add two smaller extensions to F ≤ . The first one is a generalization of the kernel ‍ F ≤ rule for bounded quantification that accepts equivalent rather than equal bounds. The second extension is the use of so-called structural folding/unfolding rules, inspired by the structural unfolding rule proposed by Abadi, Cardelli, and Viswanathan [1996]. The structural rules add expressive power to the more conventional folding/unfolding rules in the literature, and they enable additional applications. We present several results, including: type soundness; transitivity and decidability of subtyping; the conservativity of F ≤ µ over F ≤ ; and a sound and complete algorithmic formulation of F ≤ µ . Moreover, we study an extension of F ≤ µ , called F ≤≥ µ , which includes lower bounded quantification in addition to the conventional (upper) bounded quantification of F ≤ . All the results in this paper have been formalized in the Coq theorem prover.

链接与引用

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

BibTeX
@article{paperbot2080,
  title = {Recursive Subtyping for All},
  author = {Litao Zhou and Yaoda Zhou and Bruno C. d. S. Oliveira},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {7},
  number = {POPL},
  year = {2023},
  doi = {10.1145/3571241}
}