7.2 Lemmi riguardanti la funzione alpha
7.2.3 Lemma 5.5.3
Come anticipato mentre commentavamo i motivi per cui il lemma 4.1.3 fosse falso, questo è uno dei risultati in cui avremmo dovuto provvedere a formulare una dimostrazione alternativa poiché quella presentata in [5]. Riprendiamo la dimostrazione che ne è data nell’articolo per provare a trovare strade alternative.
Lemma 7.2.1
Tutti i corpi di funzione in un Crumble c0 raggiungibile durante la valutazione
della macchina Crumble GLAM sono sottotermini del crumble c iniziali a meno di ridenomina.
Dimostrazione. Le regole →subvar e →subl possono copiare astrazioni, ma dal momento che le astrazioni erano già nell’ambiente, il claim segue direttamente dall’ipotesi induttiva. Per il caso della 7→βv, la regola può copiare un corpo di una funzione e ridenominarlo, ma dal momento che per il remark 4.1.3 la tradu- zione si commuta con la rinomina delle variabili fresche operata dalla funzione ·α, il risultato segue direttamente dall’ipotesi induttiva.
La dimostrazione sembra voler procedere per induzione sulla lunghezza della riduzione ed analizzare caso per caso tutte le possibili transizioni. Nello specifico ci troviamo a dover trattare il caso della regola di transizione 7→βv. Simbolica- mente, la parte della dimostrazione in questione vuole procedere come in (7.7), dove Spc0(·)è il predicato che denota il fatto che l’argomento sia un corpo del Crumble c0iniziale a meno di ridenomine.
((λx.cn)wn, ev) 7→βv (cn+1@[x ← wn+1])αev= (c0{xa1← zb1} . . . {xam ← zbm}@[x 0 ← w0{xa1← zb1} . . . {xam ← zbm}])ev (t0{xa1← zb1} . . . {xam ← zbm}@[x 0 ← u0{xa1← zb1} . . . {xam ← zbm])ev (7.7)
7.2. LEMMI RIGUARDANTI LA FUNZIONE ALPHA 93 Ma a questo punto, Spc0(ev)per ipotesi induttiva dal momento che tutti i corpi di everano corpi del termine prima che si applicasse la transizione. Per quanto
riguarda i corpi di funzione in c0, si vuole far vedere che:
(t0{xa1← zb1} . . . {xam ← zbm}@[x 0 ← u0{xa1 ← zb1} . . . {xam← zbm}]) = (t0{xa1 ← zb1} . . . {xam← zbm}@[x 0 ← u0{xa1← zb1} . . . {xam ← zbm}]) Dove la riscrittura è giustificata per il remark (falso) 4.1.3 e la conclusione de- riva dal fatto che t0 sia sottotermine del termine iniziale per il remark 4.5.4.
L’utilizzo del remark 4.1.3 è superfluo: la condizione di uguaglianza che esso esprime è troppo forte. La condizione che baseterebbe dimostrare non è un’u- guagliaza stretta, ma è meno stringente: per la presenza della clausola “up to renaiming” ci potremmo limitare ad un’uguaglianza modulo rinomine. La stes- sa clausola non è ben formalizzata: la rinomina può agire anche sulle variabili legate da astrazioni, ma in realtà, dal momento che la ·α sostituisce variabili
fresche, le variabili legate da astrazioni non vengono di fatto mai rinominate, per cui si potrebbe riscrivere tale clausola con “up to ·α” ed il risultato conti-
nuerebbe ad essere vero. Per questa ragione, il lemma può essere riformulato con la condizione generica di ridenomina sostituita da quella di alpha ·α e la
prova si può riscrivere osservando che per la funzione ·α valga una proprietà di
idempotenza2 per cui una serie annidata di applicazioni possa essere riassunta
con l’applicazione più esterna.
La dimostrazione di questo risultato procede come mostrato da7.9, dove ·α n
denota l’applicazione della ridenomina con variabile fresca di indice n.
(b, e[x ← b0])αn α m= (b, e[x ← b 0 ])αm ((b, e)αn+1{x ← νn}[νn ← b 0 ])αm= ((b, e))αm+1{x ← νm}[νm + 1 ← b 0 ] ((b, e)αn+1{x ← νn}) α m{n ← νm}[νm ← b 0 ] = ((b, e))αm+1{x ← νm}[νm + 1 ← b 0 ] ((b, e)αn+1) α m+1{x ← νn}{n ← νm}[νm ← b 0 ] = ((b, e))αm+1{x ← νm}[νm + 1 ← b 0 ] ((b, e)αn+1) α m+1{x ← νm}[νm ← b 0 ] = ((b, e))αm+1{x ← νm}[νm + 1 ← b 0 ]
A questo punto è possibile concludere usando l’ipotesi induttiva. Per poter giungere a questo risultato è stato necessario dimostrare altri due lemmi: il primo asserisce che in virtù delle ipotesi di freschezza delle variabili sostituite dalla funzione alpha*, sia possibile commutare l’applicazione della funzione ss* all’applicazione della funzione alpha*, mentre il secondo asserisce che due sostituzioni consecutive della forma {a ← b}{b ← c} possano essere riassunte da una singola sostituzione {a ← c}. Dimostrati questi lemmi, l’enunciato per gli Environment viene formulato come mostrato da7.9.
lemma alpha_e_idem: ∀e, n, m, H1, H2, H3. m n + e_len e → (pi1 … (alpha2_e (pi1 … (alpha2_e e n H1)) m H2)) = pi1 …
(alpha2_e e m H3).
Codice 7.9: Enunciato del lemma d’idempotenza per la funzione alpha_e 2Per essere rigorosi, occorre sottolineare che la proprietà a cui facciamo riferimento non è
d’idempotenza in senso propro: la funzione ·α richiede due argomenti, dunque non ha senso
parlare d’idempotenza. Più propriamente, dimostreremo che applicazioni successive della funzione ·αannidate su di un termine c, saranno uguali al’esito della chiamata più esterna su
L’enunciato del lemma7.3richiede un’ipotesi esplicita di freschezza sulla va- riabile m, tale richiesta non è assolutamente limitante perché per la ridenomina possiamo scegliere indici arbitrariamente grandi, inoltre non è nemmeno stret- tamente necessaria per la dimostrazione del lemma, in quanto si può derivare dalle ipotesi H1, H2 e H3. La ragione per cui è stata inserita nell’enunciato è solamente quella di snellirne la dimostrazione senza indebolire lo statement.
Aver dimostrato solo questo lemma e non lemmi analoghi per tipi come Bite o Crumble non è assolutamente limitante: la dimostrazione del caso della fun- zione alpha procede esattamente nello stesso modo, ma con qualche insidia in più dovuta al fatto che il tipo di ritorno della funzione alpha non compaia in input nella funzione stessa, quindi è necessario espandere il Crumble restituito dalla funzione più interna per poter avanzare con dimostrazione e ricostruirlo per usare l’ipotesi induttiva, che andrà poi un’altra volta ri-espansa rendendo la prova più tediosa. Tuttavia, occorre osservare che il risultato generico sul Crumble può anche essere espresso come un corollario del risultato sugli Envi- ronment, dal momento che per il primo lemma di matching in7.11vale quanto espresso in7.8, dove β(·), γ(·) sono le funzioni descritte in7.1.3.
(([x ← b]e)αn)αm) = ([x ← b]e)αm ([x0← γ(b, β(e, m))](e)α m= x0h(b, e)α mi (7.8)
Tutti i passi di riscrittura sono giustificati da lemmi tecnici relativi alla scom- posizione di alpha*, beta* e gamma* rispetto ai costruttori di tipo, alle funzioni di manipolazione e a quelle di plugging già dimostrate formalmente come lemmi tecnici per provare il lemma 5.5.4. Dunque, la dimostrazione formale del lemma
7.9, ci ha permesso di concludere che l’invariante del lemma 5.5.3 vale “up to ·α” nel caso specifico della regola 7→
βv: non solo abbiamo rimosso l’utilizzo del remark 4.1.3, ma abbiamo formulato la dimostrazione di una proprietà più forte di quella richiesta.