matita/matita/contribs/lambda/labelled_sequential_reduction.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 "redex_pointer.ma".
  16 include "multiplicity.ma".
  17
  18 (* LABELLED SEQUENTIAL REDUCTION (SINGLE STEP) ******************************)
  19
  20 (* Note: the application "(A B)" is represented by "@B.A" following:
  21          F. Kamareddine and R.P. Nederpelt: "A useful λ-notation".
  22          Theoretical Computer Science 155(1), Elsevier (1996), pp. 85-109.
  23 *)
  24 inductive lsred: rptr → relation term ≝
  25 | lsred_beta   : ∀B,A. lsred (◊) (@B.𝛌.A) ([⬐B]A)
  26 | lsred_abst   : ∀p,A,C. lsred p A C → lsred p (𝛌.A) (𝛌.C)
  27 | lsred_appl_sn: ∀p,B,D,A. lsred p B D → lsred (true::p) (@B.A) (@D.A)
  28 | lsred_appl_dx: ∀p,B,A,C. lsred p A C → lsred (false::p) (@B.A) (@B.C)
  29 .
  30
  31 interpretation "labelled sequential reduction"
  32    'SeqRed M p N = (lsred p M N).
  33
  34 (* Note: we do not use → since it is reserved by CIC *)
  35 notation "hvbox( M break ⇀ [ term 46 p ] break term 46 N )"
  36    non associative with precedence 45
  37    for @{ 'SeqRed $M $p $N }.
  38
  39 lemma lsred_inv_vref: ∀p,M,N. M ⇀[p] N → ∀i. #i = M → ⊥.
  40 #p #M #N * -p -M -N
  41 [ #B #A #i #H destruct
  42 | #p #A #C #_ #i #H destruct
  43 | #p #B #D #A #_ #i #H destruct
  44 | #p #B #A #C #_ #i #H destruct
  45 ]
  46 qed-.
  47
  48 lemma lsred_inv_beta: ∀p,M,N. M ⇀[p] N → ∀D,C. @D.C = M → ◊ = p →
  49                       ∃∃A. 𝛌.A = C & [⬐D] A = N.
  50 #p #M #N * -p -M -N
  51 [ #B #A #D0 #C0 #H #_ destruct /2 width=3/
  52 | #p #A #C #_ #D0 #C0 #H destruct
  53 | #p #B #D #A #_ #D0 #C0 #_ #H destruct
  54 | #p #B #A #C #_ #D0 #C0 #_ #H destruct
  55 ]
  56 qed-.
  57
  58 lemma lsred_inv_abst: ∀p,M,N. M ⇀[p] N → ∀A. 𝛌.A = M →
  59                       ∃∃C. A ⇀[p] C & 𝛌.C = N.
  60 #p #M #N * -p -M -N
  61 [ #B #A #A0 #H destruct
  62 | #p #A #C #HAC #A0 #H destruct /2 width=3/
  63 | #p #B #D #A #_ #A0 #H destruct
  64 | #p #B #A #C #_ #A0 #H destruct
  65 ]
  66 qed-.
  67
  68 lemma lsred_inv_appl_sn: ∀p,M,N. M ⇀[p] N → ∀B,A,q. @B.A = M → true::q = p →
  69                          ∃∃D. B ⇀[q] D & @D.A = N.
  70 #p #M #N * -p -M -N
  71 [ #B #A #B0 #A0 #p0 #_ #H destruct
  72 | #p #A #C #_ #B0 #D0 #p0 #H destruct
  73 | #p #B #D #A #HBD #B0 #A0 #p0 #H1 #H2 destruct /2 width=3/
  74 | #p #B #A #C #_ #B0 #A0 #p0 #_ #H destruct
  75 ]
  76 qed-.
  77
  78 lemma lsred_inv_appl_dx: ∀p,M,N. M ⇀[p] N → ∀B,A,q. @B.A = M → false::q = p →
  79                          ∃∃C. A ⇀[q] C & @B.C = N.
  80 #p #M #N * -p -M -N
  81 [ #B #A #B0 #A0 #p0 #_ #H destruct
  82 | #p #A #C #_ #B0 #D0 #p0 #H destruct
  83 | #p #B #D #A #_ #B0 #A0 #p0 #_ #H destruct
  84 | #p #B #A #C #HAC #B0 #A0 #p0 #H1 #H2 destruct /2 width=3/
  85 ]
  86 qed-.
  87
  88 lemma lsred_fwd_mult: ∀p,M,N. M ⇀[p] N → #{N} < #{M} * #{M}.
  89 #p #M #N #H elim H -p -M -N
  90 [ #B #A @(le_to_lt_to_lt … (#{A}*#{B})) //
  91   normalize /3 width=1 by lt_minus_to_plus_r, lt_times/ (**) (* auto: too slow without trace *)
  92 | //
  93 | #p #B #D #A #_ #IHBD
  94   @(lt_to_le_to_lt … (#{B}*#{B}+#{A})) [ /2 width=1/ ] -D -p
  95 | #p #B #A #C #_ #IHAC
  96   @(lt_to_le_to_lt … (#{B}+#{A}*#{A})) [ /2 width=1/ ] -C -p
  97 ]
  98 @(transitive_le … (#{B}*#{B}+#{A}*#{A})) [ /2 width=1/ ]
  99 >distributive_times_plus normalize /2 width=1/
 100 qed-.
 101
 102 lemma lsred_lift: ∀p. liftable (lsred p).
 103 #p #h #M1 #M2 #H elim H -p -M1 -M2 normalize /2 width=1/
 104 #B #A #d <dsubst_lift_le //
 105 qed.
 106
 107 lemma lsred_inv_lift: ∀p. deliftable (lsred p).
 108 #p #h #N1 #N2 #H elim H -p -N1 -N2
 109 [ #D #C #d #M1 #H
 110   elim (lift_inv_appl … H) -H #B #M #H0 #HM #H destruct
 111   elim (lift_inv_abst … HM) -HM #A #H0 #H destruct /3 width=3/
 112 | #p #C1 #C2 #_ #IHC12 #d #M1 #H
 113   elim (lift_inv_abst … H) -H #A1 #H0 #H destruct
 114   elim (IHC12 ???) -IHC12 [4: // |2,3: skip ] #A2 #HA12 #H destruct (**) (* simplify line *)
 115   @(ex2_1_intro … (𝛌.A2)) // /2 width=1/
 116 | #p #D1 #D2 #C1 #_ #IHD12 #d #M1 #H
 117   elim (lift_inv_appl … H) -H #B1 #A #H1 #H2 #H destruct
 118   elim (IHD12 ???) -IHD12 [4: // |2,3: skip ] #B2 #HB12 #H destruct (**) (* simplify line *)
 119   @(ex2_1_intro … (@B2.A)) // /2 width=1/
 120 | #p #D1 #C1 #C2 #_ #IHC12 #d #M1 #H
 121   elim (lift_inv_appl … H) -H #B #A1 #H1 #H2 #H destruct
 122   elim (IHC12 ???) -IHC12 [4: // |2,3: skip ] #A2 #HA12 #H destruct (**) (* simplify line *)
 123   @(ex2_1_intro … (@B.A2)) // /2 width=1/
 124 ]
 125 qed-.
 126
 127 lemma lsred_dsubst: ∀p. dsubstable_dx (lsred p).
 128 #p #D1 #M1 #M2 #H elim H -p -M1 -M2 normalize /2 width=1/
 129 #D2 #A #d >dsubst_dsubst_ge //
 130 qed.
 131
 132 theorem lsred_mono: ∀p. singlevalued … (lsred p).
 133 #p #M #N1 #H elim H -p -M -N1
 134 [ #B #A #N2 #H elim (lsred_inv_beta … H ????) -H [4,5: // |2,3: skip ] #A0 #H1 #H2 destruct // (**) (* simplify line *)
 135 | #p #A #C #_ #IHAC #N2 #H elim (lsred_inv_abst … H ??) -H [3: // |2: skip ] #C0 #HAC #H destruct /3 width=1/ (**) (* simplify line *)
 136 | #p #B #D #A #_ #IHBD #N2 #H elim (lsred_inv_appl_sn … H ?????) -H [5,6: // |2,3,4: skip ] #D0 #HBD #H destruct /3 width=1/ (**) (* simplify line *)
 137 | #p #B #A #C #_ #IHAC #N2 #H elim (lsred_inv_appl_dx … H ?????) -H [5,6: // |2,3,4: skip ] #C0 #HAC #H destruct /3 width=1/ (**) (* simplify line *)
 138 ]
 139 qed-.