Types &

Polymorphism

Dr. Ritwik Banerjee

Programming Abstractions
Computer Science
Stony Brook University
Roadmap

We have studied the basics of

the type system used in OCaml,
but we have no other system for Next, we will look at
comparison. So – given that polymorphism and how it is
most of you have some implemented in the context of

© 2022 Ritwik Banerjee

experience with Java – we will the two type systems.
start with a quick overview of
the type system in Java.

1
The type system and how it may lead to the
hiding of type information,

in Java 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

© 2022 Ritwik Banerjee

2) a type hierarchy that supports single
inheritance of classes.

3
Terminology for a class hierarchy
• A class that is derived from another class is
called a subclass, extended class or child
class.

• If A is a subclass of B, then B is called the

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.

© 2022 Ritwik Banerjee

• A subclass inherits properties from its
superclass. E.g., a Poodle inherits the
properties of the more general type, dog.

4
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.

© 2022 Ritwik Banerjee

}

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
 A simple example
• A class is extended by a subclass typically because, while maintaining
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, some properties may need to be modified only for the subtype.
– E.g., all insects have wings, except for, say, ants.

• Such subtype-specific modifications can be made through overriding:

© 2022 Ritwik Banerjee

class Phoenix extends Animal {
private double lastFireUp;
Method originally defined
in a superclass is being
overridden in the public Phoenix(String species) { super(species); }
subclass.
@Override
public double getAge() { return super.getAge() - lastFireUp; }

6
}
Polymorphism

© 2022 Ritwik Banerjee

and how it relates to type systems.

7
 • The phenomenon where a single name may be

Polymorphism
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.

© 2022 Ritwik Banerjee

• 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
 • A polymorphic variable can hold values of different types.

Polymorphism
• 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.
• Overriding is not exactly the same as polymorphism, but it is
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.
• Method overloading is the act of declaring multiple methods
with the same name but different signatures, within the same

© 2022 Ritwik Banerjee

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
Parametric • We often deal with objects and behaviors that require
a generic way of handling values in a uniform
polymorphism manner, without worrying about their type.

• Parametric polymorphism is a way to provide for this

requirement while still maintaining full static type
safety.

• The data types that allow for this way handling

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.

© 2022 Ritwik Banerjee

• The generic types and functions form the basis of
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
Types and polymorphism
• Parametric polymorphism is
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”.
• In object-oriented programming, we

© 2022 Ritwik Banerjee

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
Types and polymorphism
• Polymorphism allows a single name to
represent multiple types.

• So it makes sense that class or type

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.

© 2022 Ritwik Banerjee

– This is where languages that uses static
type checking differs from those with
dynamic type checking. Note: we are
talking about static/dynamic type Image source: Palsberg, Jens, and Michael I. Schwartzbach. “A unified type system
checking, which is not the same as for object-oriented programming.” DAIMI Report Series 19, no. 341 (1990).
statically/dynamically typed.

12
Polymorphism • In Java, casting up along the type hierarchy is
automatic and implicit. This is called upcasting or
and type broadening conversion.
conversion • This is based on the common-sense knowledge of the
“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.

© 2022 Ritwik Banerjee

– 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
Polymorphism & inheritance
• We looked at the notion of inheritance, i.e., properties of a superclass
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().

• We also saw that the type hierarchy can, in general, be a lattice structure
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.

© 2022 Ritwik Banerjee

– 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
The “diamond
problem”
• I’m breathing as a snake.

• I’m crawling as a snake.

© 2022 Ritwik Banerjee

15
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().

© 2022 Ritwik Banerjee

• The Snake class inherits
from the Animal and
Reptile classes.

16
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++

© 2022 Ritwik Banerjee

code will not compile, and
display an error:
member ‘breathe’ found
in multiple base classes
of different types

17
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.

© 2022 Ritwik Banerjee

18
 public interface Stack {
void push(char item); // inserts an item at the top
char pop(); // removes an item from the top
char peek(); // returns an item from the top without removing
boolean isEmpty(); // determines if the Stack is empty
String toString(); // returns a String representation of the Stack
}

