Lemma 4.2

La prima proposizione che [5] presenta su underline e read_back è, senza dubbio, uno dei risultati più importanti per l’inizializzazione della macchina virtuale Crumble GLAM: essa asserisce che la funzione ·↓ è l’inversa sinistra di ·. In questo modo viene assicurato che lo stato iniziale goda di una delle proprietà fondamentali per la correttezza della macchina Crumble GLAM: ossia quella che il Crumble su cui la macchina opera, se ritradotto in un λp-termine sia esattamente il termine di partenza.

Lemma 6.3.1 (4.2)

∀t.t_↓= t ∧ ∀v.v↓= v

Per facilitare il confronto con [5], specifichiamo accanto all’intestazione del lemma il numero di riferimento in [5], in questo caso: 4.2.

La dimostrazione del lemma 6.3.1 in [5] ha richiesto la dimostrazione dei lemmi tecnici che seguono.

6.3. LEMMI SU UNDERLINE E READ_BACK 69

Definizione 6.3.1. c#e := DOM(e) ∩ F V (c) = ∅ Lemma 6.3.2 (C.4)

∀b, c, e, x.x /∈ DOM (e) ∪ F V (e) → (c@[x ← b]e)↓= (c@e)↓{x ← (b, e)_↓} Lemma 6.3.3 (C.5)

∀c, e.c#e → (c@e)↓= c_↓ Lemma 6.3.4 (C.6)

∀c, e.c#e → (c@[x ← b]e)↓= c↓{x ← (b, e)↓}

Il lemma C.6 (6.3.4) non è stato dimostrato perché la dimostrazione ne faceva uso solo nel caso del termine if t then u else s, rimosso dalla grammatica dei termini.

Il lemmi C.4 e C.5 non sono stati dimostrati alla lettera a causa delle diffe-renze implementative fra le definizioni di ·↓ e · con le rispettive formalizzazioni read_back e underline, ma sono stati dimostrati lemmi che avessero simile potere espressivo. I lemmi in 6.6 hanno un ruolo simile a quelli di C.4 e C.5;

infatti, dal momento che la read_back è stata definita come wrapper della fun-zione aux_read_back (cfr. 6.2), non avrebbe avuto senso dimostrare il C.5 come formulato sopra siccome, nell’espansione della read_back, non compaiono chiamate ricorsive alla read_back stessa, bensì alla aux_read_back. Per queste ragioni, stronger_aux_read_back3 può essere visto come l’analogo del lemma C.5 in cui al posto della read_back compare la aux_read_back. Similmente, il push_lemma in 6.6 è, nella formalizzazione, l’analogo del C.4 per le medesime ragioni di cui sopra.

lemma stronger_aux_read_back3: ∀e, t.

(∀x. (domb_e x e = true → fvb_t x t = false)) → aux_read_back t e = t.

lemma push_lemma:

∀t, e, x, b. aux_read_back t (push e (subst x b)) =

