From a76f56fdad6348b167376093920650379c9936d4 Mon Sep 17 00:00:00 2001 From: Ferruccio Guidi Date: Mon, 7 Apr 2014 19:53:54 +0000 Subject: [PATCH] some resuls on pointwise extensions (all of them are now in the "relocation" component --- .../lambdadelta/basic_2/computation/lprs.ma | 2 +- .../basic_2/notation/relations/lazyor_4.ma | 19 ++ .../lambdadelta/basic_2/reduction/lpr.ma | 2 +- .../basic_2/reduction/lpr_ldrop.ma | 2 +- .../lambdadelta/basic_2/reduction/lpr_lpr.ma | 2 +- .../lift_neg.etc => relocation/lift_neg.ma} | 0 .../lambdadelta/basic_2/relocation/llor.ma | 55 ++++++ .../llpx_sn_alt.ma} | 178 ++++++++---------- .../basic_2/relocation/llpx_sn_lpx_sn.ma | 2 +- .../basic_2/{grammar => relocation}/lpx_sn.ma | 0 .../basic_2/relocation/lpx_sn_alt.ma | 150 +++++++++++++++ .../{ldrop_lpx_sn.ma => lpx_sn_ldrop.ma} | 6 +- .../{grammar => relocation}/lpx_sn_lpx_sn.ma | 2 +- .../{grammar => relocation}/lpx_sn_tc.ma | 2 +- .../lleq_alt.etc => substitution/lleq_alt.ma} | 10 +- .../lambdadelta/basic_2/web/basic_2_src.tbl | 8 +- 16 files changed, 319 insertions(+), 121 deletions(-) create mode 100644 matita/matita/contribs/lambdadelta/basic_2/notation/relations/lazyor_4.ma rename matita/matita/contribs/lambdadelta/basic_2/{etc/llpx_sn/lift_neg.etc => relocation/lift_neg.ma} (100%) create mode 100644 matita/matita/contribs/lambdadelta/basic_2/relocation/llor.ma rename matita/matita/contribs/lambdadelta/basic_2/{etc/llpx_sn/llpx_sn_alt.etc => relocation/llpx_sn_alt.ma} (62%) rename matita/matita/contribs/lambdadelta/basic_2/{grammar => relocation}/lpx_sn.ma (100%) create mode 100644 matita/matita/contribs/lambdadelta/basic_2/relocation/lpx_sn_alt.ma rename matita/matita/contribs/lambdadelta/basic_2/relocation/{ldrop_lpx_sn.ma => lpx_sn_ldrop.ma} (96%) rename matita/matita/contribs/lambdadelta/basic_2/{grammar => relocation}/lpx_sn_lpx_sn.ma (98%) rename matita/matita/contribs/lambdadelta/basic_2/{grammar => relocation}/lpx_sn_tc.ma (99%) rename matita/matita/contribs/lambdadelta/basic_2/{etc/llpx_sn/lleq_alt.etc => substitution/lleq_alt.ma} (89%) diff --git a/matita/matita/contribs/lambdadelta/basic_2/computation/lprs.ma b/matita/matita/contribs/lambdadelta/basic_2/computation/lprs.ma index 6e8431959..c3d7203df 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/computation/lprs.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/computation/lprs.ma @@ -13,7 +13,7 @@ (**************************************************************************) include "basic_2/notation/relations/predsnstar_3.ma". -include "basic_2/grammar/lpx_sn_tc.ma". +include "basic_2/relocation/lpx_sn_tc.ma". include "basic_2/reduction/lpr.ma". (* SN PARALLEL COMPUTATION ON LOCAL ENVIRONMENTS ****************************) diff --git a/matita/matita/contribs/lambdadelta/basic_2/notation/relations/lazyor_4.ma b/matita/matita/contribs/lambdadelta/basic_2/notation/relations/lazyor_4.ma new file mode 100644 index 000000000..cc97e6bbe --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/notation/relations/lazyor_4.ma @@ -0,0 +1,19 @@ +(**************************************************************************) +(* ___ *) +(* ||M|| *) +(* ||A|| A project by Andrea Asperti *) +(* ||T|| *) +(* ||I|| Developers: *) +(* ||T|| The HELM team. *) +(* ||A|| http://helm.cs.unibo.it *) +(* \ / *) +(* \ / This file is distributed under the terms of the *) +(* v GNU General Public License Version 2 *) +(* *) +(**************************************************************************) + +(* NOTATION FOR THE FORMAL SYSTEM λδ ****************************************) + +notation "hvbox( L1 ⩖ break [ term 46 T ] break term 46 L2 ≡ break term 46 L )" + non associative with precedence 45 + for @{ 'LazyOr $L1 $T $L2 $L }. diff --git a/matita/matita/contribs/lambdadelta/basic_2/reduction/lpr.ma b/matita/matita/contribs/lambdadelta/basic_2/reduction/lpr.ma index 7bcf22df5..01966eefb 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/reduction/lpr.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/reduction/lpr.ma @@ -13,7 +13,7 @@ (**************************************************************************) include "basic_2/notation/relations/predsn_3.ma". -include "basic_2/grammar/lpx_sn.ma". +include "basic_2/relocation/lpx_sn.ma". include "basic_2/reduction/cpr.ma". (* SN PARALLEL REDUCTION FOR LOCAL ENVIRONMENTS *****************************) diff --git a/matita/matita/contribs/lambdadelta/basic_2/reduction/lpr_ldrop.ma b/matita/matita/contribs/lambdadelta/basic_2/reduction/lpr_ldrop.ma index 4156df6ea..c8443e08b 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/reduction/lpr_ldrop.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/reduction/lpr_ldrop.ma @@ -12,8 +12,8 @@ (* *) (**************************************************************************) +include "basic_2/relocation/lpx_sn_ldrop.ma". include "basic_2/relocation/fquq_alt.ma". -include "basic_2/relocation/ldrop_lpx_sn.ma". include "basic_2/reduction/cpr_lift.ma". include "basic_2/reduction/lpr.ma". diff --git a/matita/matita/contribs/lambdadelta/basic_2/reduction/lpr_lpr.ma b/matita/matita/contribs/lambdadelta/basic_2/reduction/lpr_lpr.ma index 7b65286ab..2f653c61b 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/reduction/lpr_lpr.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/reduction/lpr_lpr.ma @@ -12,7 +12,7 @@ (* *) (**************************************************************************) -include "basic_2/grammar/lpx_sn_lpx_sn.ma". +include "basic_2/relocation/lpx_sn_lpx_sn.ma". include "basic_2/substitution/fqup.ma". include "basic_2/reduction/lpr_ldrop.ma". diff --git a/matita/matita/contribs/lambdadelta/basic_2/etc/llpx_sn/lift_neg.etc b/matita/matita/contribs/lambdadelta/basic_2/relocation/lift_neg.ma similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/etc/llpx_sn/lift_neg.etc rename to matita/matita/contribs/lambdadelta/basic_2/relocation/lift_neg.ma diff --git a/matita/matita/contribs/lambdadelta/basic_2/relocation/llor.ma b/matita/matita/contribs/lambdadelta/basic_2/relocation/llor.ma new file mode 100644 index 000000000..8c76ecc02 --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/relocation/llor.ma @@ -0,0 +1,55 @@ +(**************************************************************************) +(* ___ *) +(* ||M|| *) +(* ||A|| A project by Andrea Asperti *) +(* ||T|| *) +(* ||I|| Developers: *) +(* ||T|| The HELM team. *) +(* ||A|| http://helm.cs.unibo.it *) +(* \ / *) +(* \ / This file is distributed under the terms of the *) +(* v GNU General Public License Version 2 *) +(* *) +(**************************************************************************) + +include "basic_2/notation/relations/lazyor_4.ma". +include "basic_2/relocation/lpx_sn_alt.ma". + +(* LAZY UNION FOR LOCAL ENVIRONMENTS ****************************************) + +inductive clor (T) (L2) (K1) (V1): predicate term ≝ +| clor_sn: ∀U. |K1| < |L2| → ⇧[|L2|-|K1|-1, 1] U ≡ T → clor T L2 K1 V1 V1 +| clor_dx: ∀I,K2,V2. |K1| < |L2| → (∀U. ⇧[|L2|-|K1|-1, 1] U ≡ T → ⊥) → + ⇩[|L2|-|K1|-1] L2 ≡ K2.ⓑ{I}V2 → clor T L2 K1 V1 V2 +. + +definition llor: relation4 term lenv lenv lenv ≝ + λT,L2. lpx_sn (clor T L2). + +interpretation + "lazy union (local environment)" + 'LazyOr L1 T L2 L = (llor T L2 L1 L). + +(* Basic properties *********************************************************) + +lemma llor_pair_sn: ∀I,L1,L2,L,V,T,U. L1 ⩖[T] L2 ≡ L → + |L1| < |L2| → ⇧[|L2|-|L1|-1, 1] U ≡ T → + L1.ⓑ{I}V ⩖[T] L2 ≡ L.ⓑ{I}V. +/3 width=2 by clor_sn, lpx_sn_pair/ qed. + +lemma llor_pair_dx: ∀I,J,L1,L2,L,K2,V1,V2,T. L1 ⩖[T] L2 ≡ L → + |L1| < |L2| → (∀U. ⇧[|L2|-|L1|-1, 1] U ≡ T → ⊥) → + ⇩[|L2|-|L1|-1] L2 ≡ K2.ⓑ{J}V2 → + L1.ⓑ{I}V1 ⩖[T] L2 ≡ L.ⓑ{I}V2. +/4 width=3 by clor_dx, lpx_sn_pair/ qed. + +lemma llor_total: ∀T,L2,L1. |L1| ≤ |L2| → ∃L. L1 ⩖[T] L2 ≡ L. +#T #L2 #L1 elim L1 -L1 /2 width=2 by ex_intro/ +#L1 #I1 #V1 #IHL1 normalize +#H elim IHL1 -IHL1 /2 width=3 by transitive_le/ +#L #HT elim (is_lift_dec T (|L2|-|L1|-1) 1) +[ * /3 width=2 by llor_pair_sn, ex_intro/ +| elim (ldrop_O1_lt L2 (|L2|-|L1|-1)) + /5 width=4 by llor_pair_dx, monotonic_lt_minus_l, ex_intro/ +] +qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/etc/llpx_sn/llpx_sn_alt.etc b/matita/matita/contribs/lambdadelta/basic_2/relocation/llpx_sn_alt.ma similarity index 62% rename from matita/matita/contribs/lambdadelta/basic_2/etc/llpx_sn/llpx_sn_alt.etc rename to matita/matita/contribs/lambdadelta/basic_2/relocation/llpx_sn_alt.ma index 4356553ff..1da11d013 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/etc/llpx_sn/llpx_sn_alt.etc +++ b/matita/matita/contribs/lambdadelta/basic_2/relocation/llpx_sn_alt.ma @@ -22,16 +22,16 @@ include "basic_2/relocation/llpx_sn.ma". inductive llpx_sn_alt (R:relation3 lenv term term): relation4 ynat term lenv lenv ≝ | llpx_sn_alt_intro: ∀L1,L2,T,d. (∀I1,I2,K1,K2,V1,V2,i. d ≤ yinj i → (∀U. ⇧[i, 1] U ≡ T → ⊥) → - ⇩[i] L1 ≡ K1.ⓑ{I1}V1 → ⇩[i] L2 ≡ K2.ⓑ{I2}V2 → I1 = I2 ∧ R K1 V1 V2 + ⇩[i] L1 ≡ K1.ⓑ{I1}V1 → ⇩[i] L2 ≡ K2.ⓑ{I2}V2 → I1 = I2 ∧ R K1 V1 V2 ) → (∀I1,I2,K1,K2,V1,V2,i. d ≤ yinj i → (∀U. ⇧[i, 1] U ≡ T → ⊥) → - ⇩[i] L1 ≡ K1.ⓑ{I1}V1 → ⇩[i] L2 ≡ K2.ⓑ{I2}V2 → llpx_sn_alt R 0 V1 K1 K2 + ⇩[i] L1 ≡ K1.ⓑ{I1}V1 → ⇩[i] L2 ≡ K2.ⓑ{I2}V2 → llpx_sn_alt R 0 V1 K1 K2 ) → |L1| = |L2| → llpx_sn_alt R d T L1 L2 . -(* Basic forward lemmas ******************************************************) +(* Basic inversion lemmas ****************************************************) -lemma llpx_sn_alt_fwd_gen: ∀R,L1,L2,T,d. llpx_sn_alt R d T L1 L2 → +lemma llpx_sn_alt_inv_gen: ∀R,L1,L2,T,d. llpx_sn_alt R d T L1 L2 → |L1| = |L2| ∧ ∀I1,I2,K1,K2,V1,V2,i. d ≤ yinj i → (∀U. ⇧[i, 1] U ≡ T → ⊥) → ⇩[i] L1 ≡ K1.ⓑ{I1}V1 → ⇩[i] L2 ≡ K2.ⓑ{I2}V2 → @@ -42,26 +42,35 @@ lemma llpx_sn_alt_fwd_gen: ∀R,L1,L2,T,d. llpx_sn_alt R d T L1 L2 → elim (IH1 … HnT HLK1 HLK2) -IH1 /4 width=8 by and3_intro/ qed-. -lemma llpx_sn_alt_fwd_length: ∀R,L1,L2,T,d. llpx_sn_alt R d T L1 L2 → |L1| = |L2|. -#R #L1 #L2 #T #d * -L1 -L2 -T -d // +lemma llpx_sn_alt_inv_flat: ∀R,I,L1,L2,V,T,d. llpx_sn_alt R d (ⓕ{I}V.T) L1 L2 → + llpx_sn_alt R d V L1 L2 ∧ llpx_sn_alt R d T L1 L2. +#R #I #L1 #L2 #V #T #d #H elim (llpx_sn_alt_inv_gen … H) -H +#HL12 #IH @conj @llpx_sn_alt_intro // -HL12 +#I1 #I2 #K1 #K2 #V1 #V2 #i #Hdi #H #HLK1 #HLK2 +elim (IH … HLK1 HLK2) -IH -HLK1 -HLK2 +/3 width=8 by nlift_flat_sn, nlift_flat_dx, conj/ qed-. -fact llpx_sn_alt_fwd_lref_aux: ∀R,L1,L2,X,d. llpx_sn_alt R d X L1 L2 → ∀i. X = #i → - ∨∨ |L1| ≤ i ∧ |L2| ≤ i - | yinj i < d - | ∃∃I,K1,K2,V1,V2. ⇩[i] L1 ≡ K1.ⓑ{I}V1 & - ⇩[i] L2 ≡ K2.ⓑ{I}V2 & - llpx_sn_alt R (yinj 0) V1 K1 K2 & - R K1 V1 V2 & d ≤ yinj i. -#R #L1 #L2 #X #d * -L1 -L2 -X -d -#L1 #L2 #X #d #H1X #H2X #HL12 #i #H destruct -elim (lt_or_ge i (|L1|)) /3 width=1 by or3_intro0, conj/ -elim (ylt_split i d) /3 width=1 by or3_intro1/ -#Hdi #HL1 elim (ldrop_O1_lt … HL1) #I1 #K1 #V1 #HLK1 -elim (ldrop_O1_lt L2 i) // #I2 #K2 #V2 #HLK2 -elim (H1X … HLK1 HLK2) -H1X /2 width=3 by nlift_lref_be_SO/ #H #HV12 destruct -lapply (H2X … HLK1 HLK2) -H2X /2 width=3 by nlift_lref_be_SO/ -/3 width=9 by or3_intro2, ex5_5_intro/ +lemma llpx_sn_alt_inv_bind: ∀R,a,I,L1,L2,V,T,d. llpx_sn_alt R d (ⓑ{a,I}V.T) L1 L2 → + llpx_sn_alt R d V L1 L2 ∧ llpx_sn_alt R (⫯d) T (L1.ⓑ{I}V) (L2.ⓑ{I}V). +#R #a #I #L1 #L2 #V #T #d #H elim (llpx_sn_alt_inv_gen … H) -H +#HL12 #IH @conj @llpx_sn_alt_intro [3,6: normalize // ] -HL12 +#I1 #I2 #K1 #K2 #V1 #V2 #i #Hdi #H #HLK1 #HLK2 +[1,2: elim (IH … HLK1 HLK2) -IH -HLK1 -HLK2 + /3 width=9 by nlift_bind_sn, conj/ +|3,4: lapply (yle_inv_succ1 … Hdi) -Hdi * #Hdi #Hi + lapply (ldrop_inv_drop1_lt … HLK1 ?) -HLK1 /2 width=1 by ylt_O/ #HLK1 + lapply (ldrop_inv_drop1_lt … HLK2 ?) -HLK2 /2 width=1 by ylt_O/ #HLK2 + elim (IH … HLK1 HLK2) -IH -HLK1 -HLK2 + [1,3,4,6: /2 width=1 by conj/ ] + @nlift_bind_dx