Programmazione II - Lezione 17groups.di.unipi.it/~daniele/teaching/pr2-10/pr2-17.pdfJava: eccezioni...

Programmazione IILezione 17

Daniele Sgandurra

[email protected]

21/12/2010

1/31 Programmazione II Lezione 17 21/12/2010

Prossime Lezioni: Argomenti (Previsti)

Martedı (9-11) Venerdı (9-13) Argomenti21/12 Linguaggi di programmazione: strutturare i dati11/01 Java: ereditarieta

14/01 Liskov: astrazione procedurale, eccezioniJava: interfacce

18/01 Liskov: astrazione sui dati21/01 Liskov: iteratori, gerarchie di tipo

Java: eccezioni25/01 Liskov: gerarchie di tipo, astrazioni polimorfe

28/01 Recupero (da confermare): esercitazione


Sommario

1 Strutturare i DatiTipi CompostiEquivalenzaCombatibilitaPolimorfismo


Strutturare i Dati

Parte I

Strutturare i Dati


Strutturare i Dati

Tipi CompostiEquivalenzaCombatibilitaPolimorfismo

Array: Forma

La forma (shape) di un array e costituita del numero delle sue dimensionie dall’intervallo su cui ciascuna di esse puo variare.

Quando e fissata?

Statica: momento della compilazione (dimensione costante):

array nel RdA (o nella memoria per le variabili globali);offset calcolato tramite la formula precedente.

Elaborazione della dichiarazione:

intervallo indici dipendente da un’espressione variabile;calcolo a run-time quando si raggiunge la dichiarazione;array nel RdA, ma offset non noto;RdA diviso in due parti: parte fissa (offset) e parte variabile(indirizzamento indiretto tramite descrittore dei dati).

Dinamica:

limiti modificabili;non e possibile allocarlo sulla pila;allocazione sull’heap e nel RdA: puntatore all’array.


Strutturare i Dati


Array: Dope Vector

Il descrittore di un array di forma non nota staticamente, si chiama dopevector.

Di solito allocato nella parte a lunghezza fissa del RdA.

Contiene:

puntatore alla prima cella dell’area di memoria riservata all’array;informazioni dinamiche necessarie a calcolare l’offset:

numero dimensioni (rango);limiti per ogni dimensione (Li );occupazione di memoria per ogni dimensione (Si ).

Inizializzato al momento della creazione dell’array.

Accesso a un elemento:

1 accesso per offset tramite frame pointer al dope vector,2 calcolo della formula precedente,3 si somma all’indirizzo dell’inizio dell’array.


Strutturare i Dati


Rda con Dope Vector


Strutturare i Dati


Insiemi (1)

Tipi insieme: i valori sono costituiti da sottoinsiemi di un tipo base(ordinale). Ad esempio, in:

s e t o f c h a r S ;s e t o f Nano N ;

abbiamo una variabile S sottoinsieme dei caratteri, e una variabile N checonterra un insieme del tipo Nano.

Assegnamento:

N = {Eolo , B r o n t o l o} ;

Operazioni possibili:

test di appartenenza;operazioni insiemistiche (unione, intersezione, differenza).


Strutturare i Dati


Insiemi (2)

Rappresentato tramite un vettore di bit (il vettore caratteristico

dell’insieme):

lunghezza pari alla cardinalita del tipo base;

es.: un sottoinsieme di char (ASCII 7 bit) rappresentato con128 bit.

se il j-esimo bit e uguale a uno, l’elemento j-esimo del tipo baseappartiene all’insieme;se il j-esimo bit e uguale a zero, l’elemento j-esimo del tipo basenon appartiene all’insieme.

Se la cardinalita tipo base e elevata: tabelle hash.


Strutturare i Dati


Puntatori (1)

Costituiti da l-valori manipolabili direttamente.

Permessa la definzione di puntatori per ogni tipo del linguaggio:

se T e un tipo, si puo definire il tipo dei puntatori a T.

Consentono la definizione di tipi ricorsivi senza primitive apposite.

Nei linguaggi con modello variabili a riferimento, non sono necessari:

ogni variabile e sempre considerata un l-valore, anche se il valorenon puo essere modificato esplicitamente.

Dichiarazione del tipo T*: tipo dei puntatori a oggetti di tipo T:

puntatori a locazioni di memoria (variabili modificabili) checontengono valori di tipo T.

Valore speciali che indica il puntatore nullo (non punta a nessun valore):null.


Strutturare i Dati


Puntatori (2)

Operazioni permesse:

creazione;test di uguaglianza (es., con null);dereferenziazione (accesso all’oggetto puntato).

