1 (* Copyright (C) 2002, HELM Team.
3 * This file is part of HELM, an Hypertextual, Electronic
4 * Library of Mathematics, developed at the Computer Science
5 * Department, University of Bologna, Italy.
7 * HELM is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
12 * HELM is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with HELM; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
22 * For details, see the HELM World-Wide-Web page,
23 * http://cs.unibo.it/helm/.
26 let debug_print = fun _ -> ()
28 (* Da rimuovere, solo per debug*)
29 let print_context ctx =
33 | Cic.Anonymous -> "_"
36 (fun i (output,context) ->
37 let (newoutput,context') =
39 Some (n,Cic.Decl t) ->
40 print_name n ^ ":" ^ CicPp.pp t context ^ "\n", (Some n)::context
41 | Some (n,Cic.Def (t,None)) ->
42 print_name n ^ ":=" ^ CicPp.pp t context ^ "\n", (Some n)::context
44 "_ ?= _\n", None::context
45 | Some (_,Cic.Def (_,Some _)) -> assert false
47 output^newoutput,context'
52 let search_theorems_in_context status =
53 let (proof, goal) = status in
55 let module R = CicReduction in
56 let module S = CicSubstitution in
57 let module PET = ProofEngineTypes in
58 let module PT = PrimitiveTactics in
59 let _,metasenv,_,_ = proof in
60 let _,context,ty = CicUtil.lookup_meta goal metasenv in
61 let rec find n = function
66 Some (PET.apply_tactic
67 (PT.apply_tac ~term:(C.Rel n)) status )
71 Some res -> res::(find (n+1) tl)
72 | None -> find (n+1) tl)
83 let new_search_theorems f proof goal depth gtl sign =
84 let choices = f (proof,goal)
87 (function (proof, goallist) ->
88 (proof,(List.map (function g -> (g,depth)) goallist)@gtl, sign))
92 exception NoOtherChoices;;
93 let rec auto dbd = function
95 | (proof, [], sign)::tl -> (proof, [], sign)::tl
96 | (proof, (goal,0)::_, _)::tl -> auto dbd tl
97 | (proof, (((goal,depth)::gtl) as allg), sign)::tl ->
98 (* first we check if the metavariable has not been already
99 closed as a side effect by some other application *)
100 let facts = (depth = 1) in
101 let name,metasenv,p,statement = proof in
104 let (_, ey ,ty) = CicUtil.lookup_meta goal metasenv in
109 (* the goal is still there *)
111 debug_print ("CURRENT GOAL = " ^ (CicPp.ppterm ty));
112 debug_print ("CURRENT PROOF = " ^ (CicPp.ppterm p));
113 debug_print ("CURRENT HYP = " ^ (fst (print_context ey)));
115 (* if the goal contains metavariables we use the input
116 signature for at_most constraints *)
117 let is_meta_closed = CicUtil.is_meta_closed ty in
119 if is_meta_closed then
120 None, Some (MetadataConstraints.signature_of ty)
121 else sign,sign in (* maybe the union ? *)
124 search_theorems_in_context
125 proof goal (depth-1) [] new_sign in
131 ~dbd ~facts:facts ?signature:sign status))
132 proof goal (depth-1) [] new_sign in
133 (* we proceed depth-first on the current goal. This is
134 a MAJOR optimization, since in case of success, and
135 if the goal is meta_closed, we may just drop the alternatives
136 tl1, avoiding useless backtracking. *)
138 local_choices@global_choices in
139 (match (auto dbd all_choices)
142 | (proof,[],_)::tl1 ->
144 let gtl' = List.map fst gtl in
145 if (gtl = [] || is_meta_closed) then
150 (function (p,l,s) -> (p,l@gtl,s)) tl1)
152 (proof,gtl,sign)::tl2@tl in
155 | None -> auto dbd ((proof,gtl,sign)::tl)
159 let auto_tac ?num dbd =
160 let auto_tac dbh (proof,goal) =
161 debug_print "Entro in Auto";
162 match (auto dbd [(proof, [(goal,depth)],None)]) with
163 [] -> debug_print("Auto failed");
164 raise (ProofEngineTypes.Fail "No Applicable theorem")
166 debug_print "AUTO_TAC HA FINITO";
170 ProofEngineTypes.mk_tactic (auto_tac dbd)
174 (************************** EXPERIMENTAL VERSION ****************************)
176 (* In this versions of auto_tac we maintain an hash table of all inspected
177 goals. We assume that the context is invariant for application.
178 To this aim, it is essential to sall hint_verbose, that in turns calls
185 | Yes of Cic.term * int
188 let inspected_goals = Hashtbl.create 503;;
190 let search_theorems_in_context status =
191 let (proof, goal) = status in
192 let module C = Cic in
193 let module R = CicReduction in
194 let module S = CicSubstitution in
195 let module PET = ProofEngineTypes in
196 let module PT = PrimitiveTactics in
197 let _,metasenv,_,_ = proof in
198 let _,context,ty = CicUtil.lookup_meta goal metasenv in
199 let rec find n = function
204 let (subst,(proof, goal_list)) =
205 PT.apply_tac_verbose ~term:(C.Rel n) status in
208 List.stable_sort (compare_goal_list proof) goal_list in
210 Some (subst,(proof, goal_list))
212 PET.Fail _ -> None in
214 Some res -> res::(find (n+1) tl)
215 | None -> find (n+1) tl)
223 (** splits a list of goals in three groups: closed propositional goals,
224 open propositional goals and non proposotional goals *)
227 let _,metasenv,_,_ = proof in
231 let (_, ey, ty) = CicUtil.lookup_meta g metasenv in
233 CicTypeChecker.type_of_aux' metasenv ey ty CicUniv.empty_ugraph in
235 CicReduction.are_convertible ey (Cic.Sort Cic.Prop) ty_sort u in
237 (if CicUtil.is_meta_closed ty then
243 CicUtil.Meta_not_found _ -> (c,o,g::z,n)
248 let my_weight dbd sign proof g =
250 search_theorems_in_context (proof,g) in
252 (List.map snd (MetadataQuery.experimental_hint
253 ~dbd ~facts:false ?signature:sign (proof,g))) in *)
255 (fun n (_,(_,l)) -> n+(List.length l)+1)
259 let add_weight dbd sign proof =
260 List.map (function g -> (g,my_weight dbd sign proof g))
265 (* let reorder_goals dbd sign proof goals =
268 (* let reorder_goals dbd sign proof goals =
269 let (c,o,z,n) = split proof goals
272 let reorder_goals dbd sign proof goals =
273 let (c,o,z,n) = split proof goals in
278 let l' = add_weight dbd sign proof l in
279 c@(List.map fst (List.sort (fun (_,x) (_,y) -> x - y) l'))@n@z
281 let compare_goals proof goal1 goal2 =
282 let _,metasenv,_,_ = proof in
283 let (_, ey1, ty1) = CicUtil.lookup_meta goal1 metasenv in
284 let (_, ey2, ty2) = CicUtil.lookup_meta goal2 metasenv in
285 let ty_sort1,_ = CicTypeChecker.type_of_aux' metasenv ey1 ty1
286 CicUniv.empty_ugraph in
287 let ty_sort2,_ = CicTypeChecker.type_of_aux' metasenv ey2 ty2
288 CicUniv.empty_ugraph in
290 let b,_ = CicReduction.are_convertible ey1 (Cic.Sort Cic.Prop) ty_sort1
291 CicUniv.empty_ugraph in
295 let b,_ = CicReduction.are_convertible ey2 (Cic.Sort Cic.Prop) ty_sort2
296 CicUniv.empty_ugraph in
302 let new_search_theorems f dbd proof goal depth sign =
303 let choices = f (proof,goal)
306 (function (subst,(proof, goallist)) ->
307 (* let goallist = reorder_goals dbd sign proof goallist in *)
308 let goallist = List.sort (compare_goals proof) goallist in
309 (subst,(proof,(List.map (function g -> (g,depth)) goallist), sign)))
313 exception NoOtherChoices;;
315 let is_in_metasenv goal metasenv =
318 CicUtil.lookup_meta goal metasenv in
322 let rec auto_single dbd proof goal ey ty depth width sign already_seen_goals
324 if depth = 0 then [] else
325 if List.mem ty already_seen_goals then [] else
326 let already_seen_goals = ty::already_seen_goals in
327 let facts = (depth = 1) in
328 let _,metasenv,p,_ = proof in
329 (* first of all we check if the goal has been already
331 assert (is_in_metasenv goal metasenv);
333 try Hashtbl.find inspected_goals ty
334 with Not_found -> NotYetInspected in
335 let is_meta_closed = CicUtil.is_meta_closed ty in
340 debug_print "ALREADY PROVED!!!!!!!!!!!!!!!!!!!!!!!!!!!!";
341 debug_print (CicPp.ppterm ty);
344 (* if we just apply the subtitution, the type
345 is irrelevant: we may use Implicit, since it will
347 CicMetaSubst.apply_subst
348 [(goal,(ey, bo, Cic.Implicit None))] in
350 ProofEngineHelpers.subst_meta_and_metasenv_in_proof
351 proof goal subst_in metasenv in
352 [(subst_in,(proof,[],sign))]
353 | No d when (d >= depth) ->
354 (* debug_print "PRUNED!!!!!!!!!!!!!!!!!!!!!!!!!!!!"; *)
355 [] (* the empty list means no choices, i.e. failure *)
359 debug_print ("CURRENT GOAL = " ^ (CicPp.ppterm ty));
360 debug_print ("CURRENT PROOF = " ^ (CicPp.ppterm p));
361 debug_print ("CURRENT HYP = " ^ (fst (print_context ey)));
364 if is_meta_closed then
365 None, Some (MetadataConstraints.signature_of ty)
366 else sign,sign in (* maybe the union ? *)
369 search_theorems_in_context dbd
370 proof goal (depth-1) new_sign in
371 let global_choices = [] in
376 (MetadataQuery.experimental_hint
377 ~dbd ~facts:facts ?signature:sign status))
378 dbd proof goal (depth-1) new_sign in *)
380 local_choices@global_choices in
383 (fun (_, (_, goals1, _)) (_, (_, goals2, _)) ->
385 (List.length goals1) (List.length goals2))
387 (match (auto_new dbd width already_seen_goals sorted_choices)
390 (* no proof has been found; we update the
392 (* if is_meta_closed then *)
393 Hashtbl.add inspected_goals ty (No depth);
395 | (subst,(proof,[],sign))::tl1 ->
396 (* a proof for goal has been found:
397 in order to get the proof we apply subst to
399 if is_meta_closed then
402 CicMkImplicit.identity_relocation_list_for_metavariable ey in
404 subst (Cic.Meta(goal,irl)) in
405 Hashtbl.add inspected_goals
406 ty (Yes (meta_proof,depth));
410 CicTypeChecker.type_of_aux' metasenv ey meta_proof CicUniv.empty_ugraph
412 if not (cty = ty) then
414 debug_print ("ty = "^CicPp.ppterm ty);
415 debug_print ("cty = "^CicPp.ppterm cty);
418 Hashtbl.add inspected_goals
419 ty (Yes (meta_proof,depth));
423 (subst,(proof,[],sign))::tl1
427 and auto_new dbd width already_seen_goals = function
429 | (subst,(proof, goals, sign))::tl ->
430 let _,metasenv,_,_ = proof in
431 let is_in_metasenv (goal, _) =
434 CicUtil.lookup_meta goal metasenv in
437 let goals'= List.filter is_in_metasenv goals in
438 auto_new_aux dbd width already_seen_goals
439 ((subst,(proof, goals', sign))::tl)
441 and auto_new_aux dbd width already_seen_goals = function
443 | (subst,(proof, [], sign))::tl -> (subst,(proof, [], sign))::tl
444 | (subst,(proof, (goal,0)::_, _))::tl ->
445 auto_new dbd width already_seen_goals tl
446 | (subst,(proof, goals, _))::tl when
447 (List.length goals) > width+1 ->
448 auto_new dbd width already_seen_goals tl
449 | (subst,(proof, (goal,depth)::gtl, sign))::tl ->
450 let maxdepthgoals,othergoals =
453 (g,d)::l when d=depth -> aux (g::acc) l
456 let _,metasenv,p,_ = proof in
457 let len1 = List.length maxdepthgoals in
458 let maxdepthgoals = reorder_goals dbd sign proof maxdepthgoals in
459 let len2 = List.length maxdepthgoals in
460 match maxdepthgoals with
462 ("caso sospetto " ^ (string_of_int (List.length othergoals)) ^ " " ^ string_of_int depth);
464 width already_seen_goals((subst,(proof, othergoals, sign))::tl)
466 let gtl = (List.map (fun x->(x,depth)) tgs)@othergoals in
471 CicUtil.lookup_meta goal metasenv in
478 match (auto_single dbd proof goal ey ty depth
479 (width - (List.length gtl) - (len1-len2)) sign already_seen_goals)
481 [] -> auto_new dbd width already_seen_goals tl
482 | (local_subst,(proof,[],sign))::tl1 ->
483 let new_subst f t = f (subst t) in
484 let is_meta_closed = CicUtil.is_meta_closed ty in
486 if is_meta_closed then
487 (new_subst local_subst,(proof,gtl,sign))::tl
491 (function (f,(p,l,s)) -> (new_subst f,(p,l@gtl,s))) tl1)
493 (new_subst local_subst,(proof,gtl,sign))::tl2@tl in
494 auto_new dbd width already_seen_goals all_choices
497 | None -> debug_print "caso none";
499 dbd width already_seen_goals ((subst,(proof, gtl, sign))::tl)
504 let auto_tac_new ~(dbd:Mysql.dbd) =
505 let auto_tac dbd (proof,goal) =
506 Hashtbl.clear inspected_goals;
507 debug_print "Entro in Auto";
509 match (auto_new dbd width [] [id,(proof, [(goal,depth)],None)]) with
510 [] -> debug_print("Auto failed");
511 raise (ProofEngineTypes.Fail "No Applicable theorem")
512 | (_,(proof,[],_))::_ ->
513 debug_print "AUTO_TAC HA FINITO";
514 let _,_,p,_ = proof in
515 debug_print (CicPp.ppterm p);
519 ProofEngineTypes.mk_tactic (auto_tac dbd)