Corso di Linguaggi di Programmazione - Lezione...

Corso di Linguaggi di ProgrammazioneLezione 7

Chiara [email protected]

Dipartimento di Tecnologie dell’InformazioneUniversità degli Studi di Milano

19 Marzo 2007

C. Braghin e A. Ceselli, DTI – Univ. di Milano Corso di Linguaggi di Programmazione

Tipo di dato

DefinitionIn un linguaggio di programmazione, un tipo di dato (osemplicemente tipo) è un nome che indica l’insieme di valoriomogenei che una variabile, o il risultato di un’espressione,possono assumere, e le operazioni che manipolano tali valori.

L’insieme dei valori ha una cardinalità finita.Un tipo è caratterizzato da un nome e dalla sintassi delladichiarazione di tipo.

Es.: in C, la definizione int x; indica che x può assumerecome valori solo numeri interi (appartenenti ad un certointervallo) e che su tali valori sono ammesse solo certeoperazioni.


Classificazioni del processo di tipizzazione (1)

Statico vs dinamicoFa riferimento al tempo del binding tipo-variabile.

- la tipizzazione è statica quando a una variabile vieneassociato rigidamente in fase di compilazione un tipo cherimane lo stesso durante tutta l’esecuzione.

- la tipizzazione è dinamica quando una variabile puòcambiare tipo durante l’esecuzione a seconda del tipodell’espressione che le viene assegnata.

Esplicito vs implicitoFa riferimento al modo in cui le annotazioni o dichiarazionidi tipo vengono generate, se specificate esplicitamente dalprogrammatore, o dedotte automaticamente dalcompilatore.


Classificazioni del processo di tipizzazione (2)

Forte vs DeboleFa riferimento alle regole imposte dal linguaggio sull’utilizzodei tipi: possono essere rigide (forti) ed impedire qualsiasiuso dei dati incoerente con il tipo specificato in fase didichiarazione, in caso contrario la tipizzazione è debole.

Sicuro vs InsicuroUn linguaggio type safe garantisce che tutti gli errori di tipo(errori dovuti ad un uso scorretto dei valori che una variabilepuò assumere) sono catturati, ma non necessariamentedurante la compilazione (un programma potrebbe falliredurante l’esecuzione a causa di violazioni di tipo).Linguaggi che permettono aritmetica dei puntatori nonpossono essere type safe.Un linguaggio debole non è necessariamente insicuro, inquanto il controllo viene semplicemente ritardato in fase diesecuzione (e.g., Perl).


Svantaggi della tipizzazione dinamica

Permette la cattura di errori di tipo solo durantel’esecuzione del programma.