Per creare un valore di tipo puntatore:

i n t ∗p ;p = ( i n t ∗) malloc ( s i z e o f ( i n t ) ) ;

oppure:

f l o a t r = 3 . 1 4 1 5 ;f l o a t ∗q = &r ;

Dereferenziazione:

∗p = 3 3 ; // s i a s s e g n a 33 a l l ’ o g g e t t o puntato da p ( s u l l o heap )r = ∗q + 1 ; // s i a s s e g n a a r i l v a l o r e 4 .1415 ( s u l l a p i l a : q m o d i f i c a t o )


Strutturare i Dati


Puntatori (3)

Definizione di strutture dati ricorsive (liste, alberi, etc). Es., lista di interi:

type int_list = elemento ∗ ;type elemento = s t r u c t { i n t val ;

int_list next ;} ;

Aritmetica dei puntatori: incremento, sottrazione tra due puntatori (perottenere un offset), somma. Ad esempio, in:

i n t ∗p = ( i n t ∗) malloc ( s i z e o f ( i n t ) ) ;i n t ∗c = ( c h a r ∗) malloc ( s i z e o f ( c h a r ) ) ;p = p + 1 ;c++;

le ultime due operazioni incrementano il valore di p e c di, rispettivamente,sizeof(int) e sizeof(char).

Nociva per la type-safety del linguaggio:

non c’e garanzia che in tutti i momenti una variabile dichiarata puntatorea un oggetto di tipo T punti a un’area di memoria contenente un oggettodi tipo T.


Strutturare i Dati


Puntatori (4)

Deallocazione:

implicita: il linguaggio non fornisce nessuno strumento per deallocare la

memoria;

il programma richiede memoria fino quando e disponibile nello heap;se parte della memoria allocata non e piu raggiungibile, si usa ilgarbage collector per recuperarla.

esplicita: il linguaggio offre un meccanismo per rilasciare la memoria

riferita da un puntatore:

ad esempio, in C se p punta a un oggetto allocato (tramitemalloc()) sullo heap, si usa free(p) per rilasciare la memoriapuntata;dangling reference: puntatori che puntano a informazioni non piusignificative.


Strutturare i Dati


Dangling Reference: Esempio

i n t ∗p = ( i n t ∗) malloc ( s i z e o f ( i n t ) ) ;i n t ∗q = p ;∗p = 5free ( p ) ;p = null ;write (∗p ) ;write (∗q ) ;


Strutturare i Dati


Tipi Ricorsivi

Tipo composto in cui un valore puo contenere (un riferimento a) unvalore dello stesso tipo. Ad esempio, in:

type int_list = { i n t val ;int_list next ;} ;

il tipo int list e formato da una coppia: un intero e un tipo int list ecosı via.

Per terminare la ricorsione, solitamente si usa un valore speciale (es.,null).

Linguaggi flessibili e potenti con i tipi ricorsivi.

Operazioni permesse: selezione di una componente e test di uguaglianzacon null.


Strutturare i Dati


Funzioni

Alcuni linguaggi, permetto di denotare il tipo delle funzioni. Ad esempio,se f e una funzione definita come: T f(S s){...}, possiamo indicare ilsuo tipo come S->T.

In generale, una funzione: T f(S1 s1, ... , Sn sn){...}, ha tipoS1× ... Sn -> T.

Valori sempre denotabili, raramente esprimibili o memorizzabili.

Operazioni principali: applicazione (invocazione di una funzione suiparametri attuali).

Nei linguaggi di ordine superiore:

le funzioni possono essere passate come argomento a un’altrafunzione;si possono definire funzioni che restituiscono funzioni come risultato.


Strutturare i Dati


Equivalenza

Regole per definire quando due tipi, formalmente diversi, sono daconsiderarsi intercambiabili (non sono distinguibili in un programma).

Relazione di equivalenza: se due tipi sono equivalenti, ogni espressione ovalore di un tipo e anche un’espressione o valore dell’altro (e viceversa).

La definizione type nuovotipo = espressione e interpretabile in due

modi diversi:

definizione di tipo opaca: si ha equivalenza per nome;definizione di tipo trasparente: si ha equivalenza strutturale.


Strutturare i Dati


Equivalenza per Nome

Equivalenza per Nome

Due tipi sono equivalenti per nome solo se hanno lo stesso nome (cioe, un tipoe equivalente solo a se stesso)

Ad esempio, le seguenti definizioni di tipo:

t y p e T1 = 1 . . 1 0 ;t y p e T2 = 1 . . 1 0 ;t y p e T3 = int ;t y p e T4 = int ;

