X-Git-Url: http://matita.cs.unibo.it/gitweb/?a=blobdiff_plain;f=helm%2Fsoftware%2Fcomponents%2Fng_tactics%2FnTactics.ml;h=a384d54d56259f89952a7a14f8d013022cee568a;hb=d268de514258947484a22a106c220b102c611cc3;hp=492e5505514bd9ee6561e402e061a7b101a681fa;hpb=b225178112c2c5ef1a717ac7e647d854d94b2e52;p=helm.git diff --git a/helm/software/components/ng_tactics/nTactics.ml b/helm/software/components/ng_tactics/nTactics.ml index 492e55055..a384d54d5 100644 --- a/helm/software/components/ng_tactics/nTactics.ml +++ b/helm/software/components/ng_tactics/nTactics.ml @@ -13,37 +13,23 @@ open Printf -let debug = true +let debug = false let debug_print s = if debug then prerr_endline (Lazy.force s) else () -exception Error of string lazy_t -let fail msg = raise (Error msg) - -type lowtac_status = { - pstatus : NCic.obj; - lstatus : LexiconEngine.status -} - -type lowtactic = lowtac_status * int -> lowtac_status * int list * int list - -type tac_status = { - gstatus : Continuationals.Stack.t; - istatus : lowtac_status; -} - -type tactic = tac_status -> tac_status - -type tactic_term = CicNotationPt.term Disambiguate.disambiguator_input +open Continuationals.Stack +open NTacStatus +module Ast = CicNotationPt -let pp_tac_status status = - prerr_endline (NCicPp.ppobj status.istatus.pstatus) +let id_tac status = status ;; +let print_tac print_status message status = + if print_status then pp_status status; + prerr_endline message; + status ;; -open Continuationals.Stack - let dot_tac status = - let new_gstatus = - match status.gstatus with + let gstatus = + match status#stack with | [] -> assert false | ([], _, [], _) :: _ as stack -> (* backward compatibility: do-nothing-dot *) @@ -57,12 +43,12 @@ let dot_tac status = (([ loc ], t, k, tag) :: s) | _ -> fail (lazy "can't use \".\" here") in - { status with gstatus = new_gstatus } + status#set_stack gstatus ;; let branch_tac status = - let new_gstatus = - match status.gstatus with + let gstatus = + match status#stack with | [] -> assert false | (g, t, k, tag) :: s -> match init_pos g with (* TODO *) @@ -70,12 +56,12 @@ let branch_tac status = | loc :: loc_tl -> ([ loc ], [], [], `BranchTag) :: (loc_tl, t, k, tag) :: s in - { status with gstatus = new_gstatus } + status#set_stack gstatus ;; let shift_tac status = - let new_gstatus = - match status.gstatus with + let gstatus = + match status#stack with | (g, t, k, `BranchTag) :: (g', t', k', tag) :: s -> (match g' with | [] -> fail (lazy "no more goals to shift") @@ -84,12 +70,12 @@ let shift_tac status = :: (loc_tl, t', k', tag) :: s)) | _ -> fail (lazy "can't shift goals here") in - { status with gstatus = new_gstatus } + status#set_stack gstatus ;; let pos_tac i_s status = - let new_gstatus = - match status.gstatus with + let gstatus = + match status#stack with | [] -> assert false | ([ loc ], t, [],`BranchTag) :: (g', t', k', tag) :: s when is_fresh loc -> @@ -98,35 +84,35 @@ let pos_tac i_s status = :: (([ loc ] @+ g') @- l_js, t', k', tag) :: s) | _ -> fail (lazy "can't use relative positioning here") in - { status with gstatus = new_gstatus } + status#set_stack gstatus ;; let wildcard_tac status = - let new_gstatus = - match status.gstatus with + let gstatus = + match status#stack with | [] -> assert false | ([ loc ] , t, [], `BranchTag) :: (g', t', k', tag) :: s when is_fresh loc -> (([loc] @+ g', t, [], `BranchTag) :: ([], t', k', tag) :: s) | _ -> fail (lazy "can't use wildcard here") in - { status with gstatus = new_gstatus } + status#set_stack gstatus ;; let merge_tac status = - let new_gstatus = - match status.gstatus with + let gstatus = + match status#stack with | [] -> assert false | (g, t, k,`BranchTag) :: (g', t', k', tag) :: s -> ((t @+ filter_open g @+ g' @+ k, t', k', tag) :: s) | _ -> fail (lazy "can't merge goals here") in - { status with gstatus = new_gstatus } + status#set_stack gstatus ;; let focus_tac gs status = - let new_gstatus = - match status.gstatus with + let gstatus = + match status#stack with | [] -> assert false | s -> assert(gs <> []); let stack_locs = @@ -140,22 +126,22 @@ let focus_tac gs status = gs; (zero_pos gs, [], [], `FocusTag) :: deep_close gs s in - { status with gstatus = new_gstatus } + status#set_stack gstatus ;; let unfocus_tac status = - let new_gstatus = - match status.gstatus with + let gstatus = + match status#stack with | [] -> assert false | ([], [], [], `FocusTag) :: s -> s | _ -> fail (lazy "can't unfocus, some goals are still open") in - { status with gstatus = new_gstatus } + status#set_stack gstatus ;; let skip_tac status = - let new_gstatus = - match status.gstatus with + let gstatus = + match status#stack with | [] -> assert false | (gl, t, k, tag) :: s -> let gl = List.map switch_of_loc gl in @@ -164,17 +150,54 @@ let skip_tac status = else ([],t,k,tag) :: s in - { status with gstatus = new_gstatus } + status#set_stack gstatus +;; + +let block_tac l status = + List.fold_left (fun status tac -> tac status) status l +;; + +let compare_statuses ~past ~present = + let _,_,past,_,_ = past#obj in + let _,_,present,_,_ = present#obj in + List.map fst (List.filter (fun (i,_) -> not(List.mem_assoc i past)) present), + List.map fst (List.filter (fun (i,_) -> not (List.mem_assoc i present)) past) +;; + + + +(* Exec and distribute_tac form a retraction pair: + 1) exec (distribute_tac low_tac) (s,i) = low_tac (s,i) + 2) tac [s]::G = G1::...::Gn::G' && G' is G with some goals closed => + distribute_tac (exec tac) [s]::G = (G1@...Gn)::G' + 3) tac G = distribute_tac (exec tac) G if + tac = distribute_tac lowtac + 4) atomic_tac t === distribute_tac (exec t) + + Note that executing an high tactic on a set of goals may be stronger + than executing the same tactic on those goals, but once at a time + (e.g. the tactic could perform a global analysis of the set of goals) +*) + +let exec tac (low_status : #lowtac_status) g = + let stack = [ [0,Open g], [], [], `NoTag ] in + let status = + (new NTacStatus.status low_status#obj stack)#set_estatus low_status + in + let status = tac status in + (low_status#set_estatus status)#set_obj status#obj ;; -let fold_tactic tac status = - match status.gstatus with +let distribute_tac tac (status : #tac_status) = + match status#stack with | [] -> assert false | (g, t, k, tag) :: s -> debug_print (lazy ("context length " ^string_of_int (List.length g))); let rec aux s go gc = function - | [] -> s, go, gc + | [] -> + debug_print (lazy "no selected goals"); + s, go, gc | loc :: loc_tl -> debug_print (lazy "inner eval tactical"); let s, go, gc = @@ -184,12 +207,16 @@ let fold_tactic tac status = match switch_of_loc loc with | Closed _ -> fail (lazy "cannot apply to a Closed goal") | Open n -> - let s, go', gc' = tac (s,n) in - s, (go @- gc') @+ go', gc @+ gc' + let sn = tac s n in + let go', gc' = compare_statuses ~past:s ~present:sn in + sn, ((go @+ [n]) @- gc') @+ go', gc @+ gc' in aux s go gc loc_tl in - let s0, go0, gc0 = status.istatus, [], [] in + let s0 = + (new NTacStatus.status status#obj ())#set_estatus + (status :> NEstatus.status) in + let s0, go0, gc0 = s0, [], [] in let sn, gon, gcn = aux s0 go0 gc0 g in debug_print (lazy ("opened: " ^ String.concat " " (List.map string_of_int gon))); @@ -198,22 +225,391 @@ let fold_tactic tac status = let stack = (zero_pos gon, t @~- gcn, k @~- gcn, tag) :: deep_close gcn s in - { gstatus = stack; istatus = sn } + ((status#set_stack stack)#set_obj(sn:>lowtac_status)#obj)#set_estatus sn +;; + +let atomic_tac htac = distribute_tac (exec htac) ;; + +let try_tac tac status = + try + tac status + with NTacStatus.Error _ -> + status +;; + +let first_tac tacl status = + let res = + HExtlib.list_findopt + (fun tac _ -> try Some (tac status) with NTacStatus.Error _ -> None) tacl + in + match res with + | None -> fail (lazy "No tactics left") + | Some x -> x +;; + +let exact_tac t : 's tactic = distribute_tac (fun status goal -> + let goalty = get_goalty status goal in + let status, t = disambiguate status t (Some goalty) (ctx_of goalty) in + instantiate status goal t) +;; + +let assumption_tac status = distribute_tac (fun status goal -> + let gty = get_goalty status goal in + let context = ctx_of gty in + let htac = + first_tac + (List.map (fun (name,_) -> exact_tac ("",0,(Ast.Ident (name,None)))) + context) + in + exec htac status goal) status +;; + +let find_in_context name context = + let rec aux acc = function + | [] -> raise Not_found + | (hd,_) :: tl when hd = name -> acc + | _ :: tl -> aux (acc + 1) tl + in + aux 1 context +;; + +let clear_tac names = + if names = [] then id_tac + else + distribute_tac (fun status goal -> + let goalty = get_goalty status goal in + let js = + List.map + (fun name -> + try find_in_context name (ctx_of goalty) + with Not_found -> + fail (lazy ("hypothesis '" ^ name ^ "' not found"))) + names + in + let n,h,metasenv,subst,o = status#obj in + let metasenv,subst,_ = NCicMetaSubst.restrict metasenv subst goal js in + status#set_obj (n,h,metasenv,subst,o)) +;; + +let generalize0_tac args = + if args = [] then id_tac + else exact_tac ("",0,Ast.Appl (Ast.Implicit :: args)) +;; + +let select0_tac ~where:(wanted,hyps,where) ~job = + let found, postprocess = + match job with + | `Substexpand argsno -> mk_in_scope, mk_out_scope argsno + | `Collect l -> (fun s t -> l := t::!l; mk_in_scope s t), mk_out_scope 1 + | `ChangeWith f -> f,(fun s t -> s, t) + in + distribute_tac (fun status goal -> + let goalty = get_goalty status goal in + let path = + match where with None -> NCic.Implicit `Term | Some where -> where + in + let status, newgoalctx = + List.fold_right + (fun (name,d as entry) (status,ctx) -> + try + let path = List.assoc name hyps in + match d with + NCic.Decl ty -> + let status,ty = + select_term status ~found ~postprocess (mk_cic_term ctx ty) + (wanted,path) in + let status,ty = term_of_cic_term status ty ctx in + status,(name,NCic.Decl ty)::ctx + | NCic.Def (bo,ty) -> + let status,bo = + select_term status ~found ~postprocess (mk_cic_term ctx bo) + (wanted,path) in + let status,bo = term_of_cic_term status bo ctx in + status,(name,NCic.Def (bo,ty))::ctx + with + Not_found -> status, entry::ctx + ) (ctx_of goalty) (status,[]) + in + let status, newgoalty = + select_term status ~found ~postprocess goalty (wanted,path) in + (* WARNING: the next two lines simply change the context of newgoalty + from the old to the new one. Otherwise mk_meta will do that herself, + calling relocate that calls delift. However, newgoalty is now + ?[out_scope] and thus the delift would trigger the special unification + case, which is wrong now :-( *) + let status,newgoalty = term_of_cic_term status newgoalty (ctx_of goalty) in + let newgoalty = mk_cic_term newgoalctx newgoalty in + + let status, instance = + mk_meta status newgoalctx (`Decl newgoalty) + in + instantiate status goal instance) +;; + +let select_tac ~where ~job move_down_hyps = + let (wanted,hyps,where) = GrafiteDisambiguate.disambiguate_npattern where in + let path = + match where with None -> NCic.Implicit `Term | Some where -> where in + if not move_down_hyps then + select0_tac ~where:(wanted,hyps,Some path) ~job + else + let path = + List.fold_left + (fun path (name,path_name) -> NCic.Prod ("_",path_name,path)) + path (List.rev hyps) + in + block_tac [ + generalize0_tac (List.map (fun (name,_) -> Ast.Ident (name,None)) hyps); + select0_tac ~where:(wanted,[],Some path) ~job; + clear_tac (List.map fst hyps) ] +;; + +let generalize_tac ~where = + let l = ref [] in + block_tac [ + select_tac ~where ~job:(`Collect l) true; + print_tac true "ha selezionato?"; + (fun s -> distribute_tac (fun status goal -> + let goalty = get_goalty status goal in + let status,canon,rest = + match !l with + [] -> + (match where with + _,_,(None,_,_) -> fail (lazy "No term to generalize") + | txt,txtlen,(Some what,_,_) -> + let status, what = + disambiguate status (txt,txtlen,what) None (ctx_of goalty) + in + status,what,[] + ) + | he::tl -> status,he,tl in + let status = + List.fold_left + (fun s t -> unify s (ctx_of goalty) canon t) status rest in + let status, canon = term_of_cic_term status canon (ctx_of goalty) in + instantiate status goal + (mk_cic_term (ctx_of goalty) (NCic.Appl [NCic.Implicit `Term ; canon ])) + ) s) ] +;; + +let reduce_tac ~reduction ~where = + let change status t = + match reduction with + | `Normalize perform_delta -> + normalize status + ?delta:(if perform_delta then None else Some max_int) (ctx_of t) t + | `Whd perform_delta -> + whd status + ?delta:(if perform_delta then None else Some max_int) (ctx_of t) t + in + let where = GrafiteDisambiguate.disambiguate_npattern where in + select0_tac ~where ~job:(`ChangeWith change) +;; + +let change_tac ~where ~with_what = + let change status t = + let status, ww = disambiguate status with_what None (ctx_of t) in + let status = unify status (ctx_of t) t ww in + status, ww + in + let where = GrafiteDisambiguate.disambiguate_npattern where in + select0_tac ~where ~job:(`ChangeWith change) +;; + +let letin_tac ~where ~what:(_,_,w) name = + block_tac [ + select_tac ~where ~job:(`Substexpand 1) true; + exact_tac ("",0,Ast.LetIn((Ast.Ident (name,None),None),w,Ast.Implicit)); + ] +;; + +let apply_tac = exact_tac;; + +type indtyinfo = { + rightno: int; + leftno: int; + consno: int; + lefts: NCic.term list; + rights: NCic.term list; + reference: NReference.reference; + } +;; + +let analyze_indty_tac ~what indtyref = distribute_tac (fun status goal -> + let goalty = get_goalty status goal in + let status, what = disambiguate status what None (ctx_of goalty) in + let status, ty_what = typeof status (ctx_of what) what in + let status, (r,consno,lefts,rights) = analyse_indty status ty_what in + let leftno = List.length rights in + let rightno = List.length rights in + indtyref := Some { + rightno = rightno; leftno = leftno; consno = consno; + lefts = lefts; rights = rights; reference = r; + }; + exec id_tac status goal) +;; + +let elim_tac ~what ~where = + let indtyinfo = ref None in + let sort = ref None in + let compute_goal_sort_tac = distribute_tac (fun status goal -> + let goalty = get_goalty status goal in + let status, goalsort = typeof status (ctx_of goalty) goalty in + sort := Some goalsort; + exec id_tac status goal) + in + atomic_tac (block_tac [ + analyze_indty_tac ~what indtyinfo; + (fun s -> select_tac + ~where ~job:(`Substexpand ((HExtlib.unopt !indtyinfo).rightno+1)) true s); + compute_goal_sort_tac; + (fun status -> + let sort = HExtlib.unopt !sort in + let ity = HExtlib.unopt !indtyinfo in + let NReference.Ref (uri, _) = ity.reference in + let status, sort = term_of_cic_term status sort (ctx_of sort) in + let name = NUri.name_of_uri uri ^ + match sort with + | NCic.Sort NCic.Prop -> "_ind" + | NCic.Sort _ -> "_rect" + | _ -> assert false + in + let holes = + HExtlib.mk_list Ast.Implicit (ity.leftno+1+ ity.consno + ity.rightno) in + let eliminator = + let _,_,w = what in + Ast.Appl(Ast.Ident(name,None)::holes @ [ w ]) + in + exact_tac ("",0,eliminator) status) ]) +;; + +let rewrite_tac ~dir ~what:(_,_,what) ~where = + let name = + match dir with `LeftToRight -> "eq_elim_r" | `RightToLeft -> "eq_ind" + in + block_tac + [ select_tac ~where ~job:(`Substexpand 1) true; + exact_tac + ("",0, + Ast.Appl(Ast.Ident(name,None)::HExtlib.mk_list Ast.Implicit 5 @ + [what]))] +;; + +let intro_tac name = + block_tac + [ exact_tac + ("",0,(Ast.Binder (`Lambda, + (Ast.Ident (name,None),None),Ast.Implicit))); + if name = "_" then clear_tac [name] else id_tac ] +;; + +let cases ~what status goal = + let gty = get_goalty status goal in + let status, what = disambiguate status what None (ctx_of gty) in + let status, ty = typeof status (ctx_of what) what in + let status, (ref, consno, _, _) = analyse_indty status ty in + let status, what = term_of_cic_term status what (ctx_of gty) in + let t = + NCic.Match (ref,NCic.Implicit `Term, what, + HExtlib.mk_list (NCic.Implicit `Term) consno) + in + let ctx = ctx_of gty in + let status,t,ty = refine status ctx (mk_cic_term ctx t) (Some gty) in + instantiate status goal t ;; +let cases_tac ~what ~where = + let indtyinfo = ref None in + atomic_tac + (block_tac [ + analyze_indty_tac ~what indtyinfo; + (fun s -> select_tac + ~where ~job:(`Substexpand ((HExtlib.unopt !indtyinfo).rightno+1))true s); + distribute_tac (cases ~what) ]) +;; + +let case1_tac name = + let name = if name = "_" then "_clearme" else name in + block_tac [ intro_tac name; + cases_tac + ~where:("",0,(None,[],None)) + ~what:("",0,Ast.Ident (name,None)); + if name = "_clearme" then clear_tac ["_clearme"] else id_tac ] +;; -let apply t (status,goal) = - let _,_,metasenv, subst,_ = status.pstatus in - let _,context,gty = List.assoc goal metasenv in - let metasenv, subst, lexicon_status, t = - GrafiteDisambiguate.disambiguate_nterm (Some gty) status.lstatus context metasenv subst t +let assert0_tac (hyps,concl) = distribute_tac (fun status goal -> + let gty = get_goalty status goal in + let eq status ctx t1 t2 = + let status,t1 = disambiguate status t1 None ctx in + let status,t1 = apply_subst status ctx t1 in + let status,t1 = term_of_cic_term status t1 ctx in + let t2 = mk_cic_term ctx t2 in + let status,t2 = apply_subst status ctx t2 in + let status,t2 = term_of_cic_term status t2 ctx in + prerr_endline ("COMPARING: " ^ NCicPp.ppterm ~subst:[] ~metasenv:[] ~context:ctx t1 ^ " vs " ^ NCicPp.ppterm ~subst:[] ~metasenv:[] ~context:ctx t2); + assert (t1=t2); + status in - prerr_endline ("termine disambiguato: " ^ NCicPp.ppterm ~context ~metasenv ~subst t); - prerr_endline ("menv:" ^ NCicPp.ppmetasenv ~subst metasenv); - prerr_endline ("subst:" ^ NCicPp.ppsubst subst ~metasenv); - prerr_endline "fine napply"; - { status with lstatus = lexicon_status }, [goal], [] + let status,gty' = term_of_cic_term status gty (ctx_of gty) in + let status = eq status (ctx_of gty) concl gty' in + let status,_ = + List.fold_right2 + (fun (id1,e1) ((id2,e2) as item) (status,ctx) -> + assert (id1=id2 || (prerr_endline (id1 ^ " vs " ^ id2); false)); + match e1,e2 with + `Decl t1, NCic.Decl t2 -> + let status = eq status ctx t1 t2 in + status,item::ctx + | `Def (b1,t1), NCic.Def (b2,t2) -> + let status = eq status ctx t1 t2 in + let status = eq status ctx b1 b2 in + status,item::ctx + | _ -> assert false + ) hyps (ctx_of gty) (status,[]) + in + exec id_tac status goal) +;; + +let assert_tac seqs status = + match status#stack with + | [] -> assert false + | (g,_,_,_) :: s -> + assert (List.length g = List.length seqs); + (match seqs with + [] -> id_tac + | [seq] -> assert0_tac seq + | _ -> + block_tac + (branch_tac:: + HExtlib.list_concat ~sep:[shift_tac] + (List.map (fun seq -> [assert0_tac seq]) seqs)@ + [merge_tac]) + ) status ;; -let apply_tac t = fold_tactic (apply t) ;; +let auto ~params:(l,_) status goal = + let gty = get_goalty status goal in + let n,h,metasenv,subst,o = status#obj in + let status,t = term_of_cic_term status gty (ctx_of gty) in + let status, l = + List.fold_left + (fun (status, l) t -> + let status, t = disambiguate status t None (ctx_of gty) in + let status, ty = typeof status (ctx_of t) t in + let status, t = term_of_cic_term status t (ctx_of gty) in + let status, ty = term_of_cic_term status ty (ctx_of ty) in + (status, (t,ty) :: l)) + (status,[]) l + in + match + NCicParamod.nparamod status metasenv subst (ctx_of gty) (NCic.Rel ~-1,t) l + with + | [] -> raise (NTacStatus.Error (lazy "no proof found",None)) + | (pt, metasenv, subst)::_ -> + let status = status#set_obj (n,h,metasenv,subst,o) in + instantiate status goal (NTacStatus.mk_cic_term (ctx_of gty) pt) +;; +let auto_tac ~params status = + distribute_tac (auto ~params) status +;;