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

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