introducono quattro tipi distinti: non vi sono equivalenze tra di essi.

Se il linguaggio adotta una equivalenza per nome debole, una

ridenominazione di un tipo non genera un nuovo tipo ma solo un alias:

nell’esempio precedente, con equivalenza per nome debole, i tipi T3e T4 sono equivalenti, mentre sono distinti T1 e T2.


Strutturare i Dati


Equivalenza Strutturale (1)

Equivalenza Strutturale

L’equivalenza strutturale fra tipi e la minima relazione d’equivalenza che soddisfa leseguenti proprieta:

un nome di tipo e equivalente a se stesso;

se un tipo T e introdotto con type nuovotipo = espressione, T eequivalente a espressione;

se due tipi sono costruiti applicando lo stesso costruttore di tipo a tipiequivalenti, allora essi sono equivalenti.

Ad esempio, le seguenti definizioni di tipo:

type T1 = i n t ; type T2 = c h a r ;type T3 = struct {

T1 a ; T2 b ;}

type T4 = struct {i n t a ; c h a r b ;

}

introducono due tipi strutturalmente equivalenti T3 e T4.


Strutturare i Dati


Equivalenza Strutturale (2)

Esempio: sono equivalenti le seguenti definizioni?

type S = s t r u c t { i n t a ;i n t b ;}

type T = s t r u c t { i n t n ;i n t m ;}

type U = s t r u c t { i n t m ;i n t n ;}

Esempio: sono equivalenti le seguenti definizioni?

type R1 = s t r u c t { i n t a ;R2 p ;}

type R2 = s t r u c t { i n t a ;R1 p ;}

Equivalenza strutturale non legata al singolo programma: sostituzionesempre possibile (trasparenza referenziale).

I linguaggi spesso adottano regole di equivalenza miste.


Strutturare i Dati


Combatibilita (1)

Combatibilita

Diciamo che il tipo T e compatibile con il tipo S, se un valore di tipo T eammesso in un qualsiasi contesto in cui sarebbe richiesto in valore di tipo S

Regola usata per controllare la correttezza:

di un assegnamento: il tipo del membro destro compatibile conquello del membro sinistro;del passaggio dei parametri: tipo del parametro attuale compatibilecon quello del formale.

Relazione piu debole dell’equivalenza:

due tipi equivalenti sono sempre compatibili (ma non viceversa);relazione riflessiva, transitiva ma non simmetrica (es., int e float).


Strutturare i Dati


Combatibilita (2)

Un tipo T puo essere compatibile con S quando:

1 T e S sono equivalenti;

2 i valori di T sono un sottoinsieme dei valori di S (es., il tipo intervallo conil tipo base);

3 tutte le operazioni sui valori di S sono possibili anche sui valori di T. Es.,

type S = s t r u c t { i n t a ;}type T = s t r u c t { i n t a ; c h a r b ;}

le operazioni ammesse su S (selezione del campo a) sono ammesse anchesu T: sottotipo.

4 i valori di T corrispondono in modo canonico a alcuni valori di S (es., intcompatibile con float);

5 i valori di T possono essere fatti corrispondere a alcuni valori di S (es.,float compatibile con int tramite conversione).


Strutturare i Dati


Conversioni

Se un tipo T e compatibile con S, il linguaggio permette di usare un valore di Tdove sarebbe richiesto un valore di S:

il compilatore e/o la macchina astratta inseriscono una conversioneimplicita di tipo da T a S (coercizione di tipo);

conversioni esplicite (cast): annotazioni del linguaggio che specificano che

un valore di un tipo deve essere convertito in un altro tipo:

notazione: S s = (S) t;: assegnamento a una variabile di tipo S ilvalore t dopo averlo convertito nel tipo S;

solitamente, i linguaggi favoriscono i cast rispetto le coercizioni:

piu espressivi (codice piu leggibile);non dipendono dal contesto sintattico in cui compaiono;si comportano meglio in presenza di overloading e polimorfismo.


Strutturare i Dati


Polimorfismo

Un sistema dei tipi e monomorfo, se ogni oggetto del linguaggio (valore,funzione, etc) ha un unico tipo.

Un sistema di tipi nel quale uno stesso oggetto puo avere piu di un tipo e detto

polimorfo:

un oggetto e polimorfo se il sistema di tipi gli assegna piu di un tipo.

Limitate forme di polimorfismo:

+: tipo int × int -> int, float × float -> float;il valore null ha tipo T* per ogni tipo T.

Solitamente, non e permesso definire oggetti polimorfi. Es.:

v o i d int_sort ( i n t A [ ] )v o i d char_sort ( c h a r C [ ] )

