Mentre il processo di read-back è sostanzialmente una decodifica, quello di un- derline è una codifica; in quanto tale, esso deve garantire che le crumbled forms così ottenute godano di determinati invarianti che garantiscono il corretto fun- zionamento della macchina. Per queste ragioni ci aspettiamo che la funzione di crumbling sia più complessa che quella di read-back.
Informalmente, la funzione di crumbling definita dall’articolo è composta da due funzioni mutualmente ricorsive: una per i pValue, indicata con il simbolo · ed una per i pTerm, indicata con il simbolo ·. La funzione · passa in rassegna il proprio argomento: qualora incontri un pValue si limita a chiamare la funzione mutua ·, mentre se incontra un’applicazione che coinvolge almeno un termine (dunque un’applicazione annidata), “stacca” i termini, effettua una chiamata ricorsiva su ciascuno di essi ed introduce nel crumbled environment un costrutto di ES fra i risultati delle chiamate ricorsive ed una variabile fresca introdotta al posto dei termini di partenza. La funzione ·, passa in rassegna il proprio argomento e se sono variabili, le trascrive, mentre se sono λ-astrazioni trascrive l’argomento e chiama la funzione · sul corpo dell’astrazione.
L’ordine in cui non vengono inseriti i costrutti di ES nel Crumble non è casuale, bensì è volto a garantire che in fase di valutazione, percorrendo l’Envi- ronment da destra a sinistra si applichi una disciplina di valutazione right-to-left closed CbV. Si prenda ad esempio l’ultima riga della6.3: i costrutti di ES gene- rati dal termine di destra verranno apposti a destra dell’Environment dimodoché percorrendo la lista da destra verso sinistra vengano valutati per primi.
Allo stesso modo della read-back, quando useremo le simbologie · e · faremo riferimento alle definizioni date in [5], mentre quando adotteremo le simbologie overline e underline faremo riferimento alle implementazioni che ne abbiamo dato in Matita. La definizione di · e · che compaiono [5] sono le seguenti:
x := x λx.t := λx.t (6.2) v := (v, ) vw := (vw, ) tv := (xv, [x ← b]) (∗) ut := ux@ ([x ← b]e) (∗) (6.3)
6.2. UNDERLINE 65 (∗) Dove t non è un valore e t = (b, e) e x è fresca
Mentre per l’implementazione6.2non ci sono particolari problemi, l’implemen- tazione in Matita della · risulta un po’ più problematica. In primo luogo, allo stesso modo della ·↓, anche questa definizione non è trascrivibile in Matita: in-
fatti la definizione del caso ut prevede che la funzione vada in ricorsione su di un termine che non è strettamente più semplice del parametro formale. Inoltre, occorre implementare dei meccanismi per garantire che la funzione sia in grado di introdurre variabili fresche.
Per rendere la6.3definibile in Matita, si può pensare di scomporre il caso ut nei sotto-casi vt e t0ted osservare che vt si espanderebbe in (vx, ) @ ([x ← b]e)
con le ipotesi (∗) su x, b ed e, mentre il caso t0tsi espanderebbe in t0x@ ([x ←
b]e)sempre con le ipotesi di (∗), il quale a sua volta si ridurrebbe in (x0x, [x0← b0]e0)@ ([x ← b]e) ≡ (x0x, [x0 ← b0]e0[x ← b]e)in cui ancora una volta valgono le
ipotesi di (∗) su x0, b0 ed e0. Le espansioni appena presentate, a differenza della
6.3, non presentano chiamate ricorsive su termini non strettamente più piccoli di quelli del chiamante, per cui è possibile riscrivere la 6.3come riportato nella
6.4. v := (v, ) vw := (vw, ) tv := (xv, [x ← b]) (∗) vt := (vx, [x ← b]) (∗) t0t := (x0x, [x0← b0]e0[x ← b]e) (∗) (6.4)
(∗) Dove t non è un valore e t = (b, e) e x è fresca
A questo punto, per poter implementare la6.4in Matita, rimane solo da iden- tificare un meccanismo per generare variabili che siano sempre fresche. Per farlo, facciamo ricorso alla definizione di F RV che abbiamo dato in5.4: si osserva che dato un qualsiasi termine t, se denotiamo g una generica trasformazione di t tale che g(t) = t0∧ V ar(t0) = V ar(t) ∪ {νF RV (t)}, allora F RV (t0) = S (F RV (t)).
Più informalmente: se modifichiamo un termine t in modo che all’insieme delle variabili che vi compaiono, sia aggiunta la variabile di indice F RV (t), allora la F RV del termine così ottenuto sarà la F RV di t incrementata di uno.
Grazie a questa intuizione, dal momento che la underline si comporta come la g di cui sopra, si potrebbe quindi pensare di implementare la underline in modo che abbia la seguente signature: pTerm × nat → Crumble × nat, dove i secondi elementi delle coppie sono gli indici progressivi della F RV del Crumble che si sta costruendo. Così, ad ogni passaggio si potrà calcolare l’indice di una variabile fresca a partire dagli indici calcolati dalle chiamate ricorsive, inserirla all’interno del Crumble che si sta generando e determinare l’indice della nuova variabile fresca da restituire in output. Formalmente questa precondizione andrà espressa mediante un’ipotesi da vormulare ogniqualvolta, nell’enunciato di un teorema o all’interno di altre funzioni, si faccia uso della funzione underline.
Rimane solo un ultimo piccolo dettaglio da formalizzare: come decidere se l’argomento della underline è una t od una v. Una soluzione semplice potrebbe
essere quella che prevede, dato r un generico pTerm, di fare match u e, nel ramo appl s s', allora comportarsi come nel caso t, mentre nel ramo val_- to_term w comportarsi come nel caso v. Questo metodo, nonostante introduca dei sottotermini che non sono immediatamente necessari alla chiamata della funzione (quelli che nell’esempio più sopra sono s, s' e w), è implementabile in maniera semplice all’interno della underline e non richiede la definizione di nessuna funzione ausiliaria esterna.
Date queste considerazioni, la · e la · sono facilmente implementabili in Matita come segue:
1 let rec underline (t: pTerm) (s: nat): Crumble × nat :=
2 match t with
3 [ val_to_term v ⇒ match overline v s with
4 [ mk_Prod vv n ⇒ mk_Prod Crumble nat h(CValue vv), Epsilon i n] 5 | appl t1 t2 ⇒ match t2 with
6 [ val_to_term v2 ⇒ match t1 with
7 [ val_to_term v1 ⇒ match overline v1 s with 8 [ mk_Prod vv n ⇒ match overline v2 n with
9 [ mk_Prod ww m ⇒ mk_Prod Crumble nat hAppValue (vv) (ww), Epsilon i m ] 10 ]
11 | appl u1 u2 ⇒ match underline t1 s with 12 [ mk_Prod c n ⇒ match c with
13 [ CCrumble b e ⇒ match overline v2 n with
14 [ mk_Prod vv m ⇒ mk_Prod Crumble nat hAppValue (var ν(m)) (vv), push e [(ν(m)) ← b]i (S m)]
15 ] 16 ] 17 ]
18 | appl u1 u2 ⇒ match underline t2 s with 19 [ mk_Prod c n ⇒ match c with
20 [ CCrumble b1 e1 ⇒ match t1 with
21 [ val_to_term v1 ⇒ match overline v1 n with
22 [ mk_Prod vv m ⇒ mk_Prod Crumble nat (at hAppValue (vv) (var (νm)), Epsilon i (push e1 [νm←b1])) (S m)]
23 | appl u1 u2 ⇒ match underline t1 n with 24 [ mk_Prod c1 n1 ⇒ match c1 with
25 [ CCrumble b e ⇒ mk_Prod Crumble nat hAppValue (var (ν(S(n1)))) (var (νn1)), concat (push e [ν(S(n1)) ← b]) (push e1 [νn1 ← b1]) i (S (S (n1)))] 26 ] 27 ] 28 ] 29 ] 30 ] 31 ] 32
33 and overline (x:pValue) (s: nat): Value × nat :=
34 match x with
35 [ pvar v ⇒ mk_Prod Value nat (var v) s 36 | abstr v t ⇒ match underline t s with
37 [ mk_Prod c n ⇒ mk_Prod Value nat (lambda (v) (c)) n ] 38 ]
39 .
Codice 6.3: Formalizzazione delle funzioni · e · in Matita.
Dal momento che la funzione underline è una funzione di codifica, ci aspet- tiamo che il suo output debba godere di alcune proprietà di ben-formatezza es- senziali per garantire il corretto funzionamento della macchina Crumble GLAM. Siccome l’aspetto peculiare del crumbling è l’inserimento di ES raggruppati in crumbled environments, è anche lecito aspettarsi che molte di queste proprietà
6.2. UNDERLINE 67 riguardino questi costrutti. In [5] una delle più importanti proprietà riguardanti la ben-formatezza delgi Environment è catturata dalla definizione informale di well-namedness.
Definizione 6.2.1 (well-namedness). Un Crumble c o un Environment e è
well-named se tutte le variabili che occorrono a sinistra di un costrutto di ES al di fuori di un’astrazione sono a due a due distinte.
Se vogliamo dare un’interpretazione intuitiva alla condizione di well-namedness, alla luce del ruolo che hanno i nomi di variabile nel contesto delle crumbling- abstract-machines, possiamo asserire innanzitutto che la parte della definizione che richiede che i nomi siano distinti fra di loro è volta a garantire che l’inter- pretazione di una variabile in un ambiente non sia ambigua, ossia che ad una medesima locazione di memoria sia associato al più un termine ala volta. La seconda parte della definizione, quella che parla delle variabili sotto astrazione, garantisce che la disciplina di valutazione non effettui riduzioni sotto astrazioni, coerentemente con quanto richiesto dalla disciplina di valutazione dei λp-termini
in 3.2.
Tuttavia questa formulazione della proprietà di well-namedness, non è abba- stanza dettagliata per permetterci di concludere i risultati attesi: è stato dunque necessario aggiungere alcuni lemmi che descrivessero con maggior dettaglio la distribuzione dei nomi di variabile freschi introdotti dalla underline.
Alcuni utili proprietà sono per esempio quelle enunciate dai seguenti lemmi:
lemma line_monotone_names:
(∀t.∀s. snd … (underline t s) s) ∧ (∀v.∀s. snd … (overline v s) s). lemma line_names:
(∀t.∀s. s fresh_var_t t → snd … (underline t s) fresh_var (fst … (underline t s))) ∧
(∀v.∀s. s fresh_var_tv v → snd … (overline v s) fresh_var_v (fst … (overline v s))).
Codice 6.4: Caratterizzazioni del secondo valore di ritorno della underline Questi due lemmi servono a garantire alcune proprietà sul secondo valore di ritorno della funzione: il primo dimostra che il secondo parametro della under- line è crescente in senso lato, mentre il secondo che il secondo valore restituito dalla underline è una variabile fresca nel Crumble restituito come primo valore. Questi due lemmi sono un’importante verifica della correttezza dell’invariante sul secondo termine restituito dalla underline esposto precedentemente, dal mo- mento che verificano formalmente che la funzione underline inserisce sempre variabili fresche nel termine.
Inoltre, tali risultati sono indispensabili per dimostrare la precondizione sul secondo argomento della funzione underline nelle ipotesi induttive quando si procede per induzione nella dimostrazione dei lemmi sulla underline: siccome la funzione underline richiede la precondizione fresh_var t ≤ s, quando
si formula un lemma sarà necessario elencarla fra le ipotesi, per questa ra- gione, quando si procederà per induzione, dimostrare tale precondizione sarà indispensabile per poter usare le ipotesi induttive.
Infine, per il secondo lemma, riusciamo ad intuire che tutti gli environment generati dalla underline hanno domini fra loro disgiunti. Un’ulteriore conferma di questo risultato (che però non verrà mai esplicitato e dimostrato formalmente) è data dai seguenti risultati, i quali asseriscono che, come aspettato, le variabili appartenente al dominio del crumbling di un termine sono comprese fra il para- mento s fornito alla underline ed il secondo valore della coppia restituita dalla funzione.
definition interval_dom := λe, b. ∀x. domb_e (νx) e =true → b ≤ x.
definition bound_dom := λe, b. ∀x. domb_e (νx) e = true → S x ≤ b.
lemma line_dom:
(∀t. ∀s. (interval_dom match (fst … (underline t s)) with [CCrumble c e ⇒ e] s)).
lemma env_bound_lemma:
(∀t. ∀s. (bound_dom match (fst … (underline t s)) with [CCrumble c e ⇒ e] (snd … (underline t s)))).
Codice 6.5: Bounds per i domini ottenuti mediante crumbling
Una volta dimostrati questi risultati, è stato finalmente possibile intra- prendere la dimostrazione degli invarianti di inizializzazione formulati da [5] riguardanti la read_back e la underline.