Sull'inferenza di tipi polimorfi

1. INTRODUZIONE

Per il problema dell' inferenza dei tipi nei linguaggi funzionali è stato proposto un algoritmo che si basa sull' interpretazione astratta. Tale algoritmo riesce a tipizzare correttamente più termini di quello di Damas-Milner (tra i più diffusi tra quelli adottati nei linguaggi funzionali) ma non ha la stessa potenza di quello di Milner-Mycroft, che però è in generale indecidibile. A parte questi risultati, però, non si avevano elementi per classificare l' algoritmo proposto. In un altro articolo è stato dimostrato che il problema dell' inferenza dei tipi con l' algoritmo di Milner-Mycroft è equivalente al problema della semiunificazione; si cita inoltre il fatto che la semiunificazione uniforme, cioè quella che risolve una disequazione su un solo termine, è decidibile. Siccome particolari funzioni ricorsive danno luogo a un problema di unificazione uniforme, è stato quindi oggetto di studio confrontare se l' algoritmo basato sull' interprete astratto risolva correttamente i casi della ricorsione uniforme e che legame abbia con la semiunificazione. I principali risultati sono stati che il sistema di interpretazione astratta fornisce una soluzione equivalente a quella di un particolare problema di semiunificazione; in particolare il problema di semiunificazione risolto dal sistema dell' interpretazione astratta è lo stesso di quello risolto dall' algoritmo di Milner-Mycroft, tranne per il fatto che le semiunificazioni nel sistema dell' interpretazione astratta sono messe in t-upla tra loro, mentre le altre appaiono distinte nel sistema di equazioni e disequazioni risultante. Inoltre, è stato confermato che nel caso della ricorsione lineare uniforme i risultati raggiunti dai 2 sistemi sono equivalenti (infatti in tale caso si ha un' unica disequazione indipendente in entrambi i sistemi). Sono anche stati individuati ulteriori esempi che mostrano l' efficacia del sistema di interpretazione astratta, oltre a quelli mostrati in [GL3].

Di seguito, verrà prima illustrato il problema della tipizzazione in generale; successivamente si introdurrà l' interpretazione astratta e il sistema basato su essa per l' inferenza di tipi utilizzato in [GL3]. Si procede poi a delineare il problema della semiunificazione e il suo legame con la tipizzazione per discutere, infine, dei risultati raggiunti confrontando i due sistemi.

2. IL PROBLEMA DELL' INFERENZA DEI TIPI

Nella programmazione funzionale si prevede la possibilità di dichiarare funzioni che possono in seguito essere richiamate sia per essere eseguite con un’ opportuna lista di argomenti in ingresso sia come argomenti di altre funzioni. Un sistema di tipi ([CAR97]) associato al linguaggio definisce come tale linguaggio classifica espressioni e valori in tipi, come esso li manipola e come questi interagiscono tra di loro. Tale classificazione, oltre a portare altri vantaggi, permette di evitare operazioni invalide o errate in quanto non semanticamente appropriate per il tipo di dato stesso. Nei linguaggi con scoping statico ([CAR85]), i controlli sulla sicurezza dei tipi possono essere effettuati a tempo di compilazione. In alcuni linguaggi imperativi, i tipi sono esplicitamente dichiarati dal programmatore al momento della dichiarazione delle relative variabili o procedure. In molti linguaggi funzionali con scoping statico, invece, al programmatore non è esplicitamente richiesto di specificare i tipi delle funzioni e costanti che vengono usate nel corso delle varie dichiarazioni; il compito di inferire tali informazioni è lasciato al linguaggio di programmazione, che deve quindi avere un opportuno sistema di inferenza dei tipi

([PIE02]). La scelta più diffusa nei linguaggi di programmazione funzionali è di avere come sistema dei tipi il lambda calcolo semplicemente tipato e come sistema di inferenza dei tipi quello di Damas-Milner ([DM82]); tale sistema di inferenza funziona in tempo polinomiale se usato su un frammento di

linguaggio senza il costrutto "let" e esponenziale altrimenti; in ogni caso l' algoritmo termina e la tipizzazione con questo algoritmo è decidibile. Ad ogni modo, adottando un sistema di tipi più

complesso, come ad esempio il "System F" di Reynolds ([REY2]), il problema di inferire il tipo diventa indecidibile e l' algoritmo di Damas-Milner copre, quindi, solo un ristretto numero di casi di tale

sistema e non individua il tipo più generale. Il "System F", infatti, realizza il polimorfismo di tipo "impredicative", ovvero il tipo che viene istanziato nel polimorfismo può a sua volta essere un tipo polimorfo (e quindi la quantificazione sui tipi non appare necessariamente come prefisso dell’ espressioni di tipi) ([REY74]). Un algoritmo d' inferenza dei tipi che realizza il polimorfismo di tipo "predicative" ([MIT90]) è stato proposto ed è noto come calcolo di Milner-Mycroft ([MYCROFT2]); tale sistema di inferenza di tipi, che differisce da quello di Damas-Milner solo per il trattamento delle funzioni ricorsive, risulta però anch' esso indecidibile. Uno dei problemi più discussi in letteratura a proposito dell' algoritmo di Damas-Milner è che, nel caso di dichiarazione di una funzione ricorsiva, all' interno della sua definizione la funzione stessa può essere usata solo in maniera "monomorfa", ovvero tutte le sue occorrenze prendono lo stesso tipo di argomenti e restituiscono lo stesso tipo come risultato; la funzione stessa può essere usata in maniera polimorfa solo all' esterno del corpo della sua

dichiarazione. Ad esempio, nel linguaggio funzionale ML la dichiarazione fun map f l = if null l then nil else f (hd l):: map f (tl l) AND

squarelist l = map (fun x : int -> x * x) l;

restituisce per map il tipo (int -> int ) -> int list -> int list , dove la sequenza di dichiarazioni fun map f l = if null l then nil else f (hd l):: map f (tl l);

squarelist l = map (fun x : int -> x * x) l; produce il tipo (a -> b ) -> a list -> b list.

3. L' INTERPRETAZIONE ASTRATTA

Normalmente, per analizzare la semantica di un linguaggio, si sviluppa un opportuno algoritmo o teoria e si procede quindi a dimostrare che i risultati ottenuti con l' algoritmo sviluppato sono gli stessi della funzione di valutazione semantica.

Nell' interpretazione astratta ([COU77], [COU79]), i domini semantici sui quali si è introdotta la funzione di valutazione semantica diventano il dominio concreto. A partire dal dominio concreto, si astrae alcune sue caratteristiche, con perdita di informazione, per creare un dominio astratto in grado di evidenziare quanto più possibile la proprietà da esaminare. Il dominio astratto, grazie al processo di astrazione, dovrebbe essere più semplice di quello concreto e in generale portare con sé solo le informazioni strettamente necessarie per la proprietà che si vuole evidenziare con la valutazione semantica. E' richiesto che sia il dominio concreto che quello astratto abbiano la struttura algebrica di reticoli completi. Si introducono quindi 2 funzioni, una di concretizzazione e una di astrazione, che permettono di passare da un elemento del dominio concreto a uno di quello astratto e viceversa (è da notare che in genere il dominio concreto ha la struttura di un insieme delle parti di modo che a un valore astratto corrispondono più valori "concreti" che vengono raggruppati in uno stesso insieme). Sia la funzione di astrazione che quella di concretizzazione devono essere monotone. Le operazioni di concretizzazione e astrazione devono inoltre soddisfare le proprietà delle connessioni di Galois, ovvero ogni elemento del dominio concreto deve essere nella relazione del dominio concreto con l' elemento che si ottiene applicando la funzione di concretizzazione al risultato dell' applicazione della funzione di astrazione all' elemento concreto stesso, mentre nel dominio astratto, l' elemento che si ottiene

applicando la funzione di astrazione al risultato dell' applicazione della funzione di concretizzazione a un qualsiasi elemento astratto deve essere nella relazione del dominio astratto con l' elemento astratto stesso. Per ogni operatore o costrutto della semantica concreta, si provvede quindi a dare un opportuno equivalente astratto che sia localmente corretto, ovvero tale che nel dominio concreto l' operatore applicato agli argomenti è sempre in relazione con la concretizzazione dell' operatore astratto applicato all' astrazione dei singoli argomenti su cui era stato applicato l' operatore concreto. Il calcolo della funzione di valutazione semantica nel dominio astratto definisce una funzione di valutazione che in generale, proprio per gli aspetti di astrazione e approssimazione introdotti nel dominio astratto, è meno precisa di quella del dominio concreto; comunque, proprio perché il dominio astratto può essere più semplice di quello concreto, il calcolo della funzione di valutazione astratta può essere più semplice e in generale terminare, mentre il calcolo del minimo punto fisso della semantica concreta richiede in generale un numero infinito di passi e può portare all' indecidibilità della proprietà. La funzione di valutazione semantica del dominio astratto è comunque corretta per costruzione, quindi se una proprietà vale nella semantica astratta allora vale anche in quella concreta. La funzione di valutazione semantica rappresenta quindi un algoritmo, in generale approssimato, ma corretto per costruzione, per analizzare la proprietà presa in considerazione.

4. UN SISTEMA PER L' INFERENZA DEI TIPI BASATO SULL'

INTERPRETAZIONE ASTRATTA

E' stato proposto un algoritmo per l' inferenza dei tipi basato sull' interpretazione astratta. Per

semplicità, in tale approccio non è stato considerato la presenza nel linguaggio del costrutto sintattico let; comunque, nonostante tale presenza faccia aumentare il tempo necessario per l' algoritmo di analisi a inferire i tipi, essa non modifica la decidibilità del problema d' inferenza stesso: è stato infatti

dimostrato ([HEN92]) che la difficoltà della decidibilità dell' inferenza dei tipi è in realtà contenuta nella definizione di una singola funzione ricorsiva, ovvero che il problema della decidibilità dell' inferenza dei tipi può essere ridotto alla decidibilità di una singola dichiarazione di funzione ricorsiva. (In particolare, l' inferenza dei tipi nel sistema di Damas - Milner senza let è eseguibile in tempo

polinomiale, quella con il let in tempo esponenziale). (Nelle osservazioni successive verrà tralasciata la presenza del let). Lo scopo dell' algoritmo proposto era di essere decidibile e fornire risultati migliori di quello dell' algoritmo di Damas - Milner. Nel caso dell' inferenza dei tipi, il dominio concreto è il sistema di inferenza dei tipi come sarebbero a run-time, mentre il dominio astratto prova a modellare i tipi come determinati in analisi statica. L' ordinamento parziale nel dominio concreto è la relazione di antistanza: un tipo t1 è in relazione con il tipo t2 se e solo se t2 è un' istanza di t1. Un tipo può essere

istanza di un altro in quanto sono presenti i monotipi come introdotti da Hindley, ovvero un tipo può essere una variabile di tipo tipo. Ad esempio, quando si introduce la funzione identità

fun f x = x;

il tipo restituito è a -> a, dove la a è una variabile che può successivamente essere istanziata, come nel caso in cui si applichi la f a un intero (e quindi in quel caso la f è usata come se avesse tipo int -> int). La presenza dei monotipi alla Hindley e di un modo per avere i tipi funzionali porta alla presenza nel dominio di catene crescenti infinite che determinano, in generale, la non terminazione del calcolo del minimo punto fisso. Il dominio astratto è analogo a quello concreto; tuttavia è stato notato che, a causa della presenza dei monotipi, sia necessario tenere nel dominio astratto anche un insieme di vincoli che possono emergere durante la dichiarazione della funzione stessa e porre restrizioni sui monotipi introdotti in precedenza. Ad esempio, nella dichiarazione

fun f x = x +1;

dove il "+" sia definito solo tra interi, quando si trova "fun f x" il tipo associato ad x è un nuovo monotipo, in quanto fino a quel momento non è presente nessuna informazione che forzi una scelta particolare per x. Tuttavia, quando si giunge a valutare x + 1, siccome il + è solo tra interi, risulta evidente che la x stessa, e quindi il monotipo a essa assegnato, debba essere di tipo intero e questo cambiamento deve ripercuotersi su tutta la dichiarazione della funzione, comprese eventuali altre occorrenze della x stessa. E' stato quindi individuato come dominio astratto la coppia (tipo, vincoli associati). I vincoli associati sono visti come delle sostituzioni; una sostituzione s1 è in relazione con

una sostituzione s2 se esiste una terza sostituzione s3 tale che applicare prima s1 e poi s3 fornisce come

risultato la sostituzione s2. Il dominio astratto definito in tal modo presenta comunque catene di

lunghezza infinita e quindi il calcolo della semantica astratta in alcuni casi necessita di un calcolo di minimo punto fisso che richiederebbe infiniti passi, portando alla non terminazione dell' algoritmo e

alla non decidibilità dell' inferenza. Per risolvere il problema, quando si incorre in tali occorrenze, invece di lasciare che il sistema affronti infiniti passi, si usa un algoritmo di widening. Gli algoritmi di widening sono degli algoritmi che servono per calcolare un' approssimazione del minimo punto fisso, nel senso che il risultato di un algoritmo di widening è un maggiorante, secondo la relazione del dominio sul quale si calcola il punto fisso, del minimo punto fisso stesso; ovviamente qualsiasi algoritmo che fornisce un maggiorante del punto fisso è un algoritmo di widening, ma saranno da preferirsi gli algoritmi che individuano i maggioranti quanto più vicino possibile al punto fisso stesso (sempre sotto la condizione che gli algoritmi che li trovano siano più efficaci di quello del calcolo del punto fisso stesso). Nel sistema dell' interpretazione astratta per l' inferenza di tipi, viene stabilito, quindi, un certo numero di passi k entro il quale il calcolo del punto fisso deve terminare; se dopo tale numero di passi non è ancora concluso, si applica un particolare algoritmo di widening (proposto in [GL3]) per trovare un' eventuale tipo risultante. L' algoritmo di widening proposto, in base al risultato delle ultime due approssimazioni del calcolo del punto fisso, cerca di ottenere una nuova

approssimazione sfruttando i vincoli calcolati fino a quel momento; l' approssimazione risultante, se trovata, è il risultato della soluzione di un opportuno sistema di unificazioni. E' stato però dimostrato che l' algoritmo così fatto restituisce lo stesso risultato indipendentemente dal passo k(>1) al quale viene applicato. Il widening restituisce fornisce quindi una semantica ancora più approssimata di quella calcolata dall' interpretazione astratta, quindi il tipo risultante, se trovato, sarà ancora corretto secondo la semantica, ma più approssimato.

Di seguito vengono riportate le regole del sistema d' inferenza dei tipi presente in [GL3]. Nelle seguenti regole, H è un' ambiente che associa ad alcune variabili una coppia (tipo, vincoli); da questo ambiente si tipizza una termine del linguaggio funzionale [BAR84], ottenendo (come risultato del sistema di inferenza stesso) un tipo e un vincolo risultante. Il simbolo ε rappresenta il fatto che la regola usata non introduce nessun vincolo addizionale (e quindi la sostituzione non ha nessun effetto

rilevante). q 1 e q 2 sono variabili fresh, indipendenti da quelle introdotte in precedenza nell’ ambiente

H.

H |- int n

->

(int, ε)

(Regola 1)

H |- id x

->

H(x)

(Regola 2)

H |- e

1

->

(τ

1

, γ

1

)

H |- e

2

->

(τ

2

, γ

2

)

γ

= unify (τ

1

= int ; τ

2

= int; eqn(γ

1

); eqn (γ

2

))

_____________________________________________

(Regola 3)

H |- e

1

+ e

2

->

( int, γ

)

H |- e

1

->

(τ

1

, γ

1

)

H |- e

2

->

(τ

2

, γ

2

)

H |- e

3

->

(τ

3

, γ

3

)

γ = unify (τ

1

= bool ; τ

2

= τ

3

; eqn(γ

1

); eqn (γ

2

); eqn (γ

3

) )

______________________________________________

(Regola 4)

H |- if e

1

then e

2

else e

3

->

( γ(τ

2

), γ)

H |- e

1

->

(τ

1

, γ

1

)

H |- e

2

->

(τ

2

, γ

2

)

γ = unify (τ

1

= τ

2

-> q

2

; eqn(γ

1

); eqn (γ

2

))

______________________________________________

(Regola 5)

H |- e

1

e

2

->

( γ(q

2

), γ)

H[x<- (q

1

,ε)] |-

e

1

->

(τ

2

, γ

2

)

τ

1

= γ

2

(q

1

)

______________________________________________

(Regola 6)

H |- λ x . e

1

->

(τ

1

-> τ

2

, γ

2

)

H |- μ f. λ x . e

1

->

fix

(τ

1

, γ

1

)

______________________________________________

(Regola 7)

H |- μ f. λ x . e

1

->

(τ

1

, γ

1

)

Il sistema fix:

H |- μ f. λ x . e

1

->

0

( a , ε)

(Regola 8)

H |- μ f. λ x . e

1

->

(n-1)

(τ

1

, γ

1

)

H |- μ f. λ x . e

1

,( τ

1

, γ

1

)

->

passo

(τ

2

, γ

2

)

______________________________________________

(Regola 9)

H |- μ f. λ x . e

1

->

n

(τ

2

, γ

2

)

(Terminazione con punto fisso)

H |- μ f. λ x . e

1

->

(n-1)

(τ

1

, γ

1

)

H |- μ f. λ x . e

1

->

n

(τ

2

, γ

2

)

(τ

1

, γ

1

) uguale a meno di renaming a (τ

2

, γ

2

)

______________________________________________

(Regola 10a)

H |- μ f. λ x . e

1

->

fix

(τ

2

, γ

2

)

(Terminazione con Widening)

n<=k

H |- μ f. λ x . e

1

->

(n-1)

(τ

1

, γ

1

)

H |- μ f. λ x . e

1

->

n

(τ

2

, γ

2

)

(τ

1

, γ

1

) uguale a meno di renaming a (τ

2

, γ

2

)

______________________________________________

(Regola 10bb)

H |- μ f. λ x . e

1

->

fix

(τ

2

, γ

2

)

H |- μ f. λ x . e

1

->

(k-1)

(τ

1

, γ

1

)

H |- μ f. λ x . e

1

,( τ

1

, γ

1

)

->

passo

(τ

2

, γ

2

)

(τ

1

, γ

1

) non uguale a meno di renaming con (τ

2

, γ

2

)

γ

3

= unify(γ

2

(τ

1

)= τ

2

; eqn(γ

2

))

______________________________________________

(Regola 10bc)

H |- μ f. λ x . e

1

->

fix

(γ

3

(τ

1

), γ

3

)

Il sistema passo:

H[f<- (τ, γ)] |- λx. e

1

->

(τ

2

, γ

2

)

______________________________________________

(Regola 11)

H |- μ f. λ x . e

1

,( τ, γ)) ->