Interfaces
public static class ArrayStack implements Stack {
private char[] stack;
• To get around the restriction of single private int top;
inheritance of classes, Java introduces
another reference type called the interface. public ArrayStack(int n) {
stack = new char[n];
• A declarative approach to polymorphism. top = -1;
}
– Two elements are polymorphic (w.r.t a set
of behaviors) if they implement the same public void push(char item) { stack[++top] = item; }
interface(s). public char pop() { return stack[top--]; }
public char peek() { return stack[top]; }
– We can think of an interface as an API,

© 2022 Ritwik Banerjee

public boolean isEmpty() { return (top < 0); }
with no concern for implementation details.
– Defines the functionality/behavior a type public String toString() {
must provide. The implementation is StringBuilder aBuilder = new StringBuilder();
mandatory in the definition of the concrete for (int i = top; i >= 0; i--) {
aBuilder.append(stack[i]).append(" ");
type (i.e., a class) implementing the
}
interface.
return aBuilder.toString();
}
}

19
Interfaces
• An interface cannot be directly A few things to note about Java interfaces:
Like classes, an interface can be extended using the extends keyword.
instantiated. But in Java, we can write •
• When one interface extends another
Stack s = new ArrayStack(10);
• it inherits all the methods and constants of its parent type, and
• it can define new methods and constants.
• What is the type of this s? • Since Java allows multiple inheritance of interfaces, an interface may have
– This is how Java indirectly allows more than one parent interface.
polymorphism in spite of enforcing single
inheritance of classes.

© 2022 Ritwik Banerjee

– One element may have multiple types.
Here, s is both the type defined by the A few things to note about Java interfaces:
class and the type defined by the interface.
• All the mandatory methods declared by an interface are implicitly abstract.
– Two elements not sharing the same class • Since an interface is like an API, all the members are implicitly public.
or superclass may still have a common • An interface cannot have an ‘instance’. Therefore,
type due to implementing the same • Fields in an interface are constants: they are static and final.
interface.
• An interface cannot have a constructor.

20
 © 2022 Ritwik Banerjee
Polymorphism Suppose we have a Shape class, and we want to
a) introduce the notion that every shape has a center,

& Interfaces b) be able to set the coordinates of that center, and

c) query the coordinates.

21
 public interface Shape {
double getPositionX();

Information
double getPositionY();
}

public class Circle implements Shape {

double center_x, center_y, radius;

hiding 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; }

The ability to use polymorphic types with variants has public double getPositionY() { return center_y; }
many advantages, but it can lead to hiding the type }

information. Let’s see what could happen: public class Square implements Shape {
double left_top_x, left_top_y, side;
• We want a list to hold a collection of Shape instances.
public Square(double left_top_x, double left_top_y, double side) {
• When retrieving the shapes, List#get(int i) this.left_top_x = left_top_x;
returns a java.lang.Object. This is correct, because this.left_top_y = left_top_y;
this.side = side;
every type “is-a” java.lang.Object. }

• Advantage of polymorphism: we can put different public double getPositionX() { return left_top_x; }

© 2022 Ritwik Banerjee

public double getPositionY() { return left_top_y; }
shapes in the same list. }

• Disadvantage of polymorphism: the items all behave

like java.lang.Object instances. So, to get the ‘real’
List shapes = new ArrayList();
type, it must undergo a typecast. shapes.add(new Circle(1, 1, 1));
shapes.add(new Square(1.5, 1.5, 1));
• Correctly typecasting is the programmer’s shapes.add(new String("tada!"));
responsibility. An incorrect cast will cause the code to
Shape s1 = (Circle) shapes.get(0);
crash with a ClassCastException. Shape s2 = (Shape) shapes.get(1);
Shape s3 = (Shape) shapes.get(2);

22
 public interface Shape {
double getPositionX();

Information
double getPositionY();
}

public class Circle implements Shape {

double center_x, center_y, radius;

hiding 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; }

• There are two layers of information hiding public double getPositionY() { return center_y; }

going on here:
}

public class Square implements Shape {

1) every item appears as java.lang.Object. double left_top_x, left_top_y, side;

