Astrazioni sui dati :
Specifica ed Implementazione di
Tipi di Dato Astratti in Java
1
Sommario
 cos’è un tipo di dato astratto
 astrazione tramite specifica:
1. specifica
2. implementazione
3. relazione tra specifica ed implementazione
(nel seguito)
2
Perché l’astrazione sui dati
 il più importante tipo di astrazione
 il nucleo della programmazione orientata ad
oggetti
 lo scopo è quello di estendere il linguaggio
– nel nostro caso, Java
con nuovi tipi di dato (oltre a quelli primitivi int,
String…)
 quali, dipende dall’applicazione
• interprete: stacks e tabelle di simboli (frame, ambiente dei
metodi)
• applicazione bancaria: conti
• applicazioni numeriche: matrici
3
Cos’è un tipo di dato astratto
 in ogni caso è
– un insieme di dati
• stacks, conti, matrici
– un insieme di operazioni
• per crearli e manipolarli
 Cosa sta nella specifica?
• La descrizione astratta dei dati
• La descrizione delle relative operazioni
4
Implementazione

Cosa sta nell’ implementazione?
• La rappresentazione (o implementazione)
dei dati
• L’implementazione delle relative
operazioni
5
Astrazione tramite specifica
 con la specifica vogliamo astrarre
dall’implementazione del tipo di dato
– l’utente deve operare sul tipo di dato
indipendendentemente dalla sua
rappresentazione (non la deve vedere)
 Le modifiche della rappresentazione non devono
modifiche dei moduli che usano il tipo di dato
6
Come procediamo?
 Prima definiamo la specifica del tipo di dato astratto
– interfaccia pubblica per l’utente
 Poi la implementiamo
– puo’ al solito essere fatto in un momento successivo, in
modo indipendente dai moduli che usano il tipo di dato
7
La specifica di un tipo di dato
astratto
 Java (parte sintattica della specifica)
– classe o interfaccia
• per ora solo classi
– nome per il tipo
• nome della classe
– operazioni
• metodi di istanza
• incluso il(i) costruttore(i)
 la specifica del tipo descrive proprietà generali degli
oggetti
– per esempio la modicabilità
 per il resto la specifica è essenzialmente una specifica dei
metodi
– strutturata come già abbiamo visto per le astrazioni procedurali
– l’oggetto su cui i metodi operano è indicato nella specifica da this
8
Formato della specifica
public class NuovoTipo {
// OVERVIEW: Gli oggetti di tipo NuovoTipo
// sono collezioni modificabili di ..
// costruttori
public NuovoTipo ()
// EFFECTS: ...
// metodi
// specifiche degli altri metodi
}
9
L’insieme di interi 1
public class IntSet {
// OVERVIEW: un IntSet è un insieme modificabile
// di interi di dimensione qualunque
// costruttore
public IntSet ()
// EFFECTS: inizializza this a vuoto
// metodi
public void insert (int x)
// MODIFIES: this
// EFFECTS: aggiunge x a this
public void remove (int x)
// MODIFIES: this
// EFFECTS: toglie x da this
public boolean isIn (int x)
// EFFECTS: se x appartiene a this ritorna
// true, altrimenti false
...}
10
L’insieme di interi 2
public class IntSet {
...
// metodi
...
public int size ()
// EFFECTS: ritorna la cardinalità di this
public int choose () throws EmptyException
// EFFECTS: se this è vuoto, solleva
// EmptyException, altrimenti ritorna un
// elemento qualunque contenuto in this
}
11
IntSet: commenti 1
public class IntSet {
// OVERVIEW: un IntSet è un insieme modificabile
// di interi di dimensione qualunque
....
}
 descrizione astratta dei dati
 gli oggetti della classe sono descritti nella specifica in
termini di concetti noti
– in questo caso, gli insiemi matematici
 gli stessi concetti sono anche utilizzati nella specifica dei
