paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Quotient Haskell: Lightweight Quotient Types for All

Quotient Haskell:面向所有人的轻量级商类型
POPL 8(POPL)2024匹配度 2/10 · 论文属于类型系统与程序验证,提出可用 SMT 判定证明义务的商类型及 Liquid Haskell 实现,但与用户核心关注的 PL↔AI、LLM/Agent 改进静态分析/形式化验证、浮点程序分析或贝叶斯程序分析均无直接关联。引用 3 inbox
Brandon Hewer, Graham Hutton
crossref: 2026-09-10

AI 速览

一句话:提出证明义务可由 SMT 判定的商类型,并实现为 Liquid Haskell 扩展 Quotient Haskell。

子类型与商类型是对偶的类型抽象,但子类型已被广泛显式或隐式使用,商类型除证明助手外鲜有实际应用。其推广困难的关键在于使用商类型会产生大量证明义务。本文引入一类商类型,使其证明义务可由 SMT 求解器判定,从而显著降低使用负担。作者以 Liquid Haskell 扩展的形式实现 Quotient Haskell,支持商类型,并通过该实现表明这一轻量级方案在实践中可行。

问题
商类型在证明助手之外难以实用化,主要障碍是使用时会带来大量证明义务。
方法
定义一类证明义务可由 SMT 求解器判定的商类型,并将其实现为 Liquid Haskell 的扩展 Quotient Haskell。
评估
通过实现 Quotient Haskell 并展示其对商类型的支持,论证该轻量级方案在实践中可行。
原文摘要(Abstract)

Subtypes and quotient types are dual type abstractions. However, while subtypes are widely used both explicitly and implicitly, quotient types have not seen much practical use outside of proof assistants. A key difficulty to wider adoption of quotient types lies in the significant burden of proof-obligations that arises from their use. In this article, we address this issue by introducing a class of quotient types for which the proof-obligations are decidable by an SMT solver. We demonstrate this idea in practice by presenting Quotient Haskell , an extension of Liquid Haskell with support for quotient types.

链接与引用

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

BibTeX
@article{paperbot2608,
  title = {Quotient Haskell: Lightweight Quotient Types for All},
  author = {Brandon Hewer and Graham Hutton},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {8},
  number = {POPL},
  year = {2024},
  doi = {10.1145/3632869}
}