Lezione 5 - Tipi di dati - Intranet DEIBhome.deib.polimi.it/comai/info3/File/Lezione 5 - Tipi di...

Politecnico di Milano - Prof. Sara Comai 1

LEZIONE 5: Tipi di dati

• Modulo 1: Tipi e costruttori di tipo• Modulo 2: Tipi definiti dall’utente e tipi di dati

astratti• Modulo 3: Sistemi di tipi

Informatica 3


Lezione 5 - Modulo 1

Tipi e costruttori di tipo

Informatica 3


Introduzione

• I dati di un linguaggio di programmazione vengono organizzati attraverso il concetto di tipo– Il tipo di un dato specifica i valori che una variabile di quel

tipo può assumere e le operazioni ammissibili

• I linguaggi offrono: – Tipi di dati predefiniti dal sistema– Costruttori di tipo (dati aggregati)– Tipi definiti dall’utente – Tipi di dati astratti


Tipi predefiniti

• Tutti i linguaggi di programmazione offrono un insieme di tipi predefiniti– Booleani– Caratteri– Interi– Reali

• Permettono di: – Classificare i dati manipolati da un programma– Proteggere i dati da operazioni illegali

Definiscono un insieme di valori e le operazioni che si possono compiere su di essi

Tipi predefiniti in C++:

char, float, double, int, void


Vantaggi

• Vantaggi dei tipi predefiniti: – Nascondere la rappresentazione sottostante

• Non si può accedere direttamente alla stringa di bit (nome dell’entità del tipo)

• Occorre applicare delle operazioni• Migliora la leggibilità del codice• Rende l’implementazione dei tipi modificabile

maggiore portabilità– Verificare il corretto uso delle variabili a tempo di

compilazione (se il tipo è noto)• Migliora l’affidabilità del codice• Non consente di verificare tutti i tipi di errore

x=i/j; non può verificare se j!=0– Fare l’overloading degli operatori a tempo di compilazione

Es. int i,j,k; i=j+k; //operatore + tra interi


Tipi primitivi

• Tipi primitivi: – Non sono costruiti a partire da altri tipi– I loro valori sono atomici e non possono essere

decomposti

– Spesso coincidono con i tipi predefiniti, salvo eccezioni (es. caratteri e stringhe in Ada)

• Si possono costruire nuovi tipi primitivi– Si definiscono i valori del nuovo tipo– Operazioni: dipendono dal linguaggio

• Esempio: tipo enumerativo


Tipo enumerativo

• Tipo ordinale i cui valori sono definiti dall'utente• Le uniche operazioni ammesse sono quelle valide per tutti gli

ordinali (:=, <>,=, <, >, ... , ORD, DEC, INC, ..)

Esempio: enum colore {bianco, giallo, rosso, verde, blu};

colore MioColore=giallo;switch(MioColore)

{case bianco: ...}

NB: l'ordine tra gli elementi è quello in cui sono dichiarati (se non si specificano valori): bianco < giallo < rosso < verde < blu

0 1 2 3 4


Aggregati

• Dai tipi primitivi: tipi aggregati

• Aggregato: – Ha un nome– Può aggregare oggetti omogenei o disomogenei– Permette operazioni sull’intero oggetto oppure sui

suoi componenti, selezionandoli


Costruttori di aggregati

• Prodotto cartesiano: – A1 x A2 x … x An tuple ordinate (c1,c2,…,cn), con ci ∈ Ai

• Esempi:– Numero complesso: (parte reale, parte immaginaria) --> float x float– Punto: (x,y) --> int x int oppure float x float

• Esempi di costruttori: – Struct, record ecc.

struct complesso {float reale;float immag;

};complesso num; num.reale



• Mapping finito: – Mapping: dominio codominio

• Esempi di costruttore: – Routine– Array

int vett[10]; definisce un mapping dai valori 0..9 all’insieme degli interi

indicizzazionevett[5]=0;

– C++:• Indici non nel dominio specificato• Indici compresi tra 0 e N-1 (in altri linguaggi anche altri

intervalli)• Non si possono specificare slicing (es. vett[1..3])



• Union– Il tipo viene specificato come un insieme disgiunto

di campi

• Esempio di costruttore:

union indirizzo {short int offset; long unsigned ind_assoluto;

};

mutuamenteesclusivi



• Ricorsione: – Per definire aggregati la cui dimensione cresce

arbitrariamente e la cui struttura ha complessità arbitraria

– Tramite puntatori: un componente viene definito come puntatore all’oggetto

• Esempio di costruttore: struct nodo {

int numero;nodo* succ;

};



Tipi definiti dall’utente e tipi di dati astratti

Informatica 3


Tipi definiti dall’utente

• tipo semplice o aggregato a cui è associato un nome scelto dall'utente

enum bool {FALSE, TRUE};bool b;

struct complesso{float parte_intera;float parte_immaginaria;

};

complesso numero;

Nome del tipo

Dichiarazionevariabile


Tipi definiti dall’utente

• Vantaggi: – leggibilità– modificabilità– fattorizzazione– espressione (limitata) della semantica di una

variabile

• Problemi: – il nuovo tipo non è protetto da operazioni illegali– rapprsentazione interna visibile


Tipo di dato astratto

• Tipo di dato astratto (abstract data type – ADT):

– Tipo di dato (insieme di valori e collezione di operazioni su tali valori) accessibile solo attraverso un’interfaccia

• Consente di scrivere programmi per mezzo di astrazioni di alto livello– Si tengono distinte le trasformazioni concettuali operate sui dati

