Le gerarchie di tipi Supertipi e sottotipi



Scaricare 458 b.
10.12.2017
Dimensione del file458 b.


Le gerarchie di tipi


Supertipi e sottotipi

  • un supertipo

    • class
    • interface
  • può avere più sottotipi

    • un sottotipo extends il supertipo (class)
      • un solo supertipo (ereditarietà singola)
    • un sottotipo implements il supertipo (interface)
      • più supertipi interface
  • la gerarchia può avere un numero arbitrario di livelli



Come si può utilizzare una gerarchia di tipi

  • 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
  • il sottotipo estende il comportamento del suo supertipo fornendo nuovi metodi o nuove caratteristiche

  • Questa forma di astrazione essenziale per lo sviluppo incrementale del codice e per il riutilizzo del codice

  • dal punto di vista semantico, supertipo e sottotipo sono legati dal principio di sostituzione



Principio di sostituzione

  • un oggetto del sottotipo può essere sostituito ad un oggetto del supertipo senza influire sul comportamento dei programmi che lo utilizzano

  • i sottotipi supportano il comportamento del supertipo

    • per esempio, un programma scritto in termini del tipo
    • Persona deve lavorare correttamente su oggetti del sottotipo Studente
  • per questo, il sottotipo deve soddisfare le specifiche del supertipo (cosa vuol dire?)



Sommario

  • Specifica del supertipo e del sottotipo

  • Implementazione

  • Relazione tra le specifiche del sottotipo e supertipo (principio di sostituzione)



Definizione di una gerarchia di tipi: specifica

  • specifica del tipo superiore della gerarchia

    • come quelle che già conosciamo
    • l’unica differenza è che può essere parziale
      • per esempio, possono mancare i costruttori
  • Puo’ essere una interfaccia o una classe astratta



Definizione di una gerarchia di tipi: specifica

  • specifica di un sottotipo

    • la specifica di un sottotipo è data relativamente a quella dei suoi supertipi
    • non si ridanno quelle parti delle specifiche del supertipo che non cambiano
    • vanno specificati
      • i costruttori del sottotipo
      • i metodi “nuovi” forniti dal sottotipo
      • i metodi del supertipo che il sottotipo ridefinisce
        • come vedremo sono ammesse modifiche (anche se molto limitate) nelle loro pre-post condizioni


Definizione di una gerarchia di tipi: implementazione

  • implementazione del supertipo

    • puo’ essere implementato completamente (classe)
    • può non essere implementato affatto (interfaccia)
    • può avere implementazioni parziali (classe astratta)
      • alcuni metodi sono implementati, altri no
      • Una caratteristica fondamentale della implementazione: se permette a potenziali sottotipi l’ accesso a variabili o metodi di istanza
      • che un “normale” utente del supertipo non può vedere (vedi l’uso del modificatore protected)


Definizione di una gerarchia di tipi: implementazione

  • i sottotipi sono implementati come estensioni dell’implementazione del supertipo, come prima

    • la rep degli oggetti del sottotipo contiene anche le variabili di istanza definite nell’implementazione del supertipo (quelle ereditate)
    • alcuni metodi possono essere ereditati
    • di altri il sottotipo può definire una nuova implementazione (overridding)


Interfacce e Classi

  • i supertipi sono definiti da

    • classi
    • interfacce
  • le classi possono essere

    • astratte
      • forniscono un’implementazione parziale del tipo
        • non hanno oggetti
        • il codice esterno non può chiamare i loro costruttori
        • possono avere metodi astratti la cui implementazione è lasciata a qualche sottoclasse
    • concrete
      • forniscono un’implementazione piena del tipo
  • le classi astratte e concrete possono contenere metodi finali

    • non possono essere reimplementati da sottoclassi


Gerarchie di tipi in Java: supertipi 2

  • le interfacce definiscono solo il tipo (specifica) e non implementano nulla

    • contengono solo (le specifiche di) metodi
      • pubblici
      • non statici
      • astratti