2) even if the programmer remembers (mostly public Square(double left_top_x, double left_top_y, double side) {
because of the variable name, shapes) that all this.left_top_x = left_top_x;
this.left_top_y = left_top_y;
the items are Shape instances, casting to specific this.side = side;
}
subtypes of Shape can again be problematic.
public double getPositionX() { return left_top_x; }
We would certainly prefer a system that

© 2022 Ritwik Banerjee

public double getPositionY() { return left_top_y; }
• }
catches such mistakes at compile time.
Otherwise, we have a language with static List shapes = new ArrayList();
typing that suffers from a disadvantage of shapes.add(new Circle(1, 1, 1));

dynamic typing!
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
Type viewed as a ‘container’
The problem posed by polymorphism can (at least partly) be resolved, again,
by polymorphism.

• Think of the data type as a container, and now we need a way to specify the
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): <T>
• Such a Box interface is the generic construct for
interface Box<T> {
our notion of a container, and the ‘payload’ type in
void box(T t);
it is denoted by the parameter T.

© 2022 Ritwik Banerjee

T unbox();
– The parameter is called a type parameter. }
– The generic construct is a parameterized type.

24
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)

• The preferred way of using polymorphism in functional programming is

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.

© 2022 Ritwik Banerjee

• OCaml example:
– Queue.create creates an empty queue of the type 'a, 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 as specified.

25
 Type as a parameter
Java OCaml
• Broadening conversions are implicit, but • Broadening conversion requires extra
parametric polymorphism requires extra code: code, but parameterization is implicit,
List<String> strings = new LinkedList<String>(); and no additional code is needed.
item.add(“this is a string”); let items = Queue.create();;
Queue.add "s" items;;
• The generic parameter is coded using a pair of
angular brackets: <T>. • Since the use of parameters is automatic
and implicit, the code is less verbose.

© 2022 Ritwik Banerjee

• When the actual list is created, the parameter is
replaced* by the concrete type. • OCaml uses type inference to check the
– That is, List<T> becomes List<String>. type (in this example, string).

26
Parametric polymorphism
• Perhaps the single most important advantage of the ability to use a type as a
parameter is that we need to write functions that are not type-specific only
once, and reuse them throughout, with different parameters.
• Let’s think of a function that swaps the two items in an ordered pair:
let swap (x, y) = (y, x);;
val swap : 'a * 'b -> 'b * 'a = <fun>
– Here, 'a and 'b are type variables, and the function’s type is derived from that.

• Since parameterization is implicit in OCaml, we can write such a function

without even thinking about the types. As a result, we never have to write

© 2022 Ritwik Banerjee

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
Parametric polymorphism
• Perhaps the single most important advantage of the ability to use a type as a
parameter is that we need to write functions that are not type-specific only
once, and reuse them throughout, with different parameters.
• Let’s think of a function that swaps the two items in an ordered pair:
let swap (x, y) = (y, x);;
val swap : 'a * 'b -> 'b * 'a = <fun>
– Here, 'a and 'b are type variables, and the function’s type is derived from that.

• Instead, we can use the polymorphic swap function by replacing the type
variables by concrete types as and when needed:

© 2022 Ritwik Banerjee

# swap(1,2);;
- : int * int = (2, 1)
# swap("foo", 0);;
- : int * string = (0, "foo")
# swap("pi", 3.14);;
- : float * string = (3.14, "pi")

28
Parametric polymorphism
• Writing the polymorphic swap function was a no-brainer in OCaml, because
OCaml performs automatic type inference.

• We could have specified our function as

let swap ((x: 'a), (y: 'b)) : 'b * 'a = (y, x);;

• But instead, we were simply able to write

let swap (x,y) = (y,x);;

• Clearly, writing polymorphic functions in OCaml is

a) less verbose because we don’t have to specify the polymorphic types, and

© 2022 Ritwik Banerjee

b) intuitive, because we don’t even have to think about polymorphism while writing
such a function.

29
Parametric polymorphism
Now let us see how to write the exact same function in another statically
typed language, Java.

• Without consciously thinking about polymorphism, we can’t even begin to

write the body of the function:
static ??? swap(??? x, ??? y) {
// haven't even reached this yet
}

• We need to define the type variables explicitly:

