- probe: new application to compute some data on the proof objects of

[helm.git] / matita / matita / contribs / lambda / st_computation.ma

diff --git a/matita/matita/contribs/lambda/st_computation.ma b/matita/matita/contribs/lambda/st_computation.ma
index 61f32a37b8e30c2d0df983b69f019f878bb0c3d4..ebcc572a40b403cd4f8ee3021279d7d87e0db210 100644 (file)
--- a/matita/matita/contribs/lambda/st_computation.ma
+++ b/matita/matita/contribs/lambda/st_computation.ma
@@ -12,7 +12,8 @@
 (*                                                                        *)
 (**************************************************************************)
 
-include "labelled_sequential_computation.ma".
+include "labeled_sequential_computation.ma".
+include "pointer_list_standard.ma".
 
 (* KASHIMA'S "ST" COMPUTATION ***********************************************)
 
@@ -20,9 +21,9 @@ include "labelled_sequential_computation.ma".
          R. Kashima: "A proof of the Standization Theorem in λ-Calculus". Typescript note, (2000).
 *)
 inductive st: relation term ≝
-| st_vref: ∀s,M,i. is_head s → M ↦*[s] #i → st M (#i)
-| st_abst: ∀s,M,A1,A2. is_head s → M ↦*[s] 𝛌.A1 → st A1 A2 → st M (𝛌.A2)
-| st_appl: ∀s,M,B1,B2,A1,A2. is_head s → M ↦*[s] @B1.A1 → st B1 B2 → st A1 A2 → st M (@B2.A2)
+| st_vref: ∀s,M,i. is_whd s → M ↦*[s] #i → st M (#i)
+| st_abst: ∀s,M,A1,A2. is_whd s → M ↦*[s] 𝛌.A1 → st A1 A2 → st M (𝛌.A2)
+| st_appl: ∀s,M,B1,B2,A1,A2. is_whd s → M ↦*[s] @B1.A1 → st B1 B2 → st A1 A2 → st M (@B2.A2)
 .
 
 interpretation "'st' computation"
