paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A quick look at impredicativity

Quick Look:非直谓类型推断
ICFP 4(ICFP)2020匹配度 3/10 · 论文属于纯编程语言类型系统方向,讨论 GHC 中的非直谓类型推断与工程实现,与用户核心关注的 PL 与 AI/LLM/Agent 交叉、静态分析在 ML/Agentic 程序中的应用、浮点程序分析或贝叶斯程序分析均无直接关系。引用 32 inbox
Alejandro Serrano, Jurriaan Hage, Simon Peyton Jones, Dimitrios Vytiniotis
dblp: 2026-09-10crossref: 2026-09-10

AI 速览

一句话:提出 Quick Look 设计,在 GHC 中实现非直谓类型推断,使多态类型成为一等公民,且改动局部且兼容现有扩展。

参数多态的类型推断极为成功,但长期存在一个尴尬缺陷:多态类型本身不是一等公民,即无法直接作为参数传递或出现在类型参数位置,这被称为 impredicativity。本文提出 Quick Look,一种实用、已实现且可部署的非直谓类型推断设计。为验证该设计,作者修改了生产级 Haskell 编译器 GHC,使其支持非直谓性。所需改动适度、局部化,并且与 GHC 众多其他类型系统扩展完全兼容。该工作表明,在实际编译器中实现 impredicative 类型推断是可行的,为 Haskell 及类似语言提供了更强的表达力。

问题
参数多态类型推断中,多态类型不能作为一等公民使用(即缺少 impredicativity),限制了程序的表达力和抽象能力。
方法
提出 Quick Look,一种面向实际部署的非直谓类型推断设计,并在生产级 Haskell 编译器 GHC 中实现。
评估
通过修改 GHC 并验证改动量小、局部化且与现有类型系统扩展完全兼容,证明设计的实用性和可部署性。
原文摘要(Abstract)

Type inference for parametric polymorphism is wildly successful, but has always suffered from an embarrassing flaw: polymorphic types are themselves not first class. We present Quick Look, a practical, implemented, and deployable design for impredicative type inference. To demonstrate our claims, we have modified GHC, a production-quality Haskell compiler, to support impredicativity. The changes required are modest, localised, and are fully compatible with GHC's myriad other type system extensions.

链接与引用

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

BibTeX
@article{SerranoHJV20,
  title = {A quick look at impredicativity},
  author = {Alejandro Serrano and Jurriaan Hage and Simon Peyton Jones and Dimitrios Vytiniotis},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {4},
  number = {ICFP},
  year = {2020},
  doi = {10.1145/3408971}
}