From ab739c4972971725f59c52275a3257ebf524143f Mon Sep 17 00:00:00 2001 From: Wilmer Ricciotti Date: Tue, 4 May 2010 16:49:59 +0000 Subject: [PATCH] * Fixed a couple of glitches in ndestruct - blob equations were not always handled properly - tactic used to fail due to not optimal behaviour of the refiner * Added (experimental) support for JM equality to ndestruct --- .../components/ng_tactics/nDestructTac.ml | 125 +++++++++++------- 1 file changed, 78 insertions(+), 47 deletions(-) diff --git a/helm/software/components/ng_tactics/nDestructTac.ml b/helm/software/components/ng_tactics/nDestructTac.ml index 3a8e257f9..fd745ccf6 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 _ -> ()) @@ -126,13 +126,17 @@ let nargs it nleft consno = 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 nleft status = +let mk_discriminator it ~use_jmeq nleft xyty status = let _,indname,_,cl = it in let mk_eq tys ts us es n = + if use_jmeq then + mk_appl [mk_id "jmeq"; + CicNotationPt.Implicit `JustOne; List.nth ts n; + CicNotationPt.Implicit `JustOne; List.nth us n] + else (* eqty = Tn u0 e0...un-1 en-1 *) let eqty = mk_appl (List.nth tys n :: iter (fun i acc -> @@ -149,7 +153,8 @@ let mk_discriminator it nleft status = List.nth es i:: acc) (n-1) []) in mk_appl [mk_id "eq"; eqty; mk_appl (mk_id ("R" ^ string_of_int n) :: params); - List.nth us n] + List.nth us n] + in let kname it j = @@ -162,8 +167,13 @@ let mk_discriminator it nleft status = let nargs = nargs it nleft i in let es = List.map (fun x -> mk_id ("e" ^ string_of_int x)) (HExtlib.list_seq 0 nargs) in let tys = List.map - (fun x -> CicNotationPt.Implicit (`Tagged ("T" ^ (string_of_int x)))) - (HExtlib.list_seq 0 nargs) in + (fun x -> iter + (fun i acc -> + CicNotationPt.Binder (`Lambda, (mk_id ("x" ^ string_of_int i), None), + CicNotationPt.Binder (`Lambda, (mk_id ("p" ^ string_of_int i), None), + acc))) (x-1) + (CicNotationPt.Implicit (`Tagged ("T" ^ (string_of_int x))))) + (HExtlib.list_seq 0 nargs) in let tys = tys @ [iter (fun i acc -> CicNotationPt.Binder (`Lambda, (mk_id ("x" ^ string_of_int i), None), @@ -236,8 +246,8 @@ let mk_discriminator it nleft 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)*) None), - CicNotationPt.Binder (`Lambda, (mk_id "y", (*Some (mk_id indname)*) None), outer)) + let principle = CicNotationPt.Binder (`Lambda, (mk_id "x", Some xyty), + CicNotationPt.Binder (`Lambda, (mk_id "y", Some xyty), outer)) in pp (lazy ("discriminator = " ^ (CicNotationPp.pp_term principle))); @@ -260,7 +270,8 @@ let name_of_rel ~context rel = let discriminate_tac ~context cur_eq status = pp (lazy (Printf.sprintf "discriminate: equation %s" (name_of_rel ~context cur_eq))); - let dbranch it leftno consno = + let dbranch it ~use_jmeq leftno consno = + let refl_id = mk_id (if use_jmeq then "refl_jmeq" else "refl") in pp (lazy (Printf.sprintf "dbranch %d %d" leftno consno)); let nlist = HExtlib.list_seq 0 (nargs it leftno consno) in (* (\forall ...\forall P.\forall DH : ( ... = ... -> P). P) *) @@ -270,16 +281,16 @@ let discriminate_tac ~context cur_eq status = NTactics.intro_tac "P"; NTactics.intro_tac "DH"; NTactics.apply_tac ("",0,mk_id "DH"); - NTactics.apply_tac ("",0,mk_id "refl"); + NTactics.apply_tac ("",0,refl_id); (* well, it works even if no goal is selected after applying DH... *) ] in - let dbranches it leftno = + let dbranches it ~use_jmeq leftno = pp (lazy (Printf.sprintf "dbranches %d" leftno)); let _,_,_,cl = it in let nbranches = List.length cl in let branches = iter (fun n acc -> let m = nbranches - n - 1 in - if m = 0 then acc @ (dbranch it leftno m) - else acc @ NTactics.shift_tac :: (dbranch it + if m = 0 then acc @ (dbranch it ~use_jmeq leftno m) + else acc @ NTactics.shift_tac :: (dbranch it ~use_jmeq leftno m)) (nbranches-1) [] in if nbranches > 1 then @@ -291,9 +302,10 @@ let discriminate_tac ~context cur_eq status = 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 - let status, leftno, it = - let it, t1, t2 = match s with - | NCic.Appl [_;it;t1;t2] -> it,t1,t2 + let status, leftno, it, use_jmeq = + let it, t1, t2, use_jmeq = match s with + | NCic.Appl [_;it;t1;t2] -> it,t1,t2,false + | NCic.Appl [_;it;t1;_;t2] -> it,t1,t2,true | _ -> assert false in (* XXX: serve? ho già fatto whd *) let status, it = whd status ctx' (mk_cic_term ctx' it) in @@ -306,7 +318,7 @@ let discriminate_tac ~context cur_eq status = | _ -> pp (lazy ("discriminate: indty =" ^ NCicPp.ppterm ~metasenv:[] ~subst:[] ~context:[] it)) ; assert false in let _,leftno,its,_,_ = its in - status, leftno, List.nth its indtyno + status, leftno, List.nth its indtyno, use_jmeq in let itnargs = @@ -314,16 +326,19 @@ let discriminate_tac ~context cur_eq status = 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 xyty = mk_appl (List.map mk_id (itname::params)) in let print_tac s status = pp s ; status in NTactics.block_tac ( [(fun status -> - 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), + let status, discr = mk_discriminator it ~use_jmeq leftno xyty status in + let cut_term = mk_prods params (CicNotationPt.Binder (`Forall, (mk_id "x", + Some xyty), + CicNotationPt.Binder (`Forall, (mk_id "y", Some xyty), 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"*)])))) in + let status = print_tac (lazy ("cut_term = "^ CicNotationPp.pp_term cut_term)) status in + NTactics.cut_tac ("",0, cut_term) status); NTactics.branch_tac; print_tac (lazy "ci sono"); @@ -335,7 +350,7 @@ let discriminate_tac ~context cur_eq status = 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 @ + @ dbranches it ~use_jmeq leftno @ [NTactics.shift_tac; print_tac (lazy "ci sono 3"); NTactics.intro_tac "#discriminate"; @@ -344,7 +359,7 @@ let discriminate_tac ~context cur_eq status = [mk_id eq_name ])); NTactics.reduce_tac ~reduction:(`Normalize true) ~where:default_pattern; NTactics.clear_tac ["#discriminate"]; - NTactics.merge_tac] + NTactics.merge_tac; print_tac (lazy "the end of discriminate")] ) status ;; @@ -356,16 +371,19 @@ let subst_tac ~context ~dir cur_eq = let status, s = term_of_cic_term status s ctx' in pp (lazy (Printf.sprintf "subst: equation %s" eq_name)); let l, r = match s with - | NCic.Appl [_;_;t1;t2] -> t1,t2 + | NCic.Appl [_;_;t1;t2] | NCic.Appl [_;_;t1;_;t2] -> t1,t2 | _ -> assert false in let var = match dir with | `LeftToRight -> l | `RightToLeft -> r in - let var = match var with + (* let var = match var with | NCic.Rel i -> i - | _ -> assert false in + | _ -> assert false in *) let names_to_gen, _ = - cascade_select_in_ctx ~subst:(get_subst status) context (var+cur_eq) in + match var with + | NCic.Rel var -> + cascade_select_in_ctx ~subst:(get_subst status) context (var+cur_eq) + | _ -> cascade_select_in_ctx ~subst:(get_subst status) context cur_eq in let names_to_gen = List.filter (fun n -> n <> eq_name) names_to_gen in let gen_tac x = NTactics.generalize_tac @@ -386,6 +404,12 @@ let clearid_tac ~context cur_eq = 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 + let streicher_id = + match s with + | NCic.Appl [_;_;_;_] -> mk_id "streicherK" + | NCic.Appl [_;_;_;_;_] -> mk_id "streicherKjmeq" + | _ -> assert false + 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 @@ -395,7 +419,7 @@ let clearid_tac ~context cur_eq = ~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"; + NTactics.apply_tac ("",0, mk_appl [streicher_id; CicNotationPt.Implicit `JustOne; CicNotationPt.Implicit `JustOne; CicNotationPt.Implicit `JustOne; @@ -430,12 +454,12 @@ let select_eq ctx acc status goal = 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 -> - `Subst `LeftToRight + when NCicTypeChecker.does_not_occur ~subst ctx' (j-1) j r + && l = NCic.Rel j -> `Subst `LeftToRight | _, NCic.Rel j - when NCicTypeChecker.does_not_occur ~subst ctx' (j-1) j l -> - `Subst `RightToLeft - | (NCic.Rel _, _ | _, NCic.Rel _ ) -> `Cycle + when NCicTypeChecker.does_not_occur ~subst ctx' (j-1) j l + && r = NCic.Rel j -> `Subst `RightToLeft + | (NCic.Rel _, _ | _, NCic.Rel _ ) -> `Cycle (* could be a blob too... *) | _ -> `Blob) in let rec aux i = try @@ -447,19 +471,25 @@ let select_eq ctx acc status goal = let status, ty = NTacStatus.whd status ctx_ty (mk_cic_term ctx_ty ty) in let status, ty = term_of_cic_term status ty ctx_ty in pp (lazy (Printf.sprintf "select_eq tries %s" (NCicPp.ppterm ~context:ctx_ty ~subst:[] ~metasenv:[] ty))); - match ty with - | NCic.Appl [NCic.Const (NReference.Ref (u,_)) ;_;l;r] when NUri.name_of_uri u = "eq" -> - (let status, kind = classify ~subst:(get_subst status) ctx_ty l r in - match kind with - | `Identity -> - let status, goalty = term_of_cic_term status (get_goalty status goal) ctx in - 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 - status, Some (List.length ctx - i), kind - else aux (i+1)) - | _ -> aux (i+1)) + let status, kind = match ty with + | NCic.Appl [NCic.Const (NReference.Ref (u,_)) ;_;l;r] + when NUri.name_of_uri u = "eq" -> + classify ~subst:(get_subst status) ctx_ty l r + | NCic.Appl [NCic.Const (NReference.Ref (u,_)) ;lty;l;rty;r] + when NUri.name_of_uri u = "jmeq" && + NCicReduction.are_convertible ~metasenv:[] + ~subst:(get_subst status) ctx_ty lty rty + -> classify ~subst:(get_subst status) ctx_ty l r + | _ -> status, `NonEq + in match kind with + | `Identity -> + let status, goalty = term_of_cic_term status (get_goalty status goal) ctx in + status, Some (List.length ctx - i), kind + | `Cycle | `Blob | `NonEq -> aux (i+1) (* XXX: skip cyclic/blob equations for now *) + | _ -> + if (List.for_all (fun x -> x <> n) acc) then + status, Some (List.length ctx - i), kind + else aux (i+1)) with Failure _ | Invalid_argument _ -> status, None, `Blob in aux 0 ;; @@ -505,6 +535,7 @@ let rec destruct_tac0 nprods acc status goal = | Some cur_eq, `Blob -> pp (lazy (Printf.sprintf "destruct: blob - nprods is %d, selection is %d, context is %s" nprods cur_eq (NCicPp.ppcontext ~metasenv:[] ~subst ctx))); assert false + | _ -> assert false ;; let destruct_tac s = NTactics.distribute_tac (destruct_tac0 0 []) s;; -- 2.39.2