Programmazione
Parametrica
( a.k.a. Generics )
• Introduzione ai meccanismi e concetti della
programmazione parametrica
• Generics e relationi di sottotipo
 wildcards
 generics e vincoli
• Implementazione di classi e metodi
parametrici
• Supporto per i generics nella JVM
Programmazione polimorfa
• Polimorfo ~ multiforme, di molti tipi
• Programmazione polimorfa: creazione di
costrutti (classi e metodi) che possono
essere utilizzati in modo uniforme su dati di
tipo diverso
 In Java, tradizionalmente ottenuta mediante i
meccanismi di sottotipo ed ereditarietà
 Da Java 1.5. anche mediante i meccanismi di
parametrizzazione di tipo (a.k.a. generics)
Variabili di Tipo
• Le variabili (o parametri) di tipo pemettono di creare
astrazioni di tipo
• Classico caso di utilzzo nelle classi “Container”
public class ArrayList<E>
{
public ArrayList() { . . . }
public void add(E element) { . . . }
. . .
}
• E = variabile di tipo
 astrae (e rappresenta) il tipo delle componenti
Continua
Variabili di Tipo
• Possono essere istanziate con tipi classe o interfaccia
ArrayList<BankAccount>
ArrayList<Measurable>
• Vincolo: tipi che istanziano variabili di tipo non possono
essere primitivi (devono essere tipi riferimento)
ArrayList<double> // No!
• Classi wrapper utili allo scopo
ArrayList<Double>
Variabili di tipo e controlli di tipo
• Utilizzare variabili di tipo nella programmazione
permette maggiori controlli sulla correttezza dei
tipi in fase di compilazione
• Aumenta quindi la solidità e robustezza del
codice
Continua
Variabili di tipo e controlli di tipo
• Un classico caso di utilizzo di containers
List intList = new LinkedList();
intList.add(new Integer(0));
Integer x = (Integer) intList.get(0);
• Il cast è problematico, per vari motivi
 verboso, fonte di errori a run time
• Ma necessario per la compilazione e per
localizzare l’eventuale errore a run time
Continua
Variabili di tipo e controlli di tipo
• Container generici: più sintetici ed eleganti
List<Integer> intList = new LinkedList<Integer>();
intList.add(new Integer(0));
Integer x = intList.get(0);
• Compilatore può
 stabilire un invariante sugli elementi della lista
 garantire l’assenza di errori a run-time in forza
di quell’invariante.
Continua
Variabili di tipo e controlli di tipo
List<Integer> intList = new LinkedList<Integer>();
intList.add(new Integer(0));
Integer x = intList.get(0);
• Ora non è possibile aggiungere una stringa
ad intlist:List<Integer>
• Le variabili di tipo rendono il codice
parametrico più robusto e semplice da
leggere e manutenere
Classi parametriche: definizione
• Un frammento delle interfacce List e
Iterator nel package java.util.*
// nulla di particolare, a parte i parametri
// tra parentesi angolate
public interface List<E>
{
void add(E x);
Iterator<E> iterator();
}
public interface Iterator<F>
{
F next();
boolean hasNext();
}
Classi parametriche: uso
• Quando utilizziamo un tipo parametrico, tutte le
occorrenze dei parametri formali sono rimpiazzate
dall’argomento (parametro attuale)
• Meccanismo simile a quello del passaggio dei
parametri in un metodo
• Diversi usi generano tipi diversi
• Ma . . .
 classi parametriche compilate una sola volta
 danno luogo ad un unico file .class
Sintassi: uso
GenericClassName<Type1, Type2, . . .>
Esempio:
ArrayList<BankAccount>
HashMap<String, Integer>
Scopo:
Fornire tipo specifici per ciascuna delle variabili di
tipo introdotte nella dichiarazione
Esempio: Pair<T,S>
• Una semplice classe parametrica per
rappresentare coppie di oggetti
public class Pair<T, S>
{
public Pair(T firstElement, S secondElement)
{
first = firstElement;
second = secondElement;
}
public T getFirst() { return first; }
public S getSecond() { return second; }
private T first;
private S second;
}
Continua
Esempio: Pair<T,S>
• Una semplice classe parametrica per
rappresentare coppie di oggetti:
Pair<String, BankAccount> result
= new Pair<String, BankAccount>
("Harry Hacker", harrysChecking);
• I metodi getFirst e getSecond
restituiscono il primo e secondo elemento,
con i tipi corrispondenti
String name = result.getFirst();
BankAccount account = result.getSecond();
Variabili di tipo: convenzioni
Variabile
Significato Inteso
E
Tipo degli elementi in una collezione
K
Tipo delle chiavi in una mappa
V
Tipo dei valori in una mappa
T,S,U
Tipi generici
Esempio: LinkedList<E>
public class LinkedList<E>
{
. . .
public E removeFirst()
{
if (first == null) throw new NoSuchElementException();
E element = first.data;
first = first.next;
return element;
}
. . .
private Node first;
private class Node
{
E data;
Node next;
}
}
Continua
Esempio: LinkedList<E>
• Notiamo la struttura della classe ausiliaria
che specifica la struttura dei nodi
• Se la classe è interna, come in questo caso,
non serve alcun accorgimento
 all’interno di Node possiamo utilizzare il tipo
