Le gerarchie di tipi:
implementazioni multiple e
principio di sostituzione
1
Come si può utilizzare una gerarchia
di tipi
 Il sottotipo estende il comportamento del tipo
–
fornendo nuovi metodi
 Implementazioni multiple di un tipo
– i sottotipi non aggiungono alcun comportamento nuovo
– la classe che implementa il sottotipo implementa esattamente il
comportamento definito dal supertipo
 dal punto di vista semantico, supertipo e sottotipo sono
legati dal principio di sostituzione: un oggetto del sottotipo
può essere sostituito ad un oggetto del supertipo senza
influire sul comportamento dei programmi che utilizzano il
tipo
2
Implementazioni multiple
 il tipo superiore della gerarchia
– un’interfaccia (solo specifica)
– una classe astratta (implementazione parziale)
 definisce una famiglia di tipi tale per cui
– tutti i membri hanno esattamente gli stessi
metodi e la stessa semantica (specifica)
 Esempio: Stack, ListStack, VectorStack
3
Implementazioni multiple
 Consideriamo le due implementazioni per Stack
• un programma potrebbe voler usare tutte e due le
implementazione (scegliendo ogni volta la più adeguata)
• La scelta viene fatta chiamando uno o l’altro costruttore
– dall’esterno si vedono solo i costruttori dei sottotipi
– gli oggetti dei sottotipi vengono dall’esterno tutti visti come oggetti
dell’unico supertipo (la specifica e’ uguale)
4
IntList
vogliamo dare implementazioni “alternative”
alcune operazioni possono essere comuni alle
implementazioni
–IntList è una classe astratta e non un interfaccia
5
Specifica della classe astratta
–la classe astratta ha alcuni metodi non astratti
•comuni alle sottoclassi
•definiti in termini dei metodi astratti
–la classe astratta non ha variabili di istanza e
quindi nemmeno costruttori
–E’ simile a quella vista, solo che il tipo e’
non modificabile
6
Cosa vuol dire?
 Non ci sono metodi modificatori
 I metodi che “modificano” la lista devono
essere trasformati in produttori; ritornano
una lista modificata, invece di modificare
this
 Esempi: addEl, first, rest
7
Specifica del supertipo IntList
public abstract class IntList {
// OVERVIEW: un IntList è una lista
// non modificabile di Integers.
// Elemento tipico [x1,...,xn]
//metodi astratti
public abstract Integer first ()
throws EmptyException;
//EFFECTS: se this è vuoto solleva
// EmptyException, altrimenti
// ritorna il primo elemento di this
public abstract IntList rest ()
throws EmptyException;
// EFFECTS: se this è vuoto solleva
// EmptyException, altrimenti
// ritorna la lista ottenuta da this togliendo
// il primo elemento
8
Specifica del supertipo IntList
public abstract Iterator elements ();
// EFFECTS: ritorna un generatore che produrrà
// tutti gli elementi di this (come Integers)
// nell’ordine che hanno in this
public abstract IntList addEl (Integer x);
// EFFECTS: ritorna una lista ottenuta
// aggiungendo x all’inizio di this
public abstract int size ();
// EFFECTS: ritorna il numero di elementi
// di this
public abstract boolean repOk ();
9
Implementazione del supertipo
IntList
// metodi concreti
public String toString () {....}
public boolean equals (Object o) {
//EFFECTS: restituisce true se this ed o sono la
//stessa lista, false altrimenti
}
}
vanno implementati sono metodi concreti
si possono implementare usando il generatore
elements (astratto)
si ottiene una implementazione comune per tutti
i possibili sottotipi
10
Implementazione
 Non ci sono variabili d’istanza e costruttori
 Vanno implementati solo i metodi concreti
