From ddc0c4b55055dd7baf9d84aea73041e2facf4f20 Mon Sep 17 00:00:00 2001 From: Wilmer Ricciotti Date: Tue, 2 Feb 2010 18:52:12 +0000 Subject: [PATCH] New version using Streicher's K axiom. Should be faster and also work with indexed inductive types. --- .../components/ng_tactics/nDestructTac.ml | 117 ++++++++++++------ 1 file changed, 80 insertions(+), 37 deletions(-) diff --git a/helm/software/components/ng_tactics/nDestructTac.ml b/helm/software/components/ng_tactics/nDestructTac.ml index 8b2065a43..01ca13ee1 100644 --- a/helm/software/components/ng_tactics/nDestructTac.ml +++ b/helm/software/components/ng_tactics/nDestructTac.ml @@ -28,7 +28,7 @@ open NTacStatus open Continuationals.Stack -let debug = false +let debug = true let pp = if debug then (fun x -> prerr_endline (Lazy.force x)) else (fun _ -> ()) @@ -44,6 +44,12 @@ let mk_id id = CicNotationPt.Ident (id,None) ;; +let rec mk_prods l t = + match l with + [] -> t + | hd::tl -> CicNotationPt.Binder (`Forall, (mk_id hd, None), mk_prods tl t) +;; + let mk_appl = function [] -> assert false @@ -89,9 +95,7 @@ let cascade_select_in_ctx ~subst ctx iname = ([1], rctx) lctx in prerr_endline "C3:"; List.iter (fun n -> prerr_endline (string_of_int n)) indices; - let indices = match rm_last indices with - | [] -> [] - | _::tl -> tl in + let indices = rm_last indices in let res = List.map (fun n -> let s,_ = List.nth ctx (n-1) in s) indices in prerr_endline "C4:"; List.iter (fun n -> prerr_endline n) res; @@ -129,8 +133,7 @@ let default_pattern = "",0,(None,[],Some CicNotationPt.UserInput);; (* returns the discrimination = injection+contradiction principle *) (* FIXME: mi riservo di considerare tipi con parametri sx alla fine *) -let mk_discriminator it status = - let nleft = 0 in +let mk_discriminator it nleft status = let _,indname,_,cl = it in @@ -177,38 +180,39 @@ let mk_discriminator it status = (HExtlib.list_seq 0 (List.length ts))); mk_appl (mk_id (kname it j)::us)])] in - CicNotationPt.Binder (`Lambda, (mk_id "e", + (** CicNotationPt.Binder (`Lambda, (mk_id "e", Some (mk_appl [mk_id "eq"; CicNotationPt.Implicit `JustOne; mk_appl (mk_id (kname it i)::ts); mk_appl (mk_id (kname it j)::us)])), - let ts = ts @ [mk_id "e"] in + let ts = ts @ [mk_id "e"] in let refl2 = mk_appl [mk_id "refl"; CicNotationPt.Implicit `JustOne; mk_appl (mk_id (kname it j)::us)] in - let us = us @ [refl2] in + let us = us @ [refl2] in *) CicNotationPt.Binder (`Forall, (mk_id "P", Some (CicNotationPt.Sort (`NType "1") )), if i = j then CicNotationPt.Binder (`Forall, (mk_id "_", Some (iter (fun i acc -> CicNotationPt.Binder (`Forall, (List.nth es i, Some (mk_eq tys ts us es i)), acc)) (nargs-1) - (CicNotationPt.Binder (`Forall, (mk_id "_", - Some (mk_eq tys ts us es nargs)), - mk_id "P")))), mk_id "P") - else mk_id "P")) + (** (CicNotationPt.Binder (`Forall, (mk_id "_", + Some (mk_eq tys ts us es nargs)),*) + (mk_id "P"))), mk_id "P") + else mk_id "P") in let inner i ts = CicNotationPt.Case (mk_id "y",None, - Some (CicNotationPt.Binder (`Lambda, (mk_id "y",None), + (*Some (CicNotationPt.Binder (`Lambda, (mk_id "y",None), CicNotationPt.Binder (`Forall, (mk_id "_", Some (mk_appl [mk_id "eq";CicNotationPt.Implicit `JustOne;(*CicNotationPt.Implicit `JustOne*) mk_appl (mk_id (kname it i)::ts);mk_id "y"])), - CicNotationPt.Implicit `JustOne ))), + CicNotationPt.Implicit `JustOne )))*) + None, List.map (fun j -> let nargs_kty = nargs it nleft j in @@ -224,9 +228,7 @@ let mk_discriminator it status = in let outer = CicNotationPt.Case (mk_id "x",None, - Some (CicNotationPt.Binder (`Lambda, (mk_id "_",None), - (*CicNotationPt.Sort (`NType "2")*) CicNotationPt.Implicit - `JustOne)) , + None , List.map (fun i -> let nargs_kty = nargs it nleft i in @@ -239,8 +241,8 @@ let mk_discriminator it status = List.combine ts nones), inner i ts) (HExtlib.list_seq 0 (List.length cl))) in - let principle = CicNotationPt.Binder (`Lambda, (mk_id "x", Some (mk_id indname)), - CicNotationPt.Binder (`Lambda, (mk_id "y", Some (mk_id indname)), outer)) + let principle = CicNotationPt.Binder (`Lambda, (mk_id "x", (*Some (mk_id indname)*) None), + CicNotationPt.Binder (`Lambda, (mk_id "y", (*Some (mk_id indname)*) None), outer)) in pp (lazy ("discriminator = " ^ (CicNotationPp.pp_term principle))); @@ -305,37 +307,49 @@ let discriminate_tac ~context cur_eq status = let status, it = whd status ctx' (mk_cic_term ctx' it) in let status, it = term_of_cic_term status it ctx' in let _uri,indtyno,its = match it with - NCic.Const (NReference.Ref (uri, NReference.Ind (_,indtyno,_)) as r) -> + | NCic.Const (NReference.Ref (uri, NReference.Ind (_,indtyno,_)) as r) + | NCic.Appl (NCic.Const + (NReference.Ref (uri, NReference.Ind (_,indtyno,_)) as r)::_) -> uri, indtyno, NCicEnvironment.get_checked_indtys r | _ -> prerr_endline ("discriminate: indty =" ^ NCicPp.ppterm ~metasenv:[] ~subst:[] ~context:[] it) ; assert false in let _,leftno,its,_,_ = its in status, leftno, List.nth its indtyno in - + + let itnargs = + let _,_,arity,_ = it in + List.length (arg_list 0 arity) in + let _,itname,_,_ = it in + let params = List.map (fun x -> "a" ^ string_of_int x) (HExtlib.list_seq 1 (itnargs+1)) in + let print_tac s status = pp s ; status in NTactics.block_tac ( [(fun status -> - let status, discr = mk_discriminator it status in - NTactics.cut_tac ("",0, CicNotationPt.Binder (`Forall, (mk_id "x", None), + let status, discr = mk_discriminator it leftno status in + NTactics.cut_tac ("",0, mk_prods params (CicNotationPt.Binder (`Forall, (mk_id "x", + Some (mk_appl (List.map mk_id (itname::params)))), CicNotationPt.Binder (`Forall, (mk_id "y", None), - CicNotationPt.Binder (`Forall, (mk_id "e", + CicNotationPt.Binder (`Forall, (mk_id "e", Some (mk_appl [mk_id "eq";CicNotationPt.Implicit `JustOne; mk_id "x"; mk_id "y"])), - mk_appl [discr; mk_id "x"; mk_id "y"; - mk_id "e"])))) + mk_appl [discr; mk_id "x"; mk_id "y"(*;mk_id "e"*)]))))) status); NTactics.branch_tac; - NTactics.reduce_tac ~reduction:(`Normalize true) ~where:default_pattern; - NTactics.intro_tac "x"; + print_tac (lazy "ci sono"); + NTactics.reduce_tac ~reduction:(`Normalize true) ~where:default_pattern] + @ List.map (fun x -> NTactics.intro_tac x) params @ + [NTactics.intro_tac "x"; NTactics.intro_tac "y"; NTactics.intro_tac "Deq"; + print_tac (lazy "ci sono 2"); NTactics.rewrite_tac ~dir:`RightToLeft ~what:("",0,mk_id "Deq") ~where:default_pattern; NTactics.cases_tac ~what:("",0,mk_id "x") ~where:default_pattern] @ dbranches it leftno @ [NTactics.shift_tac; + print_tac (lazy "ci sono 3"); NTactics.intro_tac "#discriminate"; - NTactics.apply_tac ("",0,mk_appl [mk_id "#discriminate"; - CicNotationPt.Implicit `JustOne; - CicNotationPt.Implicit `JustOne; mk_id eq_name ]); + NTactics.apply_tac ("",0,mk_appl ([mk_id "#discriminate"]@ + HExtlib.mk_list (CicNotationPt.Implicit `JustOne) (List.length params + 2) @ + [mk_id eq_name ])); NTactics.reduce_tac ~reduction:(`Normalize true) ~where:default_pattern; NTactics.clear_tac ["#discriminate"]; NTactics.merge_tac] @@ -360,6 +374,7 @@ let subst_tac ~context ~dir cur_eq = | _ -> assert false in let names_to_gen, _ = cascade_select_in_ctx ~subst:(get_subst status) context (var+cur_eq) in + let names_to_gen = match names_to_gen with [] -> [] | _::tl -> tl in let gen_tac x = NTactics.generalize_tac ~where:("",0,(Some (mk_id x),[], Some CicNotationPt.UserInput)) in @@ -373,6 +388,35 @@ let subst_tac ~context ~dir cur_eq = (List.map NTactics.intro_tac (List.rev names_to_gen))) status ;; +let clearid_tac ~context cur_eq = + fun status -> + let eq_name,(NCic.Decl s | NCic.Def (s,_)) = List.nth context (cur_eq-1) in + let _,ctx' = HExtlib.split_nth cur_eq context in + let status, s = NTacStatus.whd status ctx' (mk_cic_term ctx' s) in + let status, s = term_of_cic_term status s ctx' in + pp (lazy (Printf.sprintf "clearid: equation %s" eq_name)); + let names_to_gen, _ = + cascade_select_in_ctx ~subst:(get_subst status) context cur_eq in + let names_to_gen = names_to_gen @ [eq_name] in + let gen_tac x = + NTactics.generalize_tac + ~where:("",0,(Some (mk_id x),[], Some CicNotationPt.UserInput)) in + NTactics.block_tac ((List.map gen_tac names_to_gen)@ + [NTactics.clear_tac names_to_gen; + NTactics.apply_tac ("",0, mk_appl [mk_id "streicherK"; + CicNotationPt.Implicit `JustOne; + CicNotationPt.Implicit `JustOne; + CicNotationPt.Implicit `JustOne; + CicNotationPt.Implicit `JustOne]); + NTactics.reduce_tac ~reduction:(`Normalize true) + ~where:default_pattern] @ + (let names_to_intro = + match List.rev names_to_gen with + | [] -> [] + | _::tl -> tl in + List.map NTactics.intro_tac names_to_intro)) status +;; + let get_ctx st goal = ctx_of (get_goalty st goal) ;; @@ -391,7 +435,7 @@ let select_eq ctx acc status goal = let rit = NReference.mk_indty true kref in let _,_,its,_,itno = NCicEnvironment.get_checked_indtys rit in let it = List.nth its itno in - let newprods = (nargs it nleft (ki-1)) + 1 in + let newprods = nargs it nleft (ki-1) in `Discriminate (newprods, false) | NCic.Rel j, _ when NCicTypeChecker.does_not_occur ~subst ctx' (j-1) j r -> @@ -404,6 +448,7 @@ let select_eq ctx acc status goal = let rec aux i = try let index = List.length ctx - i in + pp (lazy ("provo classify di index = " ^string_of_int index)); match (List.nth ctx (index - 1)) with | n, (NCic.Decl ty | NCic.Def (ty,_)) -> (let _,ctx_ty = HExtlib.split_nth index ctx in @@ -416,9 +461,7 @@ let select_eq ctx acc status goal = match kind with | `Identity -> let status, goalty = term_of_cic_term status (get_goalty status goal) ctx in - if NCicTypeChecker.does_not_occur ~subst:(get_subst status) ctx (index - 1) index goalty - then status, Some (List.length ctx - i), kind - else aux (i+1) + status, Some (List.length ctx - i), kind | `Cycle | `Blob -> aux (i+1) (* XXX: skip cyclic/blob equations for now *) | _ -> if (List.for_all (fun x -> x <> n) acc) then @@ -462,7 +505,7 @@ let rec destruct_tac0 nprods acc status goal = | Some cur_eq, `Identity -> pp (lazy (Printf.sprintf "destruct: identity - nprods is %d, selection is %d, context is %s" nprods cur_eq (NCicPp.ppcontext ~metasenv:[] ~subst ctx))); let eq_name,_ = List.nth ctx (cur_eq-1) in - let status' = NTactics.exec (NTactics.clear_tac [eq_name]) status goal in + let status' = NTactics.exec (clearid_tac ~context:ctx cur_eq) status goal in destruct_tac0 nprods (List.filter (fun x -> x <> eq_name) acc) status' (get_newgoal status status' goal) | Some cur_eq, `Cycle -> (* TODO, should never happen *) pp (lazy (Printf.sprintf "destruct: cycle - nprods is %d, selection is %d, context is %s" nprods cur_eq (NCicPp.ppcontext ~metasenv:[] ~subst ctx))); -- 2.39.2