metodi
12
IntSet: commenti 2
public class IntSet {
// OVERVIEW: ...
// costruttore
public IntSet ()
// EFFECTS: inizializza this a vuoto
...}
 un solo costruttore (senza parametri)
– inizializza this (l’oggetto nuovo)
– non è possibile vedere lo stato dell’oggetto tra la creazione e
l’inizializzazione
• la specifica non ha una clausola MODIFIES
13
IntSet: commenti 3
public class IntSet {
...
// metodi
public void insert (int x)
// MODIFIES: this
// EFFECTS: aggiunge x a this
public void remove (int x)
// MODIFIES: this
// EFFECTS: toglie x da this
...}
 modificatori
– modificano lo stato del proprio oggetto (MODIFIES: this)
– notare che nè insert nè remove sollevano eccezioni
• se si inserisce un elemento che c’è già
• se si rimuove un elemento che non c’è
14
IntSet: commenti 4
public boolean isIn (int x)
// EFFECTS: se x appartiene a this ritorna
// true, altrimenti false
public int size ()
// EFFECTS: ritorna la cardinalità di this
public int choose () throws EmptyException
// EFFECTS: se this è vuoto, solleva
// EmptyException, altrimenti ritorna un
// elemento qualunque contenuto in this...}
 osservatori
– non modificano lo stato del proprio oggetto
– choose può sollevare un’eccezione (se l’insieme è vuoto)
• EmptyException può essere unchecked, perché l’utente può utilizzare
size per evitare di farla sollevare
15
Astrazione tramite specifica
• La specifica contiene tutte e sole le
informazioni per utilizzare il tipo di dato in
altri moduli
• Possiamo (dobbiamo) scrivere codice che
crea oggetti di tipo Intset e li modifica
tramite metodi e costruttori guardando solo
la specifica
16
Esempio di un metodo che usa
IntSet
public static IntSet getElements (int[] a) throws
NullPointerException
// EFFECTS:se a=null solleva NullPointerException
// altrimenti, restituisce un insieme che
//contiene tutti e soli gli interi di a
{IntSet s = new IntSet();
for (int i = 0; i < a.length; i++)
s.insert(a[i]);
return s;
}
 scritta solo conoscendo la specifica di
IntSet
17
Notate che
– non accede all’implementazione
• non esiste ancora
• anche se ci fosse non potrebbe “vederla”
– costruisce, accede e modifica l’oggetto solo
attraverso i metodi (incluso il costruttore)
18
Specifica di un tipo “primitivo”
 le specifiche sono ovviamente utili per capire ed
utilizzare correttamente i tipi di dato “primitivi” di
Java
 vedremo, come esempio, il caso dei vettori
– Vector
– arrays dinamici che possono cambiare
dimensione
– contengono Object (per il principio di sostituzione
possiamo memorizzarci qualsiasi sottotipo di Object)
19
Vector 1
public class Vector {
// OVERVIEW: un Vector è un array modificabile
// di dimensione variabile i cui elementi sono
// di tipo Object: indici tra 0 e size - 1
// costruttore
public Vector ()
// EFFECTS: inizializza this a vuoto
// metodi
public void add (Object x)
// MODIFIES: this
// EFFECTS: aggiunge una nuova posizione a
// this inserendovi x
public int size ()
// EFFECTS: ritorna il numero di elementi di
// this
...}
20
Vector 2
...
public Object get (int n) throws
IndexOutOfBoundsException
// EFFECTS: se n<0 o n>= this.size solleva
// IndexOutOfBoundsException, altrimenti
// ritorna l’oggetto in posizione n in this
public void set (int n, Object x) throws
IndexOutOfBoundsException
// MODIFIES: this
// EFFECTS: se n<0 o n>= this.size solleva
// IndexOutOfBoundsException, altrimenti
// modifica this sostituendovi l’oggetto x in
// posizione n}
21
Vector 3
...
public void remove (int n) throws
IndexOutOfBoundsException
// MODIFIES: this
// EFFECTS: se n<0 o n>= this.size solleva
// IndexOutOfBoundsException, altrimenti
// modifica this eliminando l’oggetto in
// posizione n
public void insert (Object o, int n) throws
IndexOutOfBoundsException
// MODIFIES: this
// EFFECTS: se n<0 o n>= this.size solleva
// IndexOutOfBoundsException, altrimenti
// modifica this inserendo o nella posizione n
}
22
Vector: commenti 1
public class Vector {
// OVERVIEW: un Vector è un array modificabile
// di dimensione variabile i cui elementi sono
// di tipo Object: indici tra 0 e size - 1
....
}
 gli oggetti della classe sono descritti nella specifica in