11
ToString()
public String toString () {
Iterator g=elements();
String s=“”;
while (g.hasnext())
{Integer el=(Integer) g.next();
s=s + el.intValue();}
return s; }
Usando il generatore possiamo leggere la
lista senza sapere come e’implementata
(addirittura non e’ ancora implementata)
Meccanismo di iterazione astratta
Alternativa: si potrebbero usare first() e
rest()
12
Equals()
public boolean equals (Object o) {
//EFFECTS: verifica se this ed o sono
//la stessa lista
}
Metodo sovrascritto da Object
Quello ereditato e’ poco utile perche’ verifica
se il riferimento e’ lo stesso; vorremmo invece
vedere se hanno gli stessi elementi
13
equals()
public boolean equals (Object o) {
IntList l= (IntList) o;
if (size()!= l.size())
{return false;}
if (size()==0 && l.size()==0)
{return true;} else
{Iterator g=elements();
Iterator h=l.elements();
while (g.hasnext())
{ Integer el1=(Integer) g.next();
Integer el2=(Integer) h.next();
if ( ! el1.equals (el2)) {return false;}
}
return true;}
}
14
IntList :sottoclassi
Le sottoclassi definiscono implementazioni
“alternative”: ne vediamo per esempio due
Una è quella che abbiamo visto
–ogni oggetto ha 4 campi (ne basterebbero 3)
•solo alcuni di questi sono utilizzati nei vari casi della definizione
e ricorsiva
15
Prima Implementazione
 Implementazione vista con la lista concatenata
