Types & Polymorphism
Dr. Ritwik Banerjee
CSE 216 : Programming Abstractions Stony Brook University, Computer Science
Roadmap
We have studied the basics of the type system used in OCaml, but we have no other system for comparison. So – given that most of you have some experience with Java – we will start with a quick overview of the type system in Java.
Next, we will look at polymorphism and how it is implemented in the context of the two type systems.
1
© 2019 Ritwik Banerjee
The type system in Java
and how it may lead to the hiding of type information, and how that can be a problem.
Overview
• Java’s type system is far more sophisticated than the basic type system of class-based object oriented programming.
Uses reference types and primitive types.
The most basic reference types are arrays
and classes.
Also provides interfaces and generics, which are reference types.
• The type system is mainly designed with two things in mind:
1) static typing with a mix of static and dynamic type checking, and
2) a type hierarchy that supports single inheritance of classes.
3
© 2019 Ritwik Banerjee
Terminology for a class hierarchy
• A class that is derived from another class is called a subclass, extended class or child class.
• IfAisasubclassofB,thenBiscalledthe parent class, base class or superclass.
• These are often called “is-a” relationships. E.g., a car “is-a” vehicle, etc.
• The Object is the topmost superclass because everything “is-a” object.
• A subclass inherits properties from its superclass. E.g., a Poodle inherits the properties of the more general type, dog.
4
© 2019 Ritwik Banerjee
A simple example
public class Organism { private String species; private double age; private double health;
public Organism(String species) { this.species = species; } /* assume getters and setters */
}
public class Animal extends Organism { public Animal(String species) {
super(species); // the superclass’ constructor (and also the inherited // methods) can be called using the ‘super’ keyword.
}
} }
public static void main(String[] args) {
Animal ant = new Animal(“ant”);
ant.setHealth(10); // the ‘health’ field and the ‘setHealth’ method are
// inherited from the superclass Organism.
5
© 2019 Ritwik Banerjee
A simple example
• Aclassisextendedbyasubclasstypicallybecause,whilemaintaining various properties of a type, the subtype has some properties specific only to itself.
E.g., all animals have some properties in common, but the subtype “insect” will have additional subtype-specific properties.
• Moreover,somepropertiesmayneedtobemodifiedonlyforthesubtype. E.g., all insects have wings, except for, say, ants.
• Suchsubtype-specificmodificationscanbemadethroughoverriding: class Phoenix extends Animal {
private double lastFireUp;
public Phoenix(String species) { super(species); }
@Override
public double getAge() { return super.getAge() – lastFireUp; } }
Method originally defined in a superclass is being overridden in the subclass.
6
© 2019 Ritwik Banerjee
Polymorphism and how it relates to type systems.
7
© 2019 Ritwik Banerjee
• The phenomenon where a single name may be used to represent multiple types is known as polymorphism.
• This provision is there in most modern programming languages you are likely to use (e.g., Java, OCaml, Python, C#, JavaScript). There are two main types of polymorphism you will see:
1. subtype polymorphism, and 2. parametric polymorphism.
• Some programming languages stress on the first (e.g., the ML family of languages) while others (e.g., Java) rely more on subtype polymorphism.
8
© 2019 Ritwik Banerjee
Polymorphism
• A polymorphic variable can hold values of different types.
• A polymorphic function can be applied to arguments of a
variety of types.
In a way, we can think of it as one function with multiple interpretations.
• Overridingisnotexactlythesameaspolymorphism,butitis a specific form of polymorphism.
When there is a method call from an instance of the subtype referenced by the supertype, the method from the subtype is dynamically bound.
• Methodoverloadingistheactofdeclaringmultiplemethods with the same name but different signatures, within the same type. When there is a method call, the correct method is determined using static binding.
Possible because the argument types are known at compile time.
9
© 2019 Ritwik Banerjee
Polymorphism
Parametric polymorphism
• Weoftendealwithobjectsandbehaviorsthatrequire a generic way of handling values in a uniform manner, without worrying about their type.
• Parametricpolymorphismisawaytoprovideforthis requirement while still maintaining full static type safety.
• Thedatatypesthatallowforthiswayhandling values are called generic types, and the functions that allow of it are called generic functions.
A list is a generic data type.
The list append function (semantically same as the @ operator in OCaml) is a generic function. It’s type is ‘a list -> ‘a list -> ‘a list.
• Thegenerictypesandfunctionsformthebasisof generic programming.
Intuitively, we may think of this as programming where the type is unknown at compile time, and specific “later” (usually at runtime).
10
© 2019 Ritwik Banerjee
Types and polymorphism
• Parametricpolymorphismis ubiquitous in functional programming languages. So much so that when speaking in the context of functional programming, people often just say “polymorphism” to mean “parametric polymorphism”.
• Inobject-orientedprogramming,we usually think of the types forming a tree structure, or more generally speaking, a lattice structure.
Image source: Palsberg, Jens, and Michael I. Schwartzbach. “A unified type system for object-oriented programming.” DAIMI Report Series 19, no. 341 (1990).
11
© 2019 Ritwik Banerjee
Types and polymorphism
• Polymorphismallowsasinglenameto represent multiple types.
• Soitmakessensethatclassortype hierarchies are closely interrelated to polymorphism: to understand one, we need to understand the other.
In particular, polymorphism is closely to related to how types are converted.
This is where languages that uses static type checking differs from those with dynamic type checking. Note: we are talking about static/dynamic type checking, which is not the same as statically/dynamically typed.
Image source: Palsberg, Jens, and Michael I. Schwartzbach. “A unified type system for object-oriented programming.” DAIMI Report Series 19, no. 341 (1990).
12
© 2019 Ritwik Banerjee
Polymorphism and type conversion
•
•
InJava,castingupalongthetypehierarchyis automatic and implicit. This is called upcasting or broadening conversion.
Thisisbasedonthecommon-senseknowledgeofthe “is-a” relation. For example, a car is-a vehicle. So why not let the conversion be automatic? Hence, in Java we can write code like:
Vehicle v = new Car();
But OCaml does not allow this automatically, and the
conversion must be explicit:
let v : vehicle = (new car:> vehicle);; The opposite type of conversion, where is called
downcasting or narrowing conversion.
In Java, this is done by explicitly typecasting, and it is the programmer’s job to make sure the conversion is correct. E.g., Car c = (Car) v;
OCaml does not allow this at all.
•
13
© 2019 Ritwik Banerjee
Polymorphism & inheritance
• Welookedatthenotionofinheritance,i.e.,propertiesofasuperclass automatically become the properties of a subclass.
E.g., if the type car has four wheels, then every subtype of car will also have four wheels (unless this property is overridden). This would typically be implemented with an attribute, e.g., numWheels, and a corresponding access method, e.g., getNumWheels().
• Wealsosawthatthetypehierarchycan,ingeneral,bealatticestructure instead of a tree. That is, a type may be able to inherit properties from more than one parent type.
This can lead to the diamond problem.
Some OOP languages like C++ allow multiple inheritance of classes.
Java enforces single inheritance of classes. It is, indeed, a strong restriction, but it also makes Java’s approach to OOP less complex.
14
© 2019 Ritwik Banerjee
The “diamond problem”
• I’m breathing as a snake.
• I’m crawling as a snake.
15
© 2019 Ritwik Banerjee
The “diamond problem”
• We have LivingThing as the base class .
• The Animal and Reptile classes inherit from it.
• Only the Animal class overrides the method breathe().
• The Snake class inherits from the Animal and Reptile classes.
16
© 2019 Ritwik Banerjee
The “diamond problem”
• What if the Reptile class overrides the breathe() method and Snake doesn’t?
• Now, Snake doesn’t know which breathe() method to call! This is the Diamond Problem.
• If you do this, your C++ code will not compile, and display an error:
member ‘breathe’ found
in multiple base classes
of different types
17
© 2019 Ritwik Banerjee
The “diamond problem”
• C++ allows multiple inheritance of classes, but Java does not.
• This makes Java’s type hierarchy much simpler and streamlined, allowing us to view the type system as a tree structure.
18
© 2019 Ritwik Banerjee
Interfaces
• To get around the restriction of single inheritance of classes, Java introduces another reference type called the interface.
• A declarative approach to polymorphism.
Two elements are polymorphic (w.r.t a set of behaviors) if they implement the same interface(s).
We can think of an interface as an API, with no concern for implementation details.
Defines the functionality/behavior a type must provide. The implementation is mandatory in the definition of the concrete type (i.e., a class) implementing the interface.
public interface Stack { void push(char item); char pop();
char peek();
// inserts an item at the top
// removes an item from the top
// returns an item from the top without removing // determines if the Stack is empty
// returns a String representation of the Stack
}
boolean isEmpty(); String toString();
public static class ArrayStack implements Stack { private char[] stack;
private int top;
public ArrayStack(int n) { stack = new char[n]; top = -1;
}
public void push(char item) { stack[++top] = item; } public char pop() { return stack[top–]; }
public char peek() { return stack[top]; }
public boolean isEmpty() { return (top < 0); }
public String toString() {
StringBuilder aBuilder = new StringBuilder(); for (int i = top; i >= 0; i–) {
aBuilder.append(stack[i]).append(” “); }
return aBuilder.toString(); }
}
19
© 2019 Ritwik Banerjee
Interfaces
• Aninterfacecannotbedirectly instantiated. But in Java, we can write
Stack s = new ArrayStack(10); • Whatisthetypeofthiss?
This is how Java indirectly allows polymorphism in spite of enforcing single inheritance of classes.
One element may have multiple types. Here, s is both the type defined by the
class and the type defined by the interface.
Two elements not sharing the same class or superclass may still have a common type due to implementing the same interface.
A few things to note about Java interfaces:
• Like classes, an interface can be extended using the extends keyword.
• When one interface extends another
• it inherits all the methods and constants of its parent type, and
• it can define new methods and constants.
• Since Java allows multiple inheritance of interfaces, an interface may have more than one parent interface.
A few things to note about Java interfaces:
• All the mandatory methods declared by an interface are implicitly abstract.
• Since an interface is like an API, all the members are implicitly public.
• An interface cannot have an ‘instance’. Therefore,
• Fields in an interface are constants: they are static and final.
• An interface cannot have a constructor.
20
© 2019 Ritwik Banerjee
Polymorphism & Interfaces
Suppose we have a Shape class, and we want to
a) introduce the notion that every shape has a center,
b) be able to set the coordinates of that center, and
c) query the coordinates.
21
© 2019 Ritwik Banerjee
Information hiding
The ability to use polymorphic types with variants has many advantages, but it can lead to hiding the type information. Let’s see what could happen:
• We want a list to hold a collection of Shape instances.
• When retrieving the shapes, List#get(int i)
returns a java.lang.Object. This is correct, because every type “is-a” java.lang.Object.
• Advantage of polymorphism: we can put different shapes in the same list.
• Disadvantage of polymorphism: the items all behave like java.lang.Object instances. So, to get the ‘real’
type, it must undergo a typecast.
• Correctly typecasting is the programmer’s responsibility. An incorrect cast will cause the code to crash with a ClassCastException.
public interface Shape { double getPositionX(); double getPositionY();
}
public class Circle implements Shape {
double center_x, center_y, radius;
public Circle(double center_x, double center_y, double radius) { this.center_x = center_x;
this.center_y = center_y;
this.radius = radius;
}
public double getPositionX() { return center_x; }
public double getPositionY() { return center_y; } }
public class Square implements Shape { double left_top_x, left_top_y, side;
public Square(double left_top_x, double left_top_y, double side) { this.left_top_x = left_top_x;
this.left_top_y = left_top_y;
this.side = side;
}
public double getPositionX() { return left_top_x; }
public double getPositionY() { return left_top_y; } }
List shapes = new ArrayList(); shapes.add(new Circle(1, 1, 1)); shapes.add(new Square(1.5, 1.5, 1)); shapes.add(new String(“tada!”));
Shape s1 = (Circle) shapes.get(0); Shape s2 = (Shape) shapes.get(1); Shape s3 = (Shape) shapes.get(2);
22
© 2019 Ritwik Banerjee
Information hiding
• There are two layers of information hiding going on here:
1) every item appears as java.lang.Object.
2) even if the programmer remembers (mostly because of the variable name, shapes) that all the items are Shape instances, casting to specific subtypes of Shape can again be problematic.
• We would certainly prefer a system that catches such mistakes at compile time. Otherwise, we have a language with static typing that suffers from a disadvantage of dynamic typing!
public interface Shape { double getPositionX(); double getPositionY();
}
public class Circle implements Shape {
double center_x, center_y, radius;
public Circle(double center_x, double center_y, double radius) { this.center_x = center_x;
this.center_y = center_y;
this.radius = radius;
}
public double getPositionX() { return center_x; }
public double getPositionY() { return center_y; } }
public class Square implements Shape { double left_top_x, left_top_y, side;
public Square(double left_top_x, double left_top_y, double side) { this.left_top_x = left_top_x;
this.left_top_y = left_top_y;
this.side = side;
}
public double getPositionX() { return left_top_x; }
public double getPositionY() { return left_top_y; } }
List shapes = new ArrayList(); shapes.add(new Circle(1, 1, 1)); shapes.add(new Square(1.5, 1.5, 1)); shapes.add(new String(“tada!”));
Shape s1 = (Circle) shapes.get(0); Shape s2 = (Shape) shapes.get(1); Shape s3 = (Shape) shapes.get(2);
23
© 2019 Ritwik Banerjee
Type viewed as a ‘container’
The problem posed by polymorphism can (at least partly) be resolved, again, by polymorphism.
• Thinkofthedatatypeasacontainer,andnowweneedawaytospecifythe type of the payload in that container! Going one step further, think of the type also as a container that holds instances of another reference type.
This idea gives rise to the diamond syntax used in Java (for the ‘payload’ type):
• SuchaBoxinterfaceisthegenericconstructfor our notion of a container, and the ‘payload’ type in it is denoted by the parameter T.
The parameter is called a type parameter.
The generic construct is a parameterized type.
interface Box
T unbox(); }
24
© 2019 Ritwik Banerjee
Type as a parameter
• What we saw vis-à-vis type conversion and subtypes is a glimpse into the world of subtype polymorphism.
• In many cases, it is possible to write OCaml programs with subtype polymorphism. But your code will be full of explicit type conversions. That is, lines that look like this:
let v : vehicle = (new car:> vehicle)
• Thepreferredwayofusingpolymorphisminfunctionalprogrammingis parametric polymorphism:
A polymorphic value does not have a single concrete type.
It is a parameter, i.e., a placeholder, for whatever concrete type is needed.
• OCamlexample:
Queue.create creates an empty queue of the type ‘a t, where ‘a is the
polymorphic type variable (i.e., the parameter), and t denotes the Queue data type.
When actually using this function, we use a concrete type like int or string, and obtain the type int t or string t, as specified.
25
© 2019 Ritwik Banerjee
Type as a parameter
Java OCaml
• Broadeningconversionsareimplicit,but parametric polymorphism requires extra code:
List
• Thegenericparameteriscodedusingapairof angular brackets:
• Whentheactuallistiscreated,theparameteris replaced by the concrete type.
That is, List
• Parameterizationisimplicit,andno additional code is needed.
let items = Queue.create();; Queue.add “s” items;;
• Sincetheuseofparametersisautomatic and implicit, the code is less verbose.
• OCamlusestypeinferencetocheckthe type (in this example, string).
26
© 2019 Ritwik Banerjee
Parametric polymorphism
• Perhapsthesinglemostimportantadvantageoftheabilitytouseatypeasa parameter is that we need to write functions that are not type-specific only once, and reuse them throughout, with different parameters.
• Let’sthinkofafunctionthatswapsthetwoitemsinanorderedpair: let swap (x, y) = (y, x);;
val swap : ‘a * ‘b -> ‘b * ‘a =
Here, ‘a and ‘b are type variables, and the function’s type is derived from that.
• SinceparameterizationisimplicitinOCaml,wecanwritesuchafunction without even thinking about the types. As a result, we never have to write multiple functions like
let swapInt ((x : int), (y : int)) : int * int = (y, x);;
let swapFloat ((x : float), (y : float)) : float * float = (y, x);;
let swapString ((x : string), (y : string)) : string * string = (y, x);; let swapIntFloat ((x : int), (y : float)) : float * int = (y, x);;
27
© 2019 Ritwik Banerjee
Parametric polymorphism
• Perhapsthesinglemostimportantadvantageoftheabilitytouseatypeasa parameter is that we need to write functions that are not type-specific only once, and reuse them throughout, with different parameters.
• Let’sthinkofafunctionthatswapsthetwoitemsinanorderedpair: let swap (x, y) = (y, x);;
val swap : ‘a * ‘b -> ‘b * ‘a =
Here, ‘a and ‘b are type variables, and the function’s type is derived from that.
• Instead,wecanusethepolymorphicswapfunctionbyreplacingthetype variables by concrete types as and when needed:
# swap(1,2);;
– : int * int = (2, 1)
# swap(“foo”, 0);;
– : int * string = (0, “foo”)
# swap(“pi”, 3.14);;
– : float * string = (3.14, “pi”)
28
© 2019 Ritwik Banerjee
Parametric polymorphism
• Writingthepolymorphicswapfunctionwasano-brainerinOCaml,because OCaml performs automatic type inference.
• Wecouldhavespecifiedourfunctionas
let swap ((x: ‘a), (y: ‘b)) : ‘b * ‘a = (y, x);;
• Butinstead,weweresimplyabletowrite let swap (x,y) = (y,x);;
• Clearly,writingpolymorphicfunctionsinOCamlis
a) less verbose because we don’t have to specify the polymorphic types, and
b) intuitive, because we don’t even have to think about polymorphism while writing such a function.
29
© 2019 Ritwik Banerjee
Parametric polymorphism
Now let us see how to write the exact same function in another statically typed language, Java.
• Withoutconsciouslythinkingaboutpolymorphism,wecan’tevenbeginto write the body of the function:
static ??? swap(??? x, ??? y) {
// haven’t even reached this yet
}
• Weneedtodefinethetypevariablesexplicitly:
static
}
I am using a static method here so that the swap function is not dependent on the existence of an instance.
But Java doesn’t provide a readymade tuple data type, so we need to work more.
30
© 2019 Ritwik Banerjee
Parametric polymorphism
• We need to first define the proper data type.
Without this, we cannot even figure out the return type of the swap function.
• Then, we have two ways of defining swap:
1) an instance method within the body of the type we just defined, or
2) a static method that we can write anywhere.
public static class PolymorphicPair
B second;
public PolymorphicPair(A a, B b) { this.first = a;
this.second = b; }
/* Define swap as an instance method */
public PolymorphicPair
return new PolymorphicPair<>(second, first);
} }
1
static
}
2
31
© 2019 Ritwik Banerjee
Parametrized types
• Intheexamplewejustsaw,wehadto define a parametrized data type in order to define a polymorphic function in Java.
• Wecanrevisitanothertypewesaw earlier and do the same: the stack.
It makes sense to parameterize it, since none of the core stack functions – pop(), push(), peek(), isEmpty() – depend on the type of the items in the stack!
Note that we changed the stack
implementation to be list-backed instead
of array-backed, and did not implement the toString() method.
public interface Stack
E pop();
E peek();
boolean isEmpty();
String toString(); }
public class ListStack
private int top;
public ListStack() {
stack = new LinkedList<>();
}
public void push(E element) { stack.add(element);
}
public E pop() {
return stack.remove(stack.size() – 1);
}
public E peek() {
return stack.get(stack.size() – 1);
}
public boolean isEmpty() { return stack.size() == 0;
} }
32
© 2019 Ritwik Banerjee
(* polymorphic lists *)
type ‘a list_ = Nil | Cons of ‘a * ‘a list_
(* is the list empty? *)
let is_empty (lst : ‘a list_) : bool = match lst with | Nil -> true
| _ -> false
type ‘a tree = Leaf | Node of (‘a tree) * ‘a * (‘a tree) ;;
(* to use a record type for nodes *)
type ‘a tree = Leaf | Node of ‘a node
and ‘a node = {left: ‘a tree; value: ‘a; right: ‘a tree};;
33
Parametrized types Similarly, we can define polymorphic types in OCaml using recursion.
© 2019 Ritwik Banerjee
34
A type parameter in Java is a placeholder for a concrete reference type, and cannot be used for a primitive type.
+This is perfectly fine:
List
– This is not:
List
WHY?
• Generics, i.e., parametric polymorphism, are a compile-time construct in Java. The compiled code does not have any generics. WHY?
• When Java 1.0 was released, the language designers were under
commercial pressure and little time to sit back and perfect the language at its design phase. So, the language was released without any provision for type parameters. Generics were added much later in 2004, with Java 1.5. By then, millions of devices were using the older versions of Java. As a result, the designers had to make sure that Java’s handling of type parameters remains backward compatible.
• So, the workaround was that the compiler would turn all generic code into generic-free byte code by using casts to the right type. This enabled code written in newer JDK to be run on machines with older JVM. All this, of course, happens in the background so that the programmer doesn’t have to write the code to cast and uncast objects.
• Therefore, any concrete type that replaces a type parameter must be convertible to (and from) java.lang.Object. This is why primitives cannot be used as parameters in Java generics.
Type parameters and primitives in Java: a history lesson
© 2019 Ritwik Banerjee
Type erasure
Generics are a compile-time construct, i.e., the JVM does not know anything about the type parameters since they do not exist at runtime. This removal of the parameter type’s information is called type erasure.
So how can a compiler translate a code with parameter types into parameter- free byte code that the virtual machine can correctly interpret?
There are two choices:
1)
Generate a new representation for every instantiation of a generic type or function. That is, it will generate a new compile class for List
compiled class for List
C# uses this for non-reference data types.
C++ uses this for its templates.
Code specialization provides some speed benefits in performance, but is wasteful in terms of space.
35
© 2019 Ritwik Banerjee
Type erasure
Generics are a compile-time construct, i.e., the JVM does not know anything about the type parameters since they do not exist at runtime. This removal of the parameter type’s information is called type erasure.
So how can a compiler translate a code with parameter types into parameter- free byte code that the virtual machine can correctly interpret?
There are two choices:
2)
Generate code for only one representation for every instantiation of a generic type or function, and map all the instantiations of that type or method to this unique representation. To retrieve the generic type, then, perform type conversions wherever necessary. This approach is called code sharing.
The Java compiler works this way.
When the compiler finds a generic type, it removes the type arguments to yield the
raw type. E.g., List
36
© 2019 Ritwik Banerjee
Parameter types and subtyping
List
•
You should be aware that the following are incorrect (except for the first instantiation):
Parameter types and subtyping
• Ingeneral,ifAisasubtypeofB,andRissomeparameterizedtype(e.g., List, Set), it is NOT the case that R is a subtype of R.
• Suppose we have the following type hierarchy:
interface Employee {…}
class Person {…}
class Driver extends Person {…}
class UberDriver extends Person implements Employee {…}
List
List
drivers
people
employees
= uberdrivers; = uberdrivers; = uberdrivers;
39
© 2019 Ritwik Banerjee
Parameters and algebraic types
• In general, ifAis a subtype ofB, andRis some parameterized type (e.g., List, Set), it is NOT the case that R is a subtype of R.
• This solves one type of problems:
Imagine a situation where a list of drivers were being maintained by the DMV, and they shared that data with law enforcement, who treated it as a List
The restrictions on subtyping of algebraic data type with parameters mean that we will not have such a problem.
• However, it introduces another issue.
Consider the two methods here, one printing a raw type collection, and the other trying to print a parameterized collection:
void printCollection(Collection c) { Iterator i = c.iterator();
for (int k = 0; k < c.size(); k++)
System.out.println(i.next()); }
void printCollection(Collection
Parameters and algebraic types
• In general, ifAis a subtype ofB, andRis some parameterized type (e.g., List, Set), it is NOT the case that R is a subtype of R.
• This solves one type of problems:
Imagine a situation where a list of drivers were being maintained by the DMV, and they shared that data with law enforcement, who treated it as a List
The restrictions on subtyping of algebraic data type with parameters mean that we will not have such a problem.
• However, it introduces another issue.
Consider the two methods here, one printing a raw type collection, and the other trying to print a parameterized collection:
But the code below is not very useful, because it only takes Collection
What is the supertype of all types of collections?
• More generally, if we have a sum type (e.g., List, Set, Collection) with a parameter, what is the supertype of all such data types?
• In Java, this is written using the unknown parameter type . It is also called a wildcard type.
• Using this unknown parameter type, we can correctly work with parameterized algebraic data types. We can call the code shown here with any type parameter.
• Note that inside the code, each individual item is still treated as an Object. This is type-safe – whatever the collection’s
type was, the individual items are all subtypes of java.lang.Object.
• Remember, that still doesn’t make it ok to add arbitrary objects to this collection:
void printCollection(Collection c) { for (Object obj : c) {
System.out.println(obj); }
}
Collection c = new ArrayList
42
© 2019 Ritwik Banerjee
Working with the unknown type parameter
• Addingitems:
The add() method’s parameter is a type variable E, which
denotes the element type of the collection.
Since we don’t know what that is, we can’t use the add() method on a collection of the unknown type.
The only exception is null, which is considered a member of every type.
• Retrievingitems:
This is done by the get() method, which we can use
without knowing the type parameter.
Since the individual item is a subtype of Object, we can safely work with it and pass it as an Object (remember, typecasting is possible, but at the programmer’s risk).
Collection c = new ArrayList
43
© 2019 Ritwik Banerjee
Adding flexibility to type variables
• The unknown type gives us some flexibility by giving an upper bound on the type, but we can’t just have the Object type with parameterized collections. That takes away all the item-specific functionality!
• Think of a rudimentary drawing program that draws a picture by using various simple shapes, where each shape has a draw() method. If we store all the shapes and retrieve them only as Objects, we will not be able to call the draw() method on them.
• A typical Java codebase would look something like this
public class Canvas {
public void draw(Shape s) {
s.draw(this); }
}
public abstract class Shape {
public abstract void draw(Canvas c);
}
public class Circle extends Shape {
private int x, y, radius;
public void draw(Canvas c) { /* implementation */
} }
public class Rectangle extends Shape { private int x, y, width, height;
public void draw(Canvas c) { /* implementation */
} }
44
© 2019 Ritwik Banerjee
public void drawAll(List
}
public void drawAll(List shapes) { for (Shape s : shapes) s.draw(this);
}
Adding flexibility to type variables
• No matter what the final drawing looks like, we probably need to maintain a collection of all the shapes needed to get to the final result.
• The problem is that drawAll() can only take a list of Shapes, and not a list of Circles (because, remember, a List
• There is a subtle but important distinction we want here: we want the method to accept any kind of Shape, instead of just Shape.
• This is done by replacing List
• So now, we can call drawAll() on a List
45
© 2019 Ritwik Banerjee
public void drawAll(List
}
public void drawAll(List shapes) { for (Shape s : shapes) s.draw(this);
}
Adding flexibility to type variables
• The expression is an example of a bounded parameter or a bounded wildcard.
• It means that the parameter is still unknown, but we have some information – that it is a subtype of Shape. You should note two things about bounded wildcards:
1) It could even be Shape itself.
2) Even if the upper bound is an interface, the keyword in Java is always extends (never “implements”) if we want to restrict the parameter to be any item that implements an interface.
• The unbounded wildcard is implicitly a parameter whose upper bound is Object.
• Just like we saw with the unbound wildcard, we still can’t add() items to a List.
46
© 2019 Ritwik Banerjee
public void drawAll(List
}
public void drawAll(List shapes) { for (Shape s : shapes) s.draw(this);
}
Adding flexibility to type variables
• Just like we saw with the unbound wildcard, we still can’t add() items to a List.
public void addRectangle(List shapes) {
shapes.add(0, new Circle()); }
The above code, for example, will not compile because the programmer is expected to provide a ? extends Shape instance as the 2nd parameter to add().
That is, an unknown subtype of Shape.
Now, this unknown subtype may or may not be a supertype of Circle. Therefore, it is not safe to pass a Circle instance here.
The error may seem a bit cryptic, but you should keep the above explanation in mind when you see something like
incompatible types: Rectangle cannot be converted to capture#1 of ? extends Shape
47
© 2019 Ritwik Banerjee
Polymorphic methods
• Since we should not work with algebraic types parameterized by Object, and using doesn’t solve our problems either, we should be using a specific type variable for generic methods:
static
48
© 2019 Ritwik Banerjee
Polymorphic methods
• This method can be used with any type of Collection whose parameter is a
supertype of T, the type of the item being added: /* T is inferred to be a String */
addToCollection(“s”, new HashSet<>());
/* T is inferred to be a Double, and the primitive type double is autoboxed to Double */
addToCollection(1.5, new ArrayList<>());
/* T is inferred to be a Character, and the primitive type char is autoboxed to Character */
addToCollection(‘d’, new LinkedList<>());
/* Since Shape is a supertype of Circle, this is ok */
addToCollection(new Circle(), new ArrayList
/* Shape is not a supertype of Integer, so this is a compile-time error */
addToCollection(new Integer(5), new TreeSet
49
© 2019 Ritwik Banerjee
Polymorphic methods
• Let’slookatsomeactualmethodsin Java’s collection library.
• Wejustsawtheissueswithusingthe wildcard type or simply using Object as our type variable.
• Wealsosawthatusingaspecific type variable as the parameter seems to resolve these issues.
• Wecouldhaveusedmethod definitions like this instead
So under what circumstances, and why, can/should we use the wildcard (bounded or otherwise)?
boolean containsAll(Collection c);
boolean addAll(Collection c); boolean removeAll(Collection c);
boolean removeIf(Predicate filter); boolean retainAll(Collection c);
boolean
50
© 2019 Ritwik Banerjee
Polymorphic methods with unknown type parameters
• Consider the method to copy items from a source list src, to a destination list dest: public static src, List
/* implementation */
}
Nothing wrong with this.
• Note the T is used in the type of dest and in the definition of S, but S itself is only
used once in the definition. Nothing else depends on S.
• This is where we should replace a type parameter with a wildcard.
It frees up a needless binding.
It makes the code more readable by immediately conveying that a parameter is, indeed, unknown.
It is similar to the use of the underscore “_” wildcard in OCaml.
public static
/* implementation */
}
51
© 2019 Ritwik Banerjee
• Wehaveseenupperboundsontypeparameters,e.g., or .
• Butlowerboundsarepossibletoo!Thatis,wecanspecifybounds like .
• Theupperboundsallowforflexibleuseofthetype,butmakethe data structure holding this type (usually a collection) effectively “read only”.
• Thelowerboundshavetheoppositeeffect–theycreatecollections that are effectively “write only”.
• Together,thisisoftencalledthePECSprinciple,amnemonicfor “producer extends consumer super”:
If you want to traverse through a collection and do something with each item, you have to pull out each item. The collection is thus seen as a ‘producer’ of something specific, and you should use extends (if not just a specific type parameter).
If you want to take a collection and work with a method that doesn’t care about its parameter type, the method can be thought of as a ‘consumer’
that has to accept something more general, and you should use super (again, if not a specific type parameter).
52
© 2019 Ritwik Banerjee
Bounded type parameters
Try running these examples to see for yourself what happens
public class BoundedWildcards {
interface Output
static class OutputImpl
public void print(T t) { System.out.println(t.toString()); }
}
static
for (T t : collection) {
if (first == null) first = t;
out.print(t);
}
return first; }
public static void main(String… args) { Output
Try running these examples to see for yourself what happens
public class BoundedWildcards {
interface Output
static class OutputImpl
public void print(T t) { System.out.println(t.toString()); }
}
static
for (T t : collection) {
if (first == null) first = t;
out.print(t);
}
return first; }
public static void main(String… args) { Output
Try running these examples to see for yourself what happens
public class BoundedWildcards {
interface Output
static class OutputImpl
public void print(T t) { System.out.println(t.toString()); }
}
static
for (T t : collection) {
if (first == null) first = t;
out.print(t);
}
return first; }
public static void main(String… args) { Output
Additional notes
• Overloading and overriding with type parameters
• Reified types
• Compile-time and
runtime types
• Java arrays and components
• Variance
56
© 2019 Ritwik Banerjee
Overloading with type parameters
• Methods with type parameters can be overloaded as usual.
class OverloadingDemo {
public
/* implementation */
}
public
}
public void method(Long l) { /* implementation */
} }
57
© 2019 Ritwik Banerjee
Overloading with type parameters
• But is this code legal?
public class OverloadingDemo {
public void aMethod(List
/* implementation */
}
public void aMethod(List
}
public int aMethod(List
return 0;
} }
58
© 2019 Ritwik Banerjee
Overloading with type parameters
• But is this code legal?
class OverloadingDemo {
public
/* implementation */
}
public void method(Number arg) { /* implementation */
} }
59
© 2019 Ritwik Banerjee
Overriding with type parameters
• Thetwomethodsinthesubclasshere classSuper{
overload each other because they have the same name but different signatures (one has List as its parameter, and the other has the raw type Collection).
• The printAll() method in the superclass and the second printAll() method in the
subclass have parameters of the type Collection and Collection,
respectively.
• The subclass’ method overrides the superclass’ method even though the method signatures are not identical. How is this possible?
public void printAll(Collection c) { for (Object o : c)
System.out.println(o.toString()); }
}
class Sub extends Super {
public void printAll(List c) {
for (Object o : c) System.out.println(o.toString());
}
public void printAll(Collection c) { for (Object o : c)
System.out.println(o.toString()); }
Because the subclass signature is the } erasure of the superclass signature.
60
© 2019 Ritwik Banerjee
Overriding with type parameters
• The converse is illegal – that is, if the superclass signature is the erasure of the subclass signature.
• This is a name clash error. It is neither overloading nor overriding.
class Super {
public void printAll(Collection c) {
for (Object o : c) System.out.println(o.toString());
} }
class Sub extends Super {
public void printAll(Collection c) {
for (Object o : c) System.out.println(o.toString());
} }
61
© 2019 Ritwik Banerjee
• To reify means to make an abstract item more concrete or real. In programming, this term is used to denote the opposite of type erasure.
• Java removes the parameter type, so the virtual machine (JVM) has no information about, say, whether something is a List
• In some other languages, e.g., C#, parameters do have a runtime representation. This is due to code specialization.
• In these systems, the parameter is a reified or reifiable types, which are types that do not lose any type information at runtime.
• In Java,
arrays reify their component types, generic data structures do not.
primitive types, non-parameterized reference types, and the raw type are all reified.
parameterized types with the unbounded wildcard (e.g., List or Map) may also be considered as reified, since they don’t lose any information due to type erasure.
62
© 2019 Ritwik Banerjee
Reification
• Unlike other collection data types, arrays in Java reify their component.
• That is, the JVM views a List
public class Pair
V value;
public Pair(K key, V value) { this.key = key;
this.value = value; }
}
public K getKey()
public void setKey(K key)
public V getValue()
public void setValue(V value) { this.value = value; }
{ return key; }
{ this.key = key; } { return value; }
63
© 2019 Ritwik Banerjee
Reification
Compile-time and runtime types
Type erasure leads to a difference in the type of a parameterized type as seen by the compiler and as seen by the JVM at runtime. So, it makes sense to ask the type of aList in this code:
List
Depends on whether we are considering the list at compile-time, or runtime.
The compiler will see it as a “List of Strings”. The compiler will use this type information (i.e., “of Strings”) to detect compile-time code errors such as attempting to add() an element of a wrong type to the list.
The JVM at runtime will see it as an ArrayList with of the raw type.
The runtime type – called the actual type or real type – is more specific than the
compile-time type (e.g., ArrayList, as opposed to the interface type List).
The compile-time – called the declared type or apparent type – is more specific for the parameter, because this information is completely lost at runtime.
64
© 2019 Ritwik Banerjee
Java arrays and their components
• This leads to some “interesting” behavior in Java when it comes to using arrays with type parameters.
• We already saw that even though String is a subtype of Object, List
Java arrays and their components
There are two reasons why this error can’t be caught at compile-time:
1) Arrays are covariant in Java. That is, a T[] can contain items of any subtype of T (including, of course, T itself).
2) If A is a subtype of B, then A[] is a considered a subtype of B[].
The 2nd reason is why this is acceptable in Java:
String[] strings = new String[10];
Object[] objects = strings;
This 2nd reason is, however, wrong!
• The basic philosophy of a type hierarchy is this: A is considered a subtype of B if and only if A fulfills all obligations of A. E.g., a car “is a” vehicle because a car fulfills all the properties of a vehicle.
• But, we can put any object into an Object[], but you cannot put any object into a String[]. In other words, the add() methods are different, which breaks the basic philosophy of a type hierarchy.
66
© 2019 Ritwik Banerjee
Java arrays and their components
There are two reasons why this error can’t be caught at compile-time:
1) Arrays are covariant in Java. That is, a T[] can contain items of any subtype of T (including, of course, T itself).
2) If A is a subtype of B, then A[] is a considered a subtype of B[].
The 1st reason is a culprit as well.
• Let’s say we have a Fruit type, and then different
subtypes like Apple, Orange, Banana, etc.
• If we write something like
Fruit[] fs = new Apple[10];
then the compiler allows it because of covariance.
• And then, we can say fs[0] = new Apple(); (not a new Banana or Orange, though).
• However, the compiler doesn’t know whether the real type of the array is going to be Fruit[] or Apple[].
The information about the real type, by definition, is only available at runtime.
67
© 2019 Ritwik Banerjee
Variance
• The term “covariant” comes from the more general notion of variance – which refers to how the type-relations between sum data types (e.g., lists) relates to the type-relations between their components.
• With this formal concept, we can consider Mammal to a subtype of Animal, and ask the following questions:
should a list of Mammals be substitutable whenever a list of Animals is used?
should a function that returns an Animal be allowed to return a Mammal?
how should we treat the different subtypes of Animal within a list of Animals?
• Depending on the language, the subtyping relation of the components may be either preserved (covariance), reversed (contravariance), or ignored (invariance) for the respective complex types.
• For example:
OCaml: a list of mammals would be a subtype of a list of
animals (covariance).
Java: a list of mammals has no subtype relation to a list of animals (invariance).
68
© 2019 Ritwik Banerjee
Variance of parametric types in Java
We say the type parameter T is covariant in the generic type R
In Java, there is no subtype relation between List
69
© 2019 Ritwik Banerjee
Variance of parametric types in Java
Think about the subtyping of parametrized types in terms of whether or not a “region” in the type hierarchy is contained in another. The region for is contained entirely within the region for .
As such, generics are covariant in their upper bounds. That is, List is a subtype of List.
70
© 2019 Ritwik Banerjee
Variance of parametric types in Java
Think about the subtyping of parametrized types in terms of whether or not a “region” in the type hierarchy is contained in another. The region for is contained entirely within the region for .
As such, generics are contravariant in their lower bounds. That is, List is a subtype of List.
71
© 2019 Ritwik Banerjee
Variance of parametric types in Java
• Another way to view this behavior is to realize that even though the basic type hierarchy in Java is tree structure, the use of bounded parameter types gives rise to a lattice structure.
Image Source: https://commons.wikimedia.org/wiki/File:Java_wildcard_subtyping.svg, provided under CC BY-SA 3.0 license.
72
© 2019 Ritwik Banerjee
Variance of return types and argument types
• Variance plays a role in the flexibility of overriding methods. For example, it is reasonable to ask the questions:
if I’m overriding a method in a subclass, can the method return a subtype?
if I’m overriding a method in a subclass, can the method accept arguments from a subtype?
• The answers are language dependent.
• Java is invariant in the argument types, but covariant in the return types.
Some other languages, like C#, are invariant across the board (which makes overriding very inflexible).
public interface Positionable {
void setPosition(Collection points);
}
// This is not a valid override (even though List is // a subtype of Collection) since Java is invariant // in the argument types.
public class Quadrilateral implements Positionable {
@Override
public void setPosition(List points) { /* implementation */
} }
73
© 2019 Ritwik Banerjee