© 2022 Ritwik Banerjee

static <A, B> ??? swap(A x, B y) {
// haven't even reached this yet
}
– 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
Parametric public static class PolymorphicPair<A, B> {
A first;

polymorphism
B second;

public PolymorphicPair(A a, B b) {
this.first = a;
this.second = b;
}
• We need to first define the proper
data type. /* Define swap as an instance method */
– Without this, we cannot even figure out public PolymorphicPair<B, A> swap() {
the return type of the swap function. return new PolymorphicPair<>(second, first);
}
• Then, we have two ways of defining }
swap: 1
1) an instance method within the body of
the type we just defined, or

© 2022 Ritwik Banerjee

2) a static method that we can write
anywhere.

static <A, B> PolymorphicPair<B, A> swap(PolymorphicPair<A, B> pair) {

return new PolymorphicPair<>(pair.second, pair.first);
}
2
31
 public interface Stack<E> {
void push(E element);
E pop();

Parametrized
E peek();
boolean isEmpty();
String toString();

types
}

public class ListStack<E> implements Stack<E> {

private List<E> stack;
private int top;
• In the example we just saw, we had to public ListStack() {
define a parametrized data type in stack = new LinkedList<>();
order to define a polymorphic function }
in Java. public void push(E element) {
stack.add(element);
• We can revisit another type we have }
seen before, and do the same: a stack.
public E pop() {
– It makes sense to parameterize it, since
return stack.remove(stack.size() - 1);
none of the core stack functions – pop(),

© 2022 Ritwik Banerjee

}
push(), peek(), isEmpty() – depend
on the type of the items in the stack! public E peek() {
– Note that we changed the stack return stack.get(stack.size() - 1);
implementation to be list-backed instead }
of array-backed, and did not implement
public boolean isEmpty() {
the toString() method.
return stack.size() == 0;

32
}
}
(* 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};;

© 2022 Ritwik Banerjee

Parametrized types
Similarly, we can define polymorphic types in OCaml using recursion.
33
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<Integer> ints = new ArrayList<Integer>();
- This is not:
List<int> ints = new ArrayList<int>();
• Generics, i.e., parametric polymorphism, are a compile-time construct in
WHY? 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

© 2022 Ritwik Banerjee

cannot be used as parameters in Java generics.

Type parameters and primitives in Java: a history lesson

34
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<Integer> and another new
compiled class for List<String>, and so on.

© 2022 Ritwik Banerjee

This approach is called code specialization.
– 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
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

© 2022 Ritwik Banerjee

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<String> and Map<String, Character> are translated to
List and Map, respectively.

36
interface Comparable<A> { int compareTo(A that); }

class NumericValue implements Comparable<NumericValue> {

private byte value;
public NumericValue(byte value) { this.value = value; }
public byte getValue() { return value; }
public int compareTo(NumericValue that) { return this.value - that.value; }

public static void main(String... args) {

List<NumericValue> numberList = new LinkedList<NumericValue>();
numberList.add(new NumericValue((byte) 0));
NumericValue x = numberList.get(0);
}
}

/* the raw type interface */

interface Comparable { int compareTo(Object that); }

class NumericValue implements Comparable {

private byte value;
public NumericValue(byte value) { this.value = value; }
public byte getValue() { return value; }
public int compareTo(NumericValue that) { return this.value - that.value; }

© 2022 Ritwik Banerjee

/* ”bridge method" added by the compiler */
public int compareTo(Object that) {
return this.compareTo((NumericValue) that);
}

public static void main(String... args) {

List numberList = new LinkedList(); /* the raw type list */
numberList.add(new NumericValue((byte) 0));

Type erasure
NumericValue y = (NumericValue) numberList.get(0); /* typecast added */
}

37
}
Parameter types and subtyping
List<String> strings = new ArrayList<String>();
List<Object> objects = strings;

• What does the above code do? Is it even semantically correct?

• The first line is fine, of course. But the second line is tricky. The key
question here is “since String is a subtype of Object, is a list of Strings a
subtype of a list of Objects?”

• The second line is creating an a name equivalence through aliasing.

– Through this alias, we can now add arbitrary objects to the list. And thus, retrieved

