Strutture Dati - Lacam

Transcript

Strutture Dati Nicola Fanizzi Linguaggi di Dipartimento di Informatica Programmazione [010194] Università degli Studi di Bari 9 mag, 2016 Sommario 1 2 Tipi e sistemi di tipi Definizioni Sistemi di tipi Tipi scalari Tipi scalari e ordinali Booleani Caratteri 3 Numerici: interi, reali, complessi void Enumerazioni e intervalli Tipi Composti Record LdP.ITPS/[email protected] Array Insiemi Puntatori 4 Relazioni fra tipi Equivalenza Compatibilità e conversione di tipo Polimorfismo Controllo e Inferenza 5 Strutture dati e gestione della memoria Dangling reference Garbage collection Strutture Dati 9 mag, 2016 2 / 88 Agenda 1 Tipi e sistemi di tipi Definizioni Sistemi di tipi 3 Tipi Composti 4 Relazioni fra tipi 5 2 Tipi scalari LdP.ITPS/[email protected] Strutture dati e gestione della memoria Strutture Dati 9 mag, 2016 3 / 88 Introduzione Scopi dei Tipi di dato: Progetto: supporto all’organizzazione concettuale Programma: supporto alla correttezza Traduzione: supporto all’implementazione LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 4 / 88 Tipi Definizione (Tipo) Un tipo di dato è una collezione di valori omogenei, effettivamente presentabili, dotata di un insieme di operazioni che manipolano tali valori Omogeneità I valori condividono alcune proprietà strutturali Presentabilità Devono potere avere una presentazione finita per la loro scrittura es. non esiste un tipo dei numeri reali veri e propri Operazioni La stessa collezione di valori può essere impiegata in tipi diversi a seconda delle operazioni definite es. i tipi interi nei vari linguaggi LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 5 / 88 Tipi – utilità Progetto: Supporto all’organizzazione concettuale Dominare la complessità dei problemi Esplicitare i concetti tipici attraverso nuovi tipi Aumento di leggibilità (documentazione) e di sicurezza (controlli automatici) LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 6 / 88 Tipi – utilità [. . . cont.] Programma: Supporto alla correttezza Vincoli di tipo (problemi di semantica) errori HW es. salto a zona di memoria che non contiene codice errori logici es. somma intero + stringa Controlli semantica statica: Type checker come i commenti ma i controlli sono effettuabili automaticamente non risolvono tutti i problemi logici: es. formule della fisica, prima controlli sulle dim. Polimorfismo es. stessa funzione (es. sort) su strutture di tipi diversi Sicurezza: vincoli soddisfatti ma problemi rilevati in fase d’esecuzione? linguaggi sicuri e non es. dangling reference LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 7 / 88 Tipi – utilità [. . . cont.] Traduzione: Supporto all’implementazione Informazioni per la macchina astratta disponibili staticamente Dimensione richiesta per l’allocazione sia nel RdA sullo stack sia su heap Ottimizzazioni sulle op. d’accesso Calcoli statici Ind. oggetto + offset LdP.ITPS/[email protected] (no ricerca per nome) Strutture Dati 9 mag, 2016 8 / 88 Sistemi di tipi Sistema di tipi: complesso delle informazioni e delle regole che governano i tipi di un linguaggio 1 Insieme dei tipi predefiniti 2 Costrutti per definire nuovi tipi Meccanismi per il controllo dei tipi 3 Regole di equivalenza: due tipi formalmente diversi possono essere equivalenti livello semantico Regole di compatibilità: un valore di un tipo diverso da quello atteso può essere comunque utilizzato Regole di inferenza: attribuzione di un tipo ad un’espressione complessa in base alle componenti 4 se/quali vincoli controllare staticamente/dinamicamente LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 9 / 88 Sistemi di tipi - sicurezza Un sistema di tipi (e, per estensione, un linguaggio) si dice type-safe1 (sicuro a livello di tipi) quando nessun programma può ignorare le differenze tra tipi definite dal sistema/linguaggio nessun programma può generare errori inattesi derivanti da violazioni di tipo a run-time ad esempio: accesso a memoria non allocata chiamata di un valore che non si riferisce ad una funzione 1 o strongly typed (fortemente tipizzato). LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 10 / 88 Classificazione dei tipi In base ai valori (... ed alle operazioni): denotabili possono essere associati ad un nome esprimibili possono essere il risultato di una espressione complessa (più di un semplice nome) memorizzabili possono essere memorizzati in una variabile LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 11 / 88 Classificazione dei tipi [. . . cont.] Esempi Tipo delle funzioni (int -> int) valore denotabile: possiamo associare un nome ad una funzione 1 2 3 int succ (int x) { return x + 1; } valore esprimibile: solo nei ling. funzionali e non negli imperativi Funzioni risultato della valutazione di un’espressione valore memorizzabile idem (ML, HASKELL, SCHEME) LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 12 / 88 Sistemi di tipi – controlli Tipizzazione statica: controlli a compile-time (es. JAVA) Controlli anticipati Correttezza garantita per ogni sequenza d’esecuzione Controlli a run-time inutili: maggiore efficienza Progettazione più complessa se il linguaggio deve anche essere type-safe Compilazione lenta e complessa ma facilita debugging/testing Tipizzazione dinamica: controlli a run-time (es. LISP) Ogni oggetto ha un descrittore che ne contiene il tipo La macchina astratta controlla la correttezza degli operandi nelle operazioni Il compilatore ha generato codice di controllo opportuno Caratteristiche previene errori di tipo (troppo tardi?) esecuzione meno efficiente LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 13 / 88 Sistemi di tipi – controlli [. . . cont.] Osservazioni Programmi sicuri che la tipizzazione statica può male interpretare come errati: Controllo statico: più conservatore Esempio dato il frammento: int x; if (1==0) x = "errore"; 3 else x = x + 2; 1 2 l’esecuzione non causa errore ma risulta non corretto al controllo statico Controllo sui tipi in generale: problema indecidibile Per prudenza un controllo statico esclude anche casi non pericolosi, come il precedente In molti linguaggi (es. PASCAL) controllo statico+dinamico es. utilizzo di vettori con controllo degli indici a run-time LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 14 / 88 Indecidibilità del controllo sui tipi Controllo statico: più conservatore 1 2 3 int x; Proc(); x = "errore"; Se si potesse sapere sempre se Proc() termina allora si potrebbe segnalare l’errore di tipo E se Proc() non terminasse mai ? allora l’errore di tipo non si verificherebbe quindi il programma sarebbe corretto Essendo il problema della fermata indecidibile lo sarà anche quello del controllo della correttezza dei tipi LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 15 / 88 Agenda Enumerazioni e intervalli 1 2 Tipi e sistemi di tipi Tipi scalari Tipi scalari e ordinali Numerici: interi, reali, complessi void LdP.ITPS/[email protected] 3 Tipi Composti 4 Relazioni fra tipi 5 Strutture dati e gestione della memoria Strutture Dati 9 mag, 2016 16 / 88 Tipi scalari Tipi scalari (o semplici): tipi i cui valori sono atomici, i.e. non sono costituiti da aggregati di altri valori notazione type = ; Tipi ordinali (o discreti): dotati di una relazione d’ordine totale Valori: discreti booleani, caratteri, interi, enumerazioni ed intervalli Operazioni: precedente e successivo Utili per gli indici LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 17 / 88 Booleani Per valori logici (o di verità) Valori: uno per il vero (es. true) uno per il falso (es. false) Operazioni: congiunzione (and), disgiunzione (or), negazione (not), or esclusivo, uguaglianza Valori denotabili, esprimibili, memorizzabili Memorizzazione nelle minime unità di memoria indirizzabili LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 18 / 88 Caratteri Valori: un insieme di codici di caratteri fissato durante la progettazione del linguaggio Es: ASCII, UNICODE Operazioni: logiche uguaglianza, confronti, ordinali carattere successivo (succ) o precedente (prec) Valori denotabili, esprimibili, memorizzabili Memorizzazione con 1 (ASCII) o 2 (UNICODE) byte LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 19 / 88 Interi Valori: sottoinsieme finito dei numeri interi fissato durante la progettazione del linguaggio o della macchina astratta Di solito del tipo [−2t , +2t − 1] A volte sono possibili interi di lunghezza illimitata Operazioni aritmetiche e confronti Somma, differenza, prodotto, divisione (intera), resto, potenza Valori denotabili, esprimibili, memorizzabili Memorizzazione con un numero (pari) di byte in complemento a due LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 20 / 88 Reali numeri reali in virgola fissa Valori: sottoinsieme finito dei numeri razionali fissato durante la progettazione del linguaggio o della macchina astratta Ampiezza e granularità, ecc. dell’insieme dipendono dalla rappresentazione scelta Operazioni aritmetiche e confronti Somma, differenza, prodotto, divisione (intera), resto, esponenziale, radice quadrata Valori denotabili, esprimibili, memorizzabili Memorizzazione con un numero di 4 o 8 byte complemento a 2 numero fissato di bit per la parte decimale LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 21 / 88 Reali [. . . cont.] virgola mobile Valori: sottoinsieme finito dei numeri razionali fissato durante la progettazione del linguaggio o della macchina astratta Ampiezza e granularità, ecc. dell’insieme dipendono dalla rappresentazione scelta Operazioni aritmetiche e confronti Somma, differenza, prodotto, divisione (intera), resto, esponenziale, radice quadrata Valori denotabili, esprimibili, memorizzabili Memorizzazione con un numero di 4,8,10 byte Standard IEEE 754 LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 22 / 88 Complessi numeri complessi Valori: sottoinsieme finito dei numeri complessi fissato durante la progettazione del linguaggio Ampiezza e granularità, ecc. dell’insieme dipendono dalla rappresentazione scelta Operazioni aritmetiche e confronti Somma, differenza, prodotto, divisione (intera), resto, esponenziale, radice quadrata Valori denotabili, esprimibili, memorizzabili Memorizzazione con una coppia di reali in virgola mobile LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 23 / 88 void Valori: un solo valore void o unit (insieme singoletto) oppure { } una funzione matematica non può avere codominio vuoto sono tali le funzioni che divergono sempre Operazioni: nessuna Utile a denotare operazioni che non restituiscono un valore utile (ma hanno effetti collaterali) es. assegnamento (in molti linguaggi) ossia restituiscono un unico valore implicitamente LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 24 / 88 Enumerazioni Tipi semplici definiti dall’utente Valori: un insieme finiti di costanti caratterizzate da un proprio nome es. type giorni = (lun,mar,mer,gio,ven,sab,dom); Operazioni: confronti, operatori per raggiungere il valore precedente o il successivo Vantaggi Aumenta la leggibilità Ausilio del controllo dei tipi Memorizzazione: mappaggio sugli interi In alcuni linguaggi (C/C++, ADA, ...) si possono anche scegliere esplicitamente LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 25 / 88 Intervalli Tipi semplici definiti dall’utente Valori: sottoinsieme contiguo dei valori di un altro tipo scalare (tipo base) 1 2 type NumeriLotto = 1..90; Giorniferiali = lun..ven; Operazioni: confronti, operatori per raggiungere il valore precedente o il successivo Vantaggi Maggiore la leggibilità Ausilio al controllo dei tipi: dinamico Memorizzazione: mappati sugli interi Come per il tipo base LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 26 / 88 Agenda 1 Tipi e sistemi di tipi 2 Tipi scalari Array Insiemi Puntatori Relazioni fra tipi 4 3 Tipi Composti Record LdP.ITPS/[email protected] 5 Strutture dati e gestione della memoria Strutture Dati 9 mag, 2016 27 / 88 Tipi Composti Tipi non scalari, ottenuti per combinazione di tipi più semplici Record (o strutture): collezione di valori eterogenei Array: collezione di valori omogenei Insiemi: sottoinsiemi di un tipo (base, ordinale) Puntatori: l-valori per accedere indirettamente ad altri valori Tipi ricorsivi: definiti per ricorsione LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 28 / 88 Record (o strutture) Record: Collezione di un numero finito (e spesso ordinato) di elementi detti campi Ogni campo è caratterizzato dal nome dal tipo (anche diverso da quello degli altri campi) si può assimilare quindi ad una variabile Spesso è possibile annidare record all’interno di record LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 29 / 88 Record (o strutture) [. . . cont.] Esempio type studente = struct { int matricola; 3 float statura; 4 }; 1 2 LdP.ITPS/[email protected] Esempio annidamento type Aula = struct { char nome[5]; 3 int capienza; 4 struct { 5 char dipart[10]; 6 int tel; 7 } segreteria; 8 }; 9 ... 10 Aula a; 11 a.nome = ’B-1’ 12 a.segreteria.tel = 1234; 1 2 Strutture Dati 9 mag, 2016 30 / 88 Record (o strutture) [. . . cont.] Operazioni: selezione, indicata con “.” alcuni linguaggi ammettono assegnazione e test di uguaglianza tra interi record se non permesse bisogna procedere campo per campo l’ordine dei campi può essere significativo Memorizzazione in locazioni contigue nell’ordine di definizione Esempio nome capienza Diverse organizzazioni possibili dovute all’allineamento dipartimento Migliora l’efficienza nel reperimento LdP.ITPS/[email protected] arch. 32bit telefono Strutture Dati 9 mag, 2016 31 / 88 Record varianti e unioni Record varianti: record con campi mutuamente esclusivi Nomi e sintassi diverse per ogni linguaggio es. in PASCAL, record con una parte della struttura variabile: solo una delle varianti ammesse è significativa Esempio type studente = record nome: array [1..6] of char; 3 matricola: integer; 4 case fuoricorso: boolean of 5 true: (ultimoanno: 2000..maxint); 6 false:( inpari: boolean; 7 anno: (primo,secondo,terzo) 8 ) 9 end; 1 2 LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 32 / 88 Record varianti e unioni [. . . cont.] unioni strutture con campi mutualmente esclusivi Nomi e sintassi diverse per ogni linguaggio es. in C, struttura con un solo campo alla volta valido union per la parte variante struct studente { char[6] nome; 3 int matricola; 4 int fuoricorso; 5 union { int ultimoanno; 6 struct { int inpari; 7 int anno; 8 } studente_in_corso; 9 } campi_varianti; 10 } 1 2 LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 33 / 88 Record varianti e unioni [. . . cont.] Record varianti vs. Unioni Similarità Differenze Le varianti e le unioni condividono le stesse aree di memoria In C un campo della union è svincolato dal resto più flessibile più oneroso per il programmatore più rischioso Livelli di nomi: In PASCAL, campo come gli altri: s.inpari In C, occorre aggiungere ulteriori livelli di nomi LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 34 / 88 Record varianti e unioni [. . . cont.] Problema di sicurezza modifica tag discriminante con assegnamento ordinario (in PASCAL e C) La macchina astratta potrebbe controllare (dinamicamente) il tag per sapere se il record è usato correttamente risolve molti problemi semantici ma non tutti 1 type Tre = 1..3; ma anche var tmp: record case quale: Tre of 4 1: (a:integer); 5 2: (b:boolean); 6 3: (c:char); 7 end 8 ... 9 tmp.quale:=1; 10 tmp.a:=123; 11 write(tmp.c); 12 (* errore a run-time *) 2 3 LdP.ITPS/[email protected] tmp.quale:=1; tmp.a:=123; 3 tmp.quale:=3; 4 write(tmp.c); 5 (* semanticamente errato, 6 ma non rilevato *) 1 2 Strutture Dati 9 mag, 2016 35 / 88 Array Array: Collezione finita di elementi dello stesso tipo (tipo base) indicizzata su un intervallo di tipo ordinale (tipo indice) Specifica Nome Tipo indice Tipo dei componenti es. in C: int v[10]; Array multidimensionali: usando indici molteplici a volte come array di array op. di slicing ritagliare una “fetta”, fissando una dim. LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 36 / 88 Array [. . . cont.] Operazioni Selezione: si indica (spesso tra [...]) un’espressione il cui valore rappresenta l’indice dell’elemento da selezionare es. array monodimensionale: v[] es. array multidimensionale: m[][]...[] Assegnamento Test di uguaglianza ed altri test di confronto Op. dell’algebra lineare nei ling. che supportano il trattamento delle matrici Slicing slice: sezione di array costituita da elementi contigui in una data dimensione (es. un piano) in alcuni linguaggi si possono estrarre anche selezioni diagonali cornici, ecc. LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 37 / 88 Array [. . . cont.] Controlli Selezione entro i limiti del tipo indice A run-time Per un linguaggio safe: il compilatore genera controlli per ogni selezione generazione spesso disattivabile con un’opzione del compilatore Safety & security Attacchi buffer overflow LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 38 / 88 Array [. . . cont.] Memorizzazione Sezioni contigue di memoria Array monodimensionale Allocazione secondo l’ordine degli indici Array multidimensionale Ordine di riga Elementi contigui differiscono di un’unita nell’indice più a destra nella lista Ordine di colonna Elementi contigui differiscono di un’unita nell’indice più a sinistra nella lista Dividere nell’una o l’altra maniera può avere un impatto sull’efficienza del caching LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 39 / 88 Array [. . . cont.] Calcolo degli indici Dato un array m a n dimensioni di tipo T T m[L1 ,U1 ][L2 ,U2 ]...[Ln ,Un ] Sn : unità di mem. indirizzabili per elem. di T (per riga) Sn−1 = (Un − Ln + 1)Sn (slice di ordine superiore) ... S1 = (U2 − L2 + 1)S2 Per cercare l’indirizzo di m[i1 ][i2 ]...[in ] all’indirizzo iniziale, si somma l’offset: (i1 − L1 )S1 + (i2 − L2 )S2 + · · · + (in − Ln )Sn Se le dim. sono tutte note, meglio usare: i1 S1 + · · · + in Sn − (L1 S1 + · · · + Ln Sn ) n moltiplicazioni, n addizioni, n sottrazioni (che P non servono se gli indici partono da 0, i Li Si predeterminato) LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 40 / 88 Array [. . . cont.] Forma (shape): numero delle dim. e intervallo per ogni dim. Quando viene fissata ? Statica al momento della compilazione (dim. fissate) Array nel RdA (o nella mem. per le var. globali) Accesso tramite la formula precedente Elaborazione della dichiarazione Intervallo indici dipendente da un’espressione variabile Calcolo a run-time Array nel RdA: ma offset non noto! Parte fissa (offset) e parte variabile (ind. indiretto) Dinamica Limiti modificabili Allocazione sull’heap: (sulla pila non è possibile) Nel RdA: puntatore all’array LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 41 / 88 Array [. . . cont.] Dope vector: descrittore di array di forma non nota staticamente Allocato nella parte a lunghezza fissa del RdA riservata all’array Contiene: puntatore alla prima cella dell’area di mem. riservata all’array informazioni dinamiche utili (non memorizzate se determinabili staticamente) numero dimensioni limiti per ogni dim. (Li , Ui ) occupazione per ogni dim. (Si ) Accesso ad un elemento: accesso per offset tramite frame pointer al dope vector calcolo della formula precedente si somma all’indirizzo dell’inizio dell’array LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 42 / 88 Array [. . . cont.] ... lunghezza variabile m ... var locali lunghezza fissa L3 S3 L2 S2 L1 S1 dope vector di m puntatore ad m ... frame pointer ind.ritorno parametri LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 43 / 88 Insiemi Insieme: collezione di valori che costituiscono un sottoinsieme di un tipo base (universo) Solitamente il tipo base è ordinale (PASCAL) Esempi set of char S; set of Giorni IG; WE = (Sab, Dom); Operazioni Appartenenza (∈, in) Unione (+), intersezione (*), differenza (-) (a volte anche complemento) Rappresentazione vettori di bit (vettore caratteristico) Vj = 1 sse il j-esimo elemento dell’universo appartiene all’insieme Tabelle hash . . . LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 44 / 88 Puntatori Puntatore: tipo di variabili atte a contenere l-valori, direttamente manipolabili, utili a riferirsi indirettamente ad altre var. In genere è possibile indicare anche il tipo delle variabili puntate TipoBase * P; In PASCAL o ADA: possono solo puntare a variabili del tipo dato In C/C++: non c’è un vincolo stretto Ove presenti, consentono la definizione di tipi ricorsivi senza primitive apposite Nei linguaggi con variabili-riferimento, gli l-valori non possono essere manipolati direttamente valore nullo: il puntatore non punta ad alcuna variabile es. null (o nil, in PASCAL) LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 45 / 88 Puntatori [. . . cont.] Operatori Assegnamento di un valore ad un puntatore mediante Allocazione esplicita int *p; p = (int *) malloc(sizeof (int)); Costruttori (di oggetti) Operatore & float pigreco = 3.1415, *pp; pp = &pigreco; Dereferenziazione ^ (PASCAL) oppure * (in C/C++) es. precedente: float circ = 2 * r * (*pp ); Vale sia per l’l-valore sia per l’r-valore LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 46 / 88 Puntatori [. . . cont.] test di uguaglianza Creazione di strutture ricorsive Quando non previste dal linguaggio es. lista di interi (successione ordinata di dim. variabile) typedef nodo* lista_int; typedef struct { int val; 3 lista_int succ} nodo; 1 2 LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 47 / 88 Puntatori [. . . cont.] Aritmetica In C ed alcuni derivati: operazioni aritmetiche su puntatori Incremento/decremento di un puntatore: p++ / p-indirizzo incrementato di sizeof(tipobase) Sottrazione di puntatori: p1 - p2 Offset tra p1 e p2 Somma di un quantità ad un puntatore: p + n punta alla variabile con offset pari a n*sizeof(tipobase) Nociva per la type-safety del linguaggio Non c’è garanzia che in tutti i momenti un puntatore punti effettivamente ad una variabile del tipo atteso int *p; int *c; 3 p = (int*) malloc(sizeof(int)); 4 c = (char*) malloc(sizeof(char)); 5 p = p+1 6 c++; 1 2 LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 48 / 88 Puntatori [. . . cont.] Deallocazione implicita nessuno strumento per deallocare la memoria avviene quando non c’è più spazio sullo heap possibile recuperare memoria inutilizzata tecniche di garbage collection esplicita costrutto previsto dal linguaggio In C: funzione free() free(p) libera la memoria della variabile puntata da p e conviene anche assegnare: p=null; se p vale già null allora si ha un errore semantico Dangling reference: puntatori con valore diverso da null che puntano a zone non più significative memoria deallocata o ri-allocata riferimenti non validi alla pila d’esecuzione (anche con deallocazione implicita) LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 49 / 88 Tipi ricorsivi Tipi composti in cui un valore può contenere (un riferimento ad) un valore dello stesso tipo Esempi 1 2 (pseudocodice): type ListaInt = { int val; ListaInt next; } type AlberoChar = { char val; AlberoChar sinistro; 3 AlberoChar destro; } 1 2 Operazioni Selezione Test di uguaglianza LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 50 / 88 Tipi ricorsivi [. . . cont.] Rappresentati con strutture dati su heap Ling. Imperativi: Strutture concatenate (ottenute con riferimenti/puntatori) Allocazione esplicita Ling. Funzionali: espressione diretta di val. di tipi ricorsivi No deallocazione 1 ListaInt: (2,(33,(1,(4,(3,(1,21,null))))))) 2 CharAlbero: (A, 5 (B, 6 (C,null,null), 7 (D, 8 (E,null,null), 9 null 10 ), 11 (F,null,null) 12 ) 3 A 4 LdP.ITPS/[email protected] B C / / F / / D / E / / Strutture Dati 9 mag, 2016 51 / 88 Tipi di funzioni Alcuni linguaggi permettono di definire tipi di funzioni i valori di questi tipi sono funzioni tipo di funzione denotato con T f(S1 s1, S2 s2, ... , Sn sn) {...} oppure anche con S1 x S2 x ... x Sn -> T Operazioni Definizione (soprattutto funzionali) Applicazione (chiamata su parametri effettivi) Valori implementati come puntatori PASCAL, C, C++ LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 52 / 88 Agenda 1 Tipi e sistemi di tipi 2 Tipi scalari 3 Tipi Composti LdP.ITPS/[email protected] 4 Relazioni fra tipi Equivalenza Compatibilità e conversione di tipo Polimorfismo Controllo e Inferenza 5 Strutture dati e gestione della memoria Strutture Dati 9 mag, 2016 53 / 88 Equivalenza Regole utili a stabilire quando due tipi, formalmente diversi, sono intercambiabili, ossia non distinguibili nel loro uso per due tipi equivalenti, ogni espressione/valore del primo tipo è anche espressione/valore del secondo e viceversa Definizione di un nuovo tipo type nuovotipo = espressioneTipo Regole per la sua interpretazione: Definizione opaca: equivalenza per nome Definizione trasparente: equivalenza strutturale LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 54 / 88 Equivalenza per nome Ogni nuova definizione introduce un nuovo tipo Definizione (equivalenza per nome) Due tipi si dicono equivalenti per nome sse hanno lo stesso nome un tipo è equivalente solo a se stesso Esempio T1 T2 T3 T4 = = = = 1..10; 1..10; int; int; sono tutti diversi e non equivalenti LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 55 / 88 Equivalenza per nome [. . . cont.] Osservazioni vincolo indebolito in alcuni linguaggi (PASCAL) nell’es. la ridenominazione genera alias e non nuovi tipi (caso di T3 e T4) Ogni def. di tipo in un solo punto: OK dal punto di vista ingegneristico Equivalenza relativa ad un programma, non in generale LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 56 / 88 Equivalenza strutturale Definizioni trasparenti: nome come abbreviazione del nuovo tipo definito conta la sostituzione dei nomi con le definizioni dei tipi Definizione (Equivalenza strutturale) Due tipi T1 e T2 sono strutturalmente equivalenti sse hanno lo stesso nome, oppure T1 è definito con type T1 = espressione; ed espressione rappresenta un tipo equivalente a T2, oppure T1 e T2 definiti applicando lo stesso costruttore di tipo a due tipi tra loro equivalenti LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 57 / 88 Equivalenza strutturale [. . . cont.] Esempi (pseudo-codice) equivalenza di T3 e T4 type type 3 type 4 type 1 2 T1 T2 T3 T4 = = = = int; char; struct { T1 a; T2 b; } struct { int a; char b; } equivalenti? type S = struct { int a; int b; } type T = struct { int n; int m; } 3 type U = struct { int m; int n; } 1 2 equivalenti ? (ricorsione) 1 2 type R1 = struct { int a; R2 p; } type R2 = struct { int a; R1 p; } Osservazioni LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 58 / 88 Equivalenza strutturale [. . . cont.] Equivalenza strutturale non legata al singolo programma Sostituzione sempre possibile: si parla di trasparenza referenziale I linguaggi spesso adottano regole di equivalenza miste LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 59 / 88 Compatibilità Il tipo T è compatibile con il tipo S sse un valore del tipo T è ammesso in qualsiasi contesto in cui sarebbe richiesto un valore di tipo S Compatibilità più debole dell’equivalenza Due tipi equivalenti sono sempre compatibili (ma non viceversa) Relazione riflessiva, transitiva ma non simmetrica es. char e int Relazione adottata da molti linguaggi nella disciplina dell’assegnamento: tra il tipo dell’espressione (RHS) e quello della variabile (LHS) nella disciplina del passaggio parametri LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 60 / 88 Compatibilità [. . . cont.] Gradi di compatibilità: T compatibile con S 1 T e S equivalenti 2 I valori di T costituiscono un sottoinsieme dei valori di S es. tipi intervallo 3 Tutte le operazioni per S sono ammissibili sui valori di T es. record e op. di selezione “.” type S = struct {int a;} type T = struct {int a; char b;} rel. di sottotipo (nei linguaggi ad oggetti) 4 I valori di T corrispondono canonicamente a certi valori di S int e float 5 I valori di T corrispondono ad alcuni valori di S, tramite una convenzione per la trasformazione da T a S float e int, tramite arrotondamento, troncamento, . . . LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 61 / 88 Conversione di tipo Conversione implicita: operata tacitamente dalla macchina astratta si chiama anche coercizione, o conversione forzata Conversione esplicita: indicata mediante costrutti linguistici nel sorgente del programma si chiama anche cast LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 62 / 88 Coercizioni Se T compatibile con S: valori di tipo T sono ammessi dov’è atteso un valore di tipo S Conversione operata dalla m. astratta (o dal compilatore) Implementazioni Stessa rappresentazione livello sintattico, nulla da aggiungere Compatibilità canonica codice di conversione (a run-time) aggiunto dalla m. astratta es. da int a float Corrispondenza arbitraria es. dominio di T sovrainsieme di quello di S la macchina astratta inserisce codice per la conversione (e controllo dinamico per la type safety) es.: T è int e S è un intervallo di interi LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 63 / 88 Conversioni esplicite Annotazioni nel linguaggio che specificano il tipo in cui trasformare un valore di un altro tipo S s = (S)t; Possibilità Indicazione sintattica Indicazione per la macchina astratta (come prima) Vantaggi In genere, possibile anche quando basterebbe la compatibilità Maggiore leggibilità Indipendenza dal contesto sintattico Utili ad overloading e polimorfismo LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 64 / 88 Polimorfismo Sistema di tipi monomorfo: ogni oggetto ha un solo tipo Sistema di tipi polimorfo: ogni oggetto può avere più tipi Casi di polimorfismo in molti linguaggi (anche datati) operatore + int x int -> int oppure float x float -> float funzione length: non dipende dal tipo di vettore Funzioni polimorfiche indipendenti da tipi specifici Es. ordinamento di vettori (di interi, caratteri, ecc.) con uso di tipi generici: void sort([] v) Tipologie: Polimorfismo ad hoc (overloading) Polimorfismo universale p. parametrico p. di sottotipo o inclusione LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 65 / 88 Polimorfismo [. . . cont.] Polimorfismo ad hoc: overloading Nome sovraccaricato quando vi corrispondono più oggetti L’informazione del contesto aiuta a decidere staticamente es. operatore + es. funzioni con ugual nome ma tipo e numero di parametri differente Polimorfismo apparente Legato ai nomi più che agli oggetti del linguaggio es. funzioni distinte / codice distinto Può essere gestito con una fase di pre-processing assegna un nome interno diverso ai nomi sovraccarichi Overloading 6= Coercizione es. + polimorfico 1 + 2, 1.0 + 2.0, LdP.ITPS/[email protected] 1 + 2.0, 1.0 + 2 Strutture Dati 9 mag, 2016 66 / 88 Polimorfismo [. . . cont.] Polimorfismo parametrico universale: un valore può assumere tanti tipi diversi, ottenuti per istanziazione di un unico schema universale Codice di gestione unico che lavora uniformemente le differenze non contano Istanziazione automatica: compilatore o macchina astratta in base al contesto LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 67 / 88 Polimorfismo [. . . cont.] Esempi p. universale Valore null vale per tutti i tipi puntatore (T*) Tipo indicabile con * void sort([] v) funzione di tipo []->void Funzione di swap() chiamata da sort() void swap(reference , reference ) e istanziazione int * k = null; char v,w; 3 int i,j; 4 ... 5 swap(v,w); 6 swap(i,j); 1 2 LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 68 / 88 Polimorfismo [. . . cont.] Polimorfismo parametrico universale p. esplicito annotazioni esplicite: Template C++, Generics JAVA 5.0+ p. implicito operato dal modulo di inferenza dei tipi Ling. di scripting Ling. funzionali: l’applicazione comporta istanziazione giusta es. fun Ide(x){return x;} è di tipo -> Funzioni di ordine superiore es. fun Comp(f,g,x){return f(g(x));} di tipo (( -> ) × ( -> ) × ) -> LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 69 / 88 Polimorfismo [. . . cont.] Non tutte le istanziazioni dello schema universale sono ammissibili, quindi: forma limitata tipica degli OOL una forma di compatibilità strutturale Nel p. universale di sottotipo: un valore può assumere una molteplicità di tipi diversi, ottenuti istanziando, in uno schema generale, un parametro con sottotipi di un tipo assegnato esprimibile tramite la notazione: ∀ S :< T.S -> void dove :< indica la rel. di sottotipo istanziabile con qualunque sottotipo S di T LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 70 / 88 Polimorfismo [. . . cont.] Implementazione gestione statica: a linking-time istanziazione funzioni polimorfe (in base ai tipi) produzione codice opportuno (più copie del template) e collegamento efficiente come per le funzioni non polimorfiche es. template C++ gestione dinamica: unica versione del codice generata rappresentazione più complessa: invece di allocare i dati sul RdA vengono allocati loro descrittori (dim., struttura, ind.) più flessibile ma meno efficiente a run-time es. in ML LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 71 / 88 Controllo di tipo Il controllo di tipo determina e controlla la compatibilità dei tipi degli oggetti: assegnazioni, dichiarazioni, uso parametri, conversioni, ... statico: modulo del compilatore (semantica statica) segue l’albero sintattico (bottom-up) determina e trasmette le informazioni sui tipi degli oggetti coinvolti dinamico: modulo di supporto al run-time LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 72 / 88 Inferenza di tipo Inferenza: deduzione dei tipi coinvolti in assenza di informazione esplicita spesso sostituisce il controllo di tipo es. in JAVASCRIPT, ML, . . . quando non si può determinare subito il tipo si utilizzano variabili di tipo: ’a es. fun f(n) { return n+1; } si può dedurre che f è di tipo int-> int caso difficile: fun g(v) { return v; } polimorfa LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 73 / 88 Inferenza di tipo [. . . cont.] Algoritmo: dato l’albero di derivazione assegnare un tipo/var. di tipo ad ogni nodo (anche variabile) risalire l’albero imponendo vincoli (uguaglianze di tipo) usare l’algoritmo di unificazione per risolvere i vincoli Esempio fun f(n) { return n+1; } ’a = int->int fun f ( ’z=int n ) { } return ’x n LdP.ITPS/[email protected] Strutture Dati + ; ’x = ’y = int 1 ’y 9 mag, 2016 74 / 88 Agenda Relazioni fra tipi 4 1 Tipi e sistemi di tipi 5 2 Tipi scalari 3 Tipi Composti LdP.ITPS/[email protected] Strutture dati e gestione della memoria Dangling reference Garbage collection Strutture Dati 9 mag, 2016 75 / 88 Dangling reference Esempio 1 2 int *p = malloc(); int *q = malloc(); 3 4 5 *p = 123; *q = 321; 6 7 q=p; 8 9 free(p); 10 11 LdP.ITPS/[email protected] // q dangling reference! Strutture Dati 9 mag, 2016 76 / 88 Dangling reference - tombstone Si aggiunge un livello di indirizzamento indiretto, quello della tombstone allocazione di nuovo oggetto su heap/pila: crea tombstone copia tra puntatori: copia indirizzi di tombstone deallocazione (da heap/pila): inserimento valore nullo speciale LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 77 / 88 Dangling reference - tombstone [. . . cont.] q = p; free(p); p 123 123 q 321 321 RIP p = malloc(); q = malloc(); *p = 123; *q = 321; 321 Osservazioni spazio: memoria aggiuntiva cimitero: zona di memoria speciale per le tombstone riuso delle tombstone (garbage collection) tempo: doppia dereferenziazione eventualmente + garbage collection LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 78 / 88 Dangling reference – locks & keys lucchetto parola in memoria inizializzata con valore casuale associata all’oggetto allocato chiave parola in memoria corrispondente ad un lucchetto puntatore = indirizzo + chiave allocazione di nuovo oggetto su heap: crea lucchetto copia tra puntatori: copia di indirizzo e chiave dereferenziazione: controllo che la chiave del puntatore “apra” il lucchetto (abbia lo stesso valore) deallocazione: inserimento valore nullo speciale nel lucchetto LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 79 / 88 Dangling reference – locks & keys [. . . cont.] p = malloc(); q = malloc(); *p = 123; *q = 321; p q = p; free(p); 54321 123 54321 54321 123 54321 54321 0 12345 321 12345 54321 321 12345 54321 321 12345 q Osservazioni spazio: memoria aggiuntiva tempo : op. più efficienti che con il tombstone deallocazione automatica della mem. aggiuntiva LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 80 / 88 Garbage collection Deallocazione implicita GC: Storia dei LdP LISP ’60 −→ JAVA ’90 Fasi (non necessariamente separate) distinguere gli oggetti utilizzati dagli altri per sicurezza politica conservativa recuperare la memoria degli oggetti non utilizzati Classificazione dei GC contatori di riferimenti marcatura mark & sweep mark & compact copia LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 81 / 88 Garbage collection – contatori Un contatore (reference count) per ogni oggetto; solo per la m. astratta: inaccessibile al programmatore allocazione: inizializza il contatore a 1 assegnazione q = p; (o anche quando si esce da un ambiente locale con puntatori) incremento del contatore della var. puntata da p decremento del contatore della var. puntata da q deallocazione: quando un contatore raggiunge il valore 0 si può deallocare la memoria e restituirla alla lista libera se l’oggetto da deallocare contiene puntatori applica la procedura ricorsivamente Osservazioni vantaggi: semplicità e incrementalità svantaggi: inefficienza; GC non funziona con str. circolari LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 82 / 88 Garbage collection – mark & sweep mark marcatura oggetti “non in uso” attraversando l’heap a partire dai puntatori sulla pila (root set), visita in ampiezza/profondità degli oggetti referenziati, lungo gli archi rappresentati dai puntatori, etichettando gli oggetti attraversati come “in uso” sweep deallocazione degli oggetti marcati come “non in uso” Osservazioni (svantaggi) non incrementale: parte quando la memoria si sta esaurendo frammentazione esterna inefficiente: tempo proporzionale alla dim. dell’heap sfavorisce la località dei riferimenti in memoria LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 83 / 88 Garbage collection – pointer reversal Per visitare agevolmente strutture concatenate (es. alberi) in fase di deallocazione occorre uno stack (ricorsione) Con il rovesciamento dei puntatori basta ricordare il nodo corrente e quello precedente A B C / F / / B p.prec C D / / corrente E / / LdP.ITPS/[email protected] A stack: A B C Strutture Dati / F / / D / p.corr E / / 9 mag, 2016 84 / 88 Garbage collection – mark & compact Problema della frammentazione causato dal mark & sweep Fase di sweep =⇒ fase di compattamento oggetti spostati in zone di mem. contigue più passaggi necessari Osservazioni svantaggi più passaggi necessari: marcatura calcolo nuovi puntatori, spostamento, ... vantaggi no frammentazione località dei riferimenti lista libera monoblocco LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 85 / 88 Garbage collection – copia No fase marcatura: copia (e compattazione) dei blocchi vivi GC stop & copy: heap diviso in 2 semispazi (FromSpace,ToSpace) normalmente solo 1 in uso (FromSpace); memoria libera = unico blocco memoria esaurita: chiamata al GC a partire dal root set si copia (alg. di Cheney) nell’altro semispazio (toSpace), compattando quindi ToSpace e FromSpace si scambiano i ruoli Osservazioni vantaggi allocazione efficiente: soprattutto se è noto il fabbisogno degli oggetti vivi contemporaneamente no frammentazione LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 86 / 88 ToSpace FromSpace Garbage collection – copia [. . . cont.] root set ToSpace FromSpace root set libera LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 87 / 88 Riferimenti Gabbrielli & Martini: Linguaggi di Programmazione, McGraw-Hill. 2a edizione. Cap. 10 LdP.ITPS/[email protected] Strutture Dati 9 mag, 2016 88 / 88