E, il cui scope è tutta la classe
• Se invece la classe è esterna, dobbiamo
renderla generica
Esempio: LinkedList<E>
class Node<F>
{
F data;
Node next;
}
public class LinkedList<E>
{
. . .
public E removeFirst()
{
if (first == null) throw new NoSuchElementException();
E element = first.data;
first = first.next;
return element;
}
. . .
private Node<E> first;
}
Continua
Generics e sottotipi
• I meccanismi di subtyping si estendono alle
classi generiche
class C<T> implements I<T> { . . . }
• C<T> <: I<T> per qualunque T
• Analogamente:
class C<T> implements I { . . . }
• C<T> <: I per qualunque T
• Sembra tutto facile, MA . . .
Generics e sottotipi
• Consideriamo
List<Integer> li = new ArrayList<Integer>();
List<Number> ln = li;
• La prima istruzione è legale, la seconda è più
delicata …
 Number è una classe che ha Integer , Double e
altre classi wrapper come sottotipi
 Per capire se la seconda istruzione sia da accettare
come legale continuiamo con l’esempio …
Continua
Generics e sottotipi
List<Integer> li = new ArrayList<Integer>();
List<Number> ln = li; // type error
ln.add(3.14);
Integer i = li.get(0); // uh oh ...
• Come si vede abbiamo un problema
 nella terza istruzione inseriamo un Double
 nella quarta estraiamo un Integer !
• Il vero problema è nella seconda istruzione
 soluzione: errore di compilazione per l’assegnamento
Continua
Generics e sottotipi
• In generale, dati due tipi A e B , ed tipo
generico C<T> abbiamo che:
A ≤ B NON implica C<A> ≤ C<B>
• Quindi, per le stesse ragioni di prima
Set<Integer> NON è sottotipo di Set<Object>
• Come abbiamo visto questo è necessario per
garantire la correttezza
Continua
Generics e sottotipi
• In generale, dati due tipi A e B , ed tipo
generico C<T> abbiamo che:
A ≤ B NON implica C<A> ≤ C<B>
• MA …
A ≤ B implica A[] ≤ B[]
Continua
Generics e sottotipi
Integer[] ai = new Integer[10]
Number[] an = ai;
// type OK
an[0] = 3.14;
// ArrayStoreException
Integer i = ai[0];
// uh oh ...
Continua
Generics e sottotipi
• Le limitazione sulle relazioni di sottotipo
sono contro-intuitive
 uno degli aspetti più complessi dei generics
• Non solo … sono spesso anche troppo
restrittive
 illustriamo con un esempio
Continua
Generics e sottotipi
• Stampa degli elementi di una collezione
• Primo tentativo
static void printCollection(Collection<Object> c)
{
for (Object e:c) System.out.println(e);
}
 Inutile per stampare gli elementi di una generica
Collection<T>
 Collection<Object> non è il supertipo di tutte le
collezioni
Continua
Wildcards
• Stampa degli elementi di una collezione
• Secondo tentativo
static void printCollection(Collection<?> c)
{
for (Object e:c) System.out.println(e);
}
 Collection<?> è il supertipo di tutte le
Collections
 la wildcard ? indica un qualche tipo, non specificato
