Sistemi dei tipi

Ogni linguaggio di programmazione ha un proprio sistema di tipi cioe' info e regole che governano i tipi e i loro valori, chiamati abitanti (inhabitants) del tipo

Tipi base (primitivi)

Sono tutti i tipi che definiscono i val denotabili del linguaggio. Es. 42, 3.14 'A' (int, float, char). Il modo in cui caratterizziamo 42 e int dipende dal ling che stiamo usando, in java si usano 4 byte per rappresentare un int (corrisponde a tutti i num interi da $-2^{32}$ a $2^{31}-1) In rust dovremmo specificare ulteriormete il tipo di intero che ci intererssa memorizzare (i32, u32)

Tipo Unit (vs Void)

L'unico abitante del tipo Unit e' l'unita' singoletto (rapp anche come ()) e di solito e' associato a op il cui tipo di ritorno non e' utilizzabile (es. quando devo inviare cose, stampare qualcosa a schermo) devo avvisare che ho finito, lo faccio ritornando unit.

Linguaggi come Java o C hanno un concetto simile all'unita col tipo unit, il void che pero' presenta differenze con unit. Non possiamo ne ottenere ne passare void (mentre con unit si). Java ha dovuto mettere un output a void (ritorna null).

Booleani

Valori: solo true e false

operazioni: principali operazioni logiche, come la congiunzione (&), la disgiunzione (

), la negazione (!), l'uguaglianza (==)

In c originale non c'erano

Tipi di caratteri

valori: insieme di codici di caratteri (es. ascii, unicode) operazioni: =, ><

Tipi Interi

val: sottoinsieme finito di numeri interi, fissato al momento della definizione del linguaggio

operazioni:

Reali

valori: un sottoinsime finito tra i num reali, tramite rappresentazione a virgola mobile e fissa

• i num a virgola fissa riservano bit specifici per gli interi e decimali. A virgola mobile no.

Enumeration types

Un tipo di enumerazione consiste in un iniseme finito di costanti, ciascuna caratterizzata da yn proprio nome. C, rust, java forniscono la stessa sintassi ad es:

enum rogueOne {Jean, Cassian, A, B, C }

introducono un nuovo tipo chiamato rogueOne costituito da un insieme di 5 elementi, ciascuno con un proprio nome.Le operazioni disponibili sugli enum consistono in confronti e in un meccanismo per ottenere tutti i valori o passare da uno all'altro. Da un punto di vista pragmatico, gli enum presentano due vantaggi: 1) aiutano la leggibilità, poiché i nomi dei valori costituiscono una chiara forma di auto-documentazione del programma e 2) permettono al controllo di tipo di verificare che una variabile con enumerazione assuma solo i valori corretti.

Non tutti i linguaggi integrano gli enum in modo sicuro, ad esempio in C la scrittura sopra è uno zucchero sintattico per

typedef int RogueOne; const RogueOne Jyn=0, Cassian=1, .....;

che equipara gli interi ai RogueOne e impedisce di distinguerli (e di verificarne la correttezza).

Extensional vs Intensional types

Gli interi (e i float, i chars, …) rispetto agli enum hanno una differenza importante: l'utente specifica gli enum in modo estensionale, cioè elencando tutti i possibili abitanti di quel tipo. Al contrario, i linguaggi specificano gli interi, i float e così via in modo intensionale, cioè mediante predicati che definiscono la loro appartenenza ad alcuni domini di valori possibili (ad esempio, numeri interi a 32 bit, numeri in virgola mobile, caratteri UNICODE).

Si usano sistemi intesionali quando si dispone di un insieme definito di prop che indentificanop solo gli abitanti (val validi) del tipo che sto definendo (vantaggio: risparmio di mem)

Estensionale quando e'piu efficiente (per spazio e computazione) specificare gli a bitanti del tipo o non esiste un iniseme chiaro di regole che li definiscono

Tipi composti

