matita/matita/contribs/lambda-delta/Basic-2/reduction/tpr.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 "Basic-2/substitution/tps.ma".
  16
  17 (* CONTEXT-FREE PARALLEL REDUCTION ON TERMS *********************************)
  18
  19 (* Basic-1: includes: pr0_delta1 *)
  20 inductive tpr: term → term → Prop ≝
  21 | tpr_atom : ∀I. tpr (𝕒{I}) (𝕒{I})
  22 | tpr_flat : ∀I,V1,V2,T1,T2. tpr V1 V2 → tpr T1 T2 →
  23              tpr (𝕗{I} V1. T1) (𝕗{I} V2. T2)
  24 | tpr_beta : ∀V1,V2,W,T1,T2.
  25              tpr V1 V2 → tpr T1 T2 →
  26              tpr (𝕔{Appl} V1. 𝕔{Abst} W. T1) (𝕔{Abbr} V2. T2)
  27 | tpr_delta: ∀I,V1,V2,T1,T2,T.
  28              tpr V1 V2 → tpr T1 T2 → ⋆.  𝕓{I} V2 ⊢ T2 [0, 1] ≫ T →
  29              tpr (𝕓{I} V1. T1) (𝕓{I} V2. T)
  30 | tpr_theta: ∀V,V1,V2,W1,W2,T1,T2.
  31              tpr V1 V2 → ↑[0,1] V2 ≡ V → tpr W1 W2 → tpr T1 T2 →
  32              tpr (𝕔{Appl} V1. 𝕔{Abbr} W1. T1) (𝕔{Abbr} W2. 𝕔{Appl} V. T2)
  33 | tpr_zeta : ∀V,T,T1,T2. ↑[0,1] T1 ≡ T → tpr T1 T2 →
  34              tpr (𝕔{Abbr} V. T) T2
  35 | tpr_tau  : ∀V,T1,T2. tpr T1 T2 → tpr (𝕔{Cast} V. T1) T2
  36 .
  37
  38 interpretation
  39    "context-free parallel reduction (term)"
  40    'PRed T1 T2 = (tpr T1 T2).
  41
  42 (* Basic properties *********************************************************)
  43
  44 lemma tpr_bind: ∀I,V1,V2,T1,T2. V1 ⇒ V2 → T1 ⇒ T2 →
  45                              𝕓{I} V1. T1 ⇒  𝕓{I} V2. T2.
  46 /2/ qed.
  47
  48 (* Basic-1: was by definition: pr0_refl *)
  49 lemma tpr_refl: ∀T. T ⇒ T.
  50 #T elim T -T //
  51 #I elim I -I /2/
  52 qed.
  53
  54 (* Basic inversion lemmas ***************************************************)
  55
  56 fact tpr_inv_atom1_aux: ∀U1,U2. U1 ⇒ U2 → ∀I. U1 = 𝕒{I} → U2 = 𝕒{I}.
  57 #U1 #U2 * -U1 U2
  58 [ //
  59 | #I #V1 #V2 #T1 #T2 #_ #_ #k #H destruct
  60 | #V1 #V2 #W #T1 #T2 #_ #_ #k #H destruct
  61 | #I #V1 #V2 #T1 #T2 #T #_ #_ #_ #k #H destruct
  62 | #V #V1 #V2 #W1 #W2 #T1 #T2 #_ #_ #_ #_ #k #H destruct
  63 | #V #T #T1 #T2 #_ #_ #k #H destruct
  64 | #V #T1 #T2 #_ #k #H destruct
  65 ]
  66 qed.
  67
  68 (* Basic-1: was: pr0_gen_sort pr0_gen_lref *)
  69 lemma tpr_inv_atom1: ∀I,U2. 𝕒{I} ⇒ U2 → U2 = 𝕒{I}.
  70 /2/ qed.
  71
  72 fact tpr_inv_bind1_aux: ∀U1,U2. U1 ⇒ U2 → ∀I,V1,T1. U1 = 𝕓{I} V1. T1 →
  73                         (∃∃V2,T2,T. V1 ⇒ V2 & T1 ⇒ T2 &
  74                                     ⋆.  𝕓{I} V2 ⊢ T2 [0, 1] ≫ T &
  75                                     U2 = 𝕓{I} V2. T
  76                         ) ∨
  77                         ∃∃T. ↑[0,1] T ≡ T1 & T ⇒ U2 & I = Abbr.
  78 #U1 #U2 * -U1 U2
  79 [ #J #I #V #T #H destruct
  80 | #I1 #V1 #V2 #T1 #T2 #_ #_ #I #V #T #H destruct
  81 | #V1 #V2 #W #T1 #T2 #_ #_ #I #V #T #H destruct
  82 | #I1 #V1 #V2 #T1 #T2 #T #HV12 #HT12 #HT2 #I0 #V0 #T0 #H destruct -I1 V1 T1 /3 width=7/
  83 | #V #V1 #V2 #W1 #W2 #T1 #T2 #_ #_ #_ #_ #I0 #V0 #T0 #H destruct
  84 | #V #T #T1 #T2 #HT1 #HT12 #I0 #V0 #T0 #H destruct -V T /3/
  85 | #V #T1 #T2 #_ #I0 #V0 #T0 #H destruct
  86 ]
  87 qed.
  88
  89 lemma tpr_inv_bind1: ∀V1,T1,U2,I. 𝕓{I} V1. T1 ⇒ U2 →
  90                      (∃∃V2,T2,T. V1 ⇒ V2 & T1 ⇒ T2 &
  91                                  ⋆.  𝕓{I} V2 ⊢ T2 [0, 1] ≫ T &
  92                                  U2 = 𝕓{I} V2. T
  93                      ) ∨
  94                      ∃∃T. ↑[0,1] T ≡ T1 & tpr T U2 & I = Abbr.
  95 /2/ qed.
  96
  97 (* Basic-1: was pr0_gen_abbr *)
  98 lemma tpr_inv_abbr1: ∀V1,T1,U2. 𝕓{Abbr} V1. T1 ⇒ U2 →
  99                      (∃∃V2,T2,T. V1 ⇒ V2 & T1 ⇒ T2 &
 100                                  ⋆.  𝕓{Abbr} V2 ⊢ T2 [0, 1] ≫ T &
 101                                  U2 = 𝕓{Abbr} V2. T
 102                       ) ∨
 103                       ∃∃T. ↑[0,1] T ≡ T1 & tpr T U2.
 104 #V1 #T1 #U2 #H
 105 elim (tpr_inv_bind1 … H) -H * /3 width=7/
 106 qed.
 107
 108 fact tpr_inv_flat1_aux: ∀U1,U2. U1 ⇒ U2 → ∀I,V1,U0. U1 = 𝕗{I} V1. U0 →
 109                         ∨∨ ∃∃V2,T2.            V1 ⇒ V2 & U0 ⇒ T2 &
 110                                                U2 = 𝕗{I} V2. T2
 111                          | ∃∃V2,W,T1,T2.       V1 ⇒ V2 & T1 ⇒ T2 &
 112                                                U0 = 𝕔{Abst} W. T1 &
 113                                                U2 = 𝕔{Abbr} V2. T2 & I = Appl
 114                          | ∃∃V2,V,W1,W2,T1,T2. V1 ⇒ V2 & W1 ⇒ W2 & T1 ⇒ T2 &
 115                                                ↑[0,1] V2 ≡ V &
 116                                                U0 = 𝕔{Abbr} W1. T1 &
 117                                                U2 = 𝕔{Abbr} W2. 𝕔{Appl} V. T2 &
 118                                                I = Appl
 119                          |                     (U0 ⇒ U2 ∧ I = Cast).
 120 #U1 #U2 * -U1 U2
 121 [ #I #J #V #T #H destruct
 122 | #I #V1 #V2 #T1 #T2 #HV12 #HT12 #J #V #T #H destruct -I V1 T1 /3 width=5/
 123 | #V1 #V2 #W #T1 #T2 #HV12 #HT12 #J #V #T #H destruct -J V1 T /3 width=8/
 124 | #I #V1 #V2 #T1 #T2 #T #_ #_ #_ #J #V0 #T0 #H destruct
 125 | #V #V1 #V2 #W1 #W2 #T1 #T2 #HV12 #HV2 #HW12 #HT12 #J #V0 #T0 #H
 126   destruct -J V1 T0 /3 width=12/
 127 | #V #T #T1 #T2 #_ #_ #J #V0 #T0 #H destruct
 128 | #V #T1 #T2 #HT12 #J #V0 #T0 #H destruct -J V T1 /3/
 129 ]
 130 qed.
 131
 132 lemma tpr_inv_flat1: ∀V1,U0,U2,I. 𝕗{I} V1. U0 ⇒ U2 →
 133                      ∨∨ ∃∃V2,T2.            V1 ⇒ V2 & U0 ⇒ T2 &
 134                                             U2 = 𝕗{I} V2. T2
 135                       | ∃∃V2,W,T1,T2.       V1 ⇒ V2 & T1 ⇒ T2 &
 136                                             U0 = 𝕔{Abst} W. T1 &
 137                                             U2 = 𝕔{Abbr} V2. T2 & I = Appl
 138                       | ∃∃V2,V,W1,W2,T1,T2. V1 ⇒ V2 & W1 ⇒ W2 & T1 ⇒ T2 &
 139                                             ↑[0,1] V2 ≡ V &
 140                                             U0 = 𝕔{Abbr} W1. T1 &
 141                                             U2 = 𝕔{Abbr} W2. 𝕔{Appl} V. T2 &
 142                                             I = Appl
 143                       |                     (U0 ⇒ U2 ∧ I = Cast).
 144 /2/ qed.
 145
 146 (* Basic-1: was pr0_gen_appl *)
 147 lemma tpr_inv_appl1: ∀V1,U0,U2. 𝕔{Appl} V1. U0 ⇒ U2 →
 148                      ∨∨ ∃∃V2,T2.            V1 ⇒ V2 & U0 ⇒ T2 &
 149                                             U2 = 𝕔{Appl} V2. T2
 150                       | ∃∃V2,W,T1,T2.       V1 ⇒ V2 & T1 ⇒ T2 &
 151                                             U0 = 𝕔{Abst} W. T1 &
 152                                             U2 = 𝕔{Abbr} V2. T2
 153                       | ∃∃V2,V,W1,W2,T1,T2. V1 ⇒ V2 & W1 ⇒ W2 & T1 ⇒ T2 &
 154                                             ↑[0,1] V2 ≡ V &
 155                                             U0 = 𝕔{Abbr} W1. T1 &
 156                                             U2 = 𝕔{Abbr} W2. 𝕔{Appl} V. T2.
 157 #V1 #U0 #U2 #H
 158 elim (tpr_inv_flat1 … H) -H * /3 width=12/ #_ #H destruct
 159 qed.
 160
 161 (* Basic-1: was: pr0_gen_cast *)
 162 lemma tpr_inv_cast1: ∀V1,T1,U2. 𝕔{Cast} V1. T1 ⇒ U2 →
 163                        (∃∃V2,T2. V1 ⇒ V2 & T1 ⇒ T2 & U2 = 𝕔{Cast} V2. T2)
 164                      ∨ T1 ⇒ U2.
 165 #V1 #T1 #U2 #H
 166 elim (tpr_inv_flat1 … H) -H * /3 width=5/
 167 [ #V2 #W #W1 #W2 #_ #_ #_ #_ #H destruct
 168 | #V2 #W #W1 #W2 #T2 #U1 #_ #_ #_ #_ #_ #_ #H destruct
 169 ]
 170 qed.
 171
 172 fact tpr_inv_lref2_aux: ∀T1,T2. T1 ⇒ T2 → ∀i. T2 = #i →
 173                         ∨∨           T1 = #i
 174                          | ∃∃V,T,T0. ↑[O,1] T0 ≡ T & T0 ⇒ #i &
 175                                      T1 = 𝕔{Abbr} V. T
 176                          | ∃∃V,T.    T ⇒ #i & T1 = 𝕔{Cast} V. T.
 177 #T1 #T2 * -T1 T2
 178 [ #I #i #H destruct /2/
 179 | #I #V1 #V2 #T1 #T2 #_ #_ #i #H destruct
 180 | #V1 #V2 #W #T1 #T2 #_ #_ #i #H destruct
 181 | #I #V1 #V2 #T1 #T2 #T #_ #_ #_ #i #H destruct
 182 | #V #V1 #V2 #W1 #W2 #T1 #T2 #_ #_ #_ #_ #i #H destruct
 183 | #V #T #T1 #T2 #HT1 #HT12 #i #H destruct /3 width=6/
 184 | #V #T1 #T2 #HT12 #i #H destruct /3/
 185 ]
 186 qed.
 187
 188 lemma tpr_inv_lref2: ∀T1,i. T1 ⇒ #i →
 189                      ∨∨           T1 = #i
 190                       | ∃∃V,T,T0. ↑[O,1] T0 ≡ T & T0 ⇒ #i &
 191                                   T1 = 𝕔{Abbr} V. T
 192                       | ∃∃V,T.    T ⇒ #i & T1 = 𝕔{Cast} V. T.
 193 /2/ qed.
 194
 195 (* Basic-1: removed theorems 3:
 196             pr0_subst0_back pr0_subst0_fwd pr0_subst0
 197    Basic-1: removed local theorems: 1: pr0_delta_tau
 198 *)