matita/matita/contribs/lambdadelta/basic_2A/reduction/crr.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_2A/notation/relations/predreducible_3.ma".
  16 include "basic_2A/grammar/genv.ma".
  17 include "basic_2A/substitution/drop.ma".
  18
  19 (* REDUCIBLE TERMS FOR CONTEXT-SENSITIVE REDUCTION **************************)
  20
  21 (* reducible binary items *)
  22 definition ri2: predicate item2 ≝
  23                 λI. I = Bind2 true Abbr ∨ I = Flat2 Cast.
  24
  25 (* irreducible binary binders *)
  26 definition ib2: relation2 bool bind2 ≝
  27                 λa,I. I = Abst ∨ Bind2 a I = Bind2 false Abbr.
  28
  29 (* activate genv *)
  30 (* reducible terms *)
  31 inductive crr (G:genv): relation2 lenv term ≝
  32 | crr_delta  : ∀L,K,V,i. ⬇[i] L ≡ K.ⓓV → crr G L (#i)
  33 | crr_appl_sn: ∀L,V,T. crr G L V → crr G L (ⓐV.T)
  34 | crr_appl_dx: ∀L,V,T. crr G L T → crr G L (ⓐV.T)
  35 | crr_ri2    : ∀I,L,V,T. ri2 I → crr G L (②{I}V.T)
  36 | crr_ib2_sn : ∀a,I,L,V,T. ib2 a I → crr G L V → crr G L (ⓑ{a,I}V.T)
  37 | crr_ib2_dx : ∀a,I,L,V,T. ib2 a I → crr G (L.ⓑ{I}V) T → crr G L (ⓑ{a,I}V.T)
  38 | crr_beta   : ∀a,L,V,W,T. crr G L (ⓐV.ⓛ{a}W.T)
  39 | crr_theta  : ∀a,L,V,W,T. crr G L (ⓐV.ⓓ{a}W.T)
  40 .
  41
  42 interpretation
  43    "reducibility for context-sensitive reduction (term)"
  44    'PRedReducible G L T = (crr G L T).
  45
  46 (* Basic inversion lemmas ***************************************************)
  47
  48 fact crr_inv_sort_aux: ∀G,L,T,k. ⦃G, L⦄ ⊢ ➡ 𝐑⦃T⦄ → T = ⋆k → ⊥.
  49 #G #L #T #k0 * -L -T
  50 [ #L #K #V #i #HLK #H destruct
  51 | #L #V #T #_ #H destruct
  52 | #L #V #T #_ #H destruct
  53 | #I #L #V #T #_ #H destruct
  54 | #a #I #L #V #T #_ #_ #H destruct
  55 | #a #I #L #V #T #_ #_ #H destruct
  56 | #a #L #V #W #T #H destruct
  57 | #a #L #V #W #T #H destruct
  58 ]
  59 qed-.
  60
  61 lemma crr_inv_sort: ∀G,L,k. ⦃G, L⦄ ⊢ ➡ 𝐑⦃⋆k⦄ → ⊥.
  62 /2 width=6 by crr_inv_sort_aux/ qed-.
  63
  64 fact crr_inv_lref_aux: ∀G,L,T,i. ⦃G, L⦄ ⊢ ➡ 𝐑⦃T⦄ → T = #i →
  65                        ∃∃K,V. ⬇[i] L ≡ K.ⓓV.
  66 #G #L #T #j * -L -T
  67 [ #L #K #V #i #HLK #H destruct /2 width=3 by ex1_2_intro/
  68 | #L #V #T #_ #H destruct
  69 | #L #V #T #_ #H destruct
  70 | #I #L #V #T #_ #H destruct
  71 | #a #I #L #V #T #_ #_ #H destruct
  72 | #a #I #L #V #T #_ #_ #H destruct
  73 | #a #L #V #W #T #H destruct
  74 | #a #L #V #W #T #H destruct
  75 ]
  76 qed-.
  77
  78 lemma crr_inv_lref: ∀G,L,i. ⦃G, L⦄ ⊢ ➡ 𝐑⦃#i⦄ → ∃∃K,V. ⬇[i] L ≡ K.ⓓV.
  79 /2 width=4 by crr_inv_lref_aux/ qed-.
  80
  81 fact crr_inv_gref_aux: ∀G,L,T,p. ⦃G, L⦄ ⊢ ➡ 𝐑⦃T⦄ → T = §p → ⊥.
  82 #G #L #T #q * -L -T
  83 [ #L #K #V #i #HLK #H destruct
  84 | #L #V #T #_ #H destruct
  85 | #L #V #T #_ #H destruct
  86 | #I #L #V #T #_ #H destruct
  87 | #a #I #L #V #T #_ #_ #H destruct
  88 | #a #I #L #V #T #_ #_ #H destruct
  89 | #a #L #V #W #T #H destruct
  90 | #a #L #V #W #T #H destruct
  91 ]
  92 qed-.
  93
  94 lemma crr_inv_gref: ∀G,L,p. ⦃G, L⦄ ⊢ ➡ 𝐑⦃§p⦄ → ⊥.
  95 /2 width=6 by crr_inv_gref_aux/ qed-.
  96
  97 lemma trr_inv_atom: ∀G,I. ⦃G, ⋆⦄ ⊢ ➡ 𝐑⦃⓪{I}⦄ → ⊥.
  98 #G * #i #H
  99 [ elim (crr_inv_sort … H)
 100 | elim (crr_inv_lref … H) -H #L #V #H
 101   elim (drop_inv_atom1 … H) -H #H destruct
 102 | elim (crr_inv_gref … H)
 103 ]
 104 qed-.
 105
 106 fact crr_inv_ib2_aux: ∀a,I,G,L,W,U,T. ib2 a I → ⦃G, L⦄ ⊢ ➡ 𝐑⦃T⦄ → T = ⓑ{a,I}W.U →
 107                       ⦃G, L⦄ ⊢ ➡ 𝐑⦃W⦄ ∨ ⦃G, L.ⓑ{I}W⦄ ⊢ ➡ 𝐑⦃U⦄.
 108 #G #b #J #L #W0 #U #T #HI * -L -T
 109 [ #L #K #V #i #_ #H destruct
 110 | #L #V #T #_ #H destruct
 111 | #L #V #T #_ #H destruct
 112 | #I #L #V #T #H1 #H2 destruct
 113   elim H1 -H1 #H destruct
 114   elim HI -HI #H destruct
 115 | #a #I #L #V #T #_ #HV #H destruct /2 width=1 by or_introl/
 116 | #a #I #L #V #T #_ #HT #H destruct /2 width=1 by or_intror/
 117 | #a #L #V #W #T #H destruct
 118 | #a #L #V #W #T #H destruct
 119 ]
 120 qed-.
 121
 122 lemma crr_inv_ib2: ∀a,I,G,L,W,T. ib2 a I → ⦃G, L⦄ ⊢ ➡ 𝐑⦃ⓑ{a,I}W.T⦄ →
 123                    ⦃G, L⦄ ⊢ ➡ 𝐑⦃W⦄ ∨ ⦃G, L.ⓑ{I}W⦄ ⊢ ➡ 𝐑⦃T⦄.
 124 /2 width=5 by crr_inv_ib2_aux/ qed-.
 125
 126 fact crr_inv_appl_aux: ∀G,L,W,U,T. ⦃G, L⦄ ⊢ ➡ 𝐑⦃T⦄ → T = ⓐW.U →
 127                        ∨∨ ⦃G, L⦄ ⊢ ➡ 𝐑⦃W⦄ | ⦃G, L⦄ ⊢ ➡ 𝐑⦃U⦄ | (𝐒⦃U⦄ → ⊥).
 128 #G #L #W0 #U #T * -L -T
 129 [ #L #K #V #i #_ #H destruct
 130 | #L #V #T #HV #H destruct /2 width=1 by or3_intro0/
 131 | #L #V #T #HT #H destruct /2 width=1 by or3_intro1/
 132 | #I #L #V #T #H1 #H2 destruct
 133   elim H1 -H1 #H destruct
 134 | #a #I #L #V #T #_ #_ #H destruct
 135 | #a #I #L #V #T #_ #_ #H destruct
 136 | #a #L #V #W #T #H destruct
 137   @or3_intro2 #H elim (simple_inv_bind … H)
 138 | #a #L #V #W #T #H destruct
 139   @or3_intro2 #H elim (simple_inv_bind … H)
 140 ]
 141 qed-.
 142
 143 lemma crr_inv_appl: ∀G,L,V,T. ⦃G, L⦄ ⊢ ➡ 𝐑⦃ⓐV.T⦄ →
 144                               ∨∨ ⦃G, L⦄ ⊢ ➡ 𝐑⦃V⦄ | ⦃G, L⦄ ⊢ ➡ 𝐑⦃T⦄ | (𝐒⦃T⦄ → ⊥).
 145 /2 width=3 by crr_inv_appl_aux/ qed-.