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

   1 Require Export contexts_defs.
   2 Require Export lift_defs.
   3
   4 (*#* #caption "current axioms for dropping",
   5    "base case", "untouched tail item",
   6    "dropped tail item", "updated tail item"
   7 *)
   8 (*#* #cap #alpha c in C1, e in C2, u in V, k in z, n in k, d in i, r in q *)
   9
  10       Inductive drop: nat -> nat -> C -> C -> Prop :=
  11          | drop_sort: (h,d,n:?) (drop h d (CSort n) (CSort n))
  12          | drop_comp: (c,e:?) (drop (0) (0) c e) ->
  13                       (k:?; u:?) (drop (0) (0) (CTail c k u) (CTail e k u))
  14          | drop_drop: (k:?; h:?; c,e:?) (drop (r k h) (0) c e) ->
  15                       (u:?) (drop (S h) (0) (CTail c k u) e)
  16          | drop_skip: (k:?; h,d:?; c,e:?) (drop h (r k d) c e) -> (u:?)
  17                       (drop h (S d) (CTail c k (lift h (r k d) u)) (CTail e k u)).
  18
  19 (*#* #stop file *)
  20
  21       Hint drop : ltlc := Constructors drop.
  22
  23       Hint discr : ltlc := Extern 4 (drop ? ? ? ?) Simpl.
  24
  25    Section drop_gen_base. (**************************************************)
  26
  27       Theorem drop_gen_sort: (n,h,d:?; x:?)
  28                              (drop h d (CSort n) x) -> x = (CSort n).
  29       Intros until 1; InsertEq H '(CSort n); XElim H; Intros;
  30       Try Inversion H1; XAuto.
  31       Qed.
  32
  33       Theorem drop_gen_refl: (x,e:?) (drop (0) (0) x e) -> x = e.
  34       Intros until 1; Repeat InsertEq H '(0); XElim H; Intros.
  35 (* case 1: drop_sort *)
  36       XAuto.
  37 (* case 2: drop_comp *)
  38       Rewrite H0; XAuto.
  39 (* case 3: drop_drop *)
  40       Inversion H2.
  41 (* case 4: drop_skip *)
  42       Inversion H1.
  43       Qed.
  44
  45       Theorem drop_gen_drop: (k:?; c,x:?; u:?; h:?)
  46                              (drop (S h) (0) (CTail c k u) x) ->
  47                              (drop (r k h) (0) c x).
  48       Intros until 1;
  49       InsertEq H '(CTail c k u); InsertEq H '(0); InsertEq H '(S h);
  50       XElim H; Intros.
  51 (* case 1: drop_sort *)
  52       Inversion H1.
  53 (* case 2: drop_comp *)
  54       Inversion H1.
  55 (* case 3: drop_drop *)
  56       Inversion H1; Inversion H3.
  57       Rewrite <- H5; Rewrite <- H6; Rewrite <- H7; XAuto.
  58 (* case 4: drop_skip *)
  59       Inversion H2.
  60       Qed.
  61
  62       Theorem drop_gen_skip_r: (c,x:?; u:?; h,d:?; k:?)
  63                                (drop h (S d) x (CTail c k u)) ->
  64                                (EX e | x = (CTail e k (lift h (r k d) u)) & (drop h (r k d) e c)).
  65       Intros; Inversion_clear H; XEAuto.
  66       Qed.
  67
  68       Theorem drop_gen_skip_l: (c,x:?; u:?; h,d:?; k:?)
  69                                (drop h (S d) (CTail c k u) x) ->
  70                                (EX e v | x = (CTail e k v) &
  71                                          u = (lift h (r k d) v) &
  72                                          (drop h (r k d) c e)
  73                                ).
  74       Intros; Inversion_clear H; XEAuto.
  75       Qed.
  76
  77    End drop_gen_base.
  78
  79       Hints Resolve drop_gen_refl : ltlc.
  80
  81       Tactic Definition DropGenBase :=
  82          Match Context With
  83             | [ H: (drop (0) (0) ?0 ?1) |- ? ] ->
  84                LApply (drop_gen_refl ?0 ?1); [ Clear H; Intros | XAuto ]
  85             | [ H: (drop ?0 ?1 (CSort ?2) ?3) |- ? ] ->
  86                LApply (drop_gen_sort ?2 ?0 ?1 ?3); [ Clear H; Intros | XAuto ]
  87             | [ H: (drop (S ?0) (0) (CTail ?1 ?2 ?3) ?4) |- ? ] ->
  88                LApply (drop_gen_drop ?2 ?1 ?4 ?3 ?0); [ Clear H; Intros | XAuto ]
  89             | [ H: (drop ?1 (S ?2) ?3 (CTail ?4 ?5 ?6)) |- ? ] ->
  90                LApply (drop_gen_skip_r ?4 ?3 ?6 ?1 ?2 ?5); [ Clear H; Intros H | XAuto ];
  91                XElim H; Intros
  92             | [ H: (drop ?1 (S ?2) (CTail ?4 ?5 ?6) ?3) |- ? ] ->
  93                LApply (drop_gen_skip_l ?4 ?3 ?6 ?1 ?2 ?5); [ Clear H; Intros H | XAuto ];
  94                XElim H; Intros.
  95
  96    Section drop_props. (*****************************************************)
  97
  98       Theorem drop_skip_bind: (h,d:?; c,e:?) (drop h d c e) -> (b:?; u:?)
  99                               (drop h (S d) (CTail c (Bind b) (lift h d u)) (CTail e (Bind b) u)).
 100       Intros; Pattern 2 d; Replace d with (r (Bind b) d); XAuto.
 101       Qed.
 102
 103       Theorem drop_refl: (c:?) (drop (0) (0) c c).
 104       XElim c; XAuto.
 105       Qed.
 106
 107       Hints Resolve drop_refl : ltlc.
 108
 109       Theorem drop_S: (b:?; c,e:?; u:?; h:?)
 110                       (drop h (0) c (CTail e (Bind b) u)) ->
 111                       (drop (S h) (0) c e).
 112       XElim c.
 113 (* case 1: CSort *)
 114       Intros; DropGenBase; Inversion H.
 115 (* case 2: CTail *)
 116       XElim h; Intros; DropGenBase.
 117 (* case 2.1: h = 0 *)
 118       Inversion H0; XAuto.
 119 (* case 2.1: h > 0 *)
 120       Apply drop_drop; RRw; XEAuto. (**) (* explicit constructor *)
 121       Qed.
 122
 123    End drop_props.
 124
 125       Hints Resolve drop_skip_bind drop_refl drop_S : ltlc.
 126
 127       Tactic Definition DropS :=
 128          Match Context With
 129             [ _: (drop ?1 (0) ?2 (CTail ?3 (Bind ?4) ?5)) |- ? ] ->
 130                LApply (drop_S ?4 ?2 ?3 ?5 ?1); [ Intros | XAuto ].