helm/coq-contribs/LAMBDA-TYPES/subst0_defs.v

   1 Require Export lift_defs.
   2
   3 (*#* #caption "axioms for strict substitution in terms",
   4    "substituted local reference",
   5    "substituted tail item: first operand",
   6    "substituted tail item: second operand",
   7    "substituted tail item: both operands"
   8 *)
   9 (*#* #cap #cap t, t1, t2 #alpha v in W, u in V, u1 in V1, u2 in V2, k in z, s in p *)
  10
  11       Inductive subst0 : nat -> T -> T -> T -> Prop :=
  12          | subst0_lref: (v:?; i:?) (subst0 i v (TLRef i) (lift (S i) (0) v))
  13          | subst0_fst : (v,u2,u1:?; i:?) (subst0 i v u1 u2) ->
  14                         (t:?; k:?) (subst0 i v (TTail k u1 t) (TTail k u2 t))
  15          | subst0_snd : (k:?; v,t2,t1:?; i:?) (subst0 (s k i) v t1 t2) -> (u:?)
  16                         (subst0 i v (TTail k u t1) (TTail k u t2))
  17          | subst0_both: (v,u1,u2:?; i:?) (subst0 i v u1 u2) ->
  18                         (k:?; t1,t2:?) (subst0 (s k i) v t1 t2) ->
  19                         (subst0 i v (TTail k u1 t1) (TTail k u2 t2)).
  20
  21 (*#* #stop file *)
  22
  23       Hint subst0 : ltlc := Constructors subst0.
  24
  25    Section subst0_gen_base. (************************************************)
  26
  27       Theorem subst0_gen_sort : (v,x:?; i,n:?) (subst0 i v (TSort n) x) ->
  28                                 (P:Prop) P.
  29       Intros; Inversion H.
  30       Qed.
  31
  32       Theorem subst0_gen_lref : (v,x:?; i,n:?) (subst0 i v (TLRef n) x) ->
  33                                 n = i /\ x = (lift (S n) (0) v).
  34       Intros; Inversion H; XAuto.
  35       Qed.
  36
  37       Theorem subst0_gen_tail : (k:?; v,u1,t1,x:?; i:?)
  38                                 (subst0 i v (TTail k u1 t1) x) -> (OR
  39                                 (EX u2 | x = (TTail k u2 t1) &
  40                                         (subst0 i v u1 u2)) |
  41                                 (EX t2 | x = (TTail k u1 t2) &
  42                                          (subst0 (s k i) v t1 t2)) |
  43                                 (EX u2 t2 | x = (TTail k u2 t2) &
  44                                             (subst0 i v u1 u2) &
  45                                             (subst0 (s k i) v t1 t2))
  46                                 ).
  47
  48       Intros; Inversion H; XEAuto.
  49       Qed.
  50
  51    End subst0_gen_base.
  52
  53       Tactic Definition Subst0GenBase :=
  54          Match Context With
  55             | [ H: (subst0 ?1 ?2 (TSort ?3) ?4) |- ? ] ->
  56                Apply (subst0_gen_sort ?2 ?4 ?1 ?3); Apply H
  57             | [ H: (subst0 ?1 ?2 (TLRef ?3) ?4) |- ? ] ->
  58                LApply (subst0_gen_lref ?2 ?4 ?1 ?3); [ Clear H; Intros H | XAuto ];
  59                XElim H; Intros
  60             | [ H: (subst0 ?1 ?2 (TTail ?3 ?4 ?5) ?6) |- ? ] ->
  61                LApply (subst0_gen_tail ?3 ?2 ?4 ?5 ?6 ?1); [ Clear H; Intros H | XAuto ];
  62                XElim H; Intros H; XElim H; Intros.