paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Local refinement typing

局部精化类型化
ICFP 1(ICFP)2017匹配度 3/10 · 该论文属于精化类型推断与SMT程序验证,虽与静态分析/形式化验证相关,但未涉及用户核心关注的LLM/Agent与静态分析交叉、ML/Agent程序分析、浮点程序分析或贝叶斯程序分析。引用 22 inbox
Benjamin Cosman, Ranjit Jhala
dblp: 2026-09-10crossref: 2026-09-10arxiv: 2026-09-10

AI 速览

一句话:提出 FUSION 算法实现局部精化类型推断,用 SMT 验证多态数据类型与高阶函数,显著减少模板并加速。

针对多态数据类型和高阶函数程序,现有精化类型验证通常需要大量模板,且易产生虚假告警。本文提出 FUSION 局部精化类型推断算法:程序员只需为外部导出的顶层函数以及存在递归依赖(循环依赖)的位置编写签名,FUSION 即可在可判定精化逻辑内为所有中间项可预测地合成最精确的精化类型,并借助 SMT 完成程序检查。作者实现了 FUSION,并在约 12KLOC 的 LiquidHaskell 基准上评估。在已有安全基准上,所需模板约为原先一半,速度提升近 2 倍;在新定理证明基准上,速度提升 10–50 倍,且因合成最精确类型避免虚假告警,使验证成为可能。

问题
如何减少多态数据类型与高阶函数程序精化类型验证中对人工模板与签名的依赖,并避免虚假告警,同时保持可判定性。
方法
提出 FUSION 局部精化类型推断:仅需为外部导出顶层函数和递归循环依赖处编写签名,便通过 SMT 为中间项合成最精确的可判定精化类型。
评估
在 LiquidHaskell 约 12KLOC 基准上评估:已有安全套件所需模板约减半且近 2 倍加速;新定理证明套件加速 10–50 倍,并因合成最精确类型避免误报而完成验证。
原文摘要(Abstract)

We introduce the FUSION algorithm for local refinement type inference, yielding a new SMT-based method for verifying programs with polymorphic data types and higher-order functions. FUSION is concise as the programmer need only write signatures for (externally exported) top-level functions and places with cyclic (recursive) dependencies, after which FUSION can predictably synthesize the most precise refinement types for all intermediate terms (expressible in the decidable refinement logic), thereby checking the program without false alarms. We have implemented FUSION and evaluated it on the benchmarks from the LiquidHaskell suite totalling about 12KLOC. FUSION checks an existing safety benchmark suite using about half as many templates as previously required and nearly 2 × faster. In a new set of theorem proving benchmarks FUSION is both 10 — 50 × faster and, by synthesizing the most precise types, avoids false alarms to make verification possible.

链接与引用

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

BibTeX
@article{CosmanJ17,
  title = {Local refinement typing},
  author = {Benjamin Cosman and Ranjit Jhala},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {1},
  number = {ICFP},
  year = {2017},
  doi = {10.1145/3110270}
}