Gli enum sono kinds (possono creare tipi) mentre i tipi sono es arrayInt, int, char. Gli enum devono essere istanziati per diventare tipi. Possiamo creare nuovi tipi componendo quelli di base. Nelle enumerazioni di C, abbiamo creato insiemi di elementi denominati, che corrispondono a numeri interi, ma sono possibili altre strutture, tra cui le più basilari sono: array, insiemi e puntatori.

Array

Anche gli array sono kinds (non esiste il tipo array ma esiste il tipo array di interi, float ecc). Un array denota un insieme di elementi di un certo tipo, ciascuno indicizzato da almeno una ** chiave identificativa** di uyn certo tipo (quando si usano 2 o piu chaivi si parla di array multidimensionali). La nozione piu comune di array assume chiavi come num interi non negativi all'interno di un intervallo [0-n] per n+1 elementi. Altri tipi di array (mappe) permettono di creare array associativi, permenttono all' utente di fissare sia il tipo delle chiavi che quello degli elementi.

tabella sintassi dichiarazione int in C, java e rust int x[3] int[] x let x: [i32;3] x[0] = 0 // posso farlo solo in c, in java devo prima istanziarlo int x[3] = {0,0,0} x = new int[3] x = [0,0,0]

Sia il C che Rust fissano nella dichiarazione del tipo la dimensione dell'array (3), mentre Java astrae da questo e lascia che sia l'inizializzazione a definire la dimensione dell'array (ne parleremo in seguito). La maggior parte dei linguaggi (tra cui C, Java e Rust) estendono le dichiarazioni di array lineari a quelle a più chiavi int x[10][10] int[][] x let x: [[i32;10];10]

In C posso fare il lookup di una val di una cella di un array che ho appena creato ma a cui non ho ancora associato un val (leggo celle di memoria scritte da chissa' chi, possono contenere info sensibili) L'op piu semplice da fare su un arrau e' la selezione di un elem tramite il suo indice. La notazione e' a[e] dove a e' la var di tipo array e e e' l'espressione. Per array multidimensionali sono a[e][e][e] o a[e,e,e] (per ling che hanno sia array multidimensionali che array di array). Altre op (su array di interi) sono: assegnazione (=), confronti (==, <,>) e le op aritmetiche Poiché conoscono il tipo di indice degli array, i linguaggi safe verificano che ogni accesso a un elemento dell'array avvenga davvero entro i suoi “limiti” (si fa solo a runtime).

Un array viene solitamente memorizzato in una porzione contigua di memoria. Per un array monodimensionale, l'allocazione segue l'ordine degli indici. Per gli array multidimensionali, esistono principalmente due tecniche, chiamate ordine di riga (row major) e ordine di colonna (column major). Nell'ordine di riga, due elementi sono contigui se differiscono di uno nell'ultimo indice. Nell'ordine per colonna, due elementi sono contigui se differiscono di uno nel primo indice. L'ordine di riga è un po' più comune di quello per colonna, soprattutto perché gli accessi per riga sono più frequenti di quelli per colonna. In generale, il principio di località del caricamento in funzione dei cache-miss favorisce gli algoritmi che esplorano gli array per righe con ordine di riga e viceversa per l’ordine di colonna.

Dimensione array

Il numero di dimensioni e i loro intervalli determinano la forma di un array. Un aspetto importante della definizione di un linguaggio è decidere se e quando fissare la forma degli array. Se la forma è fissa, possiamo decidere di definirla in fase di compilazione (per i linguaggi compilati, come in C e Rust) o quando elaboriamo la dichiarazione (a tempo di esecuzione). In alternativa, possiamo avere array dinamici, la cui forma è determinata e cambia in fase di esecuzione (come in Java).

In un array statico conosciamo la dimensione necessaria per memorizzare l'array (l'offset tra il primo e l'ultimo elemento dell'array), quindi l'accesso a un elemento dell'array è simile all'accesso a variabili di tipo scalare (salvo alcuni calcoli necessari, ad esempio, quando si accede ad array multidimensionali). Se decidiamo di definire l'array quando elaboriamo la sua dichiarazione, conosceremo la sua forma (fissa) nel momento in cui il controllo raggiunge la dichiarazione dell'array. Un esempio di questo tipo è se la dimensione dipende dal valore di una variabile. Possiamo allocare l'array nello stack frame del blocco che ne contiene la definizione. Tuttavia, poiché conosciamo la dimensione dell'array solo quando carichiamo il frame, non possiamo preallocare in modo sicuro lo spazio nello stack: una stima errata sprecherebbe memoria o si sovrapporrebbe ad altre variabili statiche. Per ovviare a questo problema, si utilizza l'heap e si memorizza nel frame il puntatore all'inizio della regione di memoria. Il descrittore di tale array prende il nome di dope vector, utilizzato anche nel caso di array dinamici (con alcuni elementi aggiuntivi nel dope vector per tenere traccia del suo stato).

