paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Constrained type families

受约束的类型族
ICFP 1(ICFP)2017匹配度 1/10 · 该论文聚焦 Haskell 类型族偏性、限定类型与一致性证明,属于纯类型系统/语言设计理论,未涉及 LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析,与用户当前研究画像的核心交叉方向基本无关。引用 11 inbox
J. Garrett Morris, Richard A. Eisenberg
dblp: 2026-09-10crossref: 2026-09-10arxiv: 2026-09-10

AI 速览

一句话:用限定类型为类型族计算标注定义域,在保持表达力与类型安全的同时支持偏性,并给出闭类型族语言的一致性证明。

现有类型级计算框架通常要求或默认计算是全函数,例如 Haskell 类型族虽模块化且表达力强,却隐含假设其为全函数,从而引入无意义类型,并使类型族及其扩展的元理论复杂化。本文提出一种支持偏性的类型级计算设计:用限定类型(qualified types)将类型级计算与其定义域谓词配对,显式刻画类型族在哪些参数上有定义。该方法自然对应类型族的偏函数直觉,在不牺牲表达力与类型安全的前提下简化元理论。作为证据,作者给出首个含闭类型族的语言的完整一致性证明。

问题
现有类型级计算框架要求或默认全函数性,Haskell 类型族隐含全函数假设,导致无意义类型和元理论复杂化。
方法
提出用 qualified types 将类型级计算与刻画其定义域的谓词配对,从而显式支持偏性并简化元理论。
评估
通过给出首个带闭类型族的语言的完整一致性证明来验证设计,并说明其保持表达力与类型安全。
原文摘要(Abstract)

We present an approach to support partiality in type-level computation without compromising expressiveness or type safety. Existing frameworks for type-level computation either require totality or implicitly assume it. For example, type families in Haskell provide a powerful, modular means of defining type-level computation. However, their current design implicitly assumes that type families are total, introducing nonsensical types and significantly complicating the metatheory of type families and their extensions. We propose an alternative design, using qualified types to pair type-level computations with predicates that capture their domains. Our approach naturally captures the intuitive partiality of type families, simplifying their metatheory. As evidence, we present the first complete proof of consistency for a language with closed type families.

链接与引用

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

BibTeX
@article{MorrisE17,
  title = {Constrained type families},
  author = {J. Garrett Morris and Richard A. Eisenberg},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {1},
  number = {ICFP},
  year = {2017},
  doi = {10.1145/3110286}
}