Continua
Wildcards
void printCollection(Collection<?> c)
{
for (Object e:c) System.out.println(e);
}
• Possiamo estrarre gli elementi di c al tipo
Object
• Corretto perché, qualunque sia il loro vero tipo,
sicuramente è sottotipo di Object
Continua
Wildcards
• D’altra parte …
Collection<?> c = new ArrayList<String>();
c.add(new String()); // errore di compilazione!
• Poichè non sappiamo esattamente quale
tipo indica ?, non possiamo inserire elementi
nella collezione
• In generale, non possiamo modificare valori
che hanno tipo ?
Continua
Domanda
• Date un esempio di codice che causerebbe
errore in esecuzione se permettessimo di
aggiungere elementi a Collection<?>
Risposta
Collection<Integer> ci = new ArrayList<Integer>;
Colletion<?> c = ci;
c.add(“a string”); // non compila
ci.get(0).intValue();
• L’ultima istruzione invocherebbe
intValue() sul primo elemento di ci
• ma quell’elemento ha tipo String …
• Il compilatore previene l’errore, rigettando
la add()
Wilcards con vincoli (bounded)
• Shapes: (again!)
interface Shape
{
public void draw(Graphics g);
}
class Circle extends Shape
{
private int x, y, radius;
public void draw(Graphics g) { ... }
}
class Rectangle extends Shape
{
private int x, y, width, height;
public void draw(Graphics g) { ... }
}
Continua
Wilcards con vincoli (bounded)
• Graphics e il metodo draw()
public class Graphics
{
// disegna una shape
public void draw(Shape s) { s.draw(this); }
// disegna tutte le shapes di una lista
public void drawAll(List<Shape> shapes) {
for (Shape s:shapes) s.draw(this)
}
. . .
}
• Solito problema: drawAll() non può essere
invocato su una List<Circle>
Continua
Bounded Wilcards
• Quello che ci serve è un metodo che accetti liste di
qualunque (sotto) tipo di Shape
void drawAll(List<? extends Shape> shapes) { ... }
• List<? extends Shape>
 bounded wildcard
 indica un tipo sconosciuto, sottotipo di Shape
 il bound può essere qualunque tipo riferimento (classe o
interfaccia)
• Ora il metodo ha la flessibilità necessaria e
desiderata
Continua
Bounded Wilcards
• Graphics e il metodo draw()
public class Graphics
{
// disegna una shape
public void draw(Shape s) { s.draw(this); }
// disegna tutte le shapes di una lista
public void drawAll(List<? extends Shape> shapes)
{
for (Shape s:shapes) s.draw(this)
}
. . .
}
Continua
Bounded Wilcards
• Attenzione: c’è sempre un prezzo da pagare
void addRectangle(List<? extends Shape> shapes) {
// errore di compilazione
shapes.add(new Rectangle());
}
• Non possiamo modificare strutture con
questi tipi [ perché? ]
Metodi Generici
• Metodi che dipendono da una variabile di tipo
• Possono essere definiti all’interno di
qualunque classe, generica o meno
/* trasforma un array in una lista, copiando
* tutti gli elementi di a in l
*/
static void array2List(Object[] a, List<?> l){ . . . }
• N.B. Evitiamo List<Object> perché
renderebbe il metodo non utilizzabie su
liste arbitrarie
Continua
Metodi Generici
• Al solito però . . .
/* trasforma un array in una lista, copiando
* tutti gli elementi di a in l
*/
static void array2List(Object[] a, List<?> l)
{
for (Object o : a) l.add(o) // compiler error
}
• . . . non possiamo aggiungere elementi ad una
struttura (o modificare) con elementi di tipo
wildcard
Continua
Metodi Generici
• Soluzione: rendiamo il metodo parametrico
/* trasforma un array in una lista, copiando
* tutti gli elementi di a in l
*/
static <T> void array2List(T[] a, List<T> l)
{
for (T o : a) l.add(o)
}
• possiamo invocare questo metodo con una
qualunque lista il cui tipo sia supertipo del
tipo base dell’array
 purché sia un tipo riferimento