Un linguaggio polimorfo permetterebbe di definire un’unica funzione:

v o i d sort(<T> A [ ] )

dove <T> indica un tipo generico.


Strutturare i Dati


Overloading

L’overloading (o polimorfismo ad hoc) e un polimorfismo solo inapparenza.

Un nome e sovraccaricato (overloaded) quando a esso corrispondono piu

oggetti:

si usa l’informazione fornita dal contesto per decidere quale oggettoe denotato da una specifica istanza di quel nome;es.: l’operatore +, funzioni/costruttori con lo stesso nome.

Ambiguita risolta staticamente (grazie al contesto).

Sorta di abbreviazione sintattica che scompare non appena sianointrodotte ulteriori informazioni.


Strutturare i Dati


Polimorfismo Universale Parametrico

Polimorfismo universale parametrico

Un valore esibisce polimorfismo universale parametrico quando ha un’infinita ditipi diversi, che si ottengono per istanziazione da un unico schema di tipogenerale.

Una funzione polimorfa universale e costituita da un unico codice chelavora uniformemente su tutte le istenza del suo tipo generale.

La funzione void sort(<T> A[]) ordina array di qualsiasi tipo:

il tipo polimorfo sort e <T>[]->void;<T> significa che non e un tipo vero e proprio ma si comporta comeun parametro:

sostituendolo con un qualsiasi tipo concreto, si ottiene un tipospecifico per sort;es.: int[]->void, char[]->void.


Strutturare i Dati


Polimorfismo Universale Parametrico: Esempio

Esempio di funzione polimorfa:

v o i d swap ( reference <T> x , reference <T> y ) {<T> tmp = x ;x = y ;y = tmp ;

}

Un oggetto polimorfo puo essere istanziato su uno specifico tipo.

La modalita piu semplice di istanziazione e quella automatica, effettuatadal compilatore o dalla macchina astratta:

i n t∗ k = null ; // n u l l d i t i p o i n t∗c h a r v , w ;i n t i , j

. . .swap (v , w ) ; // swap i s t a n z i a t a s u i c a r a t t e r iswap (i , j ) ; // swap i s t a n z i a t a s u g l i i n t e r i


Strutturare i Dati


Polimorfismo Universale di Sottotipo

Usato tipicamente nei linguaggi orientati agli oggetti.

Forma piu limitata di polimorfismo universale.

Un oggetto ha un’infinita di tipi diversi, che si ottengono per

istanziazione da uno schema di tipo piu generale:

non tutte le possibili istanziazioni dello schema di tipo piu generalesono ammissibili;limitate a quelle definite da nozioni di compatibilita strutturale tratipi (nozione di sottotipo).

Polimorfismo di Sottotipo

Un valore esibisce polimorfismo di sottotipo quando ha un’infinita di tipi diversiche si ottengono per istanziazione da uno schema di tipo generale, sostituendoa un opportuno parametro i sottotipi di un tipo assegnato.

Notazione: ∀T<:D.T-> void: funzione applicata a un qualsiasi sottotipo di T.


Strutturare i Dati


Polimorfismo: Implementazione

Gestione statica: linking-time:

istanziazione funzioni polimorfe (in base ai tipi):

produzione codice opportuno (varie copie del template);linking.

efficiente come le funzioni non polimorfiche;es., template in C++.

Gestione dinamica:

unica versione del codice generata:

rappresentazione piu complessa: sul RdA non sono allocati idati ma descrittori (dimensione, struttura, etc).

piu flessibile ma meno efficiente a run-time;esempio: ML.


Strutturare i Dati


Controllo e Inferenza di Tipo

E compito del type-checker verificare che un programma rispetti le regoleimposte dal sistema di tipi (in particolare, la compatibilita).

In un linguaggio con controlli statici, il type-checker e un modulo del

compilatore:

esplora l’albero sintattico;determina il tipo delle espressioni (compatibilita tra membro destroe sinistro);usa le informazioni esplicite (dichiarazioni, conversioni esplicite) oimplicite (tipi costanti).

In un linguaggio con controlli dinamici, il type-checker e un modulo delsupporto a tempo di esecuzione.


Strutturare i Dati


Riferimenti

[1] Linguaggi di programmazione: principi e paradigmi (Cap. 8).

Maurizio Gabbrielli, Simone Martini.


Programmazione II - Lezione 17groups.di.unipi.it/~daniele/teaching/pr2-10/pr2-17.pdfJava: eccezioni...

Documents

Transcript of Programmazione II - Lezione 17groups.di.unipi.it/~daniele/teaching/pr2-10/pr2-17.pdfJava: eccezioni...