Lemma 4.5

Il lemma 4.5 ha lo scopo di garantire alcune proprietà fondamentali della funzio-ne underlifunzio-ne, mediante le quali si garantisce che lo stato iniziale della macchina Crumble GLAM goda degli invarianti necessari per il suo corretto funzionamen-to. La prima di queste proprietà è quella di well-namedness (espressa in6.2.1) che garantisce che le variabili introdotte dal processo di crumbling siano distin-te nel dominio del medesimo ambiendistin-te; in questo modo è garantito che ad uno stesso nome di variabile introdotto durante la fase di crumbling sia associato uno ed un solo ES.

Prima di presentare l’enunciato del lemma, mostriamo in6.9la formalizza-zione che abbiamo dato del predicato di well-namedness e lo commentiamo.

1 lemma well_named_alpha:

2 ∀f, b, e. ∀n. fresh_var (at hb, ei f) ≤ n →

3 match (at hb, ei f) with [ CCrumble b e ⇒ ∀H. (w_well_named (pi1 … (alpha b e n H))=true) ∧ interval_dom match (pi1 … (alpha b e n H)) with [CCrumble b e ⇒

e] n].

Codice 6.9: Definizione della funzione booleana well_named

La funzione implementa chiaramente la definizione di well-namedness, infatti, dato un Crumble ci si assicura che le variabili del dominio del suo Environment e siano distinte, poi, mediante le funzione well_named_b e well_named_e, si cer-cano altri Crumble sotto λ-astrazioni per reiterare l’applicazione del predicato di well-namedness.

Lemma 6.3.9 (4.5)

1. Freshness: ∀t.well_named(t) 2. Closure: ∀t.F V (t) = ∅ → F V (t) = ∅

3. Disjointedness: ∀t, C, b, e.(t) = Chb, ei → DOM(C) ∩ F V (B) = ∅ 4. Bodies: tutti i corpi di funzione in t sono la traduzione di termini.

5. Contextual decoding: t = Chci → rv_context(C↓)

Lemma 4.5.1

La dimostrazione di questo enunciato non ha richiesto particolari accorgimenti, il risultato deriva dal fatto che la funzione underline, per come è stata costrui-ta, inserisca sempre variabili fresh nell’Environment. Questo fatto è una diret-ta conseguenza del lemma line_names in 6.4. L’invariante di well-namedness garantisce che l’operazione di look-up di una variabile qualsiasi nell’Environ-ment non sia ambigua e quindi contribuisce a dimostrare che, come richiesto dall’implementation theorem, la macchina Crumble GLAM sia deterministica.

Lemma 4.5.2

La proprietà di closure è un banale corollario del remark 4.1.1 (6.3.6), la necessità di introdurre questo lemma deriva dal fatto che, in [5], la prima crumbling abstract machine presentata, la Crumble GLAM, sia definita con un insieme di regole di transizione volte ad implementare una disciplina di valutazione weak closed CbV. Secondo tale strategia, un’applicazione può essere valutata solo se l’argomento è un’astrazione chiusa. Chiaramente, se questo lemma non fosse rispettato potrebbero verificarsi casi in cui nel Crumble su cui lavora la macchina sia possibile operare β-riduzioni che non sono possibili nel corrispondente pTerm o viceversa, rompendo uno degli invarianti dell’implementation thoerm (1).

Successivamente, in [5], vengono introdotte altre macchine (nel caso specifico la Open Crumble GLAM) che applicano diverse discipline di valutazione. Nel caso specifico della Open Crumble GLAM, la disciplina di valutazione adottata è quella weak open CbV per cui l’ipotesi di chiusura del termine iniziale, propria delle discipline di valutazione closed, non è più necessaria.

Lemma 4.5.3

Questo risultato è molto tecnico e difficilmente si riesce a fornirne un’interpreta-zione intuitiva soddisfacente. Nonostante ciò, proviamo comunque a formularne una: dalla definizione dell’operazione di read-back in6.2e dalle considerazioni date in3.2riguardo la valutazione dei termini, vediamo che entrambe le opera-zioni procedono percorrendo gli Environment da destra verso sinistra. Questo risultato, dunque, concorre con la sua formulazione dinamica a garantire che sia in fase di valutazione che di ritraduzione, i costrutti di ES che si trovano a sinistra di un Bite b condiviso siano ininfluenti nella sua valutazione e nella sua ritraduzione. Infatti nessuna variabile libera nel Bite b punta ad un termi-ne condiviso che deve ancora essere preso in esame. Dunque questo risultato, ancora una volta, rafforza il fatto che la disciplina di valutazione della Crumble GLAM sia right-to-left.

Lemma 4.5.4

Questo lemma fa riferimento contemporaneamente a due accezioni: il primo è simile a quella del remark 4.1.4 e vuole garantire la corrispondenza fra le due grammatiche dei tipi Crumble (4.2) e pTerm (4.1) che avevamo informalmente enunciato quando le abbiamo introdotte. La seconda accezione di questo lemma vuole dimostrare che la funzione di traduzione sia in un certo senso fedele, ossia che non inserisca nel Crumble finali sottotermini che non fossero già presenti nel termine di partenza.

Nel contesto della formalizzazione, la prima accezione del lemma è triviale dal momento che la definizione formale della funzione underline ha fatto sì che tutti i dati venissero tipati, per questo motivo, dal momento che essa ha come tipo di ritorno Crumble e per la definizione del tipo stesso, tutti i corpi di funzione sono Crumble e per la definizione della underline, l’unico modo per generare un corpo di funzione è mediante la traduzione di un Term.

6.3. LEMMI SU UNDERLINE E READ_BACK 77 Per quanto riguarda la seconda accezione con cui il lemma viene utilizzato all’interno di [5], la prova di questo risultato si riduce con la verifica del fatto tutti i corpi di funzione generati dalla underline siano sottotermini del termine di partenza. Per fare ciò, è stato necessario definire due predicati mutui in grado di sintetizzare la relazione di essere sottotermine di un pTerm e di un pValue e cinque predicati per la relazione analoga relativa alla grammatica dei Crumble.

Tale definizione è stata data come segue:

1 let rec subt t1 t2 on t2 :=

1314 definition tint := λt1.λt2. t1=t2 ∨ subt t1 t2.

1516 let rec subc c d on d :=

Codice 6.10: Definizione formale dei predicati che esprimono la relazione di essere sottotermine di un termine t1 per un dato termine t2

Date queste definizioni, l’enunciato del lemma 4.5.4 può essere formalizzato come segue:

(∀t, s, c. subc c (fst … (underline t s)) →

∃u, n. (c = fst … (underline u n)) ∧ (tint u t)) ∧ (∀v, s, c. subc_v c (fst … (overline v s)) →

∃u, n. (c = fst … (underline u n)) ∧ (subt_v u v)).

Codice 6.11: Formalizzazione del lemma 4.5.4