La costruzione e dimostrazione seguente fa vedere come il risultato del calcolo di punto fisso del sistema con l' interpretazione astratta si possa vedere come la soluzione di un particolare sistema di equazioni e disequazioni. Di seguito, dove si parla di sistemi composti soltanto da disequazioni, si suppone che in realtà tutte le unificazioni presenti nel sistema di equazioni e disequazioni originario siano state già risolte e rimanga soltanto un sistema di disequazioni eventualmente più vincolato di quello di partenza; tale semplificazione è permessa dall' indipendeza dell' ordine di applicazione di risoluzione delle regole del sistema di risoluzione di equazioni e disequazioni.
Si consideri il sistema di tipi proposto nell' articolo [GL3].
Si esegua il primo passo del calcolo del punto fisso tenendo "bloccato" il tipo della funzione ricorsiva, cioè ogni volta che nel vincolo compare un unificazione riguardante il tipo della funzione ricorsiva (in questo caso quello del passo 0) non si procede a eseguire l' unificazione, ma si lascia espressa l'
equazione.
Si tiene traccia, inoltre, di tutte le equazioni che dipendono dal tipo della funzione o dal vincolo a essa associato secondo il sistema di regole proposto (la dipendenza dal vincolo in realtà è ininfluente, ma serve a identificare le sostituzioni che nel corso del calcolo del punto fisso cambieranno). (In pratica, si tiene conto di tutti i casi nei quali il vincolo calcolato dal sistema di regole per l' opportuna
sottoespressione che stiamo elaborando conterrà un eqn(γf), con γf vincolo della funzione; tali
espressioni sono quelle che potranno variare nei vari passi del punto fisso).
Le unificazioni che non sono state segnate nel suddetto modo (quelle indipendenti dal particolare γf, e
quindi che restano invariate ad ogni passo) si possono svolgere subito e risolvere con l' algoritmo di unificazione (in alternativa, genereremo un sistema composto sia dalle suddette equazioni oltre che dalle
successive equazioni che andremo a mettere. Comunque, risolvere subito tale equazioni semplifica anche il calcolo del punto fisso del sistema proposto, perché esse saranno sempre presenti anche ai passi successivi (a meno di renaming, se ogni volta le variabili si prendono fresh e non si esegue il renaming del tipo della funzione, ma quello delle variabili)).
Dopo aver individuato le equazioni presenti ad ogni passo (e averle applicate), il sistema di equazioni e disequazioni prende ciascun tipo che ha tentato di unificare con il tipo della funzione ricorsiva presente nell' ambiente durante il calcolo del primo passo; siano
auf1, auf2, ... aufn
questi termini con i quali si è tentata l' unificazione (nel caso della ricorsione lineare polimorfa c' è solo auf1).
Se nel corpo della definizione della dichiarazione ricorsiva la funzione ricorsiva non appare mai, si raggiunge subito il punto fisso al passo 2. Altrimenti almeno uno dei termini auf1, auf2, ... aufn è
effettivamente presente nelle equazioni che servono per determinare i vincoli. Per il corollario 17 dell' articolo [GL3], in tutti i passi successivi
γi = γ1S
(con S opportuna sostituzione dipendente dal passo che si sta unificando, γi vincoli calcolati al passo i-
esimo e γ1 vincoli del primo passo), quindi sono presenti le stesse equazioni a meno della sostituzione
S.
Se una delle unificazioni di un certo passo non è risolvibile, il punto fisso fallisce.
Altrimenti in γi, ovvero nel γ (nei vincoli)di ogni passo è soddisfatta ciascuna delle equazioni in
questione (cioè delle equazioni di base come modificate dalla sostituzione).
Allora anche al punto fisso (se raggiunto) valgono le unificazioni presenti nel γn relativo.
In particolare, ad ogni passo, si unifica il tipo della funzione presente a quel passo con i vari auf1, auf2, ... aufn secondo lo schema
St(τ0)=St(auf1)
... St(τ0)=St(aufn)
Con St sostituzione opportuna che permette di passare dal passo 1 a quello specifico passo.
Sia n il passo del punto fisso; γn comprende le equazioni S(τ0)=S(auf1) ... S(τ0)=S(aufn)
dove τ0 è il tipo calcolato al passo 0 e presente quindi nell' ambiente al passo 1.
Siccome ad ogni passo i γi-1 <= γi, S=S1Sp, con S1 e Sp opportune sostituzioni tali che S1(τ0) = τ1 con τ1
tipo calcolato alla fine del passo 1 (γi-1 è il vincolo al passo i-1).
Al passo precedente il punto fisso Sp(S1(τ0))=Sp(S1(auf1)) ... Sp(S1(τ0))=Sp(S1(aufn)) cioè Sp(τ1=Sp(S1(auf1)) ... Sp(τ1=Sp(S1(aufn))
mentre al punto fisso, per le regole del sistema proposto, le stesse unificazioni saranno presenti a meno di renaming.
Sia R il risultato dell' unificazione al passo del punto fisso; siano R1 i vincoli di R applicabili solo alla
parte sinistra delle equazioni e R2 gli eventuali vincoli di R che influenzano entrambe le parti.
Allora al passo n
R1(R2(Sq(Sp(τ1))))=R2(Sq(Sp(S1(auf1))))
e ai passi precedenti
R1( (R2 composto Sq)(Sp(τ1)))=(R2 composto Sq)(Sp(S1(auf1)))
...
R1( (R2 composto Ti composto ....)(Tq(τ1)))=
(R2 composto Ti composto ....)Tq(S1(auf1)))
...
Quindi in nessuno dei passi precedenti il punto fisso nei quali esiste Ti sostituzione diversa dall' identità
e dal renaming per passare da un passo al successivo si può aver raggiunto il semiunificatore più generale, in quanto quello calcolato dopo aver applicato la sostituzione Ti è più generale di quello del
passo precedente.
Ad ogni passo si usa il tipo della funzione per tipizzare la definizione ricorsiva; tale tipo risulta, al più dopo essere stato istanziato, unificabile con quello di auf1. Allora per ogni i, se il calcolo del punto fisso
non fallisce nel frattempo, Si(τ1) <= Si+1(auf1). Al punto fisso, se raggiunto, Sn(τ1)=Sn-1(τ1) <= Sn(auf1).
Analogo per gli (eventuali) altri auf2 ….. aufi.... aufn.
Dal risultato precedente si ha che se il sistema basato sull' interpretazione astratta raggiunge il punto fisso, allora soddisfa le disequazioni (in t-upla tra loro)
(τ1 <= auf1; …...; τ1 <= aufi; ...; τ1 <= aufn)
In realtà, nel sistema precedente sono state ignorate le variabili esterne la dichiarazione ricorsiva; in presenza di esse, come si mostrerà in seguito, è necessario inserire nella t-upla anche la condizione sulle variabili esterne (non associate a funzioni ricorsive) x <= x per ogni x appartenente all' ambiente H precedente la dichiarazione della funzione ricorsiva (con x non associata a funzione ricorsiva). La t-upla completa sarà quindi del tipo
(τ1 <= auf1; τ1<=...; τ1 <=aufi; ...; τ1 <= aufn; x1<=x1; ... xk<=xk)
Tale trattamento delle variabili esterne, come verrà dimostrato in seguito, è identico a quello che esse subiscono nel sistema di Milner-Mycroft (e quindi nel sistema di equazioni e disequazioni a esso associato); tale sistema risolverà infatti le disequazioni del tipo
(τ1 <= auf1; x1 <= x1; ...; xk <= xk)
(...; x1 <= x1; ...; xk <= xk)
(τ1 <= aufi; x1 <= x1; ...; xk <= xk)
(...; x1 <= x1; ...; xk <= xk)
(τ1 <= aufn; x1 <= x1; ...; xk <= xk)
dove ciascuna delle linee precedenti rappresenta k+1 disequazioni in t-upla tra loro, ma indipendenti da quelle delle t-uple successive. (Per ogni i diverso da j aufi e aufj stanno in t-uple diverse). Come
descritto in precedenza riguardo al problema della semiunificazione, disequazioni in t-uple diverse, ma appartenenti a uno stesso sistema, condividono solo la sostituzione che è il semiiunificatore generale, ma non la sostituzione che viene applicata al lato sinistro della disequazione una volta che questa sia stata risolta).