Invocazione di metodi generici
• Nell’invocazione di un metodo generico non
è necessario passare l’argomento di tipo
• il compilatore inferisce il tipo, se esiste, dai
tipi degli argomenti del metodo
Invocazione di metodi generici
•
Object[] oa = new Object[100];
Collection<Object> co = new ArrayList<Object>();
fromArrayToCollection(oa, co); // T = Object (inferito)
String[] sa = new String[100];
Collection<String> cs = new ArrayList<String>();
fromArrayToCollection(sa, cs); // T = String (inferito)
fromArrayToCollection(sa, co); // T = Object (inferito)
Integer[] ia = new Integer[100];
Float[] fa = new Float[100];
Number[] na = new Number[100];
Collection<Number> cn = new ArrayList<Number>();
fromArrayToCollection(ia, cn); // T = Number (inferito)
fromArrayToCollection(fa, cn); // T = Number (inferito)
fromArrayToCollection(na, cn); // T = Number (inferito)
fromArrayToCollection(na, co); // T = Object (inferito)
fromArrayToCollection(na, cs); // compiler error
Continua
Wildarcds vs variabili di tipo
• Ci sono situazioni in cui è possibili usare
equivalentemente wildcards e variabili di
tipo.
• Nella libreria Collection troviamo
interface Collection<E>
{
public boolean containsAll(Collection<?> c);
public boolean addAll(Collection<? extends E> c);
public boolean addAll(Collection<E> c);
. . .
}
Continua
Wildarcds vs variabili di tipo
• Queste specifiche possono essere espresse
equivalentemente con metodi parametrici
interface Collection<E>
{
public <T> boolean containsAll(Collection<T> c);
public <T extends E> boolean addAll(Collection<T> c);
. . .
}
• Il secondo metodo è parametrico in
qualunque sottotipo di E
 i bounds si possono utilizzare anche con variabili, non
solo con wildcards
Continua
Wildarcds vs variabili di tipo
• Wildcards e variabili di tipo possono coesistere
interface Collection<E>
{
public static <T>
void copy(List<T> dest, List<? extends T> src)
. . .
}
• Notiamo la dipendenza tra i tipi dei due parametri:
 il tipo della sorgente deve essere un sottotipo del tipo
della destinazione
Continua
Wildarcds vs variabili di tipo
• Potremmo analogamente riformulare in modo
da evitare le wildcards
interface Collection<E>
{
public static <T, S extends T>
void copy(<List<T> dest, List<S> src)
. . .
}
• Come scegliere tra le due soluzioni?
Continua
Wildarcds vs variabili di tipo
• In generale, preferiamo le wildcards quando
entrambe le soluzioni sono possibili
• Possiamo darci la seguente “rule of thumb”
 se una variabile di tipo ha una unica occorrenza
nella specifica di un metodo
 e il tipo non è il target di un operazione di
modifica
 utilizziamo una wildcard al posto della variabile
Generics e “erasure”
• I tipi generici sono significativi a compile-time
• La JVM opera invece con tipi “raw”
• Il tipo raw è ottenuto da un tipo generico
mediante un processo detto erasure che
rimuove le variabili di tipo
 il bycode generato da un tipo generico è lo
stesso che viene generato dal corrispondente
tipo raw.
Generics e “erasure”
• Generano lo stesso bytecode
List<String> words = new ArrayList<String>();
words.add(“hi”);
words.add(“there”);
String welcome = words.get(0) + words.get(1);
List words = new ArrayList();
words.add(“hi”);
words.add(“there”);
String welcome =
(String)words.get(0) + (String)words.get(1);
Generics e “erasure”
• Cast-iron guarantee
 i cast impliciti che vengono aggiunti dalla