termini di concetti noti
– in questo caso, gli arrays
 gli stessi concetti sono anche utilizzati nella specifica dei
metodi
– indice, elemento identificato dall’indice
 il tipo è modificabile (come l’array)
 notare che gli elementi sono di tipo Object
23
Vector: commenti 2
public class Vector {
// OVERVIEW: un Vector è un array modificabile
// di dimensione variabile i cui elementi sono
// di tipo Object: indici tra 0 e size - 1
// costruttore
public Vector ()
// EFFECTS: inizializza this a vuoto
...}
 un solo costruttore (senza parametri)
– inizializza this (l’oggetto nuovo) ad un “array” vuoto
24
Vector: commenti 3
public void add (Object x)
// MODIFIES: this
// EFFECTS: aggiunge una nuova posizione a
// this inserendovi x
public void set (int n, Object x) throws
IndexOutOfBoundsException
// MODIFIES: this
// EFFECTS: se n<0 o n>= this.size solleva
// IndexOutOfBoundsException, altrimenti modifica
// this sostituendovi l’oggetto x in posizione n
 sono modificatori
– modificano lo stato del proprio oggetto (MODIFIES: this)
– set e remove possono sollevare un’eccezione primitiva
unchecked
25
Vector: commenti 3
public void remove (int n) throws IndexOutOfBoundsException
// MODIFIES: this
// EFFECTS: se n<0 o n>= this.size solleva
// IndexOutOfBoundsException, altrimenti modifica
// this eliminando l’oggetto in posizione n
public void insert (Object o, int n) throws
IndexOutOfBoundsException
// MODIFIES: this
// EFFECTS: se n<0 o n>= this.size solleva
// IndexOutOfBoundsException, altrimenti
// modifica this inserendo o nella posizione n
 sono modificatori
 In entrambi i casi vengono shiftati gli elementi che occorrono dopo la
posizione n, in indietro o avanti
26
Vector: commenti 4
public int size ()
// EFFECTS: ritorna il numero di elementi di
// this
public Object get (int n) throws
IndexOutOfBoundsException
// EFFECTS: se n<0 o n>= this.size solleva
// IndexOutOfBoundsException, altrimenti
// ritorna l’oggetto in posizione n in this
public Object lastElement ()
// EFFECTS: ritorna l’ultimo oggetto in this
 sono osservatori
– non modificano lo stato del proprio oggetto
– get può sollevare un’eccezione primitiva unchecked
27
Specifica di un tipo “primitivo”
– La specifica e’ di fatto la descrizione che
troviamo nel manuale (a parte il formato dei
commenti)
– Quando usiamo il tipo di dato primitivo non
sappiamo come e’ realizzato, ovvero come e’
implementato il Vector e come sono realizzate
le operazioni relative
– Lo stesso meccanismo di astrazione tramite
specifica deve valere per i tipi di dato astratti
che definiamo
28
Implementazione
 scelta fondamentale è quella della
rappresentazione (rep)
– come i valori del tipo astratto sono
implementati in termini di altri tipi
• tipi primitivi o già implementati
• nuovi tipi astratti che facilitano l’implementazione
del nostro
 segue l’implementazione dei costruttori e
