ParametricPolymorphi smForJava

50 %
50 %
Information about ParametricPolymorphi smForJava
Education

Published on February 7, 2008

Author: Durante

Source: authorstream.com

Parametric Polymorphism for Java:  Parametric Polymorphism for Java Derek Rayside University of Waterloo IBM Centre for Advanced Studies The Short Answer:  The Short Answer Java Community Process JSR-14 GenericJava (GJ), then NextGen Probably not until 2002/3 … [Bracha] It’s different than C++ templates! Some changes to compiler front-ends No changes to JIT’s, optimizers, etc. Except maybe “hints” in “attributes” … [cf Verbrugge et al @ CASCON 2000] The Long Answer … :  The Long Answer … What is parametric polymorphism? Why is it good? Language Design Considerations Principles Proposals Implementation Considerations Practices Proposals What is it?:  What is it? Polymorphism “Works” for things of different types. Some type information under-specified. Subtype Polymorphism The “different types” must be related by the “subtype” relation (usually hierarchical). Parametric Polymorphism The “different types” may be unrelated. A Simple Example …:  A Simple Example … Without Param. Poly. // create a collection // just holds “objects” Vector v = new Vector(); // add an object v.add(new String(“hello”)); // retrieve the object // requires a cast String s = (String) v.get(0); With Param. Poly. // create a collection // holds Strings! (expressiveness) Vector v = new Vector<String>(); // add an object v.add(new String(“hello”)); // retrieve the object // no cast required! (safety) String s = v.get(0); Why is it good?:  Why is it good? Static type safety Expressive power Reduced code maintenance Execution efficiency (potentially) Language Design:  Language Design Principles Covariance & Contravariance Constrained vs Unconstrained (F-bounds) “Binary” methods Reference types vs Primitive types Proposals Pizza, GenericJava (GJ), NextGen, PMG, PolyJ Virtual Types & Structural Virtual Types Proposals and Principles:  Proposals and Principles Parameterized Types [Pizza, GJ, NextGen] structural subtyping F-bounded quantification Virtual Types [Beta, Thorup, Torgersen] covariant subtyping mutually recursive type definitions Structural Virtual Types [Thorup+Torgersen] Poly/J [Liskov + Myers] Some Syntax … :  Some Syntax … Parameterized Types Set<E> { insert(element : E) {…} } // Set<Integer> is a type! Set<Integer> s = new Set<Integer>(); Virtual Types Set { VirtualType E; insert(element : E) {…} } IntegerSet extends Set { E := Integer; } IntegerSet s = new IntegerSet(); Important Background!:  Important Background! Subclassing  Subtyping Subclassing  Subtyping Subclassing < Subtyping Subtyping is about substitutability Subtyping without subclassing in Java: interfaces arrays Variance: Co, Contra, & No:  Variance: Co, Contra, & No variance  change co-  together contra-  opposite no-  absence co-variance  change together contra-variance  change opposite no-variance  no change Variance: Co, Contra, & No:  Variance: Co, Contra, & No Co-variant No-variant Contra-variant Variance: Co, Contra, & No:  Variance: Co, Contra, & No Vehicle drive(Road) Variance Summary:  Variance Summary Co-variance method return types method parameter types e.g. drive(RaceTrack) violates substitutability Contra-variance method parameter types e.g. drive(Mud) method return types Variance in Java:  Variance in Java Java is no-variant, for the most part … Arrays are co-variant Method return types are contra-variant but not according to the language spec! and not according to compiler front-ends! most VM’s allow contra-variant return types actually, most VM’s just don’t check … this is exploited by Pizza and possibly by GJ Variance and Java Arrays:  Variance and Java Arrays class Point { int x, y; } class ColouredPoint extends Point { int color; } ColouredPoint[] colouredPointArray = new ColoredPoint[10]; Point[] pointArray = colouredPointArray; System.out.println(pointArray[1] == null); // true pointArray[0] = new Point(); // ArrayStoreException Variance and Java Arrays:  Variance and Java Arrays Array<E> PointArray = Array<Point> ColouredPointArray = Array<ColouredPoint> Co-variant subtyping: ColouredPointArray  PointArray Array<ColouredPoint>  Array<Point> Variance and Java Arrays:  Variance and Java Arrays Arrays have parametric polymorphism “array” is the generic type the type of things in the array is the type parameter Java arrays are said to have covariant subtyping because ColouredPoint[]  Point[] if ColouredPoint  Point Structural Subtyping:  Structural Subtyping Collection<Vehicle> Set<Vehicle> Proposals and Principles:  Proposals and Principles Parameterized Types [Pizza, GJ, NextGen] structural subtyping F-bounded quantification Virtual Types [Beta, Thorup, Torgersen] covariant subtyping mutually recursive type definitions Structural Virtual Types [Thorup+Torgersen] Poly/J [Liskov + Myers] Bounded Type Parameters:  Bounded Type Parameters class Pair<A> { A x; A y; } class Map<E extends Pair> { … } Type parameters: A and E A is unbounded E is bounded by Pair “Binary” Methods:  “Binary” Methods lessThan is a “binary” method x.lessThan(y) x and y of same type! How to type-check that x and y have the same type? think of equals(Object obj) usually you use an instanceof test on obj interface Ordered<A> { boolean lessThan(A obj); } class OrderedInt implements Ordered<OrderedInt> { int i; boolean lessThan(OrderedInt j) { return i < j.i; } } F-bounds:  F-bounds B implements Ordered<B> B appears in it’s own bound! That’s an “f-bound” Necessary to type-check x.lessThan(y) In general, f-bounds require structural subtyping. You may not yet see why the f-bound is necessary … So we’ll try to do without it and see where we run into problems … class Pair<B implements Ordered<B>> { B x; B y; B min() { if (x.lessThan(y)) return x; else return y; } } Life without F-bounds:  Life without F-bounds B implements Ordered<C> B’s not in the bound no longer an f-bound We know that Pair.x and Pair.y are of the same type. But we don’t know if that type can be compared to itself! e.g. Int can only be compared to Real; not to Int e.g. Real can be compared with itself, so it’s ok We can’t type-check x.lessThan(y) class Pair<B implements Ordered<C>> { B x; B y; B min() { if (x.lessThan(y)) return x; else return y; } } class Int implements Ordered<Real> {…} class Real implements Ordered<Real> {…} Enough Type Theory Already!:  Enough Type Theory Already! variance: co-, contra-, and no- structural subtyping f-bounds and binary methods C++ templates are just macro-expansion in comparison … the main theoretical problem with C++ is that type-checking is done after expansion Language Implementation:  Language Implementation Practices Modify the VM or not? Modify the class file format or not? Heterogeneous vs Homogeneous translation Implementations using Reflection Proposals Agesen97, Poly/J, PMG, Pizza, GJ, NextGen Sun + Stanford 97:  Sun + Stanford 97 Small modifications to class files Class loader performs heterogeneous translation on the fly No modifications to the VM This will not be the official proposal. [Agesen, Freund, Mitchel] Poly/J [MIT]:  Poly/J [MIT] Small modifications to class files Small modifications to VM Uses “where” clauses instead of f-bounds (i.e. more elaborate structural subtyping) [Liskov, Myers, Banks] Poor Man’s Genericity:  Poor Man’s Genericity Hetergeneous translation Pre-processor for syntax One change to Sun’s compiler front-end No VM modifications [Bokowski, Dahm] Pizza:  Pizza No VM modifications Heterogeneous translation Homogeneous translation Slightly more complicated than GJ [Wadler, Odersky, Bracha] Generic Java (GJ):  Generic Java (GJ) No VM modifications No class file modifications Backwards compatible lets existing code be “retro-fitted” Forwards compatible will work with “NextGen” Simpler than Pizza Loss of run-time type information NextGen:  NextGen No VM modifications No class file modifications Not backwards compatible Maintains runtime type information Complicated! [Cartwright, Steele] The End:  The End Thank you! Questions?

Add a comment

Related presentations