paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Explicit Refinement Types

显式精化类型
ICFP 7(ICFP)2023匹配度 3/10 · 论文属于精化类型与形式化验证的类型理论工作,与用户关注的静态分析、LLM/Agent 交叉、浮点或贝叶斯程序分析无直接关联;虽涉及形式化验证与证明工程,但未结合 LLM/Agent、工业落地或 benchmark 失效分析。引用 2 inbox
Jad Elkhaleq Ghalayini, Neel Krishnaswami
crossref: 2026-09-10

AI 速览

一句话:提出 λert 类型理论,让程序员显式嵌入精化性质的证明,从而支持量词和归纳,并用 Lean 4 证明其可靠性。

精化类型传统上通过 SMT 求解器自动检查,如 DML 与 Liquid Haskell,但受限于可判定片段,难以表达量词和归纳等丰富性质。本文提出 λert:一种支持显式证明的精化类型理论,要求并允许程序员在程序文本中嵌入性质证明,从而将验证负担从 SMT 求解转移到显式证明项。作者证明类型系统可靠:任何精化程序擦除后都是简单类型程序;再借助指称语义证明擦除后的程序满足其精化类型所要求的全部性质。所有证明均在 Lean 4 中机器化验证。该工作展示了在依赖 SMT 的自动化路线之外,如何通过显式证明支持更丰富的逻辑性质。

问题
现有精化类型系统(如 DML、Liquid Haskell)依赖 SMT 求解约束,难以支持量词和归纳等表达力更强的性质。
方法
提出 λert,允许并要求程序员在程序中嵌入性质证明,以显式证明替代 SMT 求解;通过擦除到简单类型程序以及指称语义证明类型系统可靠。
评估
评估方式是元理论证明:所有可靠性证明均在 Lean 4 中机器化验证,而非基于实现或基准测试的实验评估。
原文摘要(Abstract)

We present λ ert , a type theory supporting refinement types with <em>explicit proofs</em>. Instead of solving refinement constraints with an SMT solver like DML and Liquid Haskell, our system requires and permits programmers to embed proofs of properties within the program text, letting us support a rich logic of properties including quantifiers and induction. We show that the type system is sound by showing that every refined program erases to a simply-typed program, and by means of a denotational semantics, we show that every erased program has all of the properties demanded by its refined type. All of our proofs are formalised in Lean 4.

链接与引用

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

BibTeX
@article{paperbot1903,
  title = {Explicit Refinement Types},
  author = {Jad Elkhaleq Ghalayini and Neel Krishnaswami},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {7},
  number = {ICFP},
  year = {2023},
  doi = {10.1145/3607837}
}