Greedy Implicit Bounded Quantification
Chen Cui, Shengyi Jiang, Bruno C. d. S. Oliveira
Abstract
Mainstream object-oriented programming languages such as Java, Scala, C#, or TypeScript have polymorphic type systems with subtyping and bounded quantification. Bounded quantification, despite being a pervasive and widely used feature, has attracted little research work on type-inference algorithms to support it. A notable exception is local type inference, which is the basis of most current implementations of type inference for mainstream languages. However, support for bounded quantification in local type inference has important restrictions, and its non-algorithmic specification is complex.
In this paper, we present a variant of kernel 𝐹 ≤ , which is the canonical calculus with bounded quantification, with implicit polymorphism. Our variant, called 𝐹 𝑏 ≤ , comes with a declarative and an algorithmic formulation of the type system. The declarative type system is based on previous work on bidirectional typing for predicative higher-rank polymorphism and a greedy approach to implicit instantiation. This allows for a clear declarative specification where programs require few type annotations and enables implicit polymorphism where applications omit type parameters. Just as local type inference, explicit type applications are also available in 𝐹 𝑏 ≤ if desired. This is useful to deal with impredicative instantiations, which would not be allowed otherwise in 𝐹 𝑏 ≤ . Due to the support for impredicative instantiations, we can obtain a completeness result with respect to kernel 𝐹 ≤ , showing that all the well-typed kernel 𝐹 ≤ programs can type-check in 𝐹 𝑏 ≤ . The corresponding algorithmic version of the type system is shown to be sound, complete, and decidable. All the results have been mechanically formalized in the Abella theorem prover.
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.
6 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
- A Lightweight Type-and-Effect System for Invalidation Safety: Tracking Permanent and Temporary Invalidation with Constraint-Based Subtype Inference cites MLstruct: principal type inference in a Boolean algebra of structural types
- A Lightweight Type-and-Effect System for Invalidation Safety: Tracking Permanent and Temporary Invalidation with Constraint-Based Subtype Inference cites When Subtyping Constraints Liberate: A Novel Type Inference Approach for First-Class Polymorphism
- Bidirectional Higher-Rank Polymorphism with Intersection and Union Types cites MLstruct: principal type inference in a Boolean algebra of structural types
- Bidirectional Higher-Rank Polymorphism with Intersection and Union Types cites When Subtyping Constraints Liberate: A Novel Type Inference Approach for First-Class Polymorphism
- Escape with Your Self: Sound and Expressive Bidirectional Typing with Avoidance for Reachability Types cites A Lightweight Type-and-Effect System for Invalidation Safety: Tracking Permanent and Temporary Invalidation with Constraint-Based Subtype Inference
- Escape with Your Self: Sound and Expressive Bidirectional Typing with Avoidance for Reachability Types cites MLstruct: principal type inference in a Boolean algebra of structural types
- Escape with Your Self: Sound and Expressive Bidirectional Typing with Avoidance for Reachability Types cites Recursive Subtyping for All
- When Subtyping Constraints Liberate: A Novel Type Inference Approach for First-Class Polymorphism cites MLstruct: principal type inference in a Boolean algebra of structural types
Cited by top-tier papers6
- 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
- A Lightweight Type-and-Effect System for Invalidation Safety: Tracking Permanent and Temporary Invalidation with Constraint-Based Subtype InferenceCunyuan Gao, Lionel ParreauxOOPSLA 2025 · 4 citations
- Modal Effect TypesWenhao Tang, Leo White, Stephen Dolan, Daniel Hillerström et al.OOPSLA 2025 · 4 citations
- Bidirectional Higher-Rank Polymorphism with Intersection and Union TypesShengyi Jiang, Chen Cui, Bruno C. d. S. OliveiraPOPL 2025 · 2 citations
- Escape with Your Self: Sound and Expressive Bidirectional Typing with Avoidance for Reachability TypesSonglin Jia, Guannan Wei, Siyuan He, Yuyan Bao et al.PLDI 2026 · 1 citation
Builds on2
Related papers
- Local Contextual Type InferenceXu Xue, Chen Cui, Shengyi Jiang, Bruno C. d. S. OliveiraPOPL 2026
- FreezeML: complete and easy type inference for first-class polymorphismFrank Emrich, Sam Lindley, Jan Stolarek, James Cheney et al.PLDI 2020 · 13 citations
- Resolution as intersection subtyping via Modus PonensKoar Marntirosian, Tom Schrijvers, Bruno C. d. S. Oliveira, Georgios KarachaliasOOPSLA 2020 · 5 citations
- A case for DOT: theoretical foundations for objects with pattern matching and GADT-style reasoningAleksander Boruch-Gruszecki, Radoslaw Wasko, Yichen Xu, Lionel ParreauxOOPSLA 2022 · 4 citations
- First-Class Refinement Types for ScalaMatt Bovel, Viktor Kunčak, Martin OderskyOOPSLA 2026