© 2022 Ritwik Banerjee

items need not be strings anymore!
– This will obviously not work because the bridge methods and typecasts added for
type erasure will work only for strings.
– The Java compiler will prevent this from happening, and the second line will cause
a compile-time error :-
incompatible types: List<String> cannot be converted to List<Object>

38
 Parameter types and subtyping
• In general, if A is a subtype of B, and R is some parameterized type (e.g.,
List, Set), it is NOT the case that R<A> is a subtype of R<B>.
• Suppose we have the following type hierarchy:

interface Employee {...}

class Person {...}
class Driver extends Person {...}
class UberDriver extends Person implements Employee {...}

You should be aware that the following are incorrect (except for the first instantiation):

© 2022 Ritwik Banerjee

•

List<UberDriver> uberdrivers = new ArrayList<>();

List<Driver> drivers = uberdrivers;
List<Person> people = uberdrivers;
List<Employee> employees = uberdrivers;

39
Parameters and
algebraic types
void printCollection(Collection c) {
• In general, if A is a subtype of B, and R is some Iterator i = c.iterator();
parameterized type (e.g., List, Set), it is NOT the for (int k = 0; k < c.size(); k++)
case that R<A> is a subtype of R<B>. System.out.println(i.next());
}
• 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<Person> and corrupted it by adding non-
drivers to that list.

© 2022 Ritwik Banerjee

– The restrictions on subtyping of algebraic data type
with parameters mean that we will not have such a
problem.

• However, it introduces another issue. void printCollection(Collection<Object> c) {

– Consider the two methods here, one printing a raw for (Object obj : c)
System.out.println(obj);
type collection, and the other trying to print a
parameterized collection: }

40
Parameters and
algebraic types
void printCollection(Collection c) {
• In general, if A is a subtype of B, and R is some Iterator i = c.iterator();
parameterized type (e.g., List, Set), it is NOT the for (int k = 0; k < c.size(); k++)
case that R<A> is a subtype of R<B>. System.out.println(i.next());
}
• This solves one type of problems:
– Imagine a situation where a list of drivers were
being maintained by the DMV, and they shared that But the code below is not very useful, because
data with law enforcement, who treated it as a it only takes Collection<Object>, which,
List<Person> and corrupted it by adding non- as we just saw, is not a supertype of all kinds
drivers to that list.
of collections!

© 2022 Ritwik Banerjee

– The restrictions on subtyping of algebraic data type
with parameters mean that we will not have such a What is the supertype of all types of
problem. collections?

• However, it introduces another issue. void printCollection(Collection<Object> c) {

– Consider the two methods here, one printing a raw for (Object obj : c)
System.out.println(obj);
type collection, and the other trying to print a
parameterized collection: }

41
 What is the
• 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?

supertype of • In Java, this is written using the unknown parameter type

<?>. It is also called a wildcard type.
all types of • Using this unknown parameter type, we can correctly work

collections?
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.

• But remember, that still doesn’t make it ok to add arbitrary

© 2022 Ritwik Banerjee

objects to this collection:

void printCollection(Collection<?> c) { Collection<?> c = new ArrayList<String>();

for (Object obj : c) { c.add(new Object()); // compile time error
System.out.println(obj);
}
}

42
Working • Adding items:
– The add() method’s parameter is a type variable E, which
denotes the element type of the collection.
with the – Since we don’t know what that is, we can’t use the add()
method on a collection of the unknown type.

unknown – The only exception is null, which is considered a subtype

of every type.

type • Retrieving items:

– This is done by the get() method, which we can use
parameter 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).

© 2022 Ritwik Banerjee

Collection<?> c = new ArrayList<String>();
c.add(new Object()); // compile time error

43
 public class Canvas {

Adding flexibility public void draw(Shape s) {

s.draw(this);

to type variables
}
}

