ITI 1121. Introduction to Computing II – subtitle
ITI 1121. Introduction to Computing II
Parametric polymorphism
by
Marcel Turcotte
Version February 2, 2020
Preamble
Preamble
Overview
Overview
Parametric polymorphism
We will see that generic types allow the design of data structures that can save objects of
various classes without compromising the static analysis of the type of expressions. These
concepts will be used to design robust abstract data types.
General objective :
This week you will be able to describe the mechanisms by which generic data
structures can be designed in Java without compromising static type analysis.
1 52
Preamble
Learning objectives
Learning objectives
Use a parameterized type.
Define a new generic type.
Design a generic class method.
Recognize situations where generic types are advantageous.
Explain in your own words how generic types lead to robust applications.
Readings:
https://docs.oracle.com/javase/tutorial/java/generics/index.html
2 52
https://docs.oracle.com/javase/tutorial/java/generics/index.html
Preamble
Plane
Plan
1 Preamble
2 Motivation
3 Generics
4 Méthodes génériques
5 Prologue
3 52
Motivation
Generic data structures
Let’s consider the example of the class Pair again. This time, we want to save the
references of two objects of type Time.
What are the instance variables?
Give the signature of the instance methods?
4 52
Time Pair
pub l i c c l a s s P a i r {
p r i v a t e Time f i r s t ;
p r i v a t e Time second ;
pub l i c P a i r ( Time f i r s t , Time second ) {
t h i s . f i r s t = f i r s t ;
t h i s . second = second ;
}
pub l i c Time g e t F i r s t ( ) {
re tu rn f i r s t ;
}
pub l i c Time getSecond ( ) {
re tu rn second ;
}
}
⇒ new Pair(new Time(14,30), new Time(16,0));
5 52
Shape Pair
pub l i c c l a s s P a i r {
p r i v a t e Shape f i r s t ;
p r i v a t e Shape second ;
pub l i c P a i r ( Shape f i r s t , Shape second ) {
t h i s . f i r s t = f i r s t ;
t h i s . second = second ;
}
pub l i c Shape g e t F i r s t ( ) {
re tu rn f i r s t ;
}
pub l i c Shape getSecond ( ) {
re tu rn second ;
}
}
⇒ new Pair(new Circle(0,0,0), new Rectangle(1,1,1,1);
6 52
Discussion
Problem: We want to design a class Pair that we can use to save objects of various
types.
What will be the type of variables and the parameters?
7 52
Pair
pub l i c c l a s s P a i r {
p r i v a t e ______ f i r s t ;
p r i v a t e ______ second ;
pub l i c P a i r (______ f i r s t , ______ second ) {
t h i s . f i r s t = f i r s t ;
t h i s . second = second ;
}
pub l i c ______ g e t F i r s t ( ) {
re tu rn f i r s t ;
}
pub l i c ______ getSecond ( ) {
re tu rn second ;
}
}
8 52
Caveat: a temporary solution
We’re first exploring an avenue using the concepts that we have been seen in class
so far.
That solution was actually the only possible one in 2004.
This solution doesn’t offer any type safety.
9 52
Find the type of the variable first!
It must be possible to save the reference from any object in the variable first.
What’s its type?
What is the most general type in Java?
What is the most general class in Java?
10 52
Pair
pub l i c c l a s s P a i r {
p r i v a t e Object f i r s t ;
p r i v a t e Object second ;
pub l i c P a i r (______ f i r s t , ______ second ) {
t h i s . f i r s t = f i r s t ;
t h i s . second = second ;
}
pub l i c ______ g e t F i r s t ( ) {
re tu rn f i r s t ;
}
pub l i c ______ getSecond ( ) {
re tu rn second ;
}
}
11 52
Pair
pub l i c c l a s s P a i r {
p r i v a t e Object f i r s t ;
p r i v a t e Object second ;
pub l i c P a i r ( Object f i r s t , Ob ject second ) {
t h i s . f i r s t = f i r s t ;
t h i s . second = second ;
}
pub l i c ______ g e t F i r s t ( ) { // type o f the r e t u r n v a l u e ?
re tu rn f i r s t ;
}
pub l i c ______ getSecond ( ) {
re tu rn second ;
}
}
12 52
Pair
pub l i c c l a s s P a i r {
p r i v a t e Object f i r s t ;
p r i v a t e Object second ;
pub l i c P a i r ( Object f i r s t , Ob ject second ) {
t h i s . f i r s t = f i r s t ;
t h i s . second = second ;
}
pub l i c Object g e t F i r s t ( ) {
re tu rn f i r s t ;
}
pub l i c Object getSecond ( ) {
re tu rn second ;
}
}
13 52
Pair
How is this class used?
P a i r p ;
S t r i n g a ;
a = ” King ” ;
S t r i n g b ;
b = ” Edward ” ;
p = new P a i r ( a , b ) ;
a = p . g e t F i r s t ( ) ;
b = p . getSecond ( ) ;
Do you see a problem with these statements?
14 52
Pair
P a i r p ;
S t r i n g a ;
a = ” King ” ;
S t r i n g b ;
b = ” Edward ” ;
p = new P a i r ( a , b ) ;
a = ( S t r i n g ) p . g e t F i r s t ( ) ;
b = ( S t r i n g ) p . g e t F i r s t ( ) ;
The class textbfObject is more general than the class textbfString! Each time an
element is removed from a data structure, the type of the return value must be
forced (type cast).
There will be an error at runtime if the object is not of type String.
With this type cast, we’re depriving ourselves of any help the compiler could give us.
15 52
Generics
Generics
Java 1.5 was a major update ∗. It introduced the concept of generic types (“generics”).
pub l i c c l a s s Pai r
. . .
}
The class declaration has a (formal) type parameter. This is the type of the objects
that will be saved by the objects of the class Pair.
∗This was 2004.
16 52
Usage
The value of T must be specified when declaring a variable.
Pai r
Pa i r range ;
as well as when creating an object:
name = new Pai r
I n t e g e r min ;
min = new I n t e g e r ( 0 ) ;
I n t e g e r max ;
max = new I n t e g e r ( 1 0 0 ) ;
range = new Pai r (min , max ) ;
17 52
Generic types: A winning solution
Victories on two fronts:
A single implementation of the class Pair that is reused in multiple contexts (it saves
references of objects of various types).
All this, without sacrificing the validation of the types at the compilation stage.
18 52
Generics
A generic type is a type with formal type parameters.
A parameterized type is an instantiation of a generic type with an actual type
argument.
19 52
Generics
Defining a generic type.
A generic type is a reference type having one or more parameters of type.
A generic type is a class with one or more type parameters.
20 52
pub l i c c l a s s Pai r
p r i v a t e T f i r s t ;
p r i v a t e T second ;
pub l i c P a i r (T f i r s t , T second ) {
t h i s . f i r s t = f i r s t ;
t h i s . second = second ;
}
pub l i c T g e t F i r s t ( ) {
re tu rn f i r s t ;
}
pub l i c T getSecond ( ) {
re tu rn second ;
}
pub l i c vo id s e t F i r s t (T v a l u e ) {
f i r s t = v a l u e ;
}
pub l i c vo id se tSecond (T v a l u e ) {
second = v a l u e ;
}
}
Generics
What did we get?
“Generic” and “robust” types.
Pai r range ;
range = new Pai r (new I n t e g e r ( 0 ) ,new I n t e g e r ( 1 0 ) ) ;
I n t e g e r i ;
i = range . g e t F i r s t ( ) ;
22 52
Compilation errors!
The declared object of type Pair
object of type Integer.
range . s e t F i r s t ( ” V o i l a ” ) ;
will produce a compile time error, and that’s what we’re hoping for!
Test.java:20: setFirst(java.lang.Integer)
in Pair
(java.lang.String)
range.setFirst(“Voila”);
^
1 error
23 52
More compilation errors.
In the same way, a reference variable having the following compilation type
Pair
The statement
range = new Pai r
will produce a compilation error,
Test.java:22: incompatible types
found : Pair
required: Pair
range = new Pair
^
1 error
24 52
pub l i c c l a s s Pai r
p r i v a t e X f i r s t ;
p r i v a t e Y second ;
pub l i c P a i r (X f i r s t , Y second ) {
t h i s . f i r s t = f i r s t ;
t h i s . second = second ;
}
pub l i c X g e t F i r s t ( ) {
re tu rn f i r s t ;
}
pub l i c Y getSecond ( ) {
re tu rn second ;
}
pub l i c vo id s e t F i r s t (X v a l u e ) {
f i r s t = v a l u e ;
}
pub l i c vo id se tSecond (Y v a l u e ) {
second = v a l u e ;
}
}
Parameterized type
When using a generic type, in this case Pair, we must provide type values for each
formal type parameter.
pub l i c c l a s s Test {
pub l i c s t a t i c vo id main ( S t r i n g [ ] a r g s ) {
Pa i r
S t r i n g a t t r i b u t e ;
a t t r i b u t e = new S t r i n g ( ” h e i g h t ” ) ;
I n t e g e r v a l u e ;
v a l u e = new I n t e g e r ( 1 0 0 ) ;
p = new Pai r
}
}
26 52
Quiz: are these statements valid?
Pai r
p = new Pai r
p . s e t F i r s t ( ” s e s s i o n ” ) ;
p . s e tSecond ( 1 2 3 4 5 ) ;
27 52
Quiz: are these statements valid?
pub l i c c l a s s T1 {
pub l i c s t a t i c vo id main ( S t r i n g [ ] a r g s ) {
Pa i r
p = new Pai r () ;
}
}
// > javac T1.java
// T1.java:6: incompatible types
// found : Pair
// required: Pair
// p = new Pair
// ^
// 1 error
28 52
Quiz: are these statements valid?
pub l i c c l a s s T2 {
pub l i c s t a t i c vo id main ( S t r i n g [ ] a r g s ) {
Pa i r
p = new Pai r
p . s e t F i r s t ( 1 2 3 4 5 ) ;
p . s e tSecond ( ” s e s s i o n ” ) ;
}
}
T2.java:5: setFirst(java.lang.String) in
Pair
p.setFirst(12345);
^
T2.java:6: setSecond(java.lang.Integer) in
Pair
p.setSecond(“session”);
^
2 errors
29 52
Quiz: are these statements valid?
pub l i c c l a s s T3 {
pub l i c s t a t i c vo id main ( S t r i n g [ ] a r g s ) {
Pa i r
p = new Pai r
I n t e g e r s = p . g e t F i r s t ( ) ;
}
}
// > javac T3.java
// T3.java:8: incompatible types
// found : java.lang.String
// required: java.lang.Integer
// Integer s = p.getFirst();
// ^
// 1 error
30 52
Generics
Generics are used to define “general” data
structures while detecting type errors at compile
time!
31 52
Generic types and interfaces
The interface also allows us to define a reference type.
The interface can also have one or more type parameters.
32 52
Interface as generic type: Comparable.
pub l i c i n t e r f a c e Comparable {
i n t compareTo ( Comparable o t h e r ) ;
}
pub l i c i n t e r f a c e Comparable
i n t compareTo (T o t h e r ) ;
}
33 52
Time: without a parameterized type
pub l i c c l a s s Time implements Comparable {
p r i v a t e i n t t ime InSeconds ;
pub l i c i n t compareTo ( Comparable ob j ) {
Time o t h e r = ( Time ) ob j ;
i n t r e s u l t ;
i f ( t i m e I n s e c o n d s < o t h e r . t ime InSeconds ) {
r e s u l t = −1;
} e l s e i f ( t ime InSeconds == o t h e r . t ime InSeconds ) {
r e s u l t = 0 ;
} e l s e {
r e s u l t = 1 ;
}
re tu rn r e s u l t ;
}
}
34 52
Time: with a parameterized type
pub l i c c l a s s Time implements Comparable
p r i v a t e i n t t ime InSeconds ;
pub l i c i n t compareTo ( Time o t h e r ) {
i n t r e s u l t ;
i f ( t i m e I n s e c o n d s < o t h e r . t ime InSeconds ) {
r e s u l t = −1;
} e l s e i f ( t ime InSeconds == o t h e r . t ime InSeconds ) {
r e s u l t = 0 ;
} e l s e {
r e s u l t = 1 ;
}
re tu rn r e s u l t ;
}
}
35 52
Discussion
pub l i c i n t e r f a c e Comparable {
i n t compareTo ( Comparable o t h e r ) ;
}
pub l i c i n t e r f a c e Comparable
i n t compareTo (T o t h e r ) ;
}
Without generic type, the contract we had asked us to implement a compareTo
method whose parameter was of type Comparable. We then had to force the type,
which could cause a runtime error.
With a generic type, the contract specifies that one must implement a method
compareTo whose type is the same as that of the class in question, here Time or
Person.
36 52
Person: without parameterized type
pub l i c c l a s s Person implements Comparable {
p r i v a t e i n t i d ;
p r i v a t e S t r i n g name ;
pub l i c i n t compareTo ( Comparable ob j ) {
Person o t h e r = ( Person ) ob j ;
i n t r e s u l t ;
i f ( i d < o t h e r . i d ) {
r e s u l t = −1;
} e l s e i f ( i d == o t h e r . i d ) {
r e s u l t = 0 ;
} e l s e {
r e s u l t = 1 ;
}
re tu rn r e s u l t ;
}
}
37 52
Person: with parameterized type
pub l i c c l a s s Person implements Comparable
p r i v a t e i n t i d ;
p r i v a t e S t r i n g name ;
pub l i c i n t compareTo ( Person o t h e r ) {
i n t r e s u l t ;
i f ( i d < o t h e r . i d ) {
r e s u l t = −1;
} e l s e i f ( i d == o t h e r . i d ) {
r e s u l t = 0 ;
} e l s e {
r e s u l t = 1 ;
}
re tu rn r e s u l t ;
}
}
38 52
pub l i c c l a s s Pai r
p r i v a t e S t r i n g f i r s t ;
p r i v a t e S t r i n g second ;
pub l i c S t r i n g g e t F i r s t ( ) {
re tu rn f i r s t ;
}
pub l i c S t r i n g getSecond ( ) {
re tu rn second ;
}
pub l i c vo id s e t F i r s t ( S t r i n g v a l u e ) {
f i r s t = v a l u e ;
}
pub l i c vo id se tSecond ( S t r i n g v a l u e ) {
second = v a l u e ;
}
}
Generic methods
Generic class method
pub l i c c l a s s Test {
pub l i c s t a t i c
f o r ( i n t i =0; i
78,95,53,21,7
S t r i n g [ ] words ;
words = new S t r i n g [ 7 ] ;
words [ 0 ] = ” a lpha ” ;
words [ 1 ] = ” bravo ” ;
words [ 2 ] = ” c h a r l i e ” ;
words [ 3 ] = ” d e l t a ” ;
words [ 4 ] = ” echo ” ;
words [ 5 ] = ” f o x t r o t ” ;
words [ 6 ] = ” g o l f ” ;
d i s p l a y ( words ) ;
> java TestDisplay
alpha,bravo,charlie,delta,echo,foxtrot,golf
Utils.max
pub l i c c l a s s U t i l s {
pub l i c s t a t i c
i f ( a . compareTo ( b ) > 0) {
re tu rn a ;
} e l s e {
re tu rn b ;
}
}
}
43 52
Call to a generic class method
The call to a generic class method does not (usually) require any additional syntax
elements.
The compiler makes the type inference automatically.
I n t e g e r i1 , i2 , iMax ;
i 1 = new I n t e g e r ( 1 ) ;
i 2 = new I n t e g e r ( 1 0 ) ;
iMax = U t i l s . max( i1 , i 2 ) ;
System . out . p r i n t l n ( ” iMax = ” + iMax ) ;
Here, the compiler infers that the parameter type must be Integer.
44 52
Calling a generic class method
S t r i n g s1 , s2 , sMax ;
s1 = new S t r i n g ( ” a lpha ” ) ;
s2 = new S t r i n g ( ” bravo ” ) ;
sMax = U t i l s . max( s1 , s2 ) ;
System . out . p r i n t l n ( “sMax = ” + sMax ) ;
Here, the compiler infers that the parameter type must be String.
45 52
Specify the value of the type parameter
We can still specify the type:
iMax = U t i l s .< I n t e g e r >max( i1 , i 2 ) ;
sMax = U t i l s .< St r i ng >max( s1 , s2 ) ;
46 52
pub l i c c l a s s S o r t A l g o r i t h m s {
pub l i c s t a t i c
vo id s e l e c t i o n S o r t (T [ ] x s ) {
f o r ( i n t i = 0 ; i < xs . l e n g t h ; i ++) { i n t min = i ; f o r ( i n t j = i +1; j < xs . l e n g t h ; j++) { i f ( xs [ j ] . compareTo ( xs [ min ] ) < 0) { min = j ; } } T tmp = xs [ min ] ; x s [ min ] = xs [ i ] ; x s [ i ] = tmp ; } } } A new syntax for loops Java 1.5 had also introduced a new syntax for loops. i n t [ ] x s ; x s = new i n t [ ] {1 , 2 , 3} ; i n t sum = 0 ; f o r ( i n t x : xs ) { sum += x ; } 48 52 Prologue Summary A generic type is a reference type with a formal type parameter. A parameterized type is an instantiation of a generic type with an actual type parameter. Generic types allow the creation of “general” data structures; general in the sense that they save references to objects of various types without compromising type validation. 49 52 Next module Abstract Data Type (ADT): stacks 50 52 References I E. B. Koffman and Wolfgang P. A. T. Data Structures: Abstraction and Design Using Java. John Wiley & Sons, 3e edition, 2016. 51 52 Marcel Turcotte Marcel. École de science informatique et de génie électrique (SIGE) Université d’Ottawa 52 / 52 Marcel. Preamble Overview Learning objectives Plane Motivation Generics Generic methods Prologue