3 Require Export contexts_defs.
4 Require Export lift_defs.
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)).
15 Hint drop : ltlc := Constructors drop.
17 Hint discr : ltlc := Extern 4 (drop ? ? ? ?) Simpl.
19 Section drop_gen_base. (**************************************************)
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.
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 *)
31 (* case 2 : drop_tail *)
33 (* case 3 : drop_drop *)
35 (* case 4 : drop_skip *)
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).
43 InsertEq H '(CTail c k u); InsertEq H '(0); InsertEq H '(S h);
45 (* case 1 : drop_sort *)
47 (* case 2 : drop_tail *)
49 (* case 3 : drop_drop *)
50 Inversion H1; Inversion H3.
51 Rewrite <- H5; Rewrite <- H6; Rewrite <- H7; XAuto.
52 (* case 4 : drop_skip *)
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.
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) &
68 Intros; Inversion_clear H; XEAuto.
73 Hints Resolve drop_gen_refl : ltlc.
75 Tactic Definition DropGenBase :=
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 ];
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 ];
90 Section drop_props. (*****************************************************)
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.
97 Theorem drop_refl: (c:?) (drop (0) (0) c c).
101 Hints Resolve drop_refl : ltlc.
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).
108 Intros; DropGenBase; Inversion H.
110 XElim h; Intros; DropGenBase.
111 (* case 2.1: h = 0 *)
113 (* case 2.1: h > 0 *)
114 Apply drop_drop; RRw; XEAuto. (**) (* explicit constructor *)
119 Hints Resolve drop_skip_bind drop_refl drop_S : ltlc.
121 Tactic Definition DropS :=
123 [ _: (drop ?1 (0) ?2 (CTail ?3 (Bind ?4) ?5)) |- ? ] ->
124 LApply (drop_S ?4 ?2 ?3 ?5 ?1); [ Intros | XAuto ].