dei metodi (più eventuali altri metodi
ausiliari privati)
29
La rappresentazione
 in Java, gli oggetti del nuovo tipo sono
semplicemente collezioni di valori di altri
tipi
– definite da un insieme di variabili di istanza
private
• accessibili solo dai costruttori e dai metodi della
classe
• questo e’ necessario per evitare l’accesso diretto alla
rappresentazione dell’oggetto da parte degli utenti
30
Implementazione di IntSet 1
public class IntSet {
// OVERVIEW: un IntSet è un insieme modificabile
// di interi di dimensione qualunque
private Vector els; // la rappresentazione
// costruttore
public IntSet ()
// EFFECTS: inizializza this a vuoto
{els = new Vector();}
...}
 un insieme di interi è rappresentato da un Vector
– più adatto dell’Array, perché l’insieme ha dimensione variabile
 gli elementi di un Vector sono di tipo Object
– non possiamo memorizzarci valori di tipo int
– usiamo oggetti di tipo Integer
31
Implementazione di IntSet 2
public void insert (int x)
// MODIFIES: this
// EFFECTS: aggiunge x a this
{Integer y = new Integer(x);
if (getIndex(y) < 0) els.add(y); }
 Inseriamo l’elemento solo se non occorre gia’ nell’insieme
 Vogliamo che non ci siano occorrenze multiple di elementi
– implementazione piu’ efficiente (vedi remove e size)
 A tale fine si utilizza un metodo ausiliario getIndex , che ritorna -1 se
l’elemento non occorre
32
Implementazione di IntSet 2
private int getIndex (Integer x)
// EFFECTS: se x occorre in this
//ritorna la posizione in cui si trova,
//altrimenti -1
{for (int i = 0; i < els.size(); i++)
if (x.equals(els.get(i))) return i;
return -1; }
 il metodo privato ausiliario getIndex ritorna un valore
speciale e non solleva eccezioni
 non sta nella specifica (perché è privato)
 notare l’uso del metodo equals su Integer
33
Implementazione di IntSet 3
public void remove (int x)
// MODIFIES: this
// EFFECTS: toglie x da this
{int i = getIndex(new Integer(x));
if (i < 0) return;
els.set(i, els.lastElement());
els.remove(els.size() - 1);}
 nella rimozione, se l’elemento c’è, ci scrivo sopra l’ultimo
corrente ed elimino l’ultimo elemento
 E’ corretto sse l’elemento occorre in una sola posizione del
vettore………
34
Implementazione di IntSet 3
public boolean isIn (int x)
// EFFECTS: se x appartiene a this ritorna
// true, altrimenti false
{ return getIndex(new Integer(x)) >= 0; }
 Usa il solito metodo ausiliario
35
Implementazione di IntSet 4
public int size ()
// EFFECTS: ritorna la cardinalità di this
{return els.size(); }
 E’ corretto dato che non ci possono essere
occorrenze multiple di elementi nel vettore
36
Implementazione di IntSet 4
public int choose () throws EmptyException
// EFFECTS: se this è vuoto, solleva
// EmptyException, altrimenti ritorna un
// elemento qualunque contenuto in this
{if (els.size() == 0) throw
new EmptyException(“IntSet.choose”);
return ((Integer) els.lastElement()).intValue();
}
 lastElement non puo’ sollevare eccezioni dato che si
effettua un controllo che non sia vuoto
 ritorna un Object (come tipo apparente), quindi per
trasformarlo in int tramite intValue() bisogna fare il cast
37
Sommario
 Abbiamo realizzato tipi di dato astratto usando l’astrazione
fornita dalla specifica
 La specifica e l’implementazione stanno nella stessa classe
 la specifica funge da interfaccia con chi usa il tipo di dato,
puo’ anche essere compilata senza avere
l’implementazione insieme ai moduli che la usano
 Specifica ed implementazione sono di conseguenza legate
da un concetto di correttezza (che vedremo)
38