paperbot · PL 论文追踪

全部论文 待读 收藏

P2 On polymorphic gradual typing

论多态渐进类型
ICFP 1(ICFP)2017匹配度 1/10 · 论文研究参数多态的渐进类型及其形式化语义,属于纯类型系统理论,与用户关注的 PL 与 AI/LLM 交叉、浮点程序分析、贝叶斯程序分析等方向均无直接关联。引用 47 inbox
Yuu Igarashi, Taro Sekiyama, Atsushi Igarashi
dblp: 2026-09-10crossref: 2026-09-10

AI 速览

一句话:研究参数多态的渐进类型,提出 System F_G 及其多态 blame 演算翻译,并证明若干 refined criteria。

本文研究将渐进类型扩展到参数多态,并检验其理论性质。作者提出 System F_G:System F 的渐进类型扩展,含动态类型与新类型一致性关系;其区分静态类型变量与渐进类型变量,使静态代码执行时无需像先前演算那样管理类型名。随后将 F_G 翻译到新的多态 blame 演算 System F_C。论文证明 F_G 满足 Siek 等 refined criteria 的大部分性质,包括类型与语义在静态/动态语言上的保守性、类型安全、blame-subtyping 定理,以及除语义层面外最难的 gradual guarantee;并说明证明 gradual guarantee 的关键猜想可归结为 Ahmed 等提出的 Jack-of-All-Trades 性质。

问题
如何将渐进类型扩展到参数多态,并满足保守性、类型安全、blame 子类型与 gradual guarantee 等 refined criteria。
方法
设计渐进类型演算 System F_G 与多态 blame 演算 System F_C,区分静态/渐进类型变量,并给出 F_G 到 F_C 的翻译。
评估
以理论证明评估:证明 System F_G 的保守性、类型安全、blame-subtyping 及大部分 gradual guarantee,并将关键猜想联系到 Jack-of-All-Trades 性质。
原文摘要(Abstract)

We study an extension of gradual typing—a method to integrate dynamic typing and static typing smoothly in a single language—to parametric polymorphism and its theoretical properties, including conservativity of typing and semantics over both statically and dynamically typed languages, type safety, blame-subtyping theorem, and the gradual guarantee—the so-called refined criteria, advocated by Siek et al. We develop System F G , which is a gradually typed extension of System F with the dynamic type and a new type consistency relation, and translation to a new polymorphic blame calculus System F C , which is based on previous polymorphic blame calculi by Ahmed et al. The design of System F G and System F C , geared to the criteria, is influenced by the distinction between static and gradual type variables, first observed by Garcia and Cimini. This distinction is also useful to execute statically typed code without incurring additional overhead to manage type names as in the prior calculi. We prove that System F G satisfies most of the criteria: all but the hardest property of the gradual guarantee on semantics. We show that a key conjecture to prove the gradual guarantee leads to the Jack-of-All-Trades property, conjectured as an important property of the polymorphic blame calculus by Ahmed et al.

链接与引用

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

BibTeX
@article{IgarashiSI17,
  title = {On polymorphic gradual typing},
  author = {Yuu Igarashi and Taro Sekiyama and Atsushi Igarashi},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {1},
  number = {ICFP},
  year = {2017},
  doi = {10.1145/3110284}
}