passo

(τ

2

, γ

2

)

Il sistema di inferenza è quindi corretto (per quanto detto in precedenza) ed è risultato migliore di quello proposto da Damas Milner in quanto, in qualche caso di dichiarazione di funzione ricorsiva, riesce a trovare un tipo più generale di quello dell' altro sistema o, talvolta, trova un tipo quando l' altro non lo fa (si veda [GL3] per alcuni esempi in proposito). Si è quindi cercato di capire quali siano le potenzialità di questo algoritmo, cercando di caratterizzare i casi nei quali fornisce lo stesso risultato dell' algoritmo di Milner-Mycroft.

5. SEMIUNIFICAZIONE

Un termine M sussume N (N è istanza di M) se esiste una sostituzione R tale che R(M)=N; in tal caso si scrive M<=N.

Dato un insieme di disequazioni M1<=? N1 ; ... ; Mk <=? Nk con k>0, una sostituzione S si dice semiunificatore delle suddette disequazioni se sono soddisfatte le condizioni S(M1) <= S(N1) ; ...; S(Mk) <= S(Nk) , cioè se esistono le sostituzioni R1, .., Rk tali che R1(S(M1)) = S(N1) ; ...;

Rk(S(Mk))= S(Nk). Si possono anche scrivere sistemi di disequazioni che sono in t-upla tra loro, ad esempio (M1<=? N1 ; ... ; Mk <=? Nk ); la differenza con il sistema non in t-upla è che invece di avere k sostituzioni R1,.. ,Rk possibilmente distinte, in questo caso vi è un' unica sostituzione R per tutte le disequazioni: R(S(M1)) = S(N1) ; ...; R(S(Mk))= S(Nk). E' inoltre noto che ogni sistema di

