===================== PUNTATORI (IN PASCAL) ===================== PREMESSA: UN MONDO SENZA PUNTATORI Nei linguaggi di programmazione (Pascal) abbiamo: - tipi base non strutturati (predefiniti): interi, booleani, caratteri,... - costruttori di tipi composti, che permettono la costruzione di tipi strutturati user-defined: array, record,... Supponiamo per ora di non avere puntatori. Con questi ingredienti possiamo avere solo tipi statici: la dimensione di un valore di tipo statico e' fissata, uguale per tutti, nota a compile time. Dichiarazione di variabile: var x: T; {T tipo statico} Il compilatore sa gia' quanta memoria serve a contenere il valore di x, qualunque esso sara' durante l'esecuzione. L'allocazione delle variabili dichiarate e' fatta a compile time. PERCHE' I PUNTATORI Necessita' di rappresentare tipi dove la dimensione e la struttura di un oggetto non e' prefissata. La quantita' di memoria necessaria per il contenuto di una variabile non e' nota a compile time, e puo' variare dinamicamente durante l'esecuzione; - sequenze di elementi di lunghezza non prefissata (liste nelle molte varianti...) - alberi - grafi .... Il compilatore non puo' allocare memoria a compile time, perche' non sa quanta ne servira', e perche' la quantita' di memoria necessaria varia a run-time. Si possono usare strutture statiche (es. vedremo liste con array), ma bisogna aver fissato dimensione max degli oggetti e si spreca della memoria (che viene allocata ma non utilizzzata). Soluzione migliore: Allocazione dimanica della memoria. Memoria allocata a run-time, quanta ne serve, accresciuta o diminuita nel tempo a seconda delle necessita'. Nei linguaggi tipo Pascal, la possibilita' di allocazione dinamica e' associata all'uso di un nuovo strumento per accedere ai dati: il puntatore. PUNTATORI I valori di un tipo puntatore sono indirizzi di locazioni in memoria. Concettualmente, gli indirizzi sono non tipati. Nei linguaggi ad alto livello (es. Pascal, diversamente da Assembler), un tipo puntatore e' legato ad un tipo base. DICHIARAZIONI DI TIPI PUNTATORI La dichiarazione di tipo: type TPTR = ^T; (dove T per ora possiamo pensarlo un tipo statico) dichiara un nuovo tipo puntatore TPTR dove i valori di tipo TPTR sono indirizzi di locazioni di tipo T, locazioni atte a contenere valori di tipo T. Sapere il tipo dell'oggetto puntato permette di sapere - la dimensione della cella puntata (e quindi la quantita' di memoria da allocare quando viene richiesta l'allocazione dinamica) - quali operazioni sono lecite sull'oggetto puntato (permette verifica di correttezza statica, consistenza dei tipi) E' una restrizione, ma permette un maggiore controllo di correttezza. Nella dichiarazione type TPTR = ^T; "^" e' un costruttore di tipo (parola chiave del linguaggio), come "array", "record". In Pascal, se ho type TPTR = ^T; var p1: TPTR; p2: ^T; { abbrevia dichiarazione di tipo e dichiarazione di variabile } risulta che p1 e p2 hanno tipi fra loro incompatibili. Differenza tra: var x: T; x e' una variabile di tipo T. x e' un nome simbolico che sta per l'indirizzo di una locazione di tipo T. Il contenuto di x e' un valore di tipo T. La memoria per x (= la locazione di tipo T il cui indirizzo e' x) viene allocata staticamente dal compilatore. var p: TPTR; p e' una variabile di tipo TPTR (puntatore a T). p e' un nome simbolico che sta per l'indirizzo di una locazione di tipo TPTR, ovvero una locazione che puo' ospitare indirizzi di locazioni di tipo T (le quali a loro volta potranno contenere valori di tipo T). La memoria per p (= la locazione di tipo TPTR il cui indirizzo e' p e che conterra' indirizzi di locazioni di tipo T) viene allocata staticamente dal compilatore. Le locazioni di tipo T il cui indirizzo sara' posto in p saranno allocare dinamicamente a run-time. L'oggetto puntato da una variabile di tipo puntatore a T e' una variabile di tipo T. Esistono dunque due tipi di variabili: - variabili statiche: dichiarate con var x: T; (T tipo qualsiasi, anche puntatore) allocate staticamente e accedute per nome. - variabili dinamiche: non dichiarate, allocate dinamicamente e accedute tramite puntatori. OPERATORE DI DEREFERENZIAZIONE Su tutti i tipi (base e strutturati) di un linguaggio vi sono operatori: - op. aritmetici sugli interi - op. [] (selezione di una componente) sui tipi costruiti con array - op. "." (selezione di una componente) sui tipi costruiti con record Sui tipi puntatori ho operarore di dereferenziazione: Se ho dichiarato var p: TPTR; l'espressione p^ denota una variabile di tipo T, l'oggetto puntato da p. ("^" postfisso e' operatore di dereferenziazione). Non esiste in Pascal un operatore del tipo "indirizzo di": Se ho dichiarato var x: T; non esiste un'espressione del tipo "indirizzo di" x con valore un puntatore di tipo TPTR. Questo fa si' che le variabili dichiarate (statiche) e quelle accedute tramite puntatori (dinamiche) siano due insiemi disgiunti. (differenza col C). OPERATORI DI CONFRONTO In Pascal, gli unici operatori di confronto validi su puntatori sono = e <> Controllo se due puntatori contengono lo stesso indirizzo (puntano alla stessa locazione) o indirizzi diversi. Agli indirizzi non si applicano le operazioni aritmetiche degli interi. COSTANTE DI TIPO PUNTATORE Esiste un'unico valore costante nil di tipo puntatore (per qualunque tipo base), che denota indirizzo nullo. p:= nil; p non punta a nessuna locazione, non vi e' memoria allocata per la cella puntata da p. Non accedere a p^ se p=nil. ALLOCAZIONE / DEALLOCAZIONE Dichiarazione var p: TPTR; staticamente il compilatore alloca a p memoria sufficiente a contenere un indirizzo di tipo T. Istruzione new(p); Dinamicamente, alloca in memoria una nuova locazione di tipo T e ne pone l'indirizzo in p. p e' il riferimento per accedere alla nuova cella: alla nuova cella accedo con p^. La memoria viene allocata per l'oggetto puntato e non per il puntatore p, che e' una variabile statica, come tutte le variabili dichiarate. La variabile dinamica e' p^. Dopo fatto new(p); posso accedere a p^. Istruzione dispose(p); Libera la cella di memoria di tipo T puntata da p. Dopo fatto dispose(p); non posso accedere a p^. Non fare dispose(p) se p=nil. GESTIONE DEGLI ERRORI Nei casi di uso sbagliato dei puntatori (accesso a p^ con p^ non allocato o deallocato ....) non sempre viene segnalato errore a run-time. Spesso l'esecuzione continua ma gli effetti possono essere imprevedibili (e rovinosi). ESEMPIO DI SITUAZIONI IN CUI POSSO AVERE EFFETTI IMPREVISTI type TPTR = ^T; var p: TPTR; . { situazione (A) } . new(p); . . dispose(p); . { situazione (B) } . Situazione (A): p dichiarato ma non allocato (ne' posto=nil). Analogia con var n: integer; .... prima di x:=... Pascal inizializza per default tutti gli interi a zero. In altri linguaggi, n contiene un valore casuale. Alcune implementazioni inizializzano per default tutti i puntatori a nil; in altre, p contiene un valore casuale, molto piu' pericoloso in quanto interpretato come indirizzo di memoria. Non accedere p^ prima di aver inizializzato p! p non inizializzato puo' puntare ovunque (nell'area dati, in locazioni non allocate o in locazioni di altre variabili, nell'area codice ...). Non viene segnalato errore, ma gli effetti possono essere rovinosi. Situazione (B): p dopo dispose. La locazione puntata da p e' stata resa disponibile per essere allocata di nuovo. Puo' essere allocata per altre variabili dinamiche anche di tipo diverso. Accedere a p^ con p^ deallocato puo' voler dire accedere a memoria che ora contiene valori di altre variabili, anche ti tipo diverso (che attraverso p^ vengono interpretati come di tipo T), con risultati inaspettati. Non sempre viene segnalato errore, ma porta effetti imprevedibili. ASSEGNAZIONI DI PUNTATORI Se ho var p, q: TPTR; Differenza tra: p^:=q^; copia nella cella puntata da p il contenuto di quella puntata da q p:=q; crea aliasing; fa si' che p e q puntino alla stessa cella ALIASING Aliasing = quando due puntatori p e q puntano alla stessa cella (contengono lo stesso indirizzo, vale p=q). Es. dopo p:= q; Senza puntatori non ho aliasing perche' ad ogni variabile statica il compilatore alloca una cella di memoria distinta. L'unico caso in cui ho aliasing senza puntatori e' nel passaggio di parametri per riferimento: var n: integer; {globale} procedure pr(var a: integer); begin ... body della procedura vede sia n che a ... end; begin {program} n:=3; pr(n); end. Dentro la chiamata pr(n) a e n denotano la stessa locazione. Senza puntatori aliasing e' fenomeno locale a dentro la procedura, non ho aliasing a top level. Aliasing e' strumento potente, ma porta rischi se usato male. SIDE EFFECT La modifica del contenuto di una variabile si ripercuote sul contenuto di un'altra. Fenomeno collegato all'aliasing (sia con puntatori che senza). Esempio senza puntatori: var n: integer; {globale} procedure pr(var a,b: integer); begin a:=a+1; b:=b+1; end; begin {program} n:=3; pr(n,n); {n e' stato incrementato di due!!} end. Esempio con puntatori: type intPTR = ^integer; var p, q: intPTR; . . . p^:=3; q^:=5; p:=q; q^:=7; {anche p^ vale 7!!} Comportamento diverso da quello che avrei usando anziche' p^ e q^ due variabili x,y: integer. GARBAGE Memoria allocata che resta non piu' accessibile (sprecata) perche' non esistono piu' riferimenti ad essa. Es: new(p); p:=q; {o anche se eseguo new(p) un'alta volta} Dovevo fare: - new(p); dispose(p); p:=q; ossia liberarla, se non mi serviva piu' la cella puntata, oppure - new(p); t:=p; p:=q; ossia salvare il riferimento alla cella, se mi serviva ancora. DANGLING REFERENCE Puntatore che punta a cella non allocata o deallocata. Es: p:=q; dispose(q); uso p^... Quando si dealloca un puntatore e' facile dimenticare che altri fanno aliasing con esso! In questi casi, alcune implementazioni segnalano errore se accedo a q^ (altre comunque no) ma nessuna implementazione segnala errore se accedo a p^. Per evitare problemi di garbage e dangling reference alcuni linguaggi non hanno dispose da programma ma garbage collection automatica. PASSAGGIO PARAMETRI Quando un puntatore e' passato per valore, l'oggetto puntato e' passato per riferimento. In effetti io passo il puntatore, che e' un riferimento all'oggetto puntato. type intptr = ^integer; var p,q: intPTR; procedure pr(x: intPTR); begin x^:=6; x:=q; end; begin new(p); new(q); p^:=4; q^:=2; pr(p); {all'uscita p e q sono distinti, ma p^=6} end. RIEPILOGO ASPETTI A CUI FARE ATTENZIONE NELL'USO DEI PUNTATORI - aliasing e side effect: attenzione a non crearli se non voluti. - passaggio parametri: ricordare che il puntato e' sempre passato per riferimento. - creazione di garbage: meglio evitare perche' spreco memoria, ma non molto dannoso. - dangling reference: pericoloso! evitare assolutamente. RACCOMANDAZIONE GENERALE Puntatori sono tecnica di programmazione di basso livello (manipolazione esplicita di indirizzi di memoria). Sono presenti in linguaggi di alto livello come Pascal per permettere di costruire strutture dati di alto livello non realizzabili efficientemente con tipi statici. Non usarli a sproposito!