aux_read_back (p_subst t (psubst x (read_back_b b)) e.

Codice 6.6: Lemmi analoghi a C.4 e C.5

Provare il lemma stronger_aux_read_back3 non è scontato: siccome la read_back agisce tramite chiamate alla p_subst, è necessario che la funzione di sostituzione su termini goda della proprietà 6.5in senso stretto. Infatti, men-tre nell’ambito teorico l’uguaglianza di termini è spesso intesa modulo alpha-conversioni, per ragioni di efficienza in [5] le uguaglianze dei termini debbono valere in senso stretto. Ma, come evidenziato in A.2, la6.5 non vale in senso stretto con la definizione canonica di sostituzione (si prenda ad esempio A.2).

Per questo motivo, per poter provare il lemma stronger_aux_read_back3, è stato necessario ridefinire la p_subst dimodoché non presentasse questa ano-malia. Per dettagli specifici sull’implementazione della p_subst, rimandiamo il lettore aA.2.

∀t, t⁰, x.x /∈ F V (t) → t{x ← t⁰} = t (6.5)

Come riportato in 6.2, la definizione della funzione underline differisce da quella della · perché altrimenti non sarebbe stato possibile implementarla in Matita. In particolare, l’ultimo caso induttivo è stato riscritto espandendo la

· fino a rendere il termine della chiamata ricorsiva sufficientemente semplice per permetter alla definizione della funzione di essere accettata da Matita. Le modifiche hanno riguardato il caso ut, scomponendolo nei sotto-casi vt e t⁰t. Queste modifiche hanno chiaramente indotto un’asimmetria fra le definizioni di underline e di ·. Per questa ragione, molti risultati che nella definizione di

· sarebbero stati disponibili come ipotesi induttive su chiamate ricorsive sono stati dovuti ricostruire per mezzo di appositi lemmi tecnici. Nel caso specifico del lemma 4.2, mentre il caso vt è analogo a quello tv, il caso t⁰t ha richiesto la definizione di due lemmi tecnici per garantire che la concatenazione dei due environment generati dalle chiamate ricorsive non creasse interferisse durante la read_back, riportati in6.7.

lemma ultra_concat_lemma:

(∀f, x, e. domb_e x f = false →

(\foralz. domb_e z f = true → fvb_e z e = false) → (aux_read_back (val_to_term (pvar x)) (concat e f)

=aux_read_back (val_to_term (pvar x)) e)).

lemma iper_concat_lemma: ∀f, e, x.

domb_e x e = false →

(aux_read_back (val_to_term (pvar x)) (concat e f)

=aux_read_back (val_to_term (pvar x)) f).

Codice 6.7: Lemmi aggiuntivi a C.4 e C.5 per il caso t⁰t

Per la dimostrazione formale del lemma6.3.1, non è stato necessario introdurre altri significativi risultati (per comodità la dimostrazione formale fa uso del primo risultato del remark6.3.6, ma la tesi sarebbe dimostrabile anche senza), al contrario è stato necessario introdurre e dimostrare un lemma riguardante la distributività dell’operazione di read_back senza il quale non è nemmeno possibile sfruttare le ipotesi immediate sui due sottotermini di un’applicazione.

Tale lemma è così semplice che nelle dimostrazioni di [5] lo si dà per scontato. In effetti è intuitivamente vero che, all’interno di un medesimo ambiente, la read_-back commuti con l’applicazione, ma giustificarlo con la definizione formale di read_back non è cosa semplice.

Lemma 6.3.5

distributività della read_back

∀t, u. read_back (appl t u) e = appl (read_back t e) (read_back u e) Dimostrazione. Per induzione su e

• Caso Epsilon, triviale

• Caso e = Snoc e' [x←b]

aux_read_back (appl t u) (Snoc e' [x←b]) =

p_subst (aux_read_back (appl t u) e') (pSubst x (read_back_b b)) =

6.3. LEMMI SU UNDERLINE E READ_BACK 71

p_subst (appl (aux_read_back t e')

(aux_read_back u e')) (pSubst x (read_back_b b))

A questo punto ci sia aspetterebbe di poter concludere utilizzando pro-prietà distributiva della funzione p_subst per procedere come segue:

p_subst (aux_read_back (appl t u) e') (pSubst x (read_back_b b)) = appl (p_subst (aux_read_back t e') (pSubst x (read_back_b b)))

(p_subst (aux_read_back t e') (pSubst x (read_back_b b))) = appl (aux_read_back t (Snoc e' [x←b]))

(aux_read_back u (Snoc e' [x←b]))

Tuttavia la dimostrazione della proprietà distributiva della p_subst non è tri-viale, perché, per ragioni di definibilità, la p_subst è stata definita per induzione sulla taglia e mediante l’uso di Σ-tipi, per cui la dimostrazione di tale proprietà è appesantita da numerosi passaggi estremamente tecnici volti ad evitare pro-blemi di tipi-dipendenti in fase di riduzione. Un’analisi più esauriente di questi fenomeni è fornita in A.2, dove sono anche presentati gli enunciati dei lemmi p_subst_distro e p_subst_bound_irrelevance (rispettivamente in A.11e in A.12) necessari ricorsivamente per la dimostrazione del lemma6.3.5.

Infine, da un punto di vista estremamente pratico, la dimostrazione del lem-ma 4.2 ha richiesto l’uso di tecniche di riduzione mirata: infatti, dal momento che la read_back effettua chiamate alla p_subst che a sua volta è zucchero sintattico per invocare la p_subst_sig con gli opportuni parametri, la taglia del goal, se normalizzato completamente, può crescere a tal punto da rendere impraticabile l’uso del proof-assistant. Un’accurata analisi della definizione del-la p_subst_sig e dei motivi per cui può causare fenomeni di esplosione deldel-la taglia dei goal è data inA.2, mentre per un rapido compendio delle tecniche di riduzione mirata e dei loro casi d’uso tipici, rimandiamo il lettore a A.4.