disequazioni, se risolvibile, ammette un unico semiunificatore più generale, ovvero esiste un' unica sostituzione S che, oltre a essere essa stessa soluzione del sistema, gode della proprietà che per qualsiasi altra sostituzione S' che soddisfa il sistema, per ogni variabile x presente nel sistema stesso, esiste una sostituzione R' tale che R'(S(x))=S'(x). Il problema di trovare la sostituzione S a partire dalle disequazioni proposte è detto problema della semiunificazione ([HEN92]).

Le disequazioni possono essere messe a sistema con delle equazioni per ottenere un sistema di

equazioni e disequazioni (SEI). Un modo di risolvere il sistema (comprese le semiunificazioni in esso presenti) è applicare in un qualsiasi ordine le regole seguenti, dopo aver assegnato un' etichetta i a ogni disequazione in modo che tutte le disequazioni in una stessa t-upla abbiano la stessa etichetta, mentre ogni coppia di disequazioni in t-uple diverse abbia etichette diverse.

1.f(s

1

, … , s

n

) = f(t

1

, … , t

n

)

->

sostituisci con le equazioni

s

1

= t

1

, … , s

n

= t

n

2.f(s

1

, … , s

n

) = g(t

1

, … , t

n

);

f e g simboli di funzione distinti

-> fail

3.f(s

1

, … , s

n

) = x

->

sostituisci con l' equazione x = f(s

1

, … , s

n

)

4.x = f(s

1

, … , s

n

), x occorre in almeno uno degli s

1

,..,

s

n

->

fail (occur check)

5.x = f(s

1

, … , s

n

), x NON occorre in almeno uno degli

s

1

,.., s

n

->

applica x = f(s

1

, … , s

n

) in tutte le

altre equazioni o disequazioni

6. x = x

-> cancella

7.

f(s

₁

, … , s

_n

) <=

_i

f(t

₁

, … , t

_n

)-> sostituisci con

le disequazioni

s

1

<=

i

t

1

, … , s

n

<=

i

t

n

8.x <=

i

t

1

e x <=

i

t

2

->

rimuovi una delle due e aggiungi t

1

= t

2

9.

f(s

1

, … , s

n

) <=

i0

x e esistono x

0

,..,x

k

tali che

x=x

0

, x

i

<

ji

x

i+1

sono disequazioni nel corrente SEI per

0<=i<=k-1 e esiste un l tale che x

n

occorre in s

l

->

fail

10.

f(s

1

, … , s

n

) <=

i0

x e NON esistono x

0

,..,x

k

tali

che x=x

0

, x

i

<

ji

x

i+1

sono disequazioni nel corrente SEI

per 0<=i<=k-1 e esiste un l tale che x

n

occorre in s

l

->

aggiungi l’ equazione x= f(y

11

, … , y

1n

),

dove y

11

… y

1n

sono variabili fresh che non appaiono nel

Il risultato del sistema di unificazioni e semiunificazioni, per come è fatto il sistema di regole, è fatto a sua volta da unificazioni e

semiunificazioni. In particolare, se la soluzione del sistema t1 <= t2 è l' insieme di equazioni eq1 e

disequazioni dq2, le equazioni sono la sostituzione che unifica e le disequazioni quella che andrebbe applicata solo alla parte sinistra. t1 <= t2 vuol dire, per definizione, che esistono R e S sostituzioni tali

che R(S(t1)) = S(t1); eq1 rappresenta quindi la sostituzione S e le disequazioni risolutrici dq2, una volta

trasformate in equazioni scambiando il <= con =, sono quelle che formano la sostituzione R.

Il problema della semiunificazione è, in generale, indecidibile; il sistema precedente, quindi, in alcuni casi non fornirà in alcuni casi nessuna soluzione in tempo finito. (Tuttavia, ad oggi non si è individuato nessun caso in cui questo succeda). Alcuni casi particolari di semiunificazione, comunque, sono invece decidibili (si veda [HEN92] per un elenco): in particolare la semiunificazione uniforme, cioè quella che risolve una disequazione su un solo termine, è decidibile.

Si noti che, siccome le regole precedenti possono essere risolte in qualsiasi ordine, si può pensare di risolvere prima tutte le unificazioni e risolvere, in seguito, un sistema di disequazioni più vincolato del sistema iniziale.

6. SEMIUNIFICAZIONE E TIPIZZAZIONE

Nell' articolo [HEN92] si dimostra che l' inferenza dei tipi per il sistema di Milner-Mycroft è riducibile a un problema di semiunificazione.

Le regole del sistema di Damas-Milner ([DM82]) sono le seguenti.

A{x:

σ }|-x : σ

(TAUT)

A|-e:per ogni t.σ

______________________________________________

(INST)

A|-e : σ[τ /t]

A|-e : σ

t non variabile libera di A

______________________________________________

(GEN)

A|-e : per ogni t.σ

A|- e

1

: τ

1

-> τ

2

A|- e

2

: τ

1

______________________________________________

(APPL)

A|-( e

1

e

2

) : τ

2

A{x: τ

1

}|-e : τ

2

______________________________________________

(ABS)

A|-

λ x.e : τ

1

-> τ

2

A{x: τ

1

}|-e : τ

1

______________________________________________

(FIXM)

A|-fix x.e : τ

1

Nel sistema di Damas-Milner la tipizzazione è decidibile. Il sistema di Milner-Mycroft

([MYCROFT2]) differisce dal precedente per la sola regola riguardante le funzioni ricorsive; la

tipizzazione in esso è, in generale, indecidibile. (Questo giustifica la particolare attenzione, nel sistema di inferenza dei tipi, per le funzioni ricorsive). Il sistema di Milner-Mycroft presenta, quindi, tutte le regole precedenti, eccetto la regola FIXM, in esso sostituita dalla regola FIXP seguente:

A{x:σ}|-e : σ

______________________________________________

(FIXP)

A|-fix x.e : σ

La differenza tra la regola FIXM e FIXP è il dominio semantico che si associa alla funzione ricorsiva (e che quindi la regola fornisce come risultato). Nella regola FIXM, tauuno è un singolo tipo. Nella regola FIXP, σ è uno schema di tipi, della forma per ogni t.σ1; qualsiasi istanziazione delle variabili t presenti

in σ1 produce un tipo che può essere usato come tipo della funzione (anche se in precedenza si era

scelto, per un' altra occorrenza della funzione ricorsiva, una sostituzione delle variabili diversa e incompatibile con quella che si decide di usare in un' altra chiamata).

Nell' articolo [HEN92] si mostra l' equivalenza del sistema di Milner-Mycroft con il seguente sistema; la presenza del per ogni indica che in realtà si è in presenza di uno schema di tipi invece che di un tipo semplice. La definizione di variabili libere di un termine è la stessa di quella presente nel lambda calcolo.