Lo stack frame ha molte piu cose (devo tenere conto di una var dimensione ecc)

Tipi insieme

Struttura di dati senza ordine con valori unici dello stesso tipo.

Le operazioni possibili sugli insiemi includono il test di inclusione e le operazioni di manipolazione degli insiemi: unione, intersezione, differenza e complemento.

L'estrazione e' un op strana perche' sono liste senza ordine quindi devo pescare a caso i val. Il caso in informatica non esiste quindi chi ha il seed dell'estrazione sa predire l'estrazione successiva.

Rappresentazione in memoria di un insieme

Un modo efficiente per rappresentare un insieme è un array di bit di lunghezza pari alla cardinalità del tipo di base (es set di elementi da 0 a 7, cardinalita' 8). Questo array è chiamato array caratteristico e, in esso, il bit -esimo indica se l’elemento -esimo del tipo base (dato un ordinamento standard) appartiene all'insieme. Questa rappresentazione permette di eseguire in modo efficiente le operazioni sugli insiemi (operazioni bit-a-bit sulla macchina fisica), ma non è adatta a grandi sottoinsiemi di tipi base. Per ovviare a questo problema, i linguaggi spesso limitano i tipi che si possono usare come tipi base di un insieme oppure scelgono rappresentazioni alternative, ad esempio tramite tabelle hash, bilanciando velocità e occupazione di memoria (perche' se ho un ash come tipo base ho campi molto grandi ma facili da trovare)

Esempio array caratteristico: Immagina che il tuo tipo base siano i numeri da 0 a 7 (cardinalità = 8). Il linguaggio crea un array di 8 bit. Se il tuo insieme è {1, 4, 5}, l'array sarà: Valore (Indice i) 0 1 2 3 4 5 6 7 Bit (1=Presente, 0=Assente) 0 1 0 0 0 0

Fare l'unione o l'intersezione tra due insiemi diventa una semplice operazione bit-a-bit (OR, AND) a livello di processore. È istantaneo. I l limite? Se il tipo base fosse "Tutti i numeri interi a 32 bit". L'array dovrebbe avere 2^{32} bit (circa 512 Megabyte di memoria) per un singolo insieme, anche se contiene solo tre numeri! Uno spreco enorme.

Esempio con tabelle Hash (Il workaround moderno)

Quando il tipo base è grande (come stringhe, o numeri interi generici), i linguaggi moderni (come Python, Java, C#) abbandonano l'array di bit e usano le Tabelle Hash.

Una piccola correzione al tuo ultimo appunto: Non è che hai un "hash come tipo base", ma usi una Tabella Hash come struttura dati sottostante. In pratica, passi il tuo valore (es. la stringa "Ciao") a una funzione di hash, che lo trasforma in un numero. Quel numero diventa l'indirizzo di memoria dove salvare il dato.

Il compromesso: Occupa un po' più di memoria rispetto all'array di bit puro ed è impercettibilmente più lenta nelle operazioni logiche, ma risolve il problema dello spreco di spazio, permettendoti di creare insiemi di qualsiasi tipo di dato senza far esplodere la RAM.