Deciphering Wildcards in Java: Unraveling Type System Mysteries
Exploring the complexities of wildcards in Java's type system through examples and explanations. The use of wildcards, challenges with polymorphism, subtyping algorithms, and open problems are discussed in depth. Unveil the mysteries behind wildcards to enhance your Java programming skills.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Taming Wildcards in Java s Type System Ross Tate Alan Leung Sorin Lerner University of California, San Diego
Why Use Wildcards? Need use-site variance What about List Integer ? Used only once Not covariant long average(List nums) { long sum = 0; for (Object num : nums) sum += ((Number)num).longValue(); return sum / nums.size(); } } } } long average(List Number nums) { long sum = 0; for (Number num : nums) sum += num.longValue(); return sum / nums.size(); return sum / nums.size(); return sum / nums.size(); P extends Number long average(List P nums) { long sum = 0; for (Number num : nums) sum += num.longValue(); sum += num.longValue(); long average(List ? extends Number nums) { long sum = 0; for (Number num : nums) Runtime Type Cast
Why Use Wildcards? Inexpressible with polymorphism P void addSuperclasses(Class P c, List ? super Class ? super P list) { Class ? super P sup = c.getSuperclass(); if (sup != null) { list.add(sup); addSuperclasses(sup, list); } } X : X :> P. Class X Untypeable with use-site variance
Open Problems with Wildcards Solved No known subtyping algorithm Subtyping rules are overly restrictive Join algorithm is incomplete Type checker is non-deterministic Type checker can affect program semantics
Broken Subtyping Algorithm class Numbers P extends Number extends ArrayList P {} List Numbers ? <: List ? extends List ? extends Number No javac Java Yes class C P extends D D ? super C L P {} C X <: D ? super C X Stack Overflow No javac Java
False Negatives class Numbers P extends Number extends ArrayList P {} List ? extends List ? extends Number List ? extends List ? direct supertype List ? extends ArrayList ? direct supertype List ? extends Numbers ? direct supertype List Numbers ?
Our Algorithm Sound & Complete (if it terminates) class Numbers P extends Number extends ArrayList P {} List Numbers ? <: List ? extends List ? extends Number Instantiation Numbers ? <: List ? extends Number Opening Context Numbers X <: List ? extends Number Inheritance X <: Number List X <: List ? extends Number Instantiation X <: Number Assumption
Non-Termination Contrived class C P extends D D ? super C L P {} C X <: D ? super C X Inheritance D D ? super C L X <: D ? super C X Infinite Proof of Subtyping Instantiation C X <: D ? super C L X Inheritance D D ? super C L X <: D ? super C L X Instantiation C L X <: D ? super C L X
Restrictions Termination Guaranteed Contrived class C P extends D D ? super C L P {} Inheritance Restriction No use of ? super in the inheritance hierarchy Contrived P extends List List ? super C L P Parameter Restriction When constraining type parameters, ? super may only be used at covariant locations
No Violations of Our Restrictions Survey 9.2 Million Lines of Code Analyzed Wildcards in Inheritance Wildcards in Constraints 100000 100000 10000 10000 1000 1000 100 Only 0.1 0 10 Unconstrained Wildcards 3.7% 1 No Wildcards 20.9% No Type Arguments No Wildcards Only Unconstrained Uses ? extends 1.5% Only Unconstrained Wildcards No Type Uses ? extends Uses ? super 1.8% Arguments 72.0% Uses ? super # of Superclass Declarations All at covariant locations
Summary of Contributions Sound and Complete Subtyping Algorithm given practical language restrictions Theory of Existential Types design of implicit constraints Techniques for Type-Argument Inference lazy joins for wildcards Fixes to the Type System improved equivalence and intersections Compatible Extensions to Java mixing use-site and declaration-site variance