A{x: per ogni α. τ }|-x : τ [s/

α

]

(TAUT')

A|- e

1

: τ

1

-> τ

2

A|- e

2

: τ

1

______________________________________________

(APPL')

A|-( e

1

e

2

) : τ

2

A{x: τ

1

}|-e : τ

2

______________________________________________

(ABS')

A|-

λ

x.e : τ

1

-> τ

2

A{x: per ogni α. τ }|-e : τ

α = variabili libere(τ) - variabili libere (A)

______________________________________________

(FIXP')

A|-fix x.e : τ [s/

α

]

E il sistema precedente, al fine di calcolare il sistema di equazioni e disequazioni che riescono a

tipizzare una singola funzione ricorsiva, risulta portare gli stessi risultati del seguente sistema, nel quale a partire da un ambiente e 2 vettori di tipi di variabili si inferisce il tipo di un termine. Il “;” nelle seguenti regole indica che al vettore o ambiente già presente si aggiunge l’ associazione o il tipo/i proposto/i. τ^

1 e τ^2

sono dei vettori di tipi; {}^ indica il vettore vuoto.

(τ, τ

^ 1

)<=( τ', τ

^1

)

______________________________________________

(TAUT'')

(A;x: τ), τ

^ 1

, τ

^2

|- x : τ'

τ'= τ

x

-> τ

(A;x: τ

x

), τ

^1

,( τ

^2

; τ

x

)|- e : τ

______________________________________________

_(ABS'')

A, τ

^ 1

, τ

^2

|-

λ x.e : τ'

τ = τ'-> τ''

A, τ

^ 1

, τ

^2

|- e : τ'

A, τ

^ 1

, τ

^2

|- e' : τ''

______________________________________________

_(APPL'')

A, τ

^ 1

, τ

^2

|-

e e' : τ''

τ

f

= τ

(A;f: τ

f

),( τ

^1

; τ

^2

), {}^ |- e : τ

______________________________________________

(FIXP'')

A, τ

^ 1

, τ

^2

|-

fix f.e : τ

La risoluzione del sistema appena proposto, in modo analogo a quanto mostrato in [HEN92], conduce a un SEI la cui soluzione determina il tipo della funzione ricorsiva.

7. ESEMPI DI TIPIZZAZIONE CON L' INTERPRETE ASTRATTO

Il calcolo del punto fisso in alcuni casi trova un tipo proprio uguale a quello di Mylner-Mycroft (e quindi migliore di quello di Damas-Milner). (Le variabili usate in ogni singolo esempio non sono correlate in nessun modo con quelle degli altri esempi).

μ f. λ g. λ n. λ x. λ z.

if (n==0) then g(x)

else f (λ y. λ h. z) n-1 (λ q.q) z

Tipo corretto calcolato in 3 passi del sistema del calcolo del punto fisso dell' interpretazione astratta. ( b -> ( c -> d )) -> int -> b -> d-> (c->d)

(La funzione seguente è riportata in [COU97]).

μ f. λ w. λ g. λ n. λ x.

if (n==0) then g(x)

else f(w) (λ y. λ h. g(h(y))) n-1 x w

Tipo corretto calcolato in 3 passi del sistema del calcolo del punto fisso dell' interpretazione astratta. (a ->a)-> ( a->b) -> int -> a -> b

La coppia di esempi seguente fa vedere che non è influente il numero o il tipo delle variabili all' interno della funzione ricorsiva per stabilire il numero di passi necessario per raggiungere il punto fisso, ma la posizione delle variabili stesse all' interno della definizione ricorsiva che fa variare con che cosa le variabili stesse sono unificate all' interno di un singolo passo del calcolo del punto fisso (e quindi il tipo risultante cambierà di conseguenza).

μ f. λ w. λ g. λ n. λ x. λ z.

if (n==0) then g(x)

else f(w) (λ y. λ h. g(h(y))) n-1 x z w

Tipo corretto calcolato in 3 passi del sistema del calcolo del punto fisso dell' interpretazione astratta. (a ->a)-> ( a->b) -> int -> a -> c -> b

I seguenti esempi sono esempi di una successione di termini che richiedono un numero sempre maggiore di passi per raggiungere il punto fisso.

μ f. λ w. λ g. λ n. λ x. λ z.

if (n==0) then g(x)

else f(w) (λ y. λ h. g(h(y))) n-1 x w z

Tipo corretto calcolato in 4 passi del sistema del calcolo del punto fisso dell' interpretazione astratta. (a ->a)-> ( a->b) -> int -> a -> (a->a) -> b

μ f. λ w. λ g. λ n. λ x. λ z. λ q.

if (n==0) then g(x)

else f(w) (λ y. λ h. g(h(y))) n-1 x w z q

Tipo corretto calcolato in 5 passi del sistema del calcolo del punto fisso dell' interpretazione astratta. (a ->a)-> ( a->b) -> int -> a -> (a->a) -> (a->a) -> b

μ f. λ w. λ g. λ n. λ x. λ z. λ q. λ j. λ k. λ c. λ d. λ e.

λ i. λ l. λ m. λ o. λ r. λ s. λ t. λ u.

if (n==0) then g(x)

else f(w) (λ y. λ h. g(h(y))) n-1 x w

z q j k c d e i l m o r s t u

Tipo corretto calcolato in 18 passi del sistema del calcolo del punto fisso dell' interpretazione astratta. (a ->a)-> ( a->b) -> int -> a -> (a->a) -> (a->a) -> (a->a) -> (a->a) -> (a->a) -> (a->a) -> (a->a) -> (a->a) -> (a->a) -> (a->a) -> (a->a) -> (a->a) -> (a->a) -> (a->a) -> (a->a) -> b

L' esempio seguente mostra che l' algoritmo di interpretazione astratta può fornire il tipo corretto anche nei casi dove vi è più di una chiamata di funzione ricorsiva. Requisito necessario ma non sufficiente affinché questo avvenga è che i tipi associati alle singole chiamate della funzione ricorsiva siano unificabili tra di loro.

μ f. λ u. λ v. λ w. λ x. λ y. λ z.

if (0==0) then

if (0==0) then u(v)

else f(λ l. u(l(v))) w (λ j.j)

(λ t. λ k. k) (λ d.d) (λ e.e)

else

if (0==0) then x(y)

else f (λ t. λ m. m) (λ n.n) (λ o.o)

(λ r. x(r(y))) z (λ q.q)

Tipo corretto calcolato in 3 passi del sistema del calcolo del punto fisso dell' interpretazione astratta. (a ->(b->b)) -> a -> (a->a) -> (c ->(b->b)) -> c -> (c->c) -> (b->b))

La dichiarazione di funzione successiva non viene tipata nel sistema di Damas-Milner, riceve un tipo dall’ interprete astratto e uno più generale da quello di Milner-Mycroft.

μ f. λ x. λ w. λ z. λ r. λ s. λ t.

if (0==0) then f(x) w

z (w(x)) (λ y. r) s t

else f(x) (λ h. r) t r

s w t

Il tipo calcolato in 3 passi del sistema del calcolo del punto fisso dell' interpretazione astratta è a -> ( a->b) -> ( a->b) -> b -> ( a->b) -> ( a->b) -> c ; quello calcolato da Milner-Mycroft è

a -> ( a->b) -> c -> d -> e -> j -> k (dove il secondo tipo è in realtà uno schema di tipi

opportunamente quantificato e le cui variabili introdotte sono indipendenti da quelle del tipo dell’ altro sistema).

Anche nell' esempio successivo il tipo restituito dall' algoritmo basato sull’ interpretazione astratta è meno generale di quello inferito dall’ algoritmo di Milner-Mycroft.

μ p. λ x. if p(1) then p(x) else p(x)

Il tipo calcolato in 2 passi del sistema del calcolo del punto fisso dell' interpretazione astratta è int->bool, mentre quello calcolato da Milner-Mycroft è a->b (opportunamente quantificato).

In altri casi l ' algoritmo di interpretazione astratta non fornisce nessun tipo mentre quello di Milner-Mycroft vi riesce; si dimostrerà di seguito che questi casi succedono solo in presenza di 2 o più chiamate della funzione ricorsiva (ma non in uno qualsiasi di quei casi, come mostrato dagli esempi precedenti).

8. OSSERVAZIONI SUL SISTEMA BASATO SULL’ INTERPRETAZIONE

ASTRATTA

Teorema: Se una variabile è nell' ambiente, o è una variabile associata a una funzione

ricorsiva oppure ha come tipo una variabile monomorfa e la sostituzione associata è

nulla.

Prova: per induzione sulle regole. Nessuna regola toglie qualcosa dall' ambiente o modifica qualcosa già presente. La regola dell' astrazione aggiunge la coppia (f1, ε) con f1 variabile "fresh" di tipo

(appartenente al sistema monomorfo) e ε sostituzione vuota. L' unica altra regola che modifica l' ambiente è quella per le funzioni ricorsive, la quale introduce nell' ambiente la sola funzione ricorsiva.

Teorema: tipizzando una funzione a partire da un ambiente vuoto, ad ogni singolo passo

del punto fisso, il vincolo della funzione ricorsiva non influenza la funzione stessa o

alcuna delle variabili in essa contenute.

Prova: per induzione sulle regole (e poi per induzione sulla struttura del termine interno alla funzione ricorsiva).

Al passo zero del punto fisso si introduce nell' ambiente come tipo della funzione variabile "fresh" di tipo (appartenente al sistema monomorfo) e come sostituzione associata quella vuota.

Per tutte le variabili interne, ogni volta che si incontra una λ astrazione, viene inserita nell' ambiente una variabile fresh che non può essere nessuna di quelle presente nel vincolo al passo precedente. In ogni regola, il vincolo fornito come risultato dipende da quelli relativi ai suoi sottotermini: siccome tali sottotermini si riconducono alle variabili fresh appena introdotte, i vincoli si riferiranno a tali variabili fresh e quindi non a eventuali variabili presenti prima della dichiarazione di f che non compaiono nella definizione ricorsiva o a quelle presenti nel vincolo associato alla funzione ricorsiva stessa.

Il vincolo riferito alla funzione ricorsiva stessa usa come tipo della funzione quello del passo precedente, mentre il resto dei vincoli si riferisce alle variabili fresh presenti nel passo; sono eventualmente presenti unificazioni tra le variabili del tipo della funzione del passo precedente con quelle fresh ottenute durante la tipizzazione del passo corrente. Il tipo fornito come risultato del passo è espresso in funzione delle variabili fresh, mentre il vincolo si riferisce al tipo del passo precedente: applicandolo al tipo calcolato non si ottiene nessun effetto.

Analogamente, al passo successivo il tipo della funzione coinvolgerà le variabili del passo precedente mentre in quel passo saranno introdotte nuove variabili fresh distinte dalle precedenti.

Teorema: a partire da un ambiente non vuoto, incontrando una funzione ricorsiva che

nel suo corpo non richiama nessuna delle variabili presenti nell' ambiente che la

precede, il vincolo della funzione ricorsiva non influenza la funzione stessa o alcuna

delle variabili ricorsive trovate dopo la dichiarazione della funzione stessa.

In base ai risultati precedenti, a partire da un' ambiente vuoto, il vincolo calcolato alla fine di un passo può influenzare solo le variabili esterne alla dichiarazione della funzione ricorsiva stessa; nel vincolo può essere presente l' unificazione tra il tipo della funzione ricorsiva introdotto nell' ambiente in quel passo e le variabili fresh del passo stesso, ma non tra il tipo calcolato alla fine del passo e le variabili di tipo introdotte nello stesso (che potrebbero altrimenti far fallire il calcolo).

Per come è fatta la regola per estrarre le variabili dall' ambiente, non si distingue se una variabile è stata introdotta all' interno di una dichiarazione ricorsiva o prima di essa (la regola si limita a restituire cosa prevede l' ambiente per essa).

Teorema: A partire da un ambiente vuoto, se una variabile è nell' ambiente, o è una

variabile associata a una funzione ricorsiva (e la sostituzione associata non la influenza)

oppure ha come tipo una variabile monomorfa e la sostituzione associata è nulla.

Prova: per induzione sulle regole.

Nessuna regola toglie qualcosa dall' ambiente o modifica qualcosa già presente.

La regola dell' astrazione aggiunge la coppia (f1, ε) con f1 variabile "fresh" di tipo (appartenente al

sistema monomorfo) e ε sostituzione vuota.

Il vincolo relativo alla funzione ricorsiva presente nell' ambiente, per quanto osservato in precedenza, non influenza il tipo della funzione ricorsiva stessa presente in quello stesso ambiente.

Per il teorema precedente, ogni volta che si estrae dall' ambiente si ha un vincolo che non influenza la variabile appena estratta. Per i teoremi precedenti, a partire dall' ambiente vuoto, il vincolo della

funzione ricorsiva non influenza nessuna delle variabili che compaiono successivamente, in quanto non contiene nessuna di esse.

Per il lemma 14, e successivi corollari 15, 16 e 17 a pag.15 dell’ articolo [GL3], e per la definizione di <= data a pagina 12 del suddetto, il risultato del corollario 17 può essere riscritto come:

esiste una sostituzione θ tale che (τ 2,γ2)=( θ(τ 1), γ1 θ).

Allora ogni passo si ottiene dal precedente applicando una sostituzione; applicando in ordine queste sostituzioni se ne ottiene una che permette di passare dal passo 0 al passo dove si raggiunge il punto fisso (ammesso che il punto fisso sia effettivamente raggiunto). Come conseguenza di questo, se il punto fisso viene raggiunto, tutti i tipi calcolati alla fine di ogni passo sono unificabili tra loro in quanto al più si possono applicare ad essi sostituzioni tali che rendano qualsiasi coppia di tipi entrambi uguali a quelli del punto fisso. Un risultato analogo vale per i vincoli.

Ad ogni passo dopo il primo, la dimostrazione individuata dal sistema di inferenza dei tipi basato sull’ interpretazione astratta è analoga a quella del passo precedente. Infatti, ad ogni passo a partire dal primo, per la regola

H[f<- (τ

n

, γ

n

)] |- λx.epr

->

(τ

n+1

, γ

n+1

)

il tipo calcolato alla fine del passo è quello risultante dalla tipizzazione dell' espressione epr; siccome epr, definizione della funzione ricorsiva, è sempre la stessa a ogni passo e il sistema è deterministico, ogni passo applicherà lo stesso numero e tipo di regole nel solito ordine del passo precedente. Tuttavia, cambia l'ambiente nel quale tali regole vengono eseguite; questo dà luogo a vincoli (e tipi) diversi ad ogni passo. In particolare, le uniche differenze rispetto all' ambiente di un altro passo sono proprio il tipo della funzione ricorsiva e il vincolo associato.

Ad ambiente vuoto, considerare di calcolare alla fine di un passo (e quindi introdurre nell' ambiente al passo successivo) la funzione o un renaming di essa, che non coinvolga nessuna delle variabili viste in precedenza, non cambia il risultato del calcolo del punto fisso. (La sostituzione coinvolge in ugual modo il tipo della funzione e i vincoli ad essa associati alla fine di un singolo passo e viene applicata alla fine del passo dopo aver calcolato i risultati come non influenzati dal suo renaming). Continuano infatti a valere tutti i risultati precedenti, in particolare la non interferenza tra il vincolo della funzione e il tipo della funzione stessa e il fatto che il vincolo al passo successivo non influenzi le variabili

ricorsive; durante il calcolo del singolo passo, quindi, nuovamente non vi sarà ancora interferenza tra il tipo della funzione e i vincoli ad essa associati; le variabili estratte ad ogni singolo passo continueranno ad essere fresh rispetto al tipo della funzione (in quanto fresh rispetto a tutto il sistema) e quindi non vi sarà interferenza nemmeno tra le variabili fresh e il vincolo associato alla funzione ricorsiva. In

particolare, le equazioni risultanti nel vincolo di fine passo saranno le stesse che si ottenevano prima, soltanto che dove prima compariva il tipo della funzione, adesso esso compare con il renaming applicato.

Si noti che anche il renaming può essere visto come una sostituzione; applicare il renaming fa ancora in modo che esista una sostituzione che permetta di passare dal tipo e vincolo del passo precedente a quelli del passo successivo e quindi non modifica la natura del calcolo del punto fisso.

Se si introduce il renaming della funzione allora a questo punto, invece di estrarre

ad ogni passo un tipo fresh dall' ambiente per ogni variabile introdotta all' interno della dichiarazione ricorsiva, si può invece estrarre le vecchie variabili che si estraevano al passo precedente, in quanto esse risulteranno fresh sia rispetto al tipo della funzione che al suo vincolo; le unificazioni

continueranno ancora a coinvolgere variabili fresh come quando le coinvolgevano prima e quindi il risultato non cambia. Le unificazioni, infatti, sono ancora tra il tipo della funzione e delle variabili per esso fresh; le unificazioni ricavate continuano a fallire o essere applicabili negli stessi casi.

Se invece è presente un ambiente prima della dichiarazione ricorsiva, nel sistema originario i nomi riferiti a tali variabili non cambiano tra i vincoli dei vari passi e nel tipo della funzione: esse avranno sempre lo stesso tipo associato. Allora basterà che il renaming introdotto non influenzi in nessun modo tali variabili presenti in precedenza nell' ambiente, in modo che, analogamente a quanto succede nel sistema basato sull' interpretazione astratta, il loro tipo rimanga presente e immutato ad ogni passo.

Assumere che avvenga il renaming può semplificare la scrittura dei vincoli nei passi successivi. Si può considerare che dopo il renaming c' è una specie di garbage collector, ristretto solo all' ambiente presente (il quale è senza puntatori) che elimina le vecchie variabili della funzione ricorsiva e lascia intatte quelle già presenti nell' ambiente prima della funzione ricorsiva. Un modo di implementarlo potrebbe essere preparare,senza applicarla, una sostituzione che coinvolga tutte le variabili che compaiono nel tipo della funzione ricorsiva e poi dopo scorrere l' ambiente esterno la dichiarazione ricorsiva e togliere, man mano che si individuano, tutte le sostituzioni riguardanti le variabili esterne all' interno della sostituzione individuata in precedenza. Tale soluzione risulta tanto più costosa quanto più è complesso l' ambiente esterno, ma rispetto al sistema così come è scritto risulta poi vantaggiosa all' aumentare di passi richiesti per calcolare il punto fisso. Usare il renaming mantenendo opportuni nomi per i tipi introdotti per le variabili all' interno della funzione ricorsiva permette anche di capire meglio, alla fine di ogni passo e quindi anche come risultato del calcolo, il legame tra il tipo delle variabili introdotte all' interno della funzione ricorsiva e quello della funzione ricorsiva stessa, risultato ottenibile nel sistema così come è scritto solo analizzando l' ambiente presente nel calcolo del passo stesso. Di seguito, per semplicità, si penserà di usare il rename delle variabili invece che variabili totalmente fresh. Un altro modo equivalente di calcolare il risultato del sistema di inferenza è applicare il renaming del tipo della funzione ricorsiva prima di introdurla nuovamente nell' ambiente per il calcolo del passo successivo; in questo modo il legame con le variabili interne al corpo della definizione ricorsiva risulta più evidente.

Secondo le indicazioni precedenti, il sistema di inferenza dei tipi basato sull' interpretazione astratta usa le seguenti regole invece di quelle presentate in precedenza

(Terminazione con punto fisso)

H |- μ f. λ x . e

1

->

(n-1)

(τ

1

, γ

1

)

H |- μ f. λ x . e

1

->

n

(τ

2

, γ

2

)

(τ

1

, γ

1

) = (τ

2

, γ

2

)

_______________________________________________________ (Regola 10a)

H |- μ f. λ x . e

1

->

fix

(τ

2

, γ

2

)

(Terminazione con Widening)

n<=k

H |- μ f. λ x . e

1

->

(n-1)

(τ

1

, γ

1

)

H |- μ f. λ x . e

1

->

n

(τ

2

, γ

2

)

(τ

1

, γ

1

) = (τ

2

, γ

2

)

_______________________________________________________ (Regola 10bb)

H |- μ f. λ x . e

1

->fix (τ

2

, γ

2

)

H |- μ f. λ x . e

1

->

(k-1)

(τ

1

, γ

1

)

H |- μ f. λ x . e

1

, ( τ

1

, γ

1

)

->

passo

(τ

2

, γ

2

)

γ

3

=unify(γ

2

(τ

1

)= τ

2

; eqn(γ

2

))

Non ( (τ

1

, γ

1

) = (τ

2

, γ

2

) )

_______________________________________________________ (Regola 10bc)

H |- μ f. λ x . e

1

->

fix

(γ

3

(τ

1

), γ

3

)

Il sistema passo:

(τ

R

, γ

R

) = Renaming ((τ, γ))

H[f<- (τ

R

, γ

R

)] |- λx. e

1

->

(τ

2

, γ

2

)

_______________________________________________________ (Regola 11)

H |- μ f. λ x . e

1

,( τ, γ)) ->

passo

(τ

2

, γ

2

)

dove "Non" nella regola 10bc indica che non deve valere la condizione di uguaglianza espressa immediatamente dopo il "non" stesso. Renaming è una particolare sostituzione che sostituisce ogni variabile presente in γ ma non in H con una variabile fresh. Affinché sussista l' uguaglianza tra tipi richiesta dalle regole 10a e 10bb occorre che ogniqualvolta si immette delle variabili nell' ambiente durante un passo della tipizzazione della funzione ricorsiva (ovvero ogniqualvolta si utilizza la Regola 6, cioè quella della λ astrazione, all' interno del sistema di inferenza ->passo relativo alla stessa

funzione ricorsiva), il tipo associato nell' ambiente a tale variabile deve essere lo stesso del tipo che si è introdotto per essa negli eventuali passi precedenti (del calcolo del punto fisso necessario per inferire il tipo di quella funzione ricorsiva.

Se applicazioni esterne alla dichiarazione della funzione ricorsiva stessa producono vincoli

incompatibili con la dichiarazione della funzione o con delle variabili esterne a essa, solo al momento di fornire il risultato di tale applicazione esterna si otterrà un vincolo incompatibile.

Estrarre una variabile esterna alla dichiarazione ricorsiva all' interno della dichiarazione ricorsiva usa lo stesso la regola per le variabili presenti nell' ambiente e produce la sostituzione vuota, in maniera analoga a quello che succede per le variabili interne alla dichiarazione ricorsiva.

La differenza è che il vincolo associato alla funzione ricorsiva può far fallire l' unificazione alla fine del singolo passo del punto fisso; vi è quindi un eventuale problema di compatibilità con il vincolo, ma non un diverso trattamento rispetto alle variabili interne. Il fallimento o meno dell' unificazione può essere verificato anche alla fine del singolo passo, invece che durante: il risultato non cambia. Infatti, le regole del sistema di equazioni e disequazioni si possono applicare in qualsiasi ordine, quindi si può immaginare che le regole che fanno fallire le unificazioni siano applicate per ultime. Per lo stesso motivo, aggiungere equazioni o disequazioni al sistema irrisolvibile non ne modifica la non risolubilità. In particolare la richiesta di consistenza richiede che durante i vari passi (e come risultato del punto fisso) il tipo, associato alla variabile esterna, non diventi mai incompatibile con il tipo inizialmente associato a essa stessa prima di entrare nella funzione ricorsiva o con qualsiasi altro tipo che essa abbia assunto nei precedenti passi del punto fisso.

Se l' unificazione fallisce per tale motivo, fallisce la tipizzazione della funzione ricorsiva; altrimenti le unificazioni si risolvono e diventa ininfluente il fatto che la variabile fosse esterna alla dichiarazione funzionale (ad ogni modo il tipo presente nel vincolo sarà unificabile con quello richiesto, quindi si potrà utilizzare quello richiesto).

Tale condizione può essere espressa con il fatto che, durante il calcolo del punto fisso, devono essere rispettate, per ogni variabile esterna alla dichiarazione della funzione ricorsiva stessa, le disequazioni

t

x

<= t

x

per ogni variabile contenuta nell' ambiente (il cui tipo associato è tx).

Infatti, tale regola permette di istanziare il tipo tx, ma nel caso che emerga un ulteriore disequazione del tipo tx <=y, per la regola 8 del sistema di equazioni e disequazioni, i tipi y e tx devono essere unificabili.

Teorema: (H |- e -> (τ, γ)) implica

(esiste f

1

tale che τ = γ(f

1

))

Prova: per induzione sulle regole, riscrivendole nel seguente modo. H |- int n -> (ε(int), ε) H |- id x -> H(x)

qui si distingue se la variabile estratta dall' ambiente è monomorfa o associata a una funzione ricorsiva. Se è monomorfa la sostituzione associata è ε, quindi si applica ε al tipo restituito dall' ambiente e il risultato vale.

Se la variabile è associata polimorfa, per quanto detto in precedenza, la sostituzione associata non la influenza, quindi posso applicarla al tipo restituito dall' ambiente e il risultato vale.

H |- e1 -> (τ 1, γ1)

H |- e2 -> (τ 2, γ2)

γ = unify (τ 1 = int ; τ 2 = int; eqn(γ1); eqn (γ2))

_____________________________________________________ H |- e1 + e2 -> ( γ(int), γ)

γ di int è sempre int.

H |- e1 -> (τ 1, γ1)

H |- e2 -> (τ 2, γ2)

H |- e3 -> (τ 3, γ3)

γ = unify (τ 1 = bool ; τ 2 = τ 3; eqn(γ1); eqn (γ2); eqn (γ3))

_____________________________________________________ H |- if e1 then e2 else e3 -> ( γ(τ 2), γ)

la regola era già scritta così nel sistema originario.

H |- e1 -> (τ 1, γ1)

H |- e2 -> (τ 2, γ2)

γ = unify (τ 1 = τ 2->q2 ; eqn(γ1); eqn (γ2))

_____________________________________________________ H |- e1 e2 -> ( γ(q2), γ)

H[x<- (q1,ε)] |-e1 -> (γ2(q2), γ2)

_____________________________________________________ H |- λ x . e1 -> (γ2 (q1) -> γ2 (q2) , γ2)

la premessa vale per la premessa dell' induzione sulle regole; γ2 (q1) è già prevista dal sistema

stesso.

H |- μ f. λ x . e1 ->fix (τ 1 , γ1)

_____________________________________________________ H |- μ f. λ x . e1 -> (τ 1 , γ1)

Qui la regola vale perché fix è risultato di un passo del punto fisso e ad ogni passo la regola vale. Infatti, al passo 0 H |- μ f. λ x . e1 ->0 (ε(a) , ε) ai successivi H[f<- (τ, γ)] |- λx. e1 -> (γ2 (q1), γ2) _____________________________________________________ H |- μ f. λ x . e1 ,( τ, γ)) ->passo (γ2 (q1) , γ2)

dove la premessa vale per l' ipotesi dell' induzione. Questo conclude la prova.

(Equivalentemente, per il lemma 9 di pag.14 di [GL3], se il sistema di inferenza calcola il tipo (τ, γ), γ (τ)= τ, quindi dicendo che ogni regola restituisce la coppia (γ (τ), γ) si ottiene lo stesso risultato).

Teorema: il tipo della funzione ricorsiva calcolato alla fine del passo

n>0 (e quindi immesso nell' ambiente al passo n+1) è

γ

n

(arg

1

)-> γ

n

(arg

2

) -> .... -> γ

n

(applicazione),

con γ

n

vincolo del passo n, arg

1

,.. , arg

k

sono i tipi degli argomenti delle lambda

astrazioni che seguono la dichiarazione della funzione ricorsiva e applicazione è il tipo

dell' applicazione di funzione finale che segue le lambda astrazioni.

Dimostrazione: per induzione strutturale sull' espressione che costituisce la dichiarazione ricorsiva, sfruttando il risultato del teorema precedente.

Infatti, dopo la dichiarazione ricorsiva, per la regola della tipizzazione della funzione ricorsiva stessa, è presente una λ astrazione del tipo λ x1.e1 (con x1 opportuna variabile il cui tipo nell' ambiente sarà arg1).

Applicando la regola di astrazione del sistema precedente H[x<- (arg1,ε)] |- e1 -> (γ2(q2), γ2)

_______________________________________________________ H |- λ x . e1 -> ( γ2(arg1) -> γ2(q2) , γ2)

si ha che il tipo risultante è γ(arg1)-> γ(q2), con q2 tipo calcolato per e1.

Se a questo punto e1 è un’ ulteriore applicazione funzionale, allora si avrà che il suo tipo è, sempre per

la regola precedente, γ(arg2)-> γ(q3), con q3 tipo opportuno; il tipo della funzione sarà quindi γ(arg1)->

γ(arg2)-> γ(q3). E' evidente che continuando a trovare lambda astrazioni si aggiungono al tipo della

funzione γn(arg1)-> γn (arg2) -> .... -> γn (argk-1) (si può dimostrare per induzione sul numero di lambda

astrazioni incontrate). Si noti, infatti, che ogni applicazione della regola di lambda astrazione lascia invariato il vincolo trovato per il sottotermine da tipizzare; il gamma applicato sarà quindi lo stesso per tutti i sottotermini.

Dopo le lambda astrazioni, affinché il programma sia corretto, vi sarà un’ applicazione di altro tipo, coperta dalle altre regole del sistema precedente; sempre per la regola della lambda astrazione espressa in precedenza, il tipo calcolato per e1 sarà γ(f2); è da notare, in particolare, che tutte le altre regole non

restituiscono un tipo nel quale è presente una funzione, ma un unico tipo al quale viene applicato il γ (ciò potrebbe a sua volta dar origine a un tipo che presenta al suo interno una funzione; tuttavia tale informazione non si può ricavare dalla regola). Quindi f2 è il tipo che nell' enunciato è stato chiamato

"applicazione". Nel caso e1 sia a sua volta una funzione ricorsiva, per l' ipotesi dell' induzione

strutturale sarà fatta nello stesso modo (cioè γ(arg1m)-> ...-> γ (applicazionem)) e il risultato continua a

valere.

Dal teorema precedente risulta che, tenendo opportunamente traccia delle variabili introdotte nei vari passi dal sistema di regole basato sull' interpretazione astratta, il γ calcolato racchiude in realtà in sé il tipo della funzione calcolato per quel passo; fornire quindi il γ risultante al passo del punto fisso invece del tipo assicura maggiori informazioni, tra le quali anche il tipo stesso della funzione. Il calcolo del punto fisso può quindi essere visto come la ricerca dell' opportuno γ che fornisce il tipo corretto della funzione.

__________________________________________________________________ Per il lemma 17 di [GL3], ad ogni passo il tipo calcolato

alla fine del passo è o equivalente al precedente o risultato di una sostituzione applicata al tipo precedente, quindi è il tipo precedente eventualmente più istanziato.

_________________________________________________________________________________

Sia τ n il tipo calcolato per la funzione ricorsiva al passo n, τ n+1 quello calcolato al passo n+1 e così via.

Teorema: per ogni n, τ

n

< τ

n+1

oppure τ

n+2

è il tipo del punto fisso.

Prova: Si supponga per assurdo τ n = τ n+1. Allora, per la regola della funzione ricorsiva τ n+2 è calcolato

mettendo nell' ambiente τ n+1 come tipo associato a f. Ma τ n+1 è lo stesso di τ n (a meno di

renaming); siccome la sostituzione associata alla funzione serve solo per vincoli di compatibilità con le variabili esterne (si veda le osservazioni apposite), indipendentemente da quale siano i vincoli previsti in essa, in entrambi i passi n+1 e n+2 il sistema starà calcolando la solita cosa, in quanto in entrambi i casi la funzione ricorsiva è presente nell’ ambiente con informazioni associate che danno luogo ai soliti risultati.

Quindi i risultati dei passi n+1 e n+2 sono identici, sia per tipo che per vincolo calcolati (a meno di renaming); pertanto al passo n+2 si raggiunge il punto fisso.

_________________________________________________________________________________

(Siano, analogamente, γn e γn+1 i vincoli calcolati alla fine del passo n e n+1)

Teorema: per ogni n, γ

n

< γ

n+1

oppure τ

n+2

è il tipo del punto fisso.

Prova: Analoga alla precedente, per assurdo. Si suppone che i γ siano uguali, poi si applica il risultato che ad ogni passo del calcolo il tipo della funzione ricorsiva è

γn(arg1)-> γn (arg2) -> .... -> γn (applicazione),

che permette di individuare il tipo del passo successivo in funzione del vincolo.

Allora

τ

n+1 =

τ

n+2 (perché ricavabili come funzione di vincoli equivalenti) , e da qui come nel teorema precedente.

I 2 teoremi appena dimostrati suggeriscono che a ogni passo il tipo inferito per la funzione deve cambiare oppure il sistema si arresterà dopo al più 2 passi; questo teorema, una volta chiarificata la funzione delle variabili esterne e la relazione con il sitema della semiunificazione, mostrerà che in realtà ad ogni passo del sistema del punto fisso corrisponde almeno un' applicazione delle regole 8 o 10 proposte per la risoluzione di sistemi di equazioni e disequazioni (sono le uniche regole che provocano l' aggiunta al sistema di nuove equazioni rispetto a quelle già ottenute in precedenza; tali equazioni fanno cambiare il tipo ottenuto per la funzione ricorsiva alla fine di un passo del calcolo del punto fisso).

(Una possibile semplificazione del sistema basato sull' interpretazione astratta rispetto a come scritto in [GL3] consiste nell' isolare le unificazioni che saranno presenti ad ogni passo; alcune di tali

unificazioni comprenderanno il tipo della funzione ricorsiva e quindi varieranno di passo in passo. Nelle equazioni che individuiamo possiamo già sostituire le unificazioni che generiamo sempre, ad ogni passo, e quindi saranno sempre applicate: tali sostituzioni non dipendono dal γf o dal tipo della funzione. Nelle altre equazioni si avrà dipendenza o dal tipo della funzione ricorsiva stessa o da un vincolo derivante da un unificazione che coinvolge il tipo della funzione ricorsiva per quel dato passo. Tale equazioni sono inserite in forma non risolta tra l' insieme di equazioni da ricalcolare ad ogni passo. Se influente ai fini del calcolo, si potrebbe anche tenere conto dell' ordine nel quale il sistema d'

inferenza dei tipi ha generato le equazioni (nell’ algoritmo di unificazione tale informazione è ininfluente). Il sistema semplificato comprende quindi delle equazioni incomplete (nelle quali andrà inserito il tipo della funzione per quel passo) e delle equazioni espresse in forma completa, ma non risolte e eliminate, in quanto alcune delle variabili in esse presenti dipendono (e possono essere

modificate), almeno in teoria, dal vincolo associato nell' ambiente alla funzione ricorsiva oppure da un vincolo derivato da unificazioni

che comprendono il tipo della funzione ricorsiva. In realtà, siccome le regole del SEI possono essere applicate in qualsiasi ordine, il sistema semplificato, per calcolare il vincolo risultante, può risolvere subito tutte le equazioni nel quale non compare il tipo della funzione ricorsiva, in quanto si può supporre che si siano risolte per prime tale equazioni del sistema di equazioni e in seguito quelle che coinvolgono il tipo della funzione. In questo modo il vincolo della funzione viene calcolato ad ogni passo unificando le nuove equazioni generate sostituendo il tipo appropriato della funzione con le altre in precedenza risolte. Tuttavia, siccome ad ogni passo bisogna calcolare anche il tipo della funzione, probabilmente è conveniente lasciare espresse le equazioni non dipendenti dal tipo della funzione, invece di fornire subito il risultato, in modo da ricavare con maggiore facilità le sostituzioni associate ai singoli tipi delle variabili introdotte durante la dichiarazione ricorsiva e, di conseguenza, il tipo della funzione.

In sintesi, eseguendo in maniera astratta il sistema di inferenza proposto, si è in grado di prevedere quali unificazioni saranno presenti ad ogni passo senza dover riapplicare il sistema di regole stesso ogni volta;

tuttavia è ancora necessario calcolare ogni volta il tipo della funzione e sostituirlo nelle equazioni, in modo analogo a quanto accade nel punto fisso).

Teorema: γ 3=unify(eqn(γ 1), eqn(γ 2)) implica γ 1<= γ 3 e γ 2<= γ 3.

Dimostrazione: γ 3 contiene le equazioni di γ 2 eventualmente più istanziate, in quanto modificate da

sostituzioni risultanti dall' algoritmo di unificazione. Analogo per γ 1.

Per il lemma 14 dell' articolo [GL3], nel sistema basato sull' interpretazione astratta ( H |- e -> (τ 1, γ 1) implica

Teorema:

(H |- e

->

(τ

1

, γ

1

) e esiste γ

3

tale che γ

3

= unify (eqn(γ

1

); eqn (γ

2

)))

implica

(γ

2

(H) |-

e

->

(τ

4

, γ

4

) e γ

3

=unify (eqn(γ

4

); eqn (γ

2

)) e τ

4

= γ

3

(τ

1

))

Dimostrazione: per induzione strutturale su e.

(Si noti che unify (eqn(γ 1); eqn (γ 2)) = unify (eqn(γ 2 (γ 1)); eqn (γ 2)) per come si risolve l' algoritmo

di unificazione, che sostituisce l' equazioni che ricava nelle altre in un ordine qualsiasi (quindi si può supporre che risolva prima quelle di γ 2)).

e = int n H |- e -> (int, ε) γ 3= γ 2 (τ 4, γ 4)=(int, ε) e i risultati valgono. e = id x H |- id x -> H(x)=( τ 1, γ 1) (τ 4, γ 4)= γ 2(τ 1, γ 1)

γ 3= unify (eqn(γ 1); eqn (γ 2))=

unify (eqn(γ 2(γ 1)); eqn (γ 2))=

unify (eqn(γ 4); eqn (γ 2))

γ 3 (τ 1)= γ 2(γ 1(τ 1))= γ 2(τ 1)= τ 4

e = e1+e2

Il tipo risultante è fornito dalla regola H |- e1 -> (int, γ b1)

H |- e2 -> (int, γ b2)

γ 1 = unify (eqn(γ b1); eqn (γ b2))

_______________________________________________________ H |- e1 + e2 -> ( int, γ 1)

con le ipotesi dell' induzione strutturale γ 2 (H)|- e1 -> (int, γ c1)

γ 3ci= unify (eqn(γ c1); eqn (γ 2))=unify (eqn(γ b1); eqn(γ 2) )

γ 2(H)|- e2 -> (int, γ c2)

γ 3c2= unify (eqn(γ c2); eqn (γ 2))=unify (eqn(γ b2); eqn(γ 2) )

γ c1 e γ c2 unificabili perché unificabili γ b1 e γ b2

γ 2 (H)|- e -> (int, γ 4)

γ 4= unify (eqn(γ c1); eqn (γ c2))=unify(eqn(γ b1); eqn (γ b2)) = γ 1

γ 3= unify (eqn(γ 4); eqn (γ 2))= unify (eqn(γ 1); eqn(γ 2) )

e=if e1 then e2 else e3

Il tipo risultante è fornito dalla regola H |- e1 -> (bool, γb1)

H |- e2 -> (τ b2, γb2)

H |- e3 -> (τ b2, γb3)

γ1 = unify ( eqn(γb1); eqn (γ b2); eqn (γ b3))

_______________________________________________________ H |- if e1 then e2 else e3 -> ( γ1(τ b2), γ1)

con le ipotesi dell' induzione strutturale γ2(H)|- e1 -> (bool, γc1)

γ3c1= unify (eqn(γc1); eqn (γ2))=unify (eqn(γb1); eqn (γ2))

γ2(H)|- e2 -> (tauc2, γc2)

γ 3c2= unify (eqn(γc2); eqn (γ2))=unify (eqn(γb2); eqn(γ2))

γ2 (H)|- e3 -> (tauc3, γc3)

γ 3c3= unify (eqn(γc3); eqn (γ2))=unify (eqn(γb3); eqn (γ2))

τc2= γ3c2(τb2)

τc3= γ3c3(τb2)

γ c1, γc2 e γc3 unificabili perché unificabili γ b1, γ b2 e γ b3

τc2 e τc3 unificabili perché unificabili γc2 e γc3 (e quindi γ3c2 e γ3c3)

γ2 (H)|- e -> (τc2, γ4)

γ4=unify(eqn(γc1); eqn (γc2); eqn (γc3))=unify(eqn(γb1); eqn (γb2); eqn (γb3))= γ1

γ 3= unify (eqn(γ4); eqn (γ 2))= unify (eqn(γ1); eqn(γ 2) )

e = e1 e2

Il tipo risultante è fornito dalla regola H |- e1 -> (τb1, γb1)

H |- e2 -> (τb2, γb2)

γ1 = unify (τb1 = τb2->q2 ; eqn(γb1); eqn (γb2))

_______________________________________________________ H |- e1 e2 -> ( γ1(q2), γ1)

con le ipotesi dell' induzione strutturale γ 2(H) |- e1 -> (τc1, γc1)

γ3c1=unify (eqn(γc1); eqn (γ 2))=unify (eqn(γb1); eqn(γ 2) )

τc1= γ3c1(τb1)

γ 2(H) |- e2 -> (τc2, γc2)

γ3c2=unify (eqn(γc2); eqn (γ 2))=unify (eqn(γb2); eqn(γ 2) )

τc2= γ3c2(τb2)

γc1 e γc2 unificabili perché unificabili γb1 e γb2

γ3c1 e γ3c2 unificabili perché unificabili γc1 e γc2

τc1=τc2->q3 perché lo erano τb1 e τb2

γ4=unify(τc1=τc2->f3;eqn(γc1); eqn (γc2))=unify(eqn(γb1); eqn (γb2); τb1 = τb2-> q2)= γ1

(a meno di renaming di q2 e q3)

τ4= γ4(q3)= γ1(q3)= γ1(q2) a meno di renaming

γ3(γ1(q2))= γ3(q2)=(unify ( eqn(γb1); eqn (γb2)))( q2)

=(unify ( eqn(γc1); eqn (γc2)))( q3) a meno di renaming

e = λ x. e1

Il tipo risultante è fornito dalla regola H[x<- (q1,ε)] |-e1 -> (γ1 (q2), γ1)

_______________________________________________________ H |- λ x . e1 -> (γ1 (q1) -> γ1 (q2) , γ1)

per fornire il tipo nell' ambiente γ2(H) si dovrà indicare il risultato di (γ2(H))[x<- (q3,ε)],

con q3 variabile fresh come lo era q1. Allora si considera la sostituzione γ2a che è uguale

a γ2 solo che fa sostituire q1 con q3.

γ2a unificato con γ1 continua a fornire una sostituzione risultante γ3a se γ2 unificato con γ1

forniva la sostituzione γ3, in quanto si è aggiunta un' equazione riguardante 2 variabili

fresh che quindi non può modificare la unificabilità delle altre.

Per l' ipotesi dell' induzione strutturale la proprietà vale per γ2a con risultato γ3a; di

H |- μ f. λ x . e1 ->fix (τ1 , γ1)

_______________________________________________________ H |- μ f. λ x . e1 -> (τ1 , γ1)

Qui la proprietà vale perché fix è risultato di un passo del punto fisso e ad ogni passo la proprietà vale.

Infatti, al passo 0

H |- μ f. λ x . e1 ->0 ( a , ε)

e a partire da un ambiente diverso si avrà la stessa coppia con il tipo uguale a meno di renaming; la dimostrazione è analoga al caso e = int. ai successivi

H[f<- (τ, γ)] |- λx. e1 -> (τ1, γ1)

_____________________________________________________ H |- μ f. λ x . e1 ,( τ, γ)) ->passo (τ1 , γ1)

e bisogna fornire il risultato del calcolo in γ2(H); la regola da

applicare sarà

(γ2(H))[f<- (τ, γ)] |- λx. e1 -> (τ4, γ4)

ma la regola precedente dice di tipizzare una funzione ricorsiva in un ambiente che cambia solo le variabili esterne alla funzione ricorsiva in un modo compatibile con i vincoli introdotti dal calcolo del tipo della funzione ricorsiva stessa (γ2 e γ1 sono infatti

unificabili per ipotesi). Allora se la funzione ricorsiva non richiama variabili esterne il risultato non verrà modificato da γ2 e γ2(τ1) = τ1 = τ4 e il risultato vale.

Se, invece, la dichiarazione ricorsiva contiene le variabili esterne, esse saranno

modificate ad ogni invocazione come previsto da γ2 e il risultato sarà ancora γ2(τ1, γ1). In

ogni caso le proprietà richieste dal teorema risultano verificate.

Corollario: (H |- e

->

(τ

1

, γ

1

))

implica

(γ

1

(H) |-

e

->

(γ

1

(τ

1

), γ

1

))