(****************************************************************************) (* *) (* The formal system \lambda\delta *) (* *) (* Author: Ferruccio Guidi *) (* *) (* This file is distributed under the terms of the *) (* GNU General Public License Version 2 *) (* *) (****************************************************************************) Require Export contexts_defs. Require Export ctail_defs. Require Export lift_defs. Inductive drop: nat -> nat -> C -> C -> Prop := | drop_refl: (c:?) (drop (0) (0) c c) | drop_drop: (k:?; h:?; c,e:?) (drop (r k h) (0) c e) -> (u:?) (drop (S h) (0) (CHead c k u) e) | drop_skip: (k:?; h,d:?; c,e:?) (drop h (r k d) c e) -> (u:?) (drop h (S d) (CHead c k (lift h (r k d) u)) (CHead e k u)). Hint drop : ld := Constructors drop. Section drop_gen_base. (**************************************************) Lemma drop_gen_sort: (n,h,d:?; x:?) (drop h d (CSort n) x) -> (AND x = (CSort n) & h = (0) & d = (0)). Proof. Intros until 1; InsertEq H '(CSort n); XElim H; Intros; XInv; Subst; XAuto. Qed. Lemma drop_gen_refl: (x,e:?) (drop (0) (0) x e) -> x = e. Proof. Intros until 1; Repeat InsertEq H '(0); XElim H; Intros; XInv; Subst; XInv; XAuto. Qed. Lemma drop_gen_drop: (k:?; c,x:?; u:?; h:?) (drop (S h) (0) (CHead c k u) x) -> (drop (r k h) (0) c x). Proof. Intros until 1; InsertEq H '(CHead c k u); InsertEq H '(0); InsertEq H '(S h); XElim H; Intros; Do 3 (Subst; XInv); Subst; XAuto. Qed. Lemma drop_gen_skip_r: (c,x:?; u:?; h,d:?; k:?) (drop h (S d) x (CHead c k u)) -> (EX e | x = (CHead e k (lift h (r k d) u)) & (drop h (r k d) e c)). Proof. Intros; InsertEq H '(CHead c k u); InsertEq H '(S d); XElim H; Clear h y x y0; Intros; Do 2 (Subst; XInv); Subst; XDEAuto 2. Qed. Lemma drop_gen_skip_l: (c,x:?; u:?; h,d:?; k:?) (drop h (S d) (CHead c k u) x) -> (EX e v | x = (CHead e k v) & u = (lift h (r k d) v) & (drop h (r k d) c e) ). Proof. Intros; InsertEq H '(CHead c k u); InsertEq H '(S d); XElim H; Clear h y y0 x; Intros; Do 2 (Subst; XInv); Subst; XDEAuto 2. Qed. End drop_gen_base. Tactic Definition DropGenBase := ( Match Context With | [ H: (drop (0) (0) ?0 ?1) |- ? ] -> LApply (drop_gen_refl ?0 ?1); [ Clear H; Intros | XAuto ] | [ H: (drop ?0 ?1 (CSort ?2) ?3) |- ? ] -> LApply (drop_gen_sort ?2 ?0 ?1 ?3); [ Clear H; Intros H | XAuto ]; XElim H; Intros | [ H: (drop (S ?0) (0) (CHead ?1 ?2 ?3) ?4) |- ? ] -> LApply (drop_gen_drop ?2 ?1 ?4 ?3 ?0); [ Clear H; Intros | XAuto ] | [ H: (drop ?1 (S ?2) ?3 (CHead ?4 ?5 ?6)) |- ? ] -> LApply (drop_gen_skip_r ?4 ?3 ?6 ?1 ?2 ?5); [ Clear H; Intros H | XAuto ]; XElim H; Intros | [ H: (drop ?1 (S ?2) (CHead ?4 ?5 ?6) ?3) |- ? ] -> LApply (drop_gen_skip_l ?4 ?3 ?6 ?1 ?2 ?5); [ Clear H; Intros H | XAuto ]; XElim H; Intros ). Section drop_props. (*****************************************************) Lemma drop_skip_bind: (h,d:?; c,e:?) (drop h d c e) -> (b:?; u:?) (drop h (S d) (CHead c (Bind b) (lift h d u)) (CHead e (Bind b) u)). Proof. Intros; Pattern 2 d; Replace d with (r (Bind b) d); XAuto. Qed. Lemma drop_skip_flat: (h,d:?; c,e:?) (drop h (S d) c e) -> (f:?; u:?) (drop h (S d) (CHead c (Flat f) (lift h (S d) u)) (CHead e (Flat f) u)). Proof. Intros; Pattern 2 (S d); Replace (S d) with (r (Flat f) d); XAuto. Qed. Lemma drop_S: (b:?; c,e:?; u:?; h:?) (drop h (0) c (CHead e (Bind b) u)) -> (drop (S h) (0) c e). Proof. XElim c. (* case 1: CSort *) Intros; DropGenBase; Subst; XInv; XInv. (* case 2: CHead *) XElim h; Intros; DropGenBase. (* case 2.1: h = 0 *) XInv; Subst; XAuto. (* case 2.2: h > 0 *) Apply drop_drop; RRw; XDEAuto 2. (**) (* explicit constructor *) Qed. Hint discr : ld := Extern 4 (drop ? ? ? ?) Simpl. Lemma drop_ctail: (c1,c2:?; d,h:?) (drop h d c1 c2) -> (k:?; u:?) (drop h d (CTail k u c1) (CTail k u c2)). Proof. XElim c1. (* case 1: CSort *) Intros; DropGenBase; Subst; XAuto. (* case 2: CHead *) Intros c1 IHc; XElim d; [ XElim h | Idtac ]; Intros; DropGenBase; Subst; XAuto. Qed. End drop_props. Hints Resolve drop_skip_bind drop_skip_flat drop_ctail : ld. Tactic Definition DropS := ( Match Context With | [ _: (drop ?1 (0) ?2 (CHead ?3 (Bind ?4) ?5)) |- ? ] -> LApply (drop_S ?4 ?2 ?3 ?5 ?1); [ Intros | XAuto ] ).