Capitolo 2
Types e Type Systems
2.1 Introduzione
La moderna ingegneria del software fornisce un ampio insieme di metodi formali per assicurare che un sistema durante il suo funzionamento rispetti determinate specifiche. Da una parte ne esistono alcuni veramente potenti come la logica di Hoare, le definizioni algebriche di linguaggi, le logiche modali e la semantica denotazionale. Questi possono essere usati per esprimere proprietà di correttezza molto generali ma sono spesso difficili da usare richiedendo al programmatore ingenti sforzi. Dall’altra ci sono tecniche di “potenza più modesta” come checker automatici che possono essere costruiti all’interno di compilatori, linkers e analizzatori di programmi, e che si prestano all’uso anche da parte di programmatori che abbiano poca familiarità con gli strumenti visti in precedenza. Tra queste ultime sta crescendo di popolarità quella che va sotto il nome di run-time monitoring[11][12][36], che consiste in un insieme di metodi che permettono ad un
sistema di accorgersi dinamicamente quando uno dei suoi componenti non sta rispettando le specifiche (condizioni descritte in varie forme). Senza dubbio però, tra questi, il metodo formale più utilizzato è quello che prevede la costruzione di un
sistema dei tipi (type systems)[13]. Come per tutti i termini di largo uso, è difficile
fornirne una definizione esaustiva. Una plausibile potrebbe essere:
Un type system è un metodo trattabile sintatticamente di provare l’assenza di determinati comportamenti in un programma classificando le sue frasi in accordo alle tipologie di valori trattati.
Cerchiamo di chiarirne alcuni aspetti. Come prima cosa, questa definizione identifica i type systems come strumenti che permettono di ragionare sui programmi. Più in generale, il termine type systems (o type theory) si riferisce ad un più ampio campo che coinvolge gli ambiti della matematica, della logica e della filosofia. In questo senso, i type systems vennero formalizzati nei primi del novecento come strumento per evitare i paradossi della logica (Russell). Proprio nell’ambito della logica, durante il ventesimo secolo, sono diventati strumenti standard a supporto della teoria delle dimostrazioni. I maggiori risultati in questo settore includono la teoria ad albero dei
tipi (Russell), gli studi di Church sul simply typed -calculus, la teoria costruttiva dei tipi (Martin-Löf).
Un altro importante elemento su cui pone l’enfasi la precedente definizione è la
classificazione dei termini, frasi sintattiche, in accordo con le proprietà dei valori che
essi calcolano quando eseguiti. Un type system può calcolare una specie di
approssimazione statica di quello che sarà il comportamento a run-time delle frasi di
un programma. La parola statico è spesso esplicitata per distinguere quelli che sono i controlli a tempo di compilazione (compile-time)[34] da quelli che avvengono a tempo d’esecuzione (run-time)[34].
Essendo statici, i type systems sono anche conservativi: essi possono provare categoricamente l’assenza di determinati “cattivi comportamenti”, ma non possono provarne la presenza, ed inoltre potrebbero anche respingere alcuni programmi che probabilmente si sarebbero comportati bene a run-time. Per esempio, molti type system possono controllare staticamente che gli argomenti delle operazioni aritmetiche siano numeri, ma non possono assicurare, per citarne uno, che il secondo argomento di una divisione non possa non essere zero.
I cattivi comportamenti che possono essere eliminati da un type system di un certo linguaggio di programmazione sono in genere chiamati errori a tempo d’esecuzione (vedere il paragrafo successivo). E’ importante notare che questi cambiano da linguaggio a linguaggio. La safety (o soundness, vedere comunque più
avanti)[13][29] di un certo sistema dei tipi deve essere verificata rispetto al suo insieme di errori a run-time.
Gli scopi di un type system vanno comunque oltre a quanto descritto finora: sono usati per rafforzare la modularità e per proteggere l’integrità delle astrazioni definite dall’utente.
I typechecker sono in genere incorporati nei compilatori e nei linkers: questo implica che essi dovrebbero svolgere il loro lavoro automaticamente, senza nessun intervento manuale da parte del programmatore. In realtà questo ultimo introduce nel codice informazioni esplicite (annotazioni) sui tipi: in questo modo il typechecker diventa effettivamente un verificatore di proprietà, visto che alcuni comportamenti possono essere codificati proprio in queste ultime.
Analizziamo in dettaglio i vari aspetti del problema.
2.2 Errori a tempo d’esecuzione
Il sintomo più ovvio di un tale errore è il verificarsi di un fallimento inaspettato del programma, causato ad esempio da un riferimento errato alla memoria. Ci sono inoltre tipologie più subdole di errori che possono condurre a corruzione dei dati non immediatamente verificabile. D’altro canto, ci sono errori di programmazione come ad esempio la divisione per zero e la dereferenziazione (nel caso di linguaggi con puntatori) ad arie di memoria vuote, che non sono in genere prevenuti dai type systems.
E’ utile quindi distinguere fra due tipi di errore[13][14] a tempo d’esecuzione: il primo che causa lo stop immediato della computazione, il secondo che in genere non viene notato e che in seguito causa strani comportamenti. I primi sono conosciuti come trapped errors (errore a run-time che produce immediatamente un fault), i secondi come untrapped errors (errore a run-time che non produce un fault
immediato ma che permette alla computazione di continuare in modo anomalo). Un
esempio di errore untrapped è l’accesso ad un dato fuori dallo spazio di indirizzamento di un array (IndexOutOfBound) o un salto ad un indirizzo sbagliato (ovviamente in assenza di altri controlli). Esempio di errore trapped è invece proprio la divisione per zero.
Un frammento di codice è detto safe (sicuro) se previene gli errori untrapped. I linguaggi dove tutti i frammenti sono safe sono chiamati safe languages. I linguaggi non tipati cercano di garantire la safety (prevenzione degli errori untrapped) con dei controlli a run-time, mentre quelli tipati cercano di farlo staticamente respingendo tutti i programmi che potenzialmente sono unsafe (non sicuri rispetto agli errori
untrapped). Questi ultimi possono anche usare un mix tra controlli statici e dinamici.
Per ogni dato linguaggio possiamo dunque stabilire un sotto insieme di possibili errori a tempo d’esecuzione che prendono il nome di forbidden errors: questi includono sia errori trapped che errori untrapped. Un frammento di codice è detto avere un buon comportamento o equivalentemente essere well behaved[13][33] (vedremo in seguito), se non causa forbidden errors. In caso contrario è detto ill
behaved[13][33] (vedremo in seguito). In particolarmente, un frammento well
behaved è anche safe. Un linguaggio dove tutti i programmi (legali) sono well behaved è detto fortemente tipato (strongly checked).
Così, dato un type system, per un linguaggio strongly checked valgono le seguenti affermazioni:
a) Non occorrono untrapped errors (garanzia di safety).
b) Non occorre nessuno dei trapped errors contenuti nella lista dei forbidden. c) Altri errori trapped potrebbero verificarsi: è responsabilità del programmatore evitarli.
I linguaggi tipati (vedere paragrafo successivo) possono “imporre” il well behaved eseguendo un check statico a tempo di compilazione. Tali linguaggi sono detti
statically checked; il processo di checking è detto typechecking e di conseguenza
l’algoritmo che lo esegue è detto typechecker. Un programma considerato corretto da questo ultimo è detto ben tipato (well typed), altrimenti mal tipato (ill typed). Esempi di linguaggi tipati staticamente sono Java, ML, Pascal.
I linguaggi non tipati (vedere paragrafo successivo) invece ricercano il well behaved eseguendo sufficienti controlli a run time per evitare i forbidden errors. Il processo di checking di questi linguaggi è chiamato dynamic checking: ne è un esempio LISP. Di solito comunque anche se un linguaggio è statically checked ha bisogno di controlli a run time per garantire la safety. Ultima cosa da notare è che molti linguaggi sfruttano la loro struttura statica dei tipi per eseguire sofisticati test dinamici. Ad esempio
instanceof di Java discrimina sul tipo a run time di un oggetto. Questi linguaggi sono
spesso considerati impropriamente statically checked proprio perché i test dinamici sui tipi sono definiti in base al type system statico.
2.3 Linguaggi tipati e non tipati
Abbiamo già visto come i linguaggi adottino strategie differenti, a seconda che siano tipati o meno, per imporre il well behaved dei programmi. Soffermiamoci adesso sulle loro caratteristiche. Una variabile può assumere un range di valori durante l’esecuzione di un programma. Un limite superiore di questo insieme viene chiamato
tipo della variabile. Per esempio, una variabile x di tipo boolean, può assumere solo
valori booleani durante l’esecuzione di un programma: così un’espressione del tipo
not(x) ha un significato stabilito. I linguaggi dove alle variabili può essere assegnato
un tipo sono chiamati tipati (typed). Al contrario i linguaggi che non restringono i range delle variabili sono chiamati non tipati (untyped): essi appunto non prevedono tipi o, equivalentemente, hanno un tipo universale che contiene tutti i valori. In questi linguaggi, le operazioni potrebbero essere applicate ad argomenti inappropriati: come risultato avremmo un valore arbitrario fissato, un’eccezione o un effetto imprevedibile.
Il -calcolo puro è il caso estremo di un linguaggio non tipato dove non si verificano errori: l’unica operazione è l’applicazione di funzione e, poiché tutti i valori sono funzioni, le operazioni non falliscono mai.
Il type system è quella componente di un linguaggio tipato che opera con i tipi delle variabili e, più in generale, con i tipi di tutte le espressioni di un programma. I type
systems sono dunque usati per determinare quando un programma è corretto dal punto di vista dei tipi. Un linguaggio si dice dunque tipato conseguentemente all’esistenza per esso di un type system, indipendentemente dal fatto che i tipi appaiano o meno nella sintassi del programma. Proprio per questo distinguiamo fra linguaggi esplicitamente tipati e linguaggi implicitamente tipati. Sono pochi quelli che adottano questa ultima sconveniente strategia, anche se, ad esempio con ML ed Haskell (linguaggi funzionali) è possibile scrivere grossi frammenti di programma omettendo i tipi: sarà poi il loro type system ad assegnarli automaticamente.
2.4 Mancanza di safety
Alla luce dei nuovi concetti introdotti, possiamo correggere un po’ il tiro ed affermare che il vero scopo di un type system dovrebbe essere quello di assicurare che un linguaggio sia safe, evitando durante l’esecuzione di un programma il verificarsi di errori untrapped. In realtà la maggior parte di questi sono disegnati per
garantire la più generale proprietà di well behaved e implicitamente quella di safety.
Succede dunque, che alcuni linguaggi controllati staticamente non assicurino tale proprietà. Cioè, il loro insieme di forbidden errors non include tutti gli untrapped
errors. Questi linguaggi sono in genere chiamati weakly checked (debolmente tipati)
con il significato che, certe operazioni unsafe sono riconosciute staticamente mentre altre no. Per fare un esempio, il C ha molte di tali operazioni come le combinazioni aritmetiche tra puntatori e il casting. A questo punto è lecito chiedersi se può un linguaggio essere completamente safe. Dare una risposta esaustiva a questo quesito non è possibile, possono essere fatte solo alcune considerazioni di massima.
La proprietà può essere “garantita” introducendo controlli a run-time che ovviamente incidono sulla performance. Ha un certo costo anche sui linguaggi che usano fortemente l’analisi statica: i controlli ad esempio sugli indici degli array non possono essere completamente risolti a compile time. Si presentano comunque anche alcuni vantaggi. La safety “produce” uno stop immediato del programma in caso di errore a tempo d’esecuzione, riducendo così i tempi di debugging. Garantisce l’integrità della
struttura a run-time, e consente il corretto funzionamento del garbage collector. Infine, è di basilare importanza per la sicurezza dei sistemi, in particolare per quelli che caricano ed eseguono codice esterno. Proprio la sicurezza sta diventando uno degli aspetti più costosi dello sviluppo e mantenimento dei programmi, e la safety
può ridurne i costi. Concludendo, la scelta tra linguaggi safe ed unsafe è legata al
rapporto tra sviluppo e mantenimento da una parte, e tempo d’esecuzione dall’altra.
2.5 Perché avere un type system?
Indubbiamente il poter contare sui tipi espliciti, fornisce parecchi vantaggi che interessano i vari aspetti di un linguaggio. In breve:
• Esecuzione: accurate informazioni di tipo a compile time evitano costosi test su
argomenti e operatori a run time.
• Sviluppo: quando un type system è ben disegnato, la fase di typechecking può
catturare un grosso numero di errori, permettendo di evitare lunghe sessioni di debugging. Quegli errori poi, che in genere occorrono sono facili da individuare e correggere, visto che la maggior parte è già stata eliminata.
• Compilazione: le informazioni di tipo possono essere organizzate in interfacce per
ogni modulo di un programma. Così questi ultimi possono essere compilati separatamente, aumentando l’efficienza.
• Sviluppo in larga scala: le interfacce ed i moduli costituiscono un vantaggio per lo
sviluppo di codice. I team di programmatori possono così stabilire le interfacce e sviluppare separatamente i pezzi di codice.
2.6 Proprietà dei type systems
I tipi hanno caratteristiche ben precise che li distinguono dalle altre annotazioni presenti in un programma. Le proprietà di base che ci si aspettano da ogni type system sono:
• Verificabilità: c’è un algoritmo (typechecking) che ci assicura che un determinato
programma è well behaved. Il type system non solo specificherà le intenzioni del programmatore, ma catturerà alcuni errori d’esecuzione prima che essi possano essere generati.
• Trasparenza: un programmatore deve essere capace di capire facilmente quando
un programma è ben tipato. Se il typechecker fallisce il motivo deve essere evidente.
• Osservabilità: le dichiarazioni di tipo devono essere controllate staticamente, e in
caso ciò non sia possibile, dinamicamente. La consistenza tra dichiarazioni di tipo e programmi associati sempre verificabile.
2.7 Come sono formalizzati i type systems
E’ già stato detto che la proprietà di safety causa lo stop dell’esecuzione nel punto esatto in cui si verifica il fault (utile per il debugging) oltre a permettere al garbage collector di proteggere la struttura a run time. Il well typing (rispetto delle regole di un dato type system), invece, facilita la stesura dei programmi prevenendo i trapped errors prima dell’esecuzione. A questo punto è lecito chiedersi: come possiamo essere sicuri che le regole di tipo di un linguaggio non consentano a programmi ill behaved di essere eseguiti? I type systems formali sono la caratterizzazione
programmazione. Una volta che un type system è stato formalizzato, possiamo sfruttare il teorema di type soundness[13][32] per provare che i programmi ben tipati sono anche well behaved. Per formalizzare dunque un type system e provare il teorema di soundness dobbiamo essenzialmente formalizzare l’intero linguaggio in questione.
Il primo passo nella formalizzazione di un linguaggio è descrivere la sua sintassi. Per molti linguaggi questo si riduce a descriverne quella dei tipi e termini (come avviene nel caso di Sigma_X).
Il secondo passo è quello di definire le regole di scoping[13][33] del linguaggio, che in modo non ambiguo associano le occorrenze degli identificatori ai loro binding. Lo scoping necessario per definire un linguaggio tipato è statico, nel senso che i legami devono essere determinati prima dell’esecuzione. Tali legami sono in genere determinati dalla sintassi del linguaggio: lo scoping statico è in genere chiamato
scoping lessicale. Lo scoping può essere formalmente specificato definendo l’insieme
delle variabili libere di un frammento di programma.
Fatto questo si passa alla specifica delle regole di tipo di un linguaggio. Queste descrivono la relazione che sta ad indicare che il termine M ha un tipo A. Alcuni linguaggi prevedono anche la relazione di sottotipo tra i tipi A e B (A B), e spesso anche l’equivalenza tra tipi nella forma . L’insieme di queste regole
costituisce il type system di un linguaggio. Queste non possono però essere
formalizzate senza aver prima introdotto un altro elemento fondamentale: l’ambiente
statico dei tipi. Questo viene usato per registrare il tipo delle variabili libere (free variables) man mano che si scorre il codice: corrisponde strettamente alla tabella dei
simboli di un compilatore durante la fase di typechecking. Ad esempio, la relazione è associata ad un ambiente statico dei tipi , che contiene informazioni sulle variabili libere di M ed A. La relazione ha la forma , che sta ad indicare che M ha un tipo A nell’ambiente .
Il passo finale nella formalizzazione è definire la semantica di un linguaggio come la relazione “ha un valore” tra termini ed un insieme di risultati. La forma di questa dipende fortemente dallo stile di semantica adottato.
Come ultima cosa è da notare che la nozione fondamentale di type system è applicabile a tutti i paradigmi programmativi: singole type rules possono essere adottate senza alcun cambiamento in linguaggi diversi.
2.8 Regole d’inferenza: il linguaggio dei type systems
Un type system specifica le regole di tipo di un linguaggio di programmazione indipendentemente dal particolare algoritmo di typechecking. E’ conveniente ed utile distinguere questi due aspetti: infatti il type system appartiene alla definizione del linguaggio, mentre l’algoritmo al compilatore. Inoltre è più semplice ma soprattutto corretto, spiegare i tipi di un linguaggio partendo dalla definizione del type system piuttosto che dall’implementazione di un typechecker dato un certo compilatore. Fatta tale distinzione, è possibile introdurre il particolare formalismo usato per descrivere i type systems. La descrizione comincia con la formulazione di un insieme di espressioni formali chiamate sentenze.
Tipicamente una sentenza ha la forma , dove e è una asserzione, e le variabili
libere di e sono dichiarate in . Diremo dunque che implica e. , come già detto, è
l’ambiente statico dei tipi. L’ambiente vuoto è in genere indicato con { }, mentre in un ambiente che ha la forma indicheremo con dom( ) l’insieme delle x. La più importante sentenza, per quel che ci riguarda, è la sentenza di tipo (typing judgment) che nella forma afferma che un termine M ha un tipo A rispetto ad un ambiente statico .
Le sentenze possono essere classificate in valide ed invalide. E’ proprio la validità di queste che formalizza la nozione di programma ben tipato (well typed program). Si è parlato di regole di tipo, descriviamone la struttura.
2.9 Regole di tipo
Le regole di tipo asseriscono la validità di certe sentenze sulla base di altre che sono già state giudicate valide. Hanno in genere la forma:
Ognuna di esse è scritta come un certo numero di premesse sopra una linea orizzontale, seguite da una singola conclusione sotto tale linea: quando tutte le premesse sono soddisfatte si può assumere la conclusione (l’insieme delle premesse può anche essere vuoto). Ogni regola ha un nome che in genere le viene indicato accanto tra parentesi. Quando necessario ci sono alcune condizioni che restringono l’applicabilità della regola.
Un insieme di regole di tipo prende il nome di type system formale (formal type
system).
2.10 Derivazioni di tipo
Una derivazione in un dato type system è un albero di sentenze con le foglie in alto e la radice in basso, dove ogni sentenza è ottenuta da quella immediatamente sopra tramite alcune regole del sistema. Una caratteristica fondamentale di un type system è che sia sempre possibile stabilire quando una di queste derivazioni è costruita correttamente. Quindi detto ciò, è possibile affermare che una sentenza è valida quando è ottenuta come radice di una derivazione. In altre parole, quando è ottenuta applicando correttamente le regole di tipo.
2.11 Correttezza dei tipi e inferenza
In un dato type system, un termine M è corretto dal punto di vista dei tipi (well typed) in un ambiente , se esiste un tipo A tale che è una sentenza valida; cioè se al termine M può essere assegnato un tipo. La scoperta di una derivazione (e quindi di un tipo) per un termine va sotto il nome di problema dell inferenza dei tipi (type inference problem). Nel caso in cui non esista alcuna derivazione per un termine siamo di fronte ad un errore di tipo (typing error). Il problema di inferire il tipo per un termine è strettamente legato al sistema dei tipi in questione: un algoritmo per la type inference potrebbe infatti essere facile, difficile o addirittura impossibile da trovare proprio a seconda della decidibilità di questo ultimo e della semidecidibilità delle formule della teoria da esso definita. Sebbene i type systems siano spesso formalizzazioni molto astratte, il loro utilizzo pratico dipende dalla disponibilità di un buon algoritmo di inferenza.
2.12 Type soundness
Quando ci occupiamo di regole di tipo, dobbiamo tenere bene a mente che un sistema dei tipi non è semplicemente una collezione di regole. Ben tipato vuol dire avere una corrispondenza della nozione semantica di programma well-behaved. In genere si verifica la correttezza di un sistema dimostrando un teorema di type soundness: è proprio qui che i tipi incontrano la semantica.
Per la denotazionale ci aspettiamo che se è valida la sentenza , allora
[M]∈[A] (vuol dire che il valore di M appartiene all’insieme dei valori denotati dal tipo A); per l’operazionale che se e M si riduce a M', allora . In entrambe i casi il teorema di type soundness garantisce che i programmi corretti dal punto di vista dei tipi computano senza errori a tempo d’esecuzione.
2.13 Subtyping
I linguaggi Object-Oriented tipati hanno type systems particolarmente interessanti e complessi. Caratteristica fondamentale di questi è senza dubbio la relazione di
sottotipo[12][13][29]. Questa cattura la nozione di inclusione (insiemistica) tra tipi,
dove i tipi sono visti come particolari collezioni di valori. Un elemento di un tipo può essere considerato anche come elemento di un suo supertipo, consentendo così ad un valore (oggetto) di essere usato flessibilmente in molti differenti contesti.
Quando consideriamo una relazione di sottotipo, è necessario aggiungere al sistema una nuova sentenza della forma che asserisce che A è sottotipo di B. Intuitivamente possiamo dire che un elemento di A è anche un elemento di B o, in modo più appropriato, che un programma di tipo A è anche un programma di tipo B. Per rendere possibile tale relazione è in genere aggiunta una regola di tipo chiamata
sussunzione che connette le proprietà di un tipo con quelle di un suo sottotipo.
Questa ultima afferma che se un termine ha un tipo A, ed A è un sottotipo di B, allora
il termine ha anche tipo B.
2.14 Polimorfismo
Polimorfico significa che può avere molte forme. Il concetto relazionato ai linguaggi
di programmazione si riferisce a dati o programmi che possono avere o operare su più di un tipo. Ci sono diverse forme di polimorfismo[25][32], ma di certo la più interessante è quella conosciuta con il nome di polimorfismo parametrico. Questa è una proprietà dei programmi ma anche dei dati, in alcuni linguaggi: il sistema dei tipi contiene variabili di tipo e tipi, definiti con queste, che sono parametrici rispetto al
tipo di alcuni dei loro identificatori. Ci sono due modi di realizzare il polimorfismo
parametrico che sono concettualmente correlati ma profondamente differenti nelle tecniche utilizzabili per operare con essi: esplicito ed implicito.
Il polimorfismo è detto esplicito quando la parametrizzazione è ottenuta esplicitando i parametri di tipo nelle header delle procedure con conseguente esplicita annotazione del tipo degli argomenti quando queste sono chiamate. In questo caso il polimorfismo coincide con l’assunzione di un parametro di tipo il più generale possibile.
E’ detto implicito invece quando non sono consentiti parametri di tipo (generali), ma sono sfruttate delle variabili di tipo, ancora da determinare. Se tra i parametri di una procedura abbiamo delle variabili di tipo o dei termini che ne contengono, allora può essere applicata ad argomenti di tipo differente.
2.15 Type Inference: il problema
La Type Inference[27][30][32] è il problema di determinare il tipo per un termine dato un type system, ammesso che questo tipo esista (e sia unico). Quando i programmi presentano abbondanti annotazioni di tipo, il problema si riduce ad un (più o meno) semplice checker che non fa altro che controllare la consistenza delle annotazioni.
Un problema più complesso, chiamato typability o type reconstruction, consiste nel partire con un programma M non tipato (esplicitamente), e trovare un ambiente , una versione M' di M type-annotated (cioè un programma con annotazioni di tipo ricavate in qualche modo da M), ed un tipo A che sia il tipo di M' rispetto a . Di solito il problema della typability è risolto (come nel nostro caso), tramite l’applicazione dell’algoritmo W di Hindley-Milner, che ha la proprietà di produrre una rappresentazione di tipo univoca per ogni termine a cui è applicato. Prima di presentare l’algoritmo nella sua forma più generale, è necessario fare alcune considerazioni preliminari.
2.16 Type Inference: concetti preliminari
Assumiamo di avere un insieme V di simboli di variabili (tipicamente x, y, z, ecc..).
Definizione. Un insieme di termini lambda non tipati è definito induttivamente da: (1)
(2) M, N∈ ⇒ (M N) ∈ (3) M∈ , x∈ V ⇒ ( x.M)∈
Assumiamo inoltre, di avere un insieme O di simboli (chiamati basic types), e un insieme TV di variabili di tipo (type variables, tipicamente ).
Definizione. Un insieme T di tipi è definito induttivamente da:
(1) O ⊂ T
(2) t1, t2 ∈ T⇒ (t1 t2)∈ T
Definizione. Un insieme di termini tipati è ottenuto modificando la clausola (3) della definizione di nel seguente modo: M ∈ , x∈ V, t∈ T⇒ ( x:t.M)∈ .
Definizione. Una type assumption è una funzione parziale A: V T con un dominio finito.
Definizione. Una type assertion è una tripla (A, M, t), dove A è una type assumption,
M è un termine (tipato o non tipato dipende dal contesto), e t è un tipo. Il dominio di A è costituito dalle free variables di M.
Alla luce di queste definizioni, il problema della type inference (per termini chiusi), può essere formulato nel seguente modo: dato un termine chiuso M in , trovare tutti
i tipi t tali che . Possiamo caratterizzare questi tipi usando il meccanismo delle espressioni di tipo (type expressions).
Definizione. L’insieme TE delle espressioni di tipo (i tipi previsti dal type system) è
definito induttivamente aggiungendo alla definizione di T la clausola TV ⊂ TE, avendo indicato, in accordo con la precedente definizione, con TV l’insieme delle variabili di tipo.
Possiamo adesso definire il teorema che sta alla base dell’algoritmo di inferenza.
Teorema.
(1) Dato un termine chiuso M in , è possibile decidere se esiste un tipo t tale che .
(2) Se esiste un tale t, allora è possibile individuare una espressione di tipo u (schema di tipo) tale che il tipo di M è precisamente il tipo della forma uσ per tutte le sostituzioniσ. Ci si riferisce ad u come tipo principale di M. Il tipo t è
chiaramente unico in assenza di polimorfismo.
2.17 Type Inference: struttura base di W
Il problema centrale di ogni algoritmo che risolva la type inference è quello di dover tener traccia di tutte le possibili derivazioni. Questo è fatto, simulando una singola derivazione e usando le espressioni di tipo (schemi) al posto dei tipi veri e propri, per tener traccia di tutti i possibili tipi che potrebbero presentarsi ad ogni nodo dell’albero di derivazione. L’algoritmo simula proprio la costruzione di una derivazione. Ad ogni passo mantiene un insieme G di sotto-goal, che non sono altro che le espressioni di tipo che devono essere provate, ed un insieme E di equazioni tra espressioni di tipo, che sono le condizioni che devono essere soddisfatte affinché la derivazione sia
Forniamo adesso la struttura di base dell’algoritmo:
• Input: Un termine M0di .
• Inizializzazione: E = , G = {(A0, M0, t0)}, dove t0 è una variabile di tipo e A0
mappa le variabili libere di M0su tipi e/o altre variabili di tipo.
• Loop Step: Se G = , allora l’algoritmo si ferma e restituisce E. Altrimenti sceglie un sotto-goal (A, M, t) da G, lo cancella da esso, ed aggiunge ad E e G rispettivamente una nuova condizione e un nuovo sotto-goal, come specificato dai costrutti del linguaggio.
Per completare la trattazione, spieghiamo che cosa si intende per soluzione della coppia (E , G).
Definizione. Sia σ una sostituzione. Diciamo che σ risolve un’equazione e se σ unifica e (unifica cioè le due parti dell’equazione). Se E è un insieme di equazioni, si
dice che σ unifica E se e solo se unifica ogni sua equazione. Se (A, M, t) è una type assertion, diciamo che σ la unifica se solo se ; stessa cosa per ogni elemento di G. Diciamo dunque che σ risolve (E , G) se e solo se risolve separatamente E e G.
Come ultima cosa ci chiediamo: come siamo sicuri che l’algoritmo generi come soluzione di (E , G) esattamente il tipo di (A0, M0, t0)? Stabiliamo un invariante per
esso.
Invariante.
(1) (∀σ)( (E , G))(σ (E , G)⇒ A0σ M0 : t0σ)
La prima clausola afferma che una soluzione per (E , G) genera solo corretti tipi (schemi di tipo) per le asserzioni della forma (A0, M0, t0) (soundness); la seconda
stabilisce che ogni schema di M0 è generato come soluzione di (E , G) (completezza).
Notiamo che questo non è esattamente un sse poiché (E , G) potrebbe coinvolgere variabili di tipo non presenti all’inizio.
2.18 Type Inference: W per il lambda-calcolo
Chiudiamo il capitolo presentando la forma originaria dell’algoritmo di Hindley-Milner[37] applicato ai termini del lambda-calcolo: variabili, astrazioni, applicazioni. Come prima cosa introduciamone la struttura e rimandiamo a dopo le
precisazioni sugli operatori utilizzati.
• Input: La coppia ( , ) dove rappresenta l’ambiente ed il termine da tipare. • Output: La coppia ( , ) dove rappresenta la sostituzione calcolata e il
tipo inferito. 1. W = ([] , instantiate(Ts)) dove ( ) ∈ 2. W( ) = let( ) = W( \ ) , fresh in ( ) 3. W( ) = let( ) = W( ) ( ) = W( ) = mgu( ) , fresh in ( )
Il primo caso è quello che riguarda le variabili. W restituisce come risultato la sostituzione vuota (parentesi quadre bilanciate) e una generica istanza dello schema
Definizione. Un tipo è una generica istanza di uno schema di tipo Ts= se esiste una sostituzione S con S = per tutte le che appartengono alle variabili
libere (non legate) di Ts tale che e S (il tipo raffinato con la sostituzione S)
sono sintatticamente equivalenti.
Il secondo caso è quello che riguarda le astrazioni. W come prima cosa, sfruttando il costrutto let ed una chiamata ricorsiva, calcola la sostituzione ed il tipo che sono rispettivamente la sostituzione ed il tipo calcolati in un ambiente in cui alla variabile
x è stata associata la variabile di tipo fresh (nuova) (in accordo con la prima regola). Alla fine restituisce la sostituzione , appunto, ed il tipo freccia inferito che ha come codominio (a destra della freccia) il tipo e come dominio il tipo calcolato raffinando con la sostituzione .
L’ultimo caso, il più complesso, è quello che coinvolge le applicazioni. W, sfruttando il let ed una chiamata ricorsiva, inferisce un tipo per il termine e calcola la corrispondente sostituzione . Stessa cosa per il termine , con la però sostanziale differenza che la chiamata ricorsiva di W viene fatta prendendo in input l’ambiente raffinato con la sostituzione appena calcolata. viene fornita come output. La sostituzione viene calcolata come mgu (most general unifier, vedere definizione successiva) tra il tipo raffinato con la sostituzione ed il tipo freccia con variabile fresh. Come risultato finale, W restituisce la sostituzione ottenuta
componendo le tre precedenti ed il tipo ottenuto raffinando con .
Definizione. Dati due tipi e , il most general unifier (il più generale degli
unificatori, mgu) tra questi è una sostituzione S tale che . Se i due tipi non possono essere unificati, mgu restituisce un errore (nel caso dell’algoritmo da noi implementato una Top Substitution).
Da notare, che l’implementazione che verrà in seguito discussa, presenta molti più costrutti di quelli del lambda-calcolo, ma dell’algoritmo W conserva l’essenza
composizionale dei raffinamenti successivi (vedere più avanti la parte riguardante
l’implementazione e l’appendice che mostra l’algoritmo W adattato per Sigma_X presentato in stile funzionale).