compilazione di codice generico non
falliscono mai.
Generics e Array
• Non è possibile creare array generici
class MyClass<T>
{
T[] contents = new T[100]; // Non compila
• Ecco perché:
public void showTheProblem()
{
Object[] objs = contents;
objs[0] = new String(); // no ArrayStoreException
T bump = contents[0];
// ClassSclassException
}
}
Variabili di Tipo e Bounds
• Abbiamo visto che possiamo definire bounds
anche per variabili di tipo (non solo wildcards)
• Un caso paradigmatico
public static <T extends Comparable<T>>
T max(Collection<T> coll)
{
T candidate = coll.iterator().next();
for (T e : coll)
if candidate.compareTo(e) < 0) candidate = e;
return candidate;
}
Variabili di Tipo e Bounds
• Il bound su una variabile impone vincoli sulla
variabile, determinando quali metodi possono essere
utilizzati su valori del tipo variabile
public static
<T extends Comparable<T>> T max(T max(List <T> coll)
• Qui il bound è ricorsivo:
 informa che i valori con cui operiamo forniscono un
metodo compareTo()
 che gli argomenti del metodo devono essere dello
stesso tipo dei valori
File LinkedList.java
019:
020:
021:
022:
023:
024:
025:
026:
027:
028:
029:
030:
031:
032:
033:
034:
035:
/**
Returns the first element in the linked list.
@return the first element in the linked list
*/
public E getFirst()
{
if (first == null)
throw new NoSuchElementException();
return first.data;
}
/**
Removes the first element in the linked list.
@return the removed element
*/
public E removeFirst()
Continua
{
File LinkedList.java
036:
037:
038:
039:
040:
041:
042:
043:
044:
045:
046:
047:
048:
049:
052:
053:
if (first == null)
throw new NoSuchElementException();
E element = first.data;
first = first.next;
return element;
}
/**
Adds an element to the front of the linked list.
@param element the element to add
*/
public void addFirst(E element)
{
Node newNode = new Node(element,first);
first = newNode;
}
Continua
File LinkedList.java
054:
055:
056:
057:
058:
059:
060:
061:
062:
063:
064:
065:
066:
067:
068:
069:
070:
071:
/**
Returns an iterator for iterating through this list.
*/
public ListIterator<E> listIterator()
{
return new LinkedListIterator();
}
private Node first;
private class Node
{
E data;
Node next;
}
Continua
LinkedListIterator
• La definiamo come classe interna di
LinkedList<E>
• Implemental’interfaccia ListIterator<E>
• Ha accesso al campo first e alla classe
interna Node
Classe LinkedListIterator
072:
073:
074:
075:
076:
077:
078:
079:
080:
081:
082:
083:
private class LinkedListIterator implements ListIterator<E>
{
/**
Costruisce un iteratore posizionato sul primo
elemento della lista
*/
public LinkedListIterator()
{
last
= null; // ultimo nodo visitato
previous = null; // precedente a position
}
Continua
LinkedListIterator – next()
084:
085:
086:
087:
088:
089:
090:
091:
092:
093:
094:
095:
096:
097:
098:
099:
100:
101:
102:
/**
Posizione l’iteratore sul prossimo.
@return il prossimo elemento
*/
public E next()
{
if (!hasNext())
throw new NoSuchElementException();
previous = last; // Remember for remove
if (last == null)
last = first;
else
last = last.next;
return last.data;
}
Continua
LinkedListIterator – hasNext()
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
/**
Testa se c’è un elemento dopo l’ultimo
visitato.
@return true se esiste un elemento dopo
l’ultimo visitato
*/
public boolean hasNext()
{
if (last == null)
return first != null;
else
return last.next != null;
}
Continua
LinkedListIterator – add()
117:
118:
119:
121:
122:
123:
124:
125:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
/** Aggiunge un elemento dopo last e sposta
l’iteratore sul prossimo elemento.
*/
public void add(E element)
{
if (last == null)
{
addFirst(element); last = first;
}
else
{
Node newNode = new Node();
newNode.data = element;
newNode.next = last.next;// (1)
last.next = newNode;
// (2)
last = newNode;
// (3)
}
previous = last;
// (4)
Continua
}
LinkedListIterator – add()
last
LinkedListIterator – remove()
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
/** Rimuove l’elemento puntato da last. Può essere
invocato solo dopo una chiamata a next()
*/
public void remove()
{
if (previous == last)
throw new IllegalStateException();
if (last == first)
{
removeFirst();
}
else
{
previous.next = last.next; // (1)
}
last = previous; // (2)
}
Continua
LinkedListIterator –remove()
last
Classe LinkedListIterator
159:
/**
160:
Sets the last traversed element to a different
161:
value.
162:
@param element the element to set
163:
*/
164:
public void set(E element)
165:
{
166:
if (position == null)
167:
throw new NoSuchElementException();
168:
position.data = element;
169:
}
170:
171:
private Node position;
172:
private Node previous;
173:
} // end LinkedListIterator
174: } // end LinkedList
File ListIterator.java
01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
/**
A list iterator allows access of a position in a linked
list. This interface contains a subset of the methods
of the standard java.util.ListIterator interface. The
methods for backward traversal are not included.
*/
public interface ListIterator<E>
{
/**
Moves the iterator past the next element.
@return the traversed element
*/
E next();
/**
Tests if there is an element after the iterator
position.
Continua
File ListIterator.java
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
@return true if there is an element after the iterator
position
*/
boolean hasNext();
/**
Adds an element before the iterator position
and moves the iterator past the inserted element.
@param element the element to add
*/
void add(E element);
/**
Removes the last traversed element. This method may
only be called after a call to the next() method.
*/
Continua
File ListIterator.java
34:
35:
36:
37:
38:
39:
40:
41:
42: }
void remove();
/**
Sets the last traversed element to a different
value.
@param element the element to set
*/
void set(E element);