CSE 3302Lecture 7: Polymorphism and generics16 September 2010Nate NystromUTAPolymorphism“poly” = many“morph” = shapeAllow a variable to contain values with different types2• OO languages support subtype polymorphism• A variable can contain an instance of a subtype of the declared typeSubtype polymorphism3Number x;x = new Integer(17);x = new Float(2.718);• Allow code to be parametrized on types•Introduce type variables or type parameters• Different languages allow one to parametrize classes, interfaces, methods, functions, expressionsParametric polymorphism4class Pair<A,B> { A fst; B snd; }In functional languages• Can parametrize algebraic data types:datatype 'a list = nil | cons of 'a * 'a listval xs: int list = cons(1, cons(2, nil))• More on this later in the course.Parametric polymorphism in OO• Many OO languages support parametrized classes, interfaces, and methods•Called generics• Issues:• What can be parametrized?• What types can be used to instantiate a type variable?• Bounded polymorphism• Variance• ImplementationTemplates•C++ supports templates• Similar to generics, but very different semantics and implementation• Will discuss laterTypes parametrized on types• Can parametrize classes and interfaces/traits:• Can parametrize methods:8class Pair<A,B> { A fst; B snd; }<A> boolean equal(Pair<A,A> p) { return p.fst == p.snd;}Instantiation•Type parameters are instantiated on other types.• As if substitution was performed:• Consider:class Pair<A,B> { A fst; B snd; }•Pair<String,Integer> is as if had writtenPairSI with the class declaration:class PairSI { String fst; Integer snd; }Instantiation• What types can a parameter be instantiated upon?• Java:•Any reference type (<: java.lang.Object)• Scala:• Any type• C#:• Any typeBounded polymorphism• Type parameters can be bounded when declared• Subtype bounds:• Java:• Scala:• Structural bounds:• PolyJ:11interface Comparable<T extends Comparable<T>> {...}def max[A <: Ordered[A]](a: A, b: A) = if (a < b) b else aclass SortedList[T] where T { int compareTo(T) } {...}Variance•What is the relationship between List[Integer] and List[Number]?•Should List[Integer] be a subtype of List[Number]?•For C[X]:•X is a covariant parameter of Cif C[A] <: C[B] when A <: B•X is a contravariant parameter of Cif C[A] <: C[B] when B <: ACovariant parametersSuppose List[Integer] <: List[Number]ints: List[Integer] = new List[Integer]();ints.add(new Integer(23));nums: List[Number] = ints;x: Number = ints.get(0);What about nums.add?13Covariant parametersSuppose List[Integer] <: List[Number]ints: List[Integer] = new List[Integer]();ints.add(new Integer(23));nums: List[Number] = ints;x: Number = ints.get(0);nums.add(new Float(56.78));Covariant parameters• Cannot call methods that take a covariant parameter as an argument.• A type system that allows this (without a run-time check) is does not enforce type safety.Covariant parameters•In Java, why is List<Integer> not a subtype of List<Number>?•What happens if we substitute Integer and Number for A in List<A>?16class List<Number> { Number get(int i) {...} void add(Number v) {...}}class List<Integer> { Integer get(int i) {...} void add(Integer v) {...}}Covariant parameters•Why is List<Integer> not a subtype of List<Number>?•What happens if we substitute Integer and Number for A in List<A>?17class List<Number> { Number get(int i) {...} void add(Number v) {...}}class List<Integer> { Integer get(int i) {...} void add(Integer v) {...}}Covariant method parametersCovariant parameters• Scala declares variance at the definition:class List[+A] {...}•A is a covariant parameter of List• The compiler checks that a covariant parameter does not occur as a method parameter type. •=> List.add(A) is not allowed.Wildcards• Java declares variance at the use:class List<A> {...}new List<? extends A>()•These are called wildcards.Covariant wildcardsclass List<A> {...}List<? extends Number> aList;List<Integer> iList = ...; aList = fList;List<Float> fList = ...; aList = iList;•The type of each element of aList is some statically unknown subtype of NumberCovariant wildcardsclass List<A> {...}List<? extends Number> aList;List<Integer> iList = ...; aList = fList;List<Float> fList = ...; aList = iList;• Compiler knows that the type parameter is some subtype of Number, but doesn’t know which subtype!Covariant wildcardsclass List<A> {...}List<? extends Number> aList;List<Integer> iList = ...; aList = fList;List<Float> fList = ...; aList = iList;•Cannot call methods that take an A, e.g., addContravariant wildcardsclass List<A> {...}List<? super Float> aList;List<Object> oList = ...; aList = oList;•The type of each element of aList is some statically unknown supertype of FloatContravariant wildcardsclass List<A> {...}List<? super Float> aList;List<Object> oList = ...; aList = oList;• Compiler knows that the type parameter is some supertype of Float, but doesn’t know which one!Contravariant wildcardsclass List<A> {...}List<? super Float> aList;List<Object> oList = ...; aList = oList;•Must assume methods that return an A, e.g., get, return Object.Wildcard usabilityWant a list of BirdsShould one declare a variable as:• List<Bird> ?• List<? extends Bird> ?• List<? super Bird> ?Hard to know which to do.26Wildcard usabilityList<Bird> birds• Cannot do:birds = new List<Penguin>();• Can do:birds = new List<Bird>();birds.add(new Bird());birds.add(new Penguin());Bird b = birds.get(0);27Wildcard usabilityList<? extends Bird> birds• Can do:birds = new List<Penguin>();Bird b = birds.get(0);• Cannot do:birds = new List<Object>();birds.add(new Bird());birds.add(new Penguin());28Wildcard usabilityList<? super Bird> birds• Can do:birds = new List<Object>();birds.add(new Bird());birds.add(new Penguin());Object o = birds.get(0);• Cannot do:birds = new List<Penguin>();Bird b = birds.get(0);29Variance in Scala• Scala declares variance at the class definition:class Map[-K,+V] {...}•Contravariant in K•Can use V in return types•Covariant in V•Can use K in argument typesVariance in C#• C# does not support variant parameters.• Why?Variance in C#• C# does not support variant parameters.• Why? Simplifies the language.Implementation• Two main approaches:• Polymorphic translation• Template instantiationPolymorphic translation• Translate a parametrized class into a
View Full Document
Unlocking...