matita/matita/lib/lambda/paths/dst_computation.ma

   1 (**************************************************************************)
   2 (*       ___                                                              *)
   3 (*      ||M||                                                             *)
   4 (*      ||A||       A project by Andrea Asperti                           *)
   5 (*      ||T||                                                             *)
   6 (*      ||I||       Developers:                                           *)
   7 (*      ||T||         The HELM team.                                      *)
   8 (*      ||A||         http://helm.cs.unibo.it                             *)
   9 (*      \   /                                                             *)
  10 (*       \ /        This file is distributed under the terms of the       *)
  11 (*        v         GNU General Public License Version 2                  *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 include "lambda/paths/standard_trace.ma".
  16 include "lambda/paths/labeled_sequential_computation.ma".
  17
  18 include "lambda/notation/relations/decomposedstd_2.ma".
  19
  20 (* DECOMPOSED STANDARD COMPUTATION ***********************************************)
  21
  22 (* Note: this is the "standard" computation of:
  23          R. Kashima: "A proof of the Standization Theorem in λ-Calculus". (2000).
  24 *)
  25 inductive dst: relation term ≝
  26 | dst_vref: ∀s,M,i. is_whd s → M ↦*[s] #i → dst M (#i)
  27 | dst_abst: ∀s,M,A1,A2. is_whd s → M ↦*[s] 𝛌.A1 → dst A1 A2 → dst M (𝛌.A2)
  28 | dst_appl: ∀s,M,B1,B2,A1,A2. is_whd s → M ↦*[s] @B1.A1 → dst B1 B2 → dst A1 A2 → dst M (@B2.A2)
  29 .
  30
  31 interpretation "decomposed standard computation"
  32     'DecomposedStd M N = (dst M N).
  33
  34 lemma dst_inv_lref: ∀M,N. M ⓢ↦* N → ∀j. #j = N →
  35                     ∃∃s. is_whd s & M ↦*[s] #j.
  36 #M #N * -M -N
  37 [ /2 width=3/
  38 | #s #M #A1 #A2 #_ #_ #_ #j #H destruct
  39 | #s #M #B1 #B2 #A1 #A2 #_ #_ #_ #_ #j #H destruct
  40 ]
  41 qed-.
  42
  43 lemma dst_inv_abst: ∀M,N. M ⓢ↦* N → ∀C2. 𝛌.C2 = N →
  44                     ∃∃s,C1. is_whd s & M ↦*[s] 𝛌.C1 & C1 ⓢ↦* C2.
  45 #M #N * -M -N
  46 [ #s #M #i #_ #_ #C2 #H destruct
  47 | #s #M #A1 #A2 #Hs #HM #A12 #C2 #H destruct /2 width=5/
  48 | #s #M #B1 #B2 #A1 #A2 #_ #_ #_ #_ #C2 #H destruct
  49 ]
  50 qed-.
  51
  52 lemma dst_inv_appl: ∀M,N. M ⓢ↦* N → ∀D2,C2. @D2.C2 = N →
  53                     ∃∃s,D1,C1. is_whd s & M ↦*[s] @D1.C1 & D1 ⓢ↦* D2 & C1 ⓢ↦* C2.
  54 #M #N * -M -N
  55 [ #s #M #i #_ #_ #D2 #C2 #H destruct
  56 | #s #M #A1 #A2 #_ #_ #_ #D2 #C2 #H destruct
  57 | #s #M #B1 #B2 #A1 #A2 #Hs #HM #HB12 #HA12 #D2 #C2 #H destruct /2 width=7/
  58 ]
  59 qed-.
  60
  61 lemma dst_refl: reflexive … dst.
  62 #M elim M -M /2 width=3/ /2 width=5/ /2 width=7/
  63 qed.
  64
  65 lemma dst_step_sn: ∀N1,N2. N1 ⓢ↦* N2 → ∀s,M. is_whd s → M ↦*[s] N1 → M ⓢ↦* N2.
  66 #N1 #N2 #H elim H -N1 -N2
  67 [ #r #N #i #Hr #HN #s #M #Hs #HMN
  68   lapply (pl_sreds_trans … HMN … HN) -N /3 width=3/
  69 | #r #N #C1 #C2 #Hr #HN #_ #IHC12 #s #M #Hs #HMN
  70   lapply (pl_sreds_trans … HMN … HN) -N /3 width=7/
  71 | #r #N #D1 #D2 #C1 #C2 #Hr #HN #_ #_ #IHD12 #IHC12 #s #M #Hs #HMN
  72   lapply (pl_sreds_trans … HMN … HN) -N /3 width=9/
  73 ]
  74 qed-.
  75
  76 lemma dst_step_rc: ∀s,M1,M2. is_whd s → M1 ↦*[s] M2 → M1 ⓢ↦* M2.
  77 /3 width=5 by dst_step_sn/
  78 qed.
  79
  80 lemma dst_lift: liftable dst.
  81 #h #M1 #M2 #H elim H -M1 -M2
  82 [ /3 width=3/
  83 | #s #M #A1 #A2 #Hs #HM #_ #IHA12 #d
  84   @(dst_abst … Hs) [2: @(pl_sreds_lift … HM) | skip ] -M // (**) (* auto fails here *)
  85 | #s #M #B1 #B2 #A1 #A2 #Hs #HM #_ #_ #IHB12 #IHA12 #d
  86   @(dst_appl … Hs) [3: @(pl_sreds_lift … HM) |1,2: skip ] -M // (**) (* auto fails here *)
  87 ]
  88 qed.
  89
  90 lemma dst_inv_lift: deliftable_sn dst.
  91 #h #N1 #N2 #H elim H -N1 -N2
  92 [ #s #N1 #i #Hs #HN1 #d #M1 #HMN1
  93   elim (pl_sreds_inv_lift … HN1 … HMN1) -N1 /3 width=3/
  94 | #s #N1 #C1 #C2 #Hs  #HN1 #_ #IHC12 #d #M1 #HMN1
  95   elim (pl_sreds_inv_lift … HN1 … HMN1) -N1 #M2 #HM12 #HM2
  96   elim (lift_inv_abst … HM2) -HM2 #A1 #HAC1 #HM2 destruct
  97   elim (IHC12 …) -IHC12 [4: // |2,3: skip ] #A2 #HA12 #HAC2 destruct (**) (* simplify line *)
  98   @(ex2_intro … (𝛌.A2)) // /2 width=5/
  99 | #s #N1 #D1 #D2 #C1 #C2 #Hs #HN1 #_ #_ #IHD12 #IHC12 #d #M1 #HMN1
 100   elim (pl_sreds_inv_lift … HN1 … HMN1) -N1 #M2 #HM12 #HM2
 101   elim (lift_inv_appl … HM2) -HM2 #B1 #A1 #HBD1 #HAC1 #HM2 destruct
 102   elim (IHD12 …) -IHD12 [4: // |2,3: skip ] #B2 #HB12 #HBD2 destruct (**) (* simplify line *)
 103   elim (IHC12 …) -IHC12 [4: // |2,3: skip ] #A2 #HA12 #HAC2 destruct (**) (* simplify line *)
 104   @(ex2_intro … (@B2.A2)) // /2 width=7/
 105 ]
 106 qed-.
 107
 108 lemma dst_dsubst: dsubstable dst.
 109 #N1 #N2 #HN12 #M1 #M2 #H elim H -M1 -M2
 110 [ #s #M #i #Hs #HM #d elim (lt_or_eq_or_gt i d) #Hid
 111   [ lapply (pl_sreds_dsubst … N1 … HM d) -HM
 112     >(dsubst_vref_lt … Hid) >(dsubst_vref_lt … Hid) /2 width=3/
 113   | destruct >dsubst_vref_eq
 114     @(dst_step_sn (↑[0,i]N1) … s) /2 width=1/
 115   | lapply (pl_sreds_dsubst … N1 … HM d) -HM
 116     >(dsubst_vref_gt … Hid) >(dsubst_vref_gt … Hid) /2 width=3/
 117   ]
 118 | #s #M #A1 #A2 #Hs #HM #_ #IHA12 #d
 119   lapply (pl_sreds_dsubst … N1 … HM d) -HM /2 width=5/ (**) (* auto needs some help here *)
 120 | #s #M #B1 #B2 #A1 #A2 #Hs #HM #_ #_ #IHB12 #IHA12 #d
 121   lapply (pl_sreds_dsubst … N1 … HM d) -HM /2 width=7/ (**) (* auto needs some help here *)
 122 ]
 123 qed.
 124
 125 lemma dst_step_dx: ∀p,M,M2. M ↦[p] M2 → ∀M1. M1 ⓢ↦* M → M1 ⓢ↦* M2.
 126 #p #M #M2 #H elim H -p -M -M2
 127 [ #B #A #M1 #H
 128   elim (dst_inv_appl … H …) -H [4: // |2,3: skip ] #s #B1 #M #Hs #HM1 #HB1 #H (**) (* simplify line *)
 129   elim (dst_inv_abst … H …) -H [3: // |2: skip ] #r #A1 #Hr #HM #HA1 (**) (* simplify line *)
 130   lapply (pl_sreds_trans … HM1 … (dx:::r) (@B1.𝛌.A1) ?) /2 width=1/ -M #HM1
 131   lapply (pl_sreds_step_dx … HM1 (◊) ([↙B1]A1) ?) -HM1 // #HM1
 132   @(dst_step_sn … HM1) /2 width=1/ /4 width=1/
 133 | #p #A #A2 #_ #IHA2 #M1 #H
 134   elim (dst_inv_abst … H …) -H [3: // |2: skip ] /3 width=5/ (**) (* simplify line *)
 135 | #p #B #B2 #A #_ #IHB2 #M1 #H
 136   elim (dst_inv_appl … H …) -H [4: // |2,3: skip ] /3 width=7/ (**) (* simplify line *)
 137 | #p #B #A #A2 #_ #IHA2 #M1 #H
 138   elim (dst_inv_appl … H …) -H [4: // |2,3: skip ] /3 width=7/ (**) (* simplify line *)
 139 ]
 140 qed-.
 141
 142 lemma pl_sreds_dst: ∀s,M1,M2. M1 ↦*[s] M2 → M1 ⓢ↦* M2.
 143 #s #M1 #M2 #H @(lstar_ind_r … s M2 H) -s -M2 // /2 width=4 by dst_step_dx/
 144 qed.
 145
 146 lemma dst_inv_pl_sreds_is_standard: ∀M,N. M ⓢ↦* N →
 147                                     ∃∃r. M ↦*[r] N & is_standard r.
 148 #M #N #H elim H -M -N
 149 [ #s #M #i #Hs #HM
 150   lapply (is_whd_is_standard … Hs) -Hs /2 width=3/
 151 | #s #M #A1 #A2 #Hs #HM #_ * #r #HA12 #Hr
 152   lapply (pl_sreds_trans … HM (rc:::r) (𝛌.A2) ?) /2 width=1/ -A1 #HM
 153   @(ex2_intro … HM) -M -A2 /3 width=1/
 154 | #s #M #B1 #B2 #A1 #A2 #Hs #HM #_ #_ * #rb #HB12 #Hrb * #ra #HA12 #Hra
 155   lapply (pl_sreds_trans … HM (dx:::ra) (@B1.A2) ?) /2 width=1/ -A1 #HM
 156   lapply (pl_sreds_trans … HM (sn:::rb) (@B2.A2) ?) /2 width=1/ -B1 #HM
 157   @(ex2_intro … HM) -M -B2 -A2 >associative_append /3 width=1/
 158 ]
 159 qed-.
 160
 161 theorem dst_trans: transitive … dst.
 162 #M1 #M #M2 #HM1 #HM2
 163 elim (dst_inv_pl_sreds_is_standard … HM1) -HM1 #s1 #HM1 #_
 164 elim (dst_inv_pl_sreds_is_standard … HM2) -HM2 #s2 #HM2 #_
 165 lapply (pl_sreds_trans … HM1 … HM2) -M /2 width=2/
 166 qed-.
 167
 168 theorem pl_sreds_standard: ∀s,M,N. M ↦*[s] N → ∃∃r. M ↦*[r] N & is_standard r.
 169 #s #M #N #H
 170 @dst_inv_pl_sreds_is_standard /2 width=2/
 171 qed-.
 172
 173 (* Note: we use "lapply (rewrite_r ?? is_whd … Hq)" (procedural)
 174          in place of "cut (is_whd (q::r)) [ >Hq ]"  (declarative)
 175 *)
 176 lemma dst_in_whd_swap: ∀p. in_whd p → ∀N1,N2. N1 ↦[p] N2 → ∀M1. M1 ⓢ↦* N1 →
 177                        ∃∃q,M2. in_whd q & M1 ↦[q] M2 & M2 ⓢ↦* N2.
 178 #p #H @(in_whd_ind … H) -p
 179 [ #N1 #N2 #H1 #M1 #H2
 180   elim (pl_sred_inv_nil … H1 …) -H1 // #D #C #HN1 #HN2
 181   elim (dst_inv_appl … H2 … HN1) -N1 #s1 #D1 #N #Hs1 #HM1 #HD1 #H
 182   elim (dst_inv_abst … H …) -H [3: // |2: skip ] #s2 #C1 #Hs2 #HN #HC1 (**) (* simplify line *)
 183   lapply (pl_sreds_trans … HM1 … (dx:::s2) (@D1.𝛌.C1) ?) /2 width=1/ -N #HM1
 184   lapply (pl_sreds_step_dx … HM1 (◊) ([↙D1]C1) ?) -HM1 // #HM1
 185   elim (pl_sreds_inv_pos … HM1 …) -HM1
 186   [2: >length_append normalize in ⊢ (??(??%)); // ]
 187   #q #r #M #Hq #HM1 #HM
 188   lapply (rewrite_r ?? is_whd … Hq) -Hq /4 width=1/ -s1 -s2 * #Hq #Hr
 189   @(ex3_2_intro … HM1) -M1 // -q
 190   @(dst_step_sn … HM) /2 width=1/
 191 | #p #_ #IHp #N1 #N2 #H1 #M1 #H2
 192   elim (pl_sred_inv_dx … H1 …) -H1 [3: // |2: skip ] #D #C1 #C2 #HC12 #HN1 #HN2 (**) (* simplify line *)
 193   elim (dst_inv_appl … H2 … HN1) -N1 #s #B #A1 #Hs #HM1 #HBD #HAC1
 194   elim (IHp … HC12 … HAC1) -p -C1 #p #C1 #Hp #HAC1 #HC12
 195   lapply (pl_sreds_step_dx … HM1 (dx::p) (@B.C1) ?) -HM1 /2 width=1/ -A1 #HM1
 196   elim (pl_sreds_inv_pos … HM1 …) -HM1
 197   [2: >length_append normalize in ⊢ (??(??%)); // ]
 198   #q #r #M #Hq #HM1 #HM
 199   lapply (rewrite_r ?? is_whd … Hq) -Hq /4 width=1/ -p -s * #Hq #Hr
 200   @(ex3_2_intro … HM1) -M1 // -q /2 width=7/
 201 ]
 202 qed-.
 203
 204 theorem pl_sreds_in_whd_swap: ∀s,M1,N1. M1 ↦*[s] N1 →
 205                               ∀p,N2. in_whd p → N1 ↦[p] N2 →
 206                               ∃∃q,r,M2. in_whd q & M1 ↦[q] M2 & M2 ↦*[r] N2 &
 207                                         is_standard (q::r).
 208 #s #M1 #N1 #HMN1 #p #N2 #Hp #HN12
 209 lapply (pl_sreds_dst … HMN1) -s #HMN1
 210 elim (dst_in_whd_swap … Hp … HN12 … HMN1) -p -N1 #q #M2 #Hq #HM12 #HMN2
 211 elim (dst_inv_pl_sreds_is_standard … HMN2) -HMN2 /3 width=8/
 212 qed-.