@@ -33,7 +34,7 @@ notation "hvbox( M ⓢ⤇* break term 46 N )"
    for @{ 'Std $M $N }.
 
 lemma st_inv_lref: ∀M,N. M ⓢ⤇* N → ∀j. #j = N →
-                   ∃∃s. is_head s & M ↦*[s] #j.
+                   ∃∃s. is_whd s & M ↦*[s] #j.
 #M #N * -M -N
 [ /2 width=3/
 | #s #M #A1 #A2 #_ #_ #_ #j #H destruct
@@ -42,7 +43,7 @@ lemma st_inv_lref: ∀M,N. M ⓢ⤇* N → ∀j. #j = N →
 qed-.
 
 lemma st_inv_abst: ∀M,N. M ⓢ⤇* N → ∀C2. 𝛌.C2 = N →
-                   ∃∃s,C1. is_head s & M ↦*[s] 𝛌.C1 & C1 ⓢ⤇* C2.
+                   ∃∃s,C1. is_whd s & M ↦*[s] 𝛌.C1 & C1 ⓢ⤇* C2.
 #M #N * -M -N
 [ #s #M #i #_ #_ #C2 #H destruct
 | #s #M #A1 #A2 #Hs #HM #A12 #C2 #H destruct /2 width=5/
@@ -51,7 +52,7 @@ lemma st_inv_abst: ∀M,N. M ⓢ⤇* N → ∀C2. 𝛌.C2 = N →
 qed-.
 
 lemma st_inv_appl: ∀M,N. M ⓢ⤇* N → ∀D2,C2. @D2.C2 = N →
-                   ∃∃s,D1,C1. is_head s & M ↦*[s] @D1.C1 & D1 ⓢ⤇* D2 & C1 ⓢ⤇* C2.
+                   ∃∃s,D1,C1. is_whd s & M ↦*[s] @D1.C1 & D1 ⓢ⤇* D2 & C1 ⓢ⤇* C2.
 #M #N * -M -N
 [ #s #M #i #_ #_ #D2 #C2 #H destruct
 | #s #M #A1 #A2 #_ #_ #_ #D2 #C2 #H destruct
@@ -63,7 +64,7 @@ lemma st_refl: reflexive … st.
 #M elim M -M /2 width=3/ /2 width=5/ /2 width=7/
 qed.
 
-lemma st_step_sn: ∀N1,N2. N1 ⓢ⤇* N2 → ∀s,M. is_head s → M ↦*[s] N1 → M ⓢ⤇* N2.
+lemma st_step_sn: ∀N1,N2. N1 ⓢ⤇* N2 → ∀s,M. is_whd s → M ↦*[s] N1 → M ⓢ⤇* N2.
 #N1 #N2 #H elim H -N1 -N2
 [ #r #N #i #Hr #HN #s #M #Hs #HMN
   lapply (lsreds_trans … HMN … HN) -N /3 width=3/
@@ -74,7 +75,7 @@ lemma st_step_sn: ∀N1,N2. N1 ⓢ⤇* N2 → ∀s,M. is_head s → M ↦*[s] N1
 ]
 qed-.
 
-lemma st_step_rc: ∀s,M1,M2. is_head s → M1 ↦*[s] M2 → M1 ⓢ⤇* M2.
+lemma st_step_rc: ∀s,M1,M2. is_whd s → M1 ↦*[s] M2 → M1 ⓢ⤇* M2.
 /3 width=5 by st_step_sn/
 qed.
 
@@ -123,21 +124,6 @@ lemma st_dsubst: dsubstable st.
 ]
 qed.
 
-lemma st_inv_lsreds_is_le: ∀M,N. M ⓢ⤇* N →
-                           ∃∃r. M ↦*[r] N & is_le r.
-#M #N #H elim H -M -N
-[ #s #M #i #Hs #HM
-  lapply (is_head_is_le … Hs) -Hs /2 width=3/
-| #s #M #A1 #A2 #Hs #HM #_ * #r #HA12 #Hr
-  lapply (lsreds_trans … HM (sn:::r) (𝛌.A2) ?) /2 width=1/ -A1 #HM
-  @(ex2_intro … HM) -M -A2 /3 width=1/
-| #s #M #B1 #B2 #A1 #A2 #Hs #HM #_ #_ * #rb #HB12 #Hrb * #ra #HA12 #Hra
-  lapply (lsreds_trans … HM (dx:::ra) (@B1.A2) ?) /2 width=1/ -A1 #HM
-  lapply (lsreds_trans … HM (sn:::rb) (@B2.A2) ?) /2 width=1/ -B1 #HM
-  @(ex2_intro … HM) -M -B2 -A2 >associative_append /3 width=1/
-]
-qed-.
-
 lemma st_step_dx: ∀p,M,M2. M ↦[p] M2 → ∀M1. M1 ⓢ⤇* M → M1 ⓢ⤇* M2.
 #p #M #M2 #H elim H -p -M -M2
 [ #B #A #M1 #H
@@ -155,12 +141,43 @@ lemma st_step_dx: ∀p,M,M2. M ↦[p] M2 → ∀M1. M1 ⓢ⤇* M → M1 ⓢ⤇*
 ]
 qed-.
 
-(* Note: we use "lapply (rewrite_r ?? is_head … Hq)" (procedural)
-         in place of "cut (is_head (q::r)) [ >Hq ]"  (declarative)
+lemma st_lsreds: ∀s,M1,M2. M1 ↦*[s] M2 → M1 ⓢ⤇* M2.
+#s #M1 #M2 #H @(lstar_ind_r ????????? H) -s -M2 // /2 width=4 by st_step_dx/
+qed.
+
+lemma st_inv_lsreds_is_standard: ∀M,N. M ⓢ⤇* N →
+                                 ∃∃r. M ↦*[r] N & is_standard r.
+#M #N #H elim H -M -N
+[ #s #M #i #Hs #HM
+  lapply (is_whd_is_standard … Hs) -Hs /2 width=3/
+| #s #M #A1 #A2 #Hs #HM #_ * #r #HA12 #Hr
+  lapply (lsreds_trans … HM (rc:::r) (𝛌.A2) ?) /2 width=1/ -A1 #HM
+  @(ex2_intro … HM) -M -A2 /3 width=1/
+| #s #M #B1 #B2 #A1 #A2 #Hs #HM #_ #_ * #rb #HB12 #Hrb * #ra #HA12 #Hra
+  lapply (lsreds_trans … HM (dx:::ra) (@B1.A2) ?) /2 width=1/ -A1 #HM
+  lapply (lsreds_trans … HM (sn:::rb) (@B2.A2) ?) /2 width=1/ -B1 #HM
+  @(ex2_intro … HM) -M -B2 -A2 >associative_append /3 width=1/
+]
+qed-.
+
+theorem st_trans: transitive … st.
+#M1 #M #M2 #HM1 #HM2
+elim (st_inv_lsreds_is_standard … HM1) -HM1 #s1 #HM1 #_
+elim (st_inv_lsreds_is_standard … HM2) -HM2 #s2 #HM2 #_
+lapply (lsreds_trans … HM1 … HM2) -M /2 width=2/
+qed-.
+
+theorem lsreds_standard: ∀s,M,N. M ↦*[s] N → ∃∃r. M ↦*[r] N & is_standard r.
+#s #M #N #H
+@st_inv_lsreds_is_standard /2 width=2/
+qed-.
+
+(* Note: we use "lapply (rewrite_r ?? is_whd … Hq)" (procedural)
+         in place of "cut (is_whd (q::r)) [ >Hq ]"  (declarative)
 *)
-lemma st_lsred_swap: ∀p. in_head p → ∀N1,N2. N1 ↦[p] N2 → ∀M1. M1 ⓢ⤇* N1 →
-                     ∃∃q,M2. in_head q & M1 ↦[q] M2 & M2 ⓢ⤇* N2.
-#p #H @(in_head_ind … H) -p
+lemma st_lsred_swap: ∀p. in_whd p → ∀N1,N2. N1 ↦[p] N2 → ∀M1. M1 ⓢ⤇* N1 →
+                     ∃∃q,M2. in_whd q & M1 ↦[q] M2 & M2 ⓢ⤇* N2.
+#p #H @(in_whd_ind … H) -p
 [ #N1 #N2 #H1 #M1 #H2
   elim (lsred_inv_nil … H1 ?) -H1 // #D #C #HN1 #HN2
   elim (st_inv_appl … H2 … HN1) -N1 #s1 #D1 #N #Hs1 #HM1 #HD1 #H
@@ -170,7 +187,7 @@ lemma st_lsred_swap: ∀p. in_head p → ∀N1,N2. N1 ↦[p] N2 → ∀M1. M1 
   elim (lsreds_inv_pos … HM1 ?) -HM1
   [2: >length_append normalize in ⊢ (??(??%)); // ]
   #q #r #M #Hq #HM1 #HM
-  lapply (rewrite_r ?? is_head … Hq) -Hq /4 width=1/ -s1 -s2 * #Hq #Hr
+  lapply (rewrite_r ?? is_whd … Hq) -Hq /4 width=1/ -s1 -s2 * #Hq #Hr
   @(ex3_2_intro … HM1) -M1 // -q
   @(st_step_sn … HM) /2 width=1/
 | #p #_ #IHp #N1 #N2 #H1 #M1 #H2
@@ -181,33 +198,17 @@ lemma st_lsred_swap: ∀p. in_head p → ∀N1,N2. N1 ↦[p] N2 → ∀M1. M1 
   elim (lsreds_inv_pos … HM1 ?) -HM1
   [2: >length_append normalize in ⊢ (??(??%)); // ]
   #q #r #M #Hq #HM1 #HM
-  lapply (rewrite_r ?? is_head … Hq) -Hq /4 width=1/ -p -s * #Hq #Hr
+  lapply (rewrite_r ?? is_whd … Hq) -Hq /4 width=1/ -p -s * #Hq #Hr
   @(ex3_2_intro … HM1) -M1 // -q /2 width=7/
 ]
 qed-.
 
-lemma st_lsreds: ∀s,M1,M2. M1 ↦*[s] M2 → M1 ⓢ⤇* M2.
-#s #M1 #M2 #H @(lstar_ind_r ????????? H) -s -M2 // /2 width=4 by st_step_dx/
-qed.
-
-theorem st_trans: transitive … st.
-#M1 #M #M2 #HM1 #HM2
-elim (st_inv_lsreds_is_le … HM1) -HM1 #s1 #HM1 #_
-elim (st_inv_lsreds_is_le … HM2) -HM2 #s2 #HM2 #_
-lapply (lsreds_trans … HM1 … HM2) -M /2 width=2/
-qed-.
-
-theorem lsreds_standard: ∀s,M,N. M ↦*[s] N → ∃∃r. M ↦*[r] N & is_le r.
-#s #M #N #H
-@st_inv_lsreds_is_le /2 width=2/
-qed-.
-
-theorem lsreds_lhap1_swap: ∀s,M1,N1. M1 ↦*[s] N1 →
-                           ∀p,N2. in_head p → N1 ↦[p] N2 →
-                           ∃∃q,r,M2. in_head q & M1 ↦[q] M2 & M2 ↦*[r] N2 &
-                                     is_le (q::r).
+theorem lsreds_lsred_swap: ∀s,M1,N1. M1 ↦*[s] N1 →
+                           ∀p,N2. in_whd p → N1 ↦[p] N2 →
+                           ∃∃q,r,M2. in_whd q & M1 ↦[q] M2 & M2 ↦*[r] N2 &
+                                     is_standard (q::r).
 #s #M1 #N1 #HMN1 #p #N2 #Hp #HN12
 lapply (st_lsreds … HMN1) -s #HMN1
 elim (st_lsred_swap … Hp … HN12 … HMN1) -p -N1 #q #M2 #Hq #HM12 #HMN2
-elim (st_inv_lsreds_is_le … HMN2) -HMN2 /3 width=8/
+elim (st_inv_lsreds_is_standard … HMN2) -HMN2 /3 width=8/
 qed-.