dalla strutturazione dei dati e dalle specifiche implementazionialgoritmiche

– Meccanismi astratti per applicazioni specifiche utili per risolvere problemi in svariati domini applicativi


Tipo di dato astratto in C++

In C++: costrutto class• Estensione di una struct in cui i campi possono essere

dati oppure routine• Solo alcuni dati/routine sono accessibili – altri sono

nascosti– Parti pubblica e privata della classe– La dichiarazione delle funzioni pubbliche formano la sua

interfaccia


Esempio: pila

• Esempio: il tipo di dato PILA (STACK)• Descrizione: una pila é un ADT in cui é

possibile– inserire un elemento (PUSH)

• La push aumenta la dimensione della pila di 1

– rimuovere l'ultimo elemento inserito (POP)• La pop decrementa la dimensione della pila di 1

• Politica LIFO (Last In First Out)

push

pop


Esempio in C++

class stack_of_char{public:

stack_of_char(int size);~stack_of_char();void push(char c);char pop();int empty() const;...

private: // codice dipendente// dall’implementazione

}

Operazioni che si possono applicare al nuovo tipo

stack_of_char pila(10);pila.push(‘a’);pila.push(‘b’);char c=pila.pop();if(pila.empty())

{…}...

a

push


Esempio in C++




}



{…}...

ab

push


Esempio in C++




}



{…}...

a

pop

b


ADT generici

• ADT generici: ADT parametrici rispetto al tipo dei loro componenti

• Costrutto C++: templatetemplate<class T> class stack {public:

stack (int size);~stack ();void push(T c);T pop();int empty() const;

private: //codice dipendente//dall’implementazione

};

stack<int> int_st(30);stack<char> char_st(10);



Sistemi di tipi

Informatica 3


Sistema dei tipi

• Sistema dei tipi (type system): – insieme di regole utilizzate dal linguaggio per

strutturare e organizzare i tipi• Gli oggetti sono istanze di tipo

– Ogni tentativo di manipolare gli oggetti con operazioni illegali è un errore di tipo (error type)

• Un programma è “type safe” se non presenta errori di tipo


Sistema dei tipi

• Un sistema dei tipi si dice forte se garantisce la type safety– Linguaggio fortemente tipizzato– Il compilatore può garantire la correttezza dei tipi

• Altrimenti si dice debole– Linguaggio debolmente tipizzato

• I linguaggi tipizzati staticamente (il tipo di ogni oggetto è noto a tempo di compilazione) sono fortemente tipizzati– Non è vero il contrario


Compatibilità dei tipi

• Ad un oggetto di tipo T1 si possono applicare operazioni del tipo T2 se T1 è compatibile con T2– Conformità o equivalenza

– Compatibilità di nome: • Un nome di tipo è compatibile solo con se stesso

– Compatibilità strutturale:• T1 è compatibile con T2 se hanno la stessa struttura

– richiede di sostituire ricorsivamente al nome dei tipi definiti dall'utente la loro definizione.

struct s1{

int y;

int w; };

struct s2{

int y;

int w; };

struct s3{

int y; };

s3 funz(s1 z) {

…

}

s1 a, x; s2 b; s3 c; int d;

a=b; x=a; c=funz(b); d=funz(a);

Esempio:


Conversioni di tipo

• Cambiamento implicito o esplicito del tipo di un operando al fine di soddisfare le regole di compatibilità

• Si supponga di voler effettuare la seguente operazione

int num1, somma; float num2;somma = num1 + num2;

• In diversi linguaggi i compilatori applicano delle conversioni automaticamente: coercizione

(num1 - int) + (num2 - float) = (float) --> assegnamento a (int)

• C/C++: castingsomma = num1 + (int) num2;


Controllo, conversione e compatibilità tra tipi

x=y+z

controllodi tipo

regole di conversione

regole dicompatibilità

OK KO


Tipi e sottotipi

• Sottotipo: – T' è sottotipo di T se ha le stesse proprietà di T ma

un insieme di valori ristretto. T' non è un nuovo tipo, ma ha dei vincoli in più

• Valori: sottoinsieme dei valori di un tipo • Stesse operazioni

type naturale=0..maxint;cifra=0..9;età=0..120;

TT’


Sistemi monomorfici e polimorfici

• Sistema monomorfico: – Ogni oggetto appartiene ad un tipo– Sistema fortemente tipizzato e poco flessibile– E’ possibile verificare a tempo di compilazione la

correttezza dei tipi

• Sistema polimorfico:– Ogni oggetto può appartenere a uno o più tipi

• Tipi compatibili, coercizione, sottotipi

• I linguaggi offrono diversi livelli di polimorfismo


Classificazione di polimorfismo

• Polimorfismo

– Universale: insieme infinito di tipi• Parametrico: es. routine generiche• Inclusione: es. sottotipi

– Ad hoc: insieme finito di tipi• Overloading• Coercizione


Verifica degli errori

• Errori:– Del linguaggio – Dell’applicazione

• Verifica degli errori:– Statica: a tempo di compilazione

• Non è possibile rilevare tutti gli errori (es. divisione per 0)

– Dinamica: durante l’esecuzione sui dati di input

Lezione 5 - Tipi di dati - Intranet DEIBhome.deib.polimi.it/comai/info3/File/Lezione 5 - Tipi di...

Documents

Transcript of Lezione 5 - Tipi di dati - Intranet DEIBhome.deib.polimi.it/comai/info3/File/Lezione 5 - Tipi di...