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 = (* ignore *) prerr_endline
28 (* let debug_print = fun _ -> () *)
31 let new_experimental_hint =
32 let profile = CicUtil.profile "new_experimental_hint" in
33 fun ~dbd ~facts ?signature ~universe status ->
34 profile.profile (MetadataQuery.new_experimental_hint ~dbd ~facts ?signature ~universe) status
35 *) let new_experimental_hint = MetadataQuery.new_experimental_hint
37 (* In this versions of auto_tac we maintain an hash table of all inspected
38 goals. We assume that the context is invariant for application.
39 To this aim, it is essential to sall hint_verbose, that in turns calls
44 | Yes of Cic.term * int
47 let inspected_goals = Hashtbl.create 503;;
49 let search_theorems_in_context status =
50 let (proof, goal) = status in
52 let module R = CicReduction in
53 let module S = CicSubstitution in
54 let module PET = ProofEngineTypes in
55 let module PT = PrimitiveTactics in
56 let _,metasenv,_,_ = proof in
57 let _,context,ty = CicUtil.lookup_meta goal metasenv in
58 let rec find n = function
62 (* we should check that the hypothesys has not been cleared *)
63 if List.nth context (n-1) = None then
67 let (subst,(proof, goal_list)) =
68 PT.apply_tac_verbose ~term:(C.Rel n) status
72 List.stable_sort (compare_goal_list proof) goal_list in
74 Some (subst,(proof, goal_list))
79 | Some res -> res::(find (n+1) tl)
80 | None -> find (n+1) tl)
88 let compare_goals proof goal1 goal2 =
89 let _,metasenv,_,_ = proof in
90 let (_, ey1, ty1) = CicUtil.lookup_meta goal1 metasenv in
91 let (_, ey2, ty2) = CicUtil.lookup_meta goal2 metasenv in
92 let ty_sort1,_ = CicTypeChecker.type_of_aux' metasenv ey1 ty1
93 CicUniv.empty_ugraph in
94 let ty_sort2,_ = CicTypeChecker.type_of_aux' metasenv ey2 ty2
95 CicUniv.empty_ugraph in
97 let b,_ = CicReduction.are_convertible ey1 (Cic.Sort Cic.Prop) ty_sort1
98 CicUniv.empty_ugraph in
102 let b,_ = CicReduction.are_convertible ey2 (Cic.Sort Cic.Prop) ty_sort2
103 CicUniv.empty_ugraph in
109 let new_search_theorems f dbd proof goal depth sign =
110 let choices = f (proof,goal)
113 (function (subst,(proof, goallist)) ->
114 (* let goallist = reorder_goals dbd sign proof goallist in *)
115 let goallist = List.sort (compare_goals proof) goallist in
116 (subst,(proof,(List.map (function g -> (g,depth)) goallist), sign)))
120 exception NoOtherChoices;;
122 let is_in_metasenv goal metasenv =
125 CicUtil.lookup_meta goal metasenv in
127 with CicUtil.Meta_not_found _ -> false
129 let rec auto_single dbd proof goal ey ty depth width sign already_seen_goals
132 if depth = 0 then [] else
133 if List.mem ty already_seen_goals then [] else
134 let already_seen_goals = ty::already_seen_goals in
135 let facts = (depth = 1) in
136 let _,metasenv,p,_ = proof in
137 (* first of all we check if the goal has been already
139 assert (is_in_metasenv goal metasenv);
141 try Hashtbl.find inspected_goals ty
142 with Not_found -> NotYetInspected in
143 let is_meta_closed = CicUtil.is_meta_closed ty in
148 debug_print "ALREADY PROVED!!!!!!!!!!!!!!!!!!!!!!!!!!!!";
149 debug_print (CicPp.ppterm ty);
152 (* if we just apply the subtitution, the type
153 is irrelevant: we may use Implicit, since it will
155 CicMetaSubst.apply_subst
156 [(goal,(ey, bo, Cic.Implicit None))] in
158 ProofEngineHelpers.subst_meta_and_metasenv_in_proof
159 proof goal subst_in metasenv in
160 [(subst_in,(proof,[],sign))]
161 | No d when (d >= depth) ->
162 (* debug_print "PRUNED!!!!!!!!!!!!!!!!!!!!!!!!!!!!"; *)
163 [] (* the empty list means no choices, i.e. failure *)
166 debug_print ("CURRENT GOAL = " ^ CicPp.ppterm ty);
167 debug_print ("CURRENT PROOF = " ^ CicPp.ppterm p);
168 debug_print ("CURRENT HYP = " ^ CicPp.ppcontext ey);
170 if is_meta_closed then
171 None, Some (MetadataConstraints.signature_of ty)
172 else sign,sign in (* maybe the union ? *)
175 search_theorems_in_context dbd
176 proof goal (depth-1) new_sign in
181 (new_experimental_hint
182 ~dbd ~facts:facts ?signature:sign ~universe status))
183 dbd proof goal (depth-1) new_sign in
185 local_choices@global_choices in
188 (fun (_, (_, goals1, _)) (_, (_, goals2, _)) ->
190 (List.length goals1) (List.length goals2))
192 (match (auto_new dbd width already_seen_goals universe sorted_choices)
195 (* no proof has been found; we update the
197 (* if is_meta_closed then *)
198 Hashtbl.add inspected_goals ty (No depth);
200 | (subst,(proof,[],sign))::tl1 ->
201 (* a proof for goal has been found:
202 in order to get the proof we apply subst to
204 if is_meta_closed then
207 CicMkImplicit.identity_relocation_list_for_metavariable ey in
209 subst (Cic.Meta(goal,irl)) in
210 Hashtbl.add inspected_goals
211 ty (Yes (meta_proof,depth));
215 CicTypeChecker.type_of_aux' metasenv ey meta_proof CicUniv.empty_ugraph
217 if not (cty = ty) then
219 debug_print ("ty = "^CicPp.ppterm ty);
220 debug_print ("cty = "^CicPp.ppterm cty);
223 Hashtbl.add inspected_goals
224 ty (Yes (meta_proof,depth));
228 (subst,(proof,[],sign))::tl1
232 and auto_new dbd width already_seen_goals universe = function
234 | (subst,(proof, goals, sign))::tl ->
235 let _,metasenv,_,_ = proof in
236 let is_in_metasenv (goal, _) =
238 let (_, ey ,ty) = CicUtil.lookup_meta goal metasenv in
240 with CicUtil.Meta_not_found _ -> false
242 let goals'= List.filter is_in_metasenv goals in
244 width already_seen_goals universe ((subst,(proof, goals', sign))::tl)
246 and auto_new_aux dbd width already_seen_goals universe = function
248 | (subst,(proof, [], sign))::tl -> (subst,(proof, [], sign))::tl
249 | (subst,(proof, (goal,0)::_, _))::tl ->
250 auto_new dbd width already_seen_goals universe tl
251 | (subst,(proof, goals, _))::tl when
252 (List.length goals) > width ->
253 auto_new dbd width already_seen_goals universe tl
254 | (subst,(proof, (goal,depth)::gtl, sign))::tl ->
255 let _,metasenv,p,_ = proof in
256 let (_, ey ,ty) = CicUtil.lookup_meta goal metasenv in
257 match (auto_single dbd proof goal ey ty depth
258 (width - (List.length gtl)) sign already_seen_goals) universe
260 [] -> auto_new dbd width already_seen_goals universe tl
261 | (local_subst,(proof,[],sign))::tl1 ->
262 let new_subst f t = f (subst t) in
263 let is_meta_closed = CicUtil.is_meta_closed ty in
265 if is_meta_closed then
266 (new_subst local_subst,(proof,gtl,sign))::tl
270 (function (f,(p,l,s)) -> (new_subst f,(p,l@gtl,s))) tl1)
272 (new_subst local_subst,(proof,gtl,sign))::tl2@tl in
273 auto_new dbd width already_seen_goals universe all_choices
277 let default_depth = 5
278 let default_width = 3
281 let auto_tac ?(depth=default_depth) ?(width=default_width) ~(dbd:Mysql.dbd)
284 let auto_tac dbd (proof,goal) =
285 let universe = MetadataQuery.signature_of_goal ~dbd (proof,goal) in
286 Hashtbl.clear inspected_goals;
287 debug_print "Entro in Auto";
289 let t1 = Unix.gettimeofday () in
290 match auto_new dbd width [] universe [id,(proof, [(goal,depth)],None)] with
291 [] -> debug_print("Auto failed");
292 raise (ProofEngineTypes.Fail "No Applicable theorem")
293 | (_,(proof,[],_))::_ ->
294 let t2 = Unix.gettimeofday () in
295 debug_print "AUTO_TAC HA FINITO";
296 let _,_,p,_ = proof in
297 debug_print (CicPp.ppterm p);
298 Printf.printf "tempo: %.9f\n" (t2 -. t1);
302 ProofEngineTypes.mk_tactic (auto_tac dbd)
306 let paramodulation_tactic = ref
307 (fun dbd status -> raise (ProofEngineTypes.Fail "Not Ready yet..."));;
309 let term_is_equality = ref
310 (fun term -> debug_print "term_is_equality E` DUMMY!!!!"; false);;
313 let auto_tac ?(depth=default_depth) ?(width=default_width) ?paramodulation ~(dbd:Mysql.dbd) () =
314 let auto_tac dbd (proof, goal) =
316 let universe = MetadataQuery.signature_of_goal ~dbd (proof, goal) in
317 Hashtbl.clear inspected_goals;
318 debug_print "Entro in Auto";
320 let t1 = Unix.gettimeofday () in
322 auto_new dbd width [] universe [id, (proof, [(goal, depth)], None)]
324 [] -> debug_print("Auto failed");
325 raise (ProofEngineTypes.Fail "No Applicable theorem")
326 | (_,(proof,[],_))::_ ->
327 let t2 = Unix.gettimeofday () in
328 debug_print "AUTO_TAC HA FINITO";
329 let _,_,p,_ = proof in
330 debug_print (CicPp.ppterm p);
331 debug_print (Printf.sprintf "tempo: %.9f\n" (t2 -. t1));
335 let paramodulation_ok =
336 match paramodulation with
339 let _, metasenv, _, _ = proof in
340 let _, _, meta_goal = CicUtil.lookup_meta goal metasenv in
341 !term_is_equality meta_goal
343 if paramodulation_ok then (
344 debug_print "USO PARAMODULATION...";
346 !paramodulation_tactic dbd (proof, goal)
347 (* with ProofEngineTypes.Fail _ -> *)
352 ProofEngineTypes.mk_tactic (auto_tac dbd)