FreezeML: complete and easy type inference for first-class polymorphism
Frank Emrich, Sam Lindley, Jan Stolarek, James Cheney, Jonathan Coates
Abstract
ML is remarkable in providing statically typed polymorphism without the programmer ever having to write any type annotations. The cost of this parsimony is that the programmer is limited to a form of polymorphism in which quantifiers can occur only at the outermost level of a type and type variables can be instantiated only with monomorphic types.
Type inference for unrestricted System F-style polymorphism is undecidable in general. Nevertheless, the literature abounds with a range of proposals to bridge the gap between ML and System F.
We put forth a new proposal, FreezeML, a conservative extension of ML with two new features. First, let-and lambdabinders may be annotated with arbitrary System F types. Second, variable occurrences may be frozen, explicitly disabling instantiation. FreezeML is equipped with type-preserving translations back and forth between System F and admits a type inference algorithm, an extension of algorithm W, that is sound and complete and which yields principal types.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
5 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Bidirectional Higher-Rank Polymorphism with Intersection and Union Types cites When Subtyping Constraints Liberate: A Novel Type Inference Approach for First-Class Polymorphism
- Local Contextual Type Inference cites Bidirectional Higher-Rank Polymorphism with Intersection and Union Types
- Local Contextual Type Inference cites When Subtyping Constraints Liberate: A Novel Type Inference Approach for First-Class Polymorphism
- Practical Type Inference with Levels cites When Subtyping Constraints Liberate: A Novel Type Inference Approach for First-Class Polymorphism
Cited by top-tier papers5
- When Subtyping Constraints Liberate: A Novel Type Inference Approach for First-Class PolymorphismLionel Parreaux, Aleksander Boruch-Gruszecki, Andong Fan, Chun Yin ChauPOPL 2024 · 13 citations
- Structural Subtyping as Parametric PolymorphismWenhao Tang, Daniel Hillerström, James McKinna, Michel Steuwer et al.OOPSLA 2023 · 3 citations
- Practical Type Inference with LevelsAndong Fan, Han Xu, Ningning XiePLDI 2025 · 3 citations
- Bidirectional Higher-Rank Polymorphism with Intersection and Union TypesShengyi Jiang, Chen Cui, Bruno C. d. S. OliveiraPOPL 2025 · 2 citations
- Local Contextual Type InferenceXu Xue, Chen Cui, Shengyi Jiang, Bruno C. d. S. OliveiraPOPL 2026
Related papers
- Principal Type Inference under a Prefix: A Fresh Look at Static OverloadingDaan Leijen, Wenjia YePLDI 2025 · 2 citations
- Polymorphic types and effects with Boolean unificationMagnus Madsen, Jaco van de PolOOPSLA 2020 · 18 citations
- The Undecidability of System F Typability and Type Checking for ReductionistsAndrej DudenhefnerLICS 2021 · 1 citation
- Greedy Implicit Bounded QuantificationChen Cui, Shengyi Jiang, Bruno C. d. S. OliveiraOOPSLA 2023 · 9 citations
- Polymorphic Type Inference for Dynamic LanguagesGiuseppe Castagna, Mickaël Laurent, Kim NguyenPOPL 2024 · 12 citations