class IntListUno extends IntList{
private
private
private
private
boolean vuota;
Integer val;
IntList next;
int sz;
Definizione ricorsiva: caso base la lista vuota
(rappresentata tramite la variabile booleana vuota)
16
Rappresentazione Lista
val
next
vuota
Lista
vuota:
any
any
154
24
any
any
true
false
false
true
Lista non vuota:
17
Commenti
 Vantaggio: definizione ricorsiva pulita, caso base: lista
vuota
 Svantaggio dell’implementazione: ogni lista vuota o non
vuota ha 4 variabili d’istanza (ne bastano tre)
 Nei metodi sono necessari continui test su “vuota” per
distinguere i due casi
18
Implementazione alternativa
 usiamo due sottotipi differenti per implementare i due casi
della definizione ricorsiva
– lista vuota
– lista non vuota
– Piu’ efficiente, occupa meno spazio, meno test necessari
– Unisce i vantaggi delle due implementazioni viste in
precedenza
19
Implementazione del sottotipo
EmptyIntList
 Implementa il caso della lista vuota
 Non ha variabili d’istanza (e quindi neanche
invariante)
 Dobbiamo fornire i costruttori e
l’implementazione dei metodi astratti di
IntList
20
Implementazione del sottotipo
EmptyIntList
 Presentiamo la specifica insieme
all’implementazione, direttamente
 La specifica e’ leggermente diversa da quella del
supertipo, e’ specializzata al caso della lista vuota
 le parti della specifica del sottotipo che sono
uguali a quelle del supertipo non le riportiamo
21
Implementazione del sottotipo
EmptyIntList
public class EmptyIntList extends IntList {
// OVERVIEW: un EmptyIntList è una lista
//di Integers vuota. Elemento tipico []
public EmptyIntList () {}
Non ha variabili d’istanza!
22
Implementazione del sottotipo
EmptyIntList
public Integer first () throws EmptyException
// EFFECTS: solleva EmptyException
{ throw new EmptyException ("EmptyIntList.first"); }
public IntList rest () throws EmptyException
// EFFECTS: solleva EmptyException
{ throw new EmptyException ("EmptyIntList.rest"); }
Sono specializzati per il caso della lista vuota!!!!
23
Implementazione del sottotipo
EmptyIntList
public IntList addEl (Integer x)
{FullIntList n = new FullIntList(x);
return n; }
public int size () {return 0;}
public boolean repOk () {return true;}
Deve essere chiamato il costruttore dell’altro
sottotipo quando si aggiunge un elemento
24
Implementazione del sottotipo
EmptyIntList
public abstract Iterator elements (){
// EFFECTS: ritorna un generatore che produrrà
// tutti gli elementi di this (come Integers)
// nell’ordine che hanno in this
return new EmptyGen();}
private static class EmptyGen implements Iterator {
EmptyGen () {}
public boolean hasNext () { return false; }
public Object next () throws NoSuchElementException
{throw new NoSuchElementException("IntList.elements");
}
}
25
Invariante e funzione di
astrazione
 Invariante non c’e’ (non ci sono variabili
d’istanza)
 Funzione di astrazione (rappresenta la lista
vuota)
aEmptyIntList(c) = []
26
Implementazione del sottotipo
FullIntList
public class FullIntList extends IntList {
//OVERVIEW: un FullIntList è una lista di Integers
//non vuota. Elemento tipico [x1, …,xn] n>0
private Integer val; valore
private IntList next; resto della lista
private int sz; numero di elementi
Implementazione ricorsiva (caso nodo)
Non serve la variabile booleana
sz variabile ausiliaria per contare il numero di elementi
27
Invariante e f. di astrazione
IFullIntlist(c) = (c.next != null e
c.sz= 1 + c.next.size()
e c.next e’ EmptyIntList o
IFullIntlist(c.next) )
Le condizioni si separano e dividono nei due casi
a(c) = [c.val] + a(c.next)
28
Implementazione del sottotipo
FullIntList
public FullIntList (Integer x)
// EFFECTS: inizializza this alla lista che contiene x
{sz=1; val=x; next=EmptyIntlist();}
public Integer first () throws EmptyException
// EFFECTS: ritorna il primo elemento della lista
{return val; }
public IntList rest () throws EmptyException
// EFFECTS: ritorna il resto della lista
{ return next; }
Non ci sono piu’ da fare test , in questo caso di sicuro
val e next sono definiti (vedi anche l’invariante)
29
Implementazione del sottotipo
FullIntList
public Iterator elements () {return new FullGen(this)}
public IntList addEl (Integer x)
{FullIntList n = new FullIntList(x);
n.next=this;n.sz=this.sz+1;
return n; }
public int size () {return sz;}
public boolean repOk () {……..}
Omettiamo la definizione del generatore; pensate
voi a come adattarlo
30
Vantaggi
 I metodi per i due casi (lista vuota e non vuota)
sono implementati in modo più efficiente
 Si evitano tutta una serie di test per distinguere i
due casi (il metodo più specifico viene chiamato
automaticamente)
 Anche dal punto di vista della correttezza e’ piu’
facile ragionare sui due casi separamente (si
semplificano l’invariante e la funzione di
astrazione)
31
Cosa cambia dal punto di vista
dell’utente del tipo di dato?
 Puo’ scegliere l’implementazione piu’
efficiente (scegliendo l’opportuno
costruttore)
 Siamo sicuri che tutti i sottotipi della classe
astratta si comportano nello stesso modo?
 Sarebbe ovviamente vero se tutti i sottotipi
avessero per ogni metodo esattamente le
stesse specifiche (ma…)
32
Differenza tra le specifiche
 Abbiamo visto che gli oggetti del tipo
FullIntList differiscono da quelli del
supertipo (vedi OVERVIEW)
 Anche le postcondizioni di alcuni metodi
(es. first, rest)
 Analogo per EmptyIntList
 Ma esiste una relazione particolare tra
specifiche del supertipo e del sottotipo
33
Prima proprieta’:dati
 Le proprieta’ dei dati del supertipo sono piu’
generali di quelle dei sottotipi
 Una lista non vuota e’ un tipo particolare di lista
 Una lista vuota e’ un tipo particolare di lista
 In conclusione, i dati del sottotipo soddisfano
anche le richieste del supertipo
34
Seconda proprieta’:metodi
 Le specifiche dei metodi (p.e. first) del supertipo e
di quelli dei sottotipi richiedono lo stesso risultato
per la lista vuota o non vuota rispettivamente
 Le specifiche dei metodi del sottotipo non
differiscono da quelle del supertipo, sono solo
specializzate sui due casi rappresentati dai due
sottotipi, lista vuota e non vuota
35
Esempio
//metodo del supertipo
public abstract Integer first () throws
EmptyException;
// EFFECTS: se this è vuoto solleva
// EmptyException, altrimenti
// ritorna il primo elemento di this
//metodo del sottotipo Full
public Integer first () throws EmptyException
// EFFECTS: ritorna il primo elemento della lista
Quando viene selezionato quello del sottotipo, la
lista e’ non vuota, il comportamento richiesto e’
esattamente quello del supertipo
36
Di conseguenza
 Vuol dire che un programma scritto in
termini del supertipo IntList lavora
correttamente su oggetti del sottotipo
FullIntList o EmptyIntList
Vale il Principio di Sostituzione: un oggetto del
sottotipo può essere sostituito ad un oggetto del
supertipo senza influire sul comportamento dei
programmi che utilizzano il tipo
37
Esempio
 Supponiamo di avere un metodo statico che e’
scritto guardando la specifica del supertipo IntList
public static boolean cerca (Intlist l,Integer x)
throws NullPointerException {
//EFFECTS: se l o x sono null solleva
//NullPointerException, altrimenti restituisce
// true se x occorre nella lista l, false se
// non occorre}
38
Implementazione ricorsiva
public static boolean cerca(Intlist l,Integer x)
throws NullPointerException {
if (x==null|| l==null)
throw new NullPointerException(“Lista.cerca”);
if (l.size()==0) {return false;}
else
{Integer el=l.first();
if (el.equals(x)) {return true;}
return cerca(l.rest(),x);}
}
39
Principio di Sostituzione
 I metodi dei due sottotipi garantiscono lo
stesso comportamento di quelli di IntList
 Di conseguenza cerca puo’ essere utilizzato
sia con un parametro di tipo FullIntList che
EmptyIntList
 Inoltre per provarne la correttezza e’
sufficiente avere considerato le specifiche di
IntList
40
Principio di Sostituzione
 Deve valere sempre, altrimenti il meccanismo di
fattorizzazione offerto dall’ereditarieta’ servirebbe a poco
 Bisogna garantire la modularita’ ovvero che la definizione
di sottotipi non richieda di dimostrare da capo la
correttezza di tutto il codice corretto rispetto al supertipo
41
Principio di sostituzione
 Non vale sempre in generale
 Quale deve essere la relazione tra le
specifiche del sottotipo e del supertipo?
 Perche’ valga il sottotipo deve soddisfare le
specifiche del supertipo
 Cosa vuol dire?
 Cosa succede se non vale?
42
Intuitivamente
 La specifica del sottotipo deve implicare
quella del supertipo
 Proprieta’ dei dati (OVERVIEW)
 Proprieta’ dei metodi riscritti
–se la specifica nel supertipo è nondeterministica
(ammette varie possibilità) il sottotipo può avere una
specifica più forte che risolve (in parte) il
nondeterminismo
43
Esempio
 SortedIntSet (insiemi ordinati) sottotipo di IntSet
(insiemi non ordinati)
public class IntSet {
public Iterator elements ()
// EFFECTS: ritorna un generatore che produrrà tutti gli elementi di
// this (come Integers) ciascuno una sola volta, in ordine arbitrario
 il metodo elements di SortedIntSet assume
l’ordine crescente
public class SortedIntSet {
public Iterator elements ()
// EFFECTS: ritorna un generatore che produrrà tutti gli elementi di
// this (come Integers) ciascuno una sola volta, in ordine crescente
44
Vale il principio di sostituzione
 Specifica del sottotipo e’ piu’ forte, implica anche
le proprieta’ del supertipo
 Per i dati: un insieme ordinato e’ anche un insieme
 Il generatore che restituisce gli elementi in ordine
e’ un caso particolare di quello che lo restituisce in
qualsiasi ordine
45
Di conseguenza
 I programmi provati corretti rispetto alla
specifica di IntSet funzionano
correttamente anche per il sottotipo
SortedIntSet
 Vediamo un esempio
46
Procedura per l’uguaglianza
public static boolean uguali(IntSet x,IntSet y){
// EFFECTS: verifica se x ed y hanno gli stessi elementi
{{if (x == null || y==null) return false;
Iterator g=x.elements();
while (g.hasnext())
{int temp=( (Integer) g.next()).intValue();
if (!y.isIn(temp)) {return false;}
}
Iterator g=y.elements();
while (g.hasnext())
{int temp=( (Integer) g.next()).intValue();
if (!x.isIn(temp)) {return false;}
}
return true;}
47
Procedura per l’uguaglianza
 Scritta guardando la specifica di IntSet
 Siccome non sono ordinati deve generare tutti gli elementi
di x e di y
 La procedura uguale e’ corretta rispetto alla
specifica del supertipo IntSet
48
Commenti
 Dato che vale il p. di sostituzione e’ corretta
anche se chiamata con parametri del
sottotipo SortedIntSet
 In tal caso il generatore e’ quello del
sottotipo e genera i valori in modo ordinato
(tutto continua a funzionare)
49
Vantaggio
 Non dobbiamo ridimostrare la correttezza
del metodo uguali per il sottotipo
SortedIntSet
 La correttezza del sottotipo (pr. Di
sostituzione) garantisce che valga
 Sarebbe impensabile dover ripetere tutte le
dimostrazioni per ogni sottotipo
50
Cosa succede se non vale?
 Se non vale il principio di sostituzione programmi
dimostrati corretti rispetto alla specifica del
supertipo potrebbero non esserlo quando si usa il
sottotipo
 Dovrei ridimostrare la loro correttezza rispetto alle
specifiche di tutti i sottotipi
 Sconsigliato: vuol dire che non sono ben definiti
(perdo la flessibilita’ dell’uso dei sottotipi)
51
Esempio
 Se ammettessi di definire IntSet come
sottotipo di SortedIntSet
 Non vale il principio di sostituzione: il
sottotipo soddisfa proprieta’ piu’ deboli
 Un insieme in cui gli elementi sono messi in
modo arbitrario non e’ ordinato (analogo per
il generatore)
52
Procedura che verifica
l’uguaglianza (per SortedIntset)
public static boolean uguali(SortedIntSet x,SortedIntSet y){
// EFFECTS: verifica se x ed y hanno gli stessi elementi
{{if (x == null || y==null) return false;
Iterator g=x.elements();
Iterator h=y.elements();
while (g.hasnext() & & h.hasnext())
{int temp1=( (Integer) g.next()).intValue();
int temp2=( (Integer) h.next()).intValue();
if (!temp1.equals (temp2)) {return false;}
}
if (! (g.hasnext() | | h.hasnext()))
{return true;} else {return false;}
}
53
Procedura che calcola
l’uguaglianza
 Corretta rispetto alla specifica del supertipo
 Sfrutta le caratteristiche del supertipo
ovvero l’ordinamento (piu’ efficiente)
 Se chiamata con parametri del sottotipo
IntSet (in tal caso non funziona
correttamente)
54
Dove sta l’errore?
 Il sottotipo non ordinato non e’ un sottotipo
corretto di ordinato
 Il principio di sostituzione non vale
 Il principio di sostituzione e’ fondamentale
per riutilizzare il codice
55
Principio di sostituzione
 Perche’ valga in generale bisogna verificare che
– la regola delle proprietà
• il sottotipo deve preservare tutte le proprietà che valgono sugli oggetti
del supertipo
– la regola dei metodi
• le chiamate dei metodi del sottotipo devono comportarsi come le
chiamate dei corrispondenti metodi del supertipo
 tutte le regole riguardano solo le specifiche di supertipo e
sottotipo
56
Regola dei metodi 1
 le chiamate dei metodi del sottotipo devono
comportarsi come le chiamate dei corrispondenti
metodi del supertipo
 va bene se i metodi overriden del sottotipo
hanno esattamente le stesse specifiche di
quelli del supertipo
 Possono essere diverse se la specifica dei
metodi del sottotipo e’ piu’ forte
– Come nell’esempio del generatore visto prima
57
Regola dei metodi 3
 Per formalizzare bene il concetto di specifica più forte
bisogna considerare
– La precondizione (specificata dalla clausola REQUIRES)
definisce i vincoli sugli inputs
– La postcondizione (specificata dalla clausola EFFECTS) definisce
le proprietà che valgono dopo l’esecuzione del metodo sugli inputs
che soddisfano la precondizione
58
Regola dei metodi 4
 in generale un sottotipo può indebolire le precondizioni e
rafforzare le post condizioni
 per avere compatibilità tra le specifiche del supertipo e
quelle del sottotipo devono essere soddisfatte le regole
– regola delle precondizione
• pre super ==> pre sub
– regola delle postcondizione
• pre super && post sub ==> post super
59
Regola dei metodi 4
 indebolire la precondizione
– pre super ==> pre sub
ha senso, perché il codice che utilizza il metodo è scritto
per usare il supertipo
– ne verifica la precondizione
– verifica anche la precondizione del metodo del sottotipo
 esempio: un metodo in IntSet
public void addZero (
)
// REQUIRES: this non è vuoto
// EFFECTS: aggiunge 0 a this
potrebbe essere ridefinito in un sottotipo
public void addZero (
)
// EFFECTS: aggiunge 0 a this
60
Regola dei metodi 5
 rafforzare la post condizione
– pre super && post sub ==> post super
ha senso, perché il codice che utilizza il metodo è scritto
per usare il supertipo
– È soddisfatta la precondizione più forte (quella del supertipo)
– gli effetti del metodo del sottotipo includono comunque quelli del
supertipo (se la chiamata soddisfa la precondizione più forte)
 esempio: un metodo in IntSet
public void addZero (
)
// REQUIRES: this non è vuoto
// EFFECTS: aggiunge 0 a this
potrebbe essere ridefinito in un sottotipo
public void addZero (
)
// EFFECTS: se this non è vuoto aggiunge 0 a this altrimenti aggiunge 1
a this
61
Regola dei metodi 6
public class IntSet {
public Iterator elements ()
// EFFECTS: ritorna un generatore che produrrà tutti gli elementi di
// this (come Integers) ciascuno una sola volta, in ordine arbitrario
public class SortedIntSet extends IntSet {
public Iterator elements ()
// EFFECTS: ritorna un generatore che produrrà tutti gli elementi di
// this (come Integers) ciascuno una sola volta, in ordine crescente
 entrambi i metodi hanno precondizione true
 la postcondizione del metodo del sottotipo
– gli elementi sono generati in ordine crescente
implica la postcondizione del metodo del supertipo
62
Regola dei metodi: violazioni 1
 consideriamo insert in IntSet
public class IntSet {
public void insert (int x)
// MODIFIES: this
// EFFECTS: aggiunge x a this
 supponiamo di definire un sottotipo di IntSet con la seguente specifica di
insert
public class StupidoIntSet extends IntSet {
public void insert (int x)
// MODIFIES: this
// EFFECTS: aggiunge x a this se x è pari, altrimenti
non fa nulla
 La postcondizione è stata indebolita (errore)
 Chi usa insert si aspetta che x venga aggiunto comunque!
 Se vogliamo un metodo di questo tipo nel sottotipo perche’ chiamarlo uguale
esovrascriverlo?
63
Regola dei metodi: violazioni 2
 consideriamo addEl in OrderedIntList
public class OrderedIntList {
public void addEl (int x) throws DuplicateException {
// MODIFIES: this
// EFFECTS: aggiunge x a this se non c’è già, altrimenti solleva
l’eccezione
 supponiamo di definire un sottotipo di
OrderedIntList con la seguente specifica di addEl
public void addEl (int x)
// MODIFIES: this
// EFFECTS: aggiunge x a this
 non è un problema la differenza della segnatura
 ma c’è un problema con la regola dei metodi
– se l’elemento c’è già, i due metodi hanno comportamento diverso
– e quello del sottotipo fa “meno cose” (è più debole)
64
Regola delle proprietà
 il ragionamento sulle proprietà degli oggetti basato sul
supertipo è ancora valido quando gli oggetti appartengono
al sottotipo
 proprietà degli oggetti astratti
– non proprietà dei metodi
 da dove vengono le proprietà degli oggetti?
– dal modello del tipo di dato astratto
• le proprietà degli insiemi matematici, etc.
• le elenchiamo esplicitamente nell’overview del
supertipo
 Un insieme ordinato e’ anche un insieme
65