public abstract class Shape {

public abstract void draw(Canvas c);
• 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 public class Circle extends Shape {
parameterized collections. That takes away all private int x, y, radius;
the item-specific functionality!
public void draw(Canvas c) {
• Think of a rudimentary drawing program that /* implementation */
draws a picture by using various simple }
shapes, where each shape has a draw() }
method. If we store all the shapes and retrieve

© 2022 Ritwik Banerjee

them only as Objects, we will not be able to public class Rectangle extends Shape {
call the draw() method on them. private int x, y, width, height;

• A typical Java codebase would look something public void draw(Canvas c) {

like this /* implementation */
}
}

44
 Adding flexibility
public void drawAll(List<Shape> shapes) {
to type variables
for (Shape s : shapes) s.draw(this);
}
• No matter what the final drawing looks
public void drawAll(List<? extends Shape> shapes) { like, we probably need to maintain a
for (Shape s : shapes) s.draw(this); 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<Circle> is not a subtype of
List<Shape>).
• There is a subtle but important
distinction we want here: we want the
method to accept any kind of Shape,

© 2022 Ritwik Banerjee

instead of just Shape.
• This is done by replacing List<Shape>
with List<? extends Shape>, which
will accept a list of any subtype of Shape.
• So now, we can call drawAll() on a
List<Rectangle> or a List<Circle>,
as we want.
45
 Adding flexibility
public void drawAll(List<Shape> shapes) {
to type variables
for (Shape s : shapes) s.draw(this);
}
• The expression <? extends Shape> is an
public void drawAll(List<? extends Shape> shapes) { example of a bounded parameter or a
for (Shape s : shapes) s.draw(this); 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

© 2022 Ritwik Banerjee

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<?
extends Shape>.

46
 Adding flexibility
public void drawAll(List<Shape> shapes) {
to type variables
for (Shape s : shapes) s.draw(this);
}
• Just like we saw with the unbound wildcard, we
public void drawAll(List<? extends Shape> shapes) {
still can’t add() items to a List<? extends
for (Shape s : shapes) s.draw(this);
}
Shape>.
void addRectangle(List<? extends Shape> s)
{ s.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.

© 2022 Ritwik Banerjee

–
– 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

47
converted to capture#1 of ? extends Shape
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 <T> void addToCollection(T a, Collection<T> c) { c.add(a); }

© 2022 Ritwik Banerjee

48
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 */

© 2022 Ritwik Banerjee

addToCollection(new Circle(), new ArrayList<Shape>());

/* Shape is not a supertype of Integer, so this is a compile-time error */

addToCollection(new Integer(5), new TreeSet<Shape>());

49
Polymorphic methods
• Let’s look at some actual methods in boolean containsAll(Collection<?> c);
Java’s collection library. boolean addAll(Collection<? extends E> c);

• We just saw the issues with using the boolean removeAll(Collection<?> c);
wildcard type or simply using Object boolean removeIf(Predicate<? super E> filter);
as our type variable.
boolean retainAll(Collection<?> c);
• We also saw that using a specific
type variable as the parameter seems
to resolve these issues.

© 2022 Ritwik Banerjee

• We could have used method boolean <T extends E> addAll(Collection<T> c);
definitions like this instead

So under what circumstances, and why, can/should we use the wildcard (bounded or otherwise)?

50
Polymorphic methods with unknown type
parameters
• Consider the method to copy items from a source list src, to a destination list dest:
public static <T, S extends T> void copy(List<S> src, List<T> dest) {
/* 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.

© 2022 Ritwik Banerjee

– It makes the code more readable by immediately conveying that a parameter is,
indeed, unknown.
– It is similar
public to the
static usevoid
<T> of the underscore “_”
copy(List<? wildcard
extends T> in OCaml.
src, List<T> dest) {
/* implementation */
}

51
 • We saw upper bounds on type parameters, e.g., <? extends T> or
Bounded type
parameters
<S extends T>.
• But lower bounds are possible too! That is, we can specify bounds
like <? super T>.
• The upper bounds allow for flexible use of the type, but make the
data structure holding this type (usually a collection) effectively
“read only”.
• The lower bounds have the opposite effect – they create collections
that are effectively “write only”.
• Together, this is often called the PECS principle, a mnemonic for
“producer extends consumer super”:
– If you want to traverse through a collection and do something with each

© 2022 Ritwik Banerjee

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
Bounded wildcards in “write only” structures Try running these examples to see for yourself what happens
public class BoundedWildcards {
interface Output<T> { void print(T t); }

static class OutputImpl<T> implements Output<T> {

public void print(T t) { System.out.println(t.toString()); }
}

static <T> void writeAll(Collection<T> collection, Output<T> out) {

T first = null;
for (T t : collection) {
if (first == null) first = t;
out.print(t);
}
return first;
}

© 2022 Ritwik Banerjee

public static void main(String... args) {
Output<Object> output = new OutputImpl<>();
Collection<String> strings = new ArrayList<>();

// neither String nor Object is appropriate for the type T

// The collection and the type parameter of output must be the same type
String s = writeAll(strings, output);

}
}
53
Bounded wildcards in “write only” structures Try running these examples to see for yourself what happens
public class BoundedWildcards {
interface Output<T> { void print(T t); }

static class OutputImpl<T> implements Output<T> {

public void print(T t) { System.out.println(t.toString()); }
}

static <T> T writeAll(Collection<? extends T> collection, Output<T> out) {

T first = null;
for (T t : collection) {
if (first == null) first = t;
out.print(t);
}
return first;
}

© 2022 Ritwik Banerjee

public static void main(String... args) {
Output<Object> output = new OutputImpl<>();
Collection<String> strings = new ArrayList<>();

// the returned item is an Object, not a String

String s = writeAll(strings, output);

}
}
54
Bounded wildcards in “write only” structures Try running these examples to see for yourself what happens
public class BoundedWildcards {
interface Output<T> { void print(T t); }

static class OutputImpl<T> implements Output<T> {

public void print(T t) { System.out.println(t.toString()); }
}

static <T> T writeAll(Collection<T> collection, Output<? super T> out) {

T first = null;
for (T t : collection) {
if (first == null) first = t;
out.print(t);
}
return first;
}

© 2022 Ritwik Banerjee

public static void main(String... args) {
Output<Object> output = new OutputImpl<>();
Collection<String> strings = new ArrayList<>();

// this is ok
String s = writeAll(strings, output);

}
}
55
 • Overloading and
overriding with type
parameters
• Reified types

Additional notes • Compile-time and

runtime types
• Java arrays and
components

© 2022 Ritwik Banerjee

• Variance

56
Overloading with
type parameters class OverloadingDemo {
public <T> void method(T t) {
• Methods with type parameters can /* implementation */
be overloaded as usual. }

public <T extends Number> void method(T t) {

/* implementation */
}

public void method(Long l) {

/* implementation */

© 2022 Ritwik Banerjee

}
}

57
Overloading with
type parameters public class OverloadingDemo {
public void aMethod(List<String> strings) {
/* implementation */
• But is this code legal? }

public void aMethod(List<Integer> ints) {

/* implementation */
}

public int aMethod(List<Double> doubles) {

/* implementation */
return 0;

© 2022 Ritwik Banerjee

}
}

58
Overloading with
type parameters
• But is this code legal? class OverloadingDemo {
public <T extends Number> void method(T arg) {
/* implementation */
}

public void method(Number arg) {

/* implementation */
}
}

© 2022 Ritwik Banerjee

59
Overriding with type parameters
• The two methods in the subclass here class Super {
overload each other because they have the public void printAll(Collection<?> c) {
same name but different signatures (one has for (Object o : c)
List<?> as its parameter, and the other has System.out.println(o.toString());
the raw type Collection). }
}
• The printAll() method in the superclass
and the second printAll() method in the class Sub extends Super {
subclass have parameters of the type public void printAll(List<?> c) {
for (Object o : c)
Collection<?> and Collection,
System.out.println(o.toString());
respectively. }
• The subclass’ method overrides the

© 2022 Ritwik Banerjee

superclass’ method even though the method public void printAll(Collection c) {
signatures are not identical. How is this for (Object o : c)
System.out.println(o.toString());
possible? }
– Because the subclass signature is the }
erasure of the superclass signature.

60
Overriding with type parameters
• The converse is illegal – that is, if the
superclass signature is the erasure of class Super {
the subclass signature. public void printAll(Collection c) {
for (Object o : c)
• This is a name clash error. It is System.out.println(o.toString());
neither overloading nor overriding. }
}

class Sub extends Super {

public void printAll(Collection<?> c) {
for (Object o : c)

© 2022 Ritwik Banerjee

System.out.println(o.toString());
}
}

61
 • To reify means to make an abstract item more concrete or real. In

Reification
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<Integer> or
a List<Integer>. It only sees the raw type.

• 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

© 2022 Ritwik Banerjee

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
 Unlike other collection data types, arrays in Java reify their component.

Reification
•

• That is, the JVM views a List<Pair<String, String>> as the raw

type List at runtime, but a Pair<String, String>[] becomes a
Pair[] at runtime and not an Object[].

public class Pair<K, V> {

K key;
V value;

public Pair(K key, V value) {

this.key = key;
this.value = value;
}

© 2022 Ritwik Banerjee

public K getKey() { return key; }
public void setKey(K key) { this.key = key; }
public V getValue() { return value; }
public void setValue(V value) { this.value = value; }
}

63
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<String> aList = new ArrayList<>();
– 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

© 2022 Ritwik Banerjee

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
Java arrays and • This leads to some “interesting” behavior in Java when it
comes to using arrays with type parameters.
their components • We already saw that even though String is a subtype of
Object, List<String> is not a subtype of
List<Object>.

• So we get a compile error in the 2nd line of the following

code due to casting
List<String> between
strings = newincompatible types:
ArrayList<>(10);
List<Object> objects = (List<Object>) strings;
objects.add(new Object());

• However, if we had used an array instead of a list,

String[] strings = new String[10];
Object[] objects = strings;
objects[0] = new Object();
the code compiles just fine, and at runtime throws an

© 2022 Ritwik Banerjee

error.

• So why can’t this error be realized at compile time?

65
Java arrays and There are two reasons why this error can’t be caught at
compile-time:
their components 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

© 2022 Ritwik Banerjee

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
Java arrays and There are two reasons why this error can’t be caught at
compile-time:
their components 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

© 2022 Ritwik Banerjee

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
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

© 2022 Ritwik Banerjee

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
 © 2022 Ritwik Banerjee
We say the type parameter T is covariant in the generic
Variance of type R<T> if, whenever A is a subtype of B, R<A> is a
subtype of R<B>.
parametric types in In Java, there is no subtype-supertype relation between
Java List<Mammal> and List<Animal>, i.e., generics are
invariant.

69
<? extends Animal>

<? extends Mammal>

© 2022 Ritwik Banerjee

Think about the subtyping of parametrized types in terms of
Variance of whether or not a “region” in the type hierarchy is contained in
another. The region for <? extends Mammal> is contained
parametric types in entirely within the region for <? extends Animal>.

Java
As such, generics are covariant in their upper bounds. That is,
List<? extends Mammal> is a subtype of List<?
extends Animal>.

70
 mal>
Mam
uper
s
<?
t>
Ca
r
pe
su
<?

© 2022 Ritwik Banerjee

Think about the subtyping of parametrized types in terms of
Variance of whether or not a “region” in the type hierarchy is contained in
another. The region for <? super Mammal> is contained
parametric types in entirely within the region for <? super Cat>.

Java As such, generics are contravariant in their lower bounds.

That is, List<? super Mammal> is a subtype of
List<? super Cat>.
71
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.

© 2022 Ritwik Banerjee

Image Source: https://commons.wikimedia.org/wiki/File:Java_wildcard_subtyping.svg,
provided under CC BY-SA 3.0 license.

72
Variance of return
types and argument
types
public interface Positionable {
• Variance plays a role in the flexibility void setPosition(Collection<? extends Point> points);
of overriding methods. For example, }
it is reasonable to ask the questions:
// This is not a valid override (even though List<? extends Point> is
– if I’m overriding a method in a subclass, // a subtype of Collection<? extends Point>) since Java is invariant
can the method return a subtype? // in the argument types.
– if I’m overriding a method in a subclass, public class Quadrilateral implements Positionable {
can the method accept arguments from a @Override
subtype? public void setPosition(List<? extends Point> points) {
/* implementation */
• The answers are language dependent. }

© 2022 Ritwik Banerjee

}
• 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).

73