Es.: (in pseudo-codice, L# indica la linea)L1 var x = 5;L2 var y = "test";L3 var z = x + y;

In un linguaggio con tipizzazione dinamica, solo in fase diesecuzione viene segnalato un errore quando si cerca dieseguire l’istruzione alla linea L3.

L’implementazione è più costosa:maggiore tempo di esecuzione perché il controllo dei tipideve venire fatto durante l’esecuzione del programmamaggior utilizzo della memoria perché si deve tenerememoria del tipo delle variabili durante l’esecuzione delprogramma.


Linguaggio Fortemente Tipato

In genere, un linguaggio di programmazione si considerafortemente tipato (strongly typed) se:

- Utilizza tipizzazione staticai tipi delle variabili sono fissati in fase di compilazione e nonsono modificabili.

- Impedisce qualsiasi uso dei dati incoerente con il tipospecificato in fase di dichiarazione (i.e., impossibilità diconversione di tipi)

a volte la conversione esplicita (casting) è permessa,mentre quella implicita (coercion) no.

Impedisce di evadere il sistema di tipi.Questo permette di avere una garanzia piuttosto forte sulcomportamento del programma in fase di esecuzione.


Combinazioni di Tipizzazioni

Linguaggio Statico / Dinamico Strong / Weak SafetyAda statico strong sicuroC statico weak insicuroC++ statico strong insicuroJava statico strong sicuroPascal statico strong sicuroLisp dinamico strong sicuroML dinamico strong sicuroJavaScript dinamico weak sicuroPerl dinamico weak sicuroPHP dinamico weak sicuroPython dinamico strong sicuroRuby dinamico strong sicuro


TipizzazioneEsempi nei vari linguaggi (1)

Linguaggi a tipizzazione statica:Ada, C, C++, Java, Fortran: tipizzazione esplicitaPerl, JavaScript, ML: tipizzazione implicita

in Perl, ogni nome che inizia con $ può contenere unastringa o un valore numericoin ML, la definizione fun square(x): real = x * x; ècorretta.

di norma vengono compilati (i tipi sono importanti anche infase di ottimizzazione del codice).

Linguaggi a tipizzazione dinamica:Lisp, Scheme, Python, Perl, Ruby, JavaScript, PHPla maggior parte dei linguaggi di scripting o di svilupporapido sono di solito a tipizzazione dinamicadi norma vengono interpretati.



Linguaggio debolmente tipato: Perlprint “2” + 4; in Perl stampa a video 6 poiché vienefatta una conversione implicita

Linguaggio debolmente tipato e unsafe: C vs C++char* buf = malloc(20); viene compilata in C senzaproblemi, ma genera un errore in C++ perché mallocritorna un valore di tipo void* e il C++ richiede unaconversione esplicita (cast).a difesa del C va detto che è volutamente unsafe per motividi efficienza.

Linguaggio fortemente tipato ma unsafe: C++Quando viene eseguito il seguente programma (che passasenza problemi la fase di compilazione), va in crash.int* p = 0;

*p = 5;



Classifica di linguaggi fortemente tipati:OCaml, Haskell:

non permettono alcuna conversione di tipo implicita(coercion)

Ada:non permette alcuna conversione di tipo implicita, ma ha lapossibilità di sospendere temporaneamente il controllo ditipo.

Java, C#permettono alcuni tipi di casting, e coercion nel caso dioperatori aritmeticiEs.: l’istruzione x = 3 ∗ 1.5; è valida, in quantol’espressione intera viene convertita in floating-point.


Classificazione di Tipi

A seconda della loro struttura:- semplici o primitivi: tipi che non possono essere

decomposti;- strutturati: tipi ottenuti dai tipi semplici mediante operatori

forniti dal linguaggio.A secondo di chi li definisce:

- predefiniti: insieme di tipi predefiniti dal linguaggio;- definiti dall’utente: definiti mediante l’utilizzo di operatori

forniti dal linguaggio.

Nota beneLe due classificazioni non sono perfettamente sovrapponibili:non tutti i tipi predefiniti dal linguaggio sono primitivi.Es.: le strinche in C sono tipi derivati ma predefiniti dallinguaggio.


Tipi e Linguaggi

Ogni linguaggio definisce accuratamente i tipi che permette digestire, associando agli stessi:

un insieme di operazioni ammessel’insieme di operazioni ammesse dipende dal linguaggio(vedi operazioni su stringhe)

un ordinamento totale (facoltativo)scalare

una codifica, spesso dipendente dalla macchinadecisa dall’implementatore e a seconda della macchinainsieme di regole che permette di tradurre ogni valore inuna stringa di bit (complemento a 1, complemento a 2,floating, ...)viene ignorata dal programmatore


Tipi nei vari linguaggi (1)

Tipo Booleanovalori: prevede 2 soli valori, vero o falso, utilizzatisoprattutto nelle espressioni condizionalioperazioni: congiunzione (and), disgiunzione (or),negazione (not), uguaglianzainvece che memorizzarlo in un singolo bit, per motivi diefficienza si usa un byte (unità minima di memoria)in altri linguaggio, 0 indica falso; valori maggiori di 0 vero

Tipi Numerici (Interi o Reali)valori: a differenza degli insiemi matematici cherappresentano, includono un massimo e un minimo numerorappresentabile dovendo essere contenuti in una parola dimemoriaoperazioni: operazioni aritmetiche e confronti (somma,differenza, prodotto, divisione, resto)alcuni degli operatori possono venire usati sia da tipi interiche reali (operatori overloaded)



Record (o Strutture)valori: usato per mantenere informazioni eterogeneecorrelate

- ogni campo è caratterizzato dal suo nome e dal suo tipo(anche diverso da quello degli altri campi

operazioni: ciascun campo può essere acceduto in modoindipendente mediante l’operatore di selezione (.)

Arrayvalori: collezione finita di elementi dello stesso tipo (tipobase), indicizzata su un intervallo di tipo ordinale (tipoindice)operazioni: selezione, assegnamento, uguaglianza

si indica, spesso tra quadre, un’espressione il cui valoreindica l’indice dell’elemento da selezionare (Es.:array [< expr >]).



Caratteri e Stringheil tipo carattere tradotto con la codifica ASCII o Unicodela stringa non sempre è predefinita nel linguaggio

operazioni: operazioni per la concatenazione, la selezione diuna sottostringa di una stringa data, ecc.nei linguaggi di scripting anche operatori per il patternmatching


Equivalenza di Tipi

Stabilire quando due tipi, formalmente diversi, sonointercambiabili, ossia non distinguibili nel loro uso.

Equivalenza per nomeDue tipi sono equivalenti se e solo se hanno lo stessonome (sono lo stesso tipo)Es.: T1 = int e T2 = int sono diversiFacile da implementare ma molto restrittivaIndebolita in alcuni linguaggi: la ridenominazione (T3 e T4)genera alias e non nuovi tipi

Equivalenza strutturaleDue tipi sono equivalenti se e solo se hanno la stessastruttura (dichiarazioni equivalenti)Più flessibile, ma più complicata da implementare(specialmente per tipi ricorsivi).Problema: nel caso di strutture, si confronta solo il tipo deicampi o anche il loro nome? E l’ordine in cui compaiono?


Equivalenza di TipiEsempi

C, C++ utilizzano la versione indebolita dell’equivalenzaper nome nel caso di un unico file, mentre l’equivalenzastrutturale nel caso di file compilati separatemente

- struct e union creano sempre un nuovo tipo che non èequivalente con nessun altro tipo.

Es.: (in pseudo-codice)type T1 = int;type T2 = char;type T3 = struct { T1 a; T2 b; }type T4 = struct { T1 a; T2 b; }


Compatibilità di Tipi

DefinitionIl tipo T è compatibile con il tipo S sse un valore del tipo T èammesso in qualsiasi contesto in cui sarebbe richiesto unvalore di tipo S.

Ogni linguaggio definisce le regole di compatibilità traoggetti di tipo differente, che vengono adottate nelladisciplina dell’assegnazione, delle operazioni aritmetiche edel passaggio dei parametri.Compatibilità più debole dell’equivalenza:

Due tipi equivalenti sono sempre compatibili, ma nonviceversa.Relazione riflessiva, transitiva, ma non simmetrica.


Conversione di Tipo

Conversione implicita (coercion)operata in fase di compilazione del programmaindebolisce il meccanismo di verifica dei tipiin quasi tutti i linguaggi capita se si esegue un’operazionetra tipi numerici diversi.

Conversione esplicita (cast)indicata mediante costrutti linguistici nel sorgente delprogramma.


Inferenza di Tipo

Il tipo di un’espressione è dedotto senza richiedere alprogrammatore di specificare il tipo delle variabili.Quando non si può determinare subito il tipo, si utilizza unavariabile di tipo.Es.: data la seguente istruzionefun(n) {return n+1;}

si può dedurre che f è di tipo int -> int


Sistema di tipo di un linguaggio di programmazione

Complesso delle informazioni e delle regole che governano itipi di un linguaggio:

Insieme dei tipi predefinitiCostrutti per definire nuovi tipiMeccanismi per il controllo dei tipi:

Regole di equivalenza: due tipi formalmente diversipossono essere equivalenti a livello semantico;Regole di compatibilità: un valore di un tipo diverso daquello atteso può comunque essere utilizzato;Regole di inferenza attribuzione di un tipo adun’espressione complessa.

Lista (possibilmente vuota) di vincoli da controllarestaticamente o dinamicamente.


Cosa servono i tipi durante l’analisi semantica?


Obiettivi dell’analisi semantica

Controllo di tipoControllare che gli identificatori siano stati dichiarati primadi essere usati

come supporto a questa fase viene creata una tabella deisimboli (symbol table) che contiene informazioni su tutti glielementi simbolici incontrati quali nome, scope, tipo (sepresente) etc.il risultato di questa fase è l’albero di sintassi astratta (AST).


Descrittore di Tipo

Un descrittore di tipo è una struttura dati che contiene tutte leinformazioni necessarie a definire il tipo:

se il tipo è statico, serve solo al compilatorese il tipo è dinamico, una sua parte può servire per icontrolli durante l’esecuzione (es. controllo sugli indici diun vettore dinamico).


Controllo sui Tipi

Determina e controlla la compatibilità dei tipi degli oggetti:assegnazioni, dichiarazioni, uso parametri, conversioni, ...Il controllo avviene rispetto alle regole di tipo definite dalparticolare linguaggioTipo di controllo:

statico: avviene in fase di compilazione- segue l’albero sintattico (bottom-up)- determina e trasmette le informazioni sui tipi degli oggetti

coinvoltidinamico: modulo di supporto a run-time

- pesante dal punto di vista prestazionale- tipico dei linguaggi interpretati


Polimorfismo

Sistema di Tipi:monomorfo: ogni oggetto di un linguaggio ha un solo tipopolimorfo: ogni oggetto può avere più tipi

- Esempi di polimorfismo in linguaggi anche datati:- l’operatore +- la funzione length

- nel caso di linguaggi con sottotipi, una variabile di unsottotipo può comparire al posto di una variabile delsupertipo.

... To Be Continued


Corso di Linguaggi di Programmazione - Lezione...

Documents

Transcript of Corso di Linguaggi di Programmazione - Lezione...