Gerarchie di tipi in Java: sottotipi 1

  • una sottoclasse dichiara la superclasse che estende (e/o le interfacce che implementa)

    • ha tutti i metodi della superclasse con gli stessi nomi e segnature
    • può implementare i metodi astratti e reimplementare i metodi normali (purché non final)
    • qualunque metodo sovrascritto deve avere segnatura identica a quella della superclasse
      • ma i metodi della sottoclasse possono sollevare meno eccezioni
  • la rappresentazione di un oggetto di una sottoclasse consiste delle variabili di istanza proprie e di quelle dichiarate per la superclasse

    • quelle della superclasse non possono essere accedute direttamente se sono (come dovrebbero essere) dichiarate private
  • ogni classe che non estenda esplicitamente un’altra classe estende implicitamente Object



Modificatore protected

  • la superclasse può lasciare parti della sua implementazione accessibili alle sottoclassi

    • dichiarando metodi e variabili protected
      • implementazioni delle sottoclassi piú efficienti
      • si perde l’astrazione completa, che dovrebbe consentire di reimplementare la superclasse senza influenzare l’implementazione delle sottoclassi
  • meglio lasciare la rappresentazione della superclasse private ed interagirvi solo attraverso le loro interfacce pubbliche (tramite i metodi pubblici)



Un esempio di gerarchia con supertipo classe concreta

  • in cima alla gerarchia c’è una variante di IntSet

    • la solita, con in più il metodo subset
    • la classe non è astratta
    • fornisce un insieme di metodi che le sottoclassi possono ereditare, estendere o sovrascrivere


Specifica del supertipo

  • public class IntSet {

  • // OVERVIEW: un IntSet è un insieme modificabile di interi di

  • // dimensione qualunque

  • public IntSet ()

  • // EFFECTS: inizializza this a vuoto

  • 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

  • public int size ()

  • // EFFECTS: ritorna la cardinalità di this

  • public Iterator elements ()

  • // EFFECTS: ritorna un generatore che produrrà tutti gli elementi di

  • // this (come Integers) ciascuno una sola volta, in ordine arbitrario

  • // REQUIRES: this non deve essere modificato finché il generatore è in

  • // uso

  • public boolean subset (Intset s)

  • // EFFECTS: se s è un sottoinsieme di this ritorna true, altrimenti

  • // false

  • }



Implementazione del supertipo

  • public class IntSet {

  • // OVERVIEW: un IntSet è un insieme modificabile di interi di

  • // dimensione qualunque

  • private Vector els; // la rappresentazione

  • public IntSet () {els = new Vector();}

  • // EFFECTS: inizializza this a vuoto

  • private int getIndex (Integer x) {... }

  • // EFFECTS: se x occorre in this ritorna la posizione in cui si

  • // trova, altrimenti -1

  • public boolean isIn (int x)

  • // EFFECTS: se x appartiene a this ritorna true, altrimenti false

  • {return getIndex(new Integer(x)) >= 0; }

  • public boolean subset (Intset s)

  • // EFFECTS: se s è un sottoinsieme di this ritorna true, altrimenti

  • // false

  • {if (s == null) return false;

  • for (int i = 0; i < els.size(); i++)

  • if (!s.isIn(((Integer) els.get(i)).intValue()))

  • return false;

  • return true; }

  • }



Nota

  • La rappresentazione (Vettore els) e’ privata

  • I sottotipi la ereditano ma non possono direttamente accedere

  • Non e’ un problema perche’ c’e’ un metodo iteratore

  • La scelta di rendere visibile o meno la rappresentazione ai sottotipi (che verranno eventualmente progettati in seguito per estendere il tipo) dipende dai metodi pubblici forniti



Un sottotipo: MaxIntSet

  • si comporta come IntSet

    • ma ha un metodo nuovo max
      • che ritorna l’elemento massimo nell’insieme
    • la specifica di MaxIntSet definisce solo quello che c’è di nuovo
      • il costruttore
      • il metodo max
    • tutto il resto della specifica viene ereditato da IntSet


Specifica del sottotipo

  • public class MaxIntSet extends IntSet {

  • // OVERVIEW: un MaxIntSet è un sottotipo di //IntSet che lo estende con il metodo max

  • public MaxIntSet ()

  • // EFFECTS:inizializza this al MaxIntSet vuoto

  • public int max () throws EmptyException

  • // EFFECTS: se this è vuoto solleva //EmptyException, altrimenti

  • // ritorna l’elemento massimo in this

  • }



Implementazione di MaxIntSet

  • La rappresentazione di IntSet e’ private

  • Non e’ possibile accedere dalla sottoclasse al vettore els

  • L’unico modo per calcolare il massimo e’ tramite il generatore





Soluzione migliore

  • per evitare di generare ogni volta tutti gli elementi dell’insieme, usiamo una variabile di istanza di MaxIntSet che memorizza il valore massimo corrente

    • oltre ad implementare max
    • dobbiamo pero’ rimplementare i metodi modificatori (insert e remove ) per tenere aggiornato il valore massimo corrente
    • sono i soli metodi per cui c’è overriding
    • tutti gli altri vengono ereditati da IntSet


Implementazione del sottotipo 1

  • public class MaxIntSet {

  • // OVERVIEW: un MaxIntSet è un sottotipo di IntSet che lo estende con

  • // il metodo max

  • private int mass; // l’elemento massimo, se this non è vuoto

  • public MaxIntSet ()

  • // EFFECTS: inizializza this al MaxIntSet vuoto

  • { super( ); }

  • ... }

  • chiamata esplicita del costruttore del supertipo

    • potrebbe in questo caso essere omessa
    • necessaria se il costruttore ha parametri
  • nient’altro da fare

    • perché mass non ha valore quando els è vuoto


Implementazione del sottotipo 2

  • public class MaxIntSet extends IntSet {

  • private int mass;

  • …….

  • public int max () throws EmptyException

  • // EFFECTS: se this è vuoto solleva EmptyException, altrimenti

  • // ritorna l’elemento massimo in this

  • {if (size( ) == 0) throw new

  • EmptyException(“MaxIntSet.max”); return mass;}

  • ... }

  • usa un metodo ereditato dal supertipo (size)



Implementazione del sottotipo 3

  • public class MaxIntSet extends IntSet {

  • private int mass;

  • ...

  • public void insert (int x) {

  • if (size() == 0 || x > mass) mass = x;

  • super.insert(x); }

  • ... }

  • ha bisogno di usare il metodo insert del supertipo, anche se overriden

    • attraverso il prefisso super


Implementazione del sottotipo 4

  • public class MaxIntSet extends IntSet {

  • private int mass;

  • ...

  • public void remove (int x) {

  • super.remove(x);

  • if (size() == 0 || x < mass) return;

  • Iterator g = elements();

  • mass = ((Integer) g.next()).intValue();

  • while (g.hasNext() {

  • int z = ((Integer) g.next( )).intValue();

  • if (z > mass) mass = z; }

  • return; } }

  • anche qui si usa il metodo overriden del supertipo

    • oltre ai metodi ereditati size e elements


Procedura stand-alone?

  • perché non realizzare semplicemente un metodo max stand alone esterno alla classe IntSet?

    • facendo un sottotipo si implementa max in modo più efficiente (si aggiorna solo quando necessario a seguito di modifiche insert o remove)
    • Se dovessi realizzare la procedura fuori dalla classe dovremmo per forza generare, tramite l’iteratore, tutti gli elementi e confrontarli fino a trovare il max
    • Analogamente alla prima implementazione vista (meno efficiente)


Funzione di astrazione di sottoclassi di una classe concreta

  • definita in termini di quella del supertipo

    • nome della classe come indice per distinguerle
  • funzione di astrazione per MaxIntSet

  • MaxIntSet(c) = IntSet(c)

  • la funzione di astrazione è la stessa di IntSet perché produce lo stesso insieme di elementi dalla stessa rappresentazione (els)

    • il valore della variabile mass non ha influenza sull’insieme rappresentato


Invariante di rappresentazione di sottoclassi di una classe concreta

  • invariante di rappresentazione per MaxIntSet

  • IMaxIntSet (c) = c.size() > 0 ==>

  • (c.mass appartiene a IntSet(c) &&

  • per tutti gli x in IntSet(c),

  • x <= c. mass)

  • usa la funzione di astrazione del supertipo per riferirsi all’insieme

  • definisce il legame tra mass e l’insieme



Notate che

  • l’invariante della sottoclasse non include (e non utilizza in questo caso) l’invariante della superclasse

  • tocca all’implementazione di IntSet preservare la sua invariante che e’ indipendente dalla sottoclasse

  • Infatti, le operazioni di MaxIntSet non possono interferire con l’invariante del supertipo perché operano sulla rep del supertipo solo attraverso i suoi metodi pubblici

  • ma la correttezza dell’implementazione di IntSet è chiaramente necessaria per la correttezza della sottoclasse



Cosa succede se il supertipo fa vedere la rappresentazione?

  • l’efficienza di remove potrebbe essere migliorata

    • questa versione richiede di visitare els due volte
      • per rimuovere l’elemento (attraverso la remove della superclasse)
      • per aggiornare il nuovo mass (utilizzando l’iteratore)
  • dichiarando els protected nell’implementazione di IntSet

  • Basterebbe visitare una sola volta il vettore



Svantaggi

  • in questo caso, l’invariante di rappresentazione di MaxIntSet deve includere quello di IntSet

    • perché l’implementazione di MaxIntSet potrebbe violarlo
  • IMaxIntSet (c) = IIntSet (c) &&

  • c.size() > 0 ==>

  • (c.mass appartiene a IntSet(c) &&

  • per tutti gli x in IntSet(c), x <= c. mass)



Inoltre

  • Si perde l’astrazione verso la sottoclasse

  • Se cambiamo la rappresentazione della superclasse dobbiamo reimplementare anche la sottoclasse che accede alla rappresentazione

  • Spesso la soluzione piu’ efficiente non e’ quella metodologicamente migliore



Classi astratte come supertipi

  • implementazione parziale di un tipo

  • può avere variabili di istanza e uno o piú costruttori

  • non ha oggetti

  • i costruttori possono essere chiamati solo dalle sottoclassi per inizializzare la parte di rappresentazione della superclasse

  • contiene metodi astratti (senza implementazione) e metodi concreti (implementati)



Classi astratte come supertipi

  • può contenere metodi regolari (implementati)

    • questo evita di implementare piú volte i metodi quando la classe abbia piú sottoclassi e permette di dimostrare più facilmente la correttezza
    • l’implementazione può utilizzare i metodi astratti
    • i metodi implementati, i costruttori e le variabili d’istanza della superclasse catturano la parte generica dell’implementazione, comune ai sottotipi
    • i sottotipi forniscono i dettagli specifici (aggiuntivi) e l’implementazione delle parti mancanti


Interfaccia

  • Una classe astratta fornisce una implementazione parziale, astrae la parte comune ai sottotipi

  • Una interfaccia non fornisce alcuna implementazione (in pratica tutti i metodi sono astratti)



Perché può convenire trasformare IntSet in una classe astratta

  • vogliamo definire (come sottotipo di IntSet) il tipo SortedIntSet

    • il generatore elements fornisce accesso agli elementi in modo ordinato
    • un nuovo metodo subset (overloaded) per ottenere una implementazione più efficiente quando l’argomento è di tipo SortedIntSet (se sono sorted non ho bisogno di confrontare ogni elemento del primo insieme con ogni elemento del secondo!)
  • vediamo cosa vorremmo per la specifica di SortedIntSet



Specifica del sottotipo

  • public class SortedIntSet extends IntSet {

  • // OVERVIEW: un SortedIntSet è un sottotipo di IntSet //che lo estende con i metodi max e

  • // subset(SortedIntSet) e in cui gli elementi sono

  • // accessibili in modo ordinato

  • public SortedIntSet ()

  • // EFFECTS: inizializza this al SortedIntSet vuoto

  • public int max () throws EmptyException

  • // EFFECTS: se this è vuoto solleva EmptyException, //altrimenti

  • // ritorna l’elemento massimo in this



Specifica del sottotipo

  • public Iterator elements ()

  • // EFFECTS: ritorna un generatore che produrrà tutti gli //elementi di this (come Integers) ciascuno una sola //volta, in ordine crescente

  • public boolean subset (SortedIntset s)

  • // EFFECTS: se s è un sottoinsieme di this ritorna true, //altrimenti false }

  • }

  • L’iteratore è overridden (la postcondizione è diversa da quella della superclasse)

  • mentre subset è overloaded (la specifica è uguale, il tipo e’ diverso)

  • In SortedIntSet ho due diversi metodi subset



Implementazione del sottotipo

  • la rappresentazione degli oggetti di tipo SortedIntSet potrebbe utilizzare una lista ordinata

    • Avremmo due variabili d’istanza, la variabile di istanza ereditata da IntSet (utilizzata dai metodi eredidati quali insert e remove)
    • Bisogna mantenere la consistenza tra le due rappresentazioni (poco efficiente e complicato)
    • Se anche ridefinissi tutti i metodi per la lista ordinata la variabile d’istanza eredidata non servirebbe a nulla (poco senso)


Soluzione migliore

    • Eliminare il vettore els da IntSet
    • senza els, IntSet non può avere oggetti e quindi deve essere ASTRATTA
    • Realizzare i due casi Ordinato e non Ordinato come sottotipi della classe astratta
    • Per progettare la classe astratta bisogna capire se c’e’ qualche informazione che puo’ essere data in modo comune alle due sottoclassi, var. d’istanza o metodi?
    • Altrimenti e’ conveniente usare una interfaccia


IntSet come classe astratta

  • specifica uguale a quella gia’ vista (solo che alcuni metodi sono astratti)

  • dato che la parte importante della rappresentazione (come sono memorizzati gli elementi dell’insieme) non è definita qui, devono essere astratti i metodi insert, remove, elements e repOk

  • isIn, subset possono essere implementati in termini del metodo astratto elements



IntSet implementazione

  • size potrebbe essere implementata in termini di elements

    • inefficiente
  • teniamo traccia nella superclasse della dimensione con una variabile intera sz

    • che è ragionevole sia visibile dalle sottoclassi (protected)
    • la superclasse non può nemmeno garantire proprietà di sz
  • non c’è funzione di rappresentazione

    • tipico delle classi astratte, perché la vera implementazione è fatta nelle sottoclassi


Implementazione di IntSet come classe astratta

  • public abstract class IntSet {

  • protected int sz; // la dimensione

  • // costruttore

  • public IntSet () {sz = 0 ;}

  • // metodi astratti

  • public abstract void insert (int x);

  • public abstract void remove (int x);

  • public abstract Iterator elements ( );

  • public abstract boolean repOk ( );



Implementazione di IntSet come classe astratta

  • // metodi concreti

  • public boolean isIn (int x)

  • {Iterator g = elements ();

  • Integer z = new Integer(x);

  • while (g.hasNext())

  • if (g.next().equals(z)) return true;

  • return false; }

  • public int size () {return sz; }

  • public boolean subset (Intset s){

  • // implementazione di subset (per esercizio)}

  • }



Metodi concreti e costruttori

  • I metodi concreti si possono implementare usando i metodo astratti (e.g. elements)

  • Quando i sottotipi completeranno l’implementazione verra’ selezionato l’opportuno metodo overriden da eseguire

  • I costruttori di una classe astratta sono parziali



Specifica della sottoclasse SortedIntSet 1

  • e’ una classe concreta (completamente implementata) come quella che abbiamo visto solo che ora IntSet e’ astratta

  • si aggiungono il costruttore, il metodo max

  • inoltre l’iteratore elements e’ overriden (cambia la postcondizione)

  • si aggiunge un metodo subset overloaded



Implementazione della sottoclasse SortedIntSet 1

  • Rappresentazione dell’insieme ordinato come OrderedIntList su cui si assumono anche delle operazioni size e max

  • Si implementano tutti

    • Metodi astratti (della superclasse)
    • Costruttore
    • Metodi overloaded o overriden (tipo subset)
  • I metodi non astratti (tipo size o isIn) che sono definiti in base ai metodi astratti vengono eredidati



Implementazione della sottoclasse SortedIntSet 1

  • public class SortedIntSet extends IntSet {

  • private OrderedIntList els; // la rappresentazione

  • // costruttore

  • public SortedIntSet () {els = new OrderedIntList() ;}

  • // metodi

  • public int max () throws EmptyException {

  • if (sz == 0) throw new EmptyException("SortedIntSet.max");

  • return els.max( ); }

  • public Iterator elements ( ) {return els.smallToBig(); }

  • // implementations of insert, remove

  • ...}

  • Si usa l’iteratore delle liste ordinate

  • insert e remove si implementano banalmente usando le operazioni relative sulle liste ordinate (non li facciamo vedere)



Implementazione della sottoclasse SortedIntSet 2

  • public class SortedIntSet extends IntSet {

  • private OrderedIntList els; // la rappresentazione

  • .....

  • public boolean subset (IntSet s) {.....}

  • public boolean subset (SortedIntSet s)

  • // qui si approfitta del fatto che smallToBig di OrderedIntList

  • // ritorna gli elementi in ordine crescente

  • }



Per esercizio GIntSet

  • Altro sottotipo della classe astratta (insieme non ordinato)

  • E’ una classe concreta (completamente implementata) come quella che abbiamo visto solo che ora IntSet e’ astratta

  • Va definito il costruttore, i metodi di inserimento, rimozione e l’iteratore



Vantaggio della gerarchia

  • Una parte dello stato e delle operazioni sono definite in modo comune tra i diversi sottotipi (quelli implementati nella classe astratta)

  • Le due sottoclassi concrete definiscono implementazioni diverse: ordinato e non ordinato

  • Le due sottoclassi implementano solo le parti differenti



Gerarchie di classi astratte

  • anche le sottoclassi possono essere astratte

  • possono continuare ad elencare come astratti alcuni dei metodi astratti della superclasse

  • possono introdurre nuovi metodi astratti



Interfacce

  • contiene solo metodi non statici, pubblici (non è necessario specificarlo)

  • tutti i metodi sono astratti

  • è implementata da una classe che abbia la clausola implements nell’intestazione

  • un esempio che conosciamo: Iterator

  • public interface Iterator {

  • public boolean hasNext ( );

  • // EFFECTS: restituisce true se ci sono altri elementi

  • // altrimenti false

  • public Object next throws NoSuchElementException;

  • // MODIFIES: this

  • // EFFECTS: se ci sono altri elementi da generare dà il

  • // successivo e modifica lo stato di this, altrimenti

  • // solleva NoSuchElementException (unchecked)}



Ereditarietà multipla

  • una classe può estendere soltanto una classe

  • ma può implementare una o piú interfacce

  • si riesce così a realizzare una forma di ereditarietà multipla

    • nel senso di supertipi multipli
    • anche se non c’è niente di implementato che si eredita dalle interfacce
  • public class SortedIntSet extends IntSet

  • implements SortedCollection { .. }

  • SortedIntSet è sottotipo sia di IntSet che di SortedCollection



A cosa servono le interfacce?

  • A realizzare implementazioni multiple di un tipo di dato astratto

  • Per esempio potremmo definire IntSet come interfaccia

  • Definire sottotipi di IntSet che la implementano in modo diverso (con un vettore, o con una lista)

  • In questo modo l’interfaccia maschera l’implementazione (astrae dall’implemenazione)



A cosa servono le interfacce?

  • A realizzare tipi con un insieme di operazioni in comune (come nel caso di Iterator o Comparable)

  • Il codice scritto guardando l’interfaccia astrae dal particolare generatore







©astratto.info 2017
invia messaggio

    Pagina principale