]> matita.cs.unibo.it Git - helm.git/blob - helm/ocaml/tactics/autoTactic.ml
removed deadcode / fixed typos (thanks to ocaml 3.09)
[helm.git] / helm / ocaml / tactics / autoTactic.ml
1 (* Copyright (C) 2002, HELM Team.
2  * 
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.
6  * 
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.
11  * 
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.
16  *
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,
20  * MA  02111-1307, USA.
21  * 
22  * For details, see the HELM World-Wide-Web page,
23  * http://cs.unibo.it/helm/.
24  *)
25
26  let debug = false
27  let debug_print s = if debug then prerr_endline (Lazy.force s)
28
29 (* let debug_print = fun _ -> () *)
30
31 (* Profiling code
32 let new_experimental_hint =
33  let profile = CicUtil.profile "new_experimental_hint" in
34  fun ~dbd ~facts ?signature ~universe status ->
35   profile.profile (MetadataQuery.new_experimental_hint ~dbd ~facts ?signature ~universe) status
36 *) let new_experimental_hint = MetadataQuery.new_experimental_hint
37
38 (* In this versions of auto_tac we maintain an hash table of all inspected
39    goals. We assume that the context is invariant for application. 
40    To this aim, it is essential to sall hint_verbose, that in turns calls
41    apply_verbose. *)
42
43 type exitus = 
44     No of int 
45   | Yes of Cic.term * int 
46   | NotYetInspected
47         
48 let inspected_goals = Hashtbl.create 503;;
49
50 let search_theorems_in_context status =
51   let (proof, goal) = status in
52   let module C = Cic in
53   let module R = CicReduction in
54   let module S = CicSubstitution in
55   let module PET = ProofEngineTypes in 
56   let module PT = PrimitiveTactics in 
57   let _,metasenv,_,_ = proof in
58   let _,context,ty = CicUtil.lookup_meta goal metasenv in
59   let rec find n = function 
60     | [] -> []
61     | hd::tl ->
62         let res =
63           (* we should check that the hypothesys has not been cleared *)
64           if List.nth context (n-1) = None then
65             None
66           else
67             try
68               let (subst,(proof, goal_list)) =
69                 PT.apply_tac_verbose ~term:(C.Rel n) status  
70               in
71               (* 
72                  let goal_list =
73                    List.stable_sort (compare_goal_list proof) goal_list in 
74               *)
75               Some (subst,(proof, goal_list))
76             with 
77              PET.Fail _ -> None 
78         in
79         (match res with
80         | Some res -> res::(find (n+1) tl)
81         | None -> find (n+1) tl)
82   in
83   try 
84     find 1 context
85   with Failure s -> []
86 ;;     
87
88
89 let compare_goals proof goal1 goal2 =
90   let _,metasenv,_,_ = proof in
91   let (_, ey1, ty1) = CicUtil.lookup_meta goal1 metasenv in
92   let (_, ey2, ty2) =  CicUtil.lookup_meta goal2 metasenv in
93   let ty_sort1,_ = CicTypeChecker.type_of_aux' metasenv ey1 ty1 
94                      CicUniv.empty_ugraph in
95   let ty_sort2,_ = CicTypeChecker.type_of_aux' metasenv ey2 ty2 
96                      CicUniv.empty_ugraph in
97   let prop1 =
98     let b,_ = CicReduction.are_convertible ey1 (Cic.Sort Cic.Prop) ty_sort1 
99                 CicUniv.empty_ugraph in
100       if b then 0 else 1
101   in
102   let prop2 =
103     let b,_ = CicReduction.are_convertible ey2 (Cic.Sort Cic.Prop) ty_sort2 
104                 CicUniv.empty_ugraph in
105       if b then 0 else 1
106   in
107   prop1 - prop2
108
109
110 let new_search_theorems f dbd proof goal depth sign =
111   let choices = f (proof,goal)
112   in 
113   List.map 
114     (function (subst,(proof, goallist)) ->
115        (* let goallist = reorder_goals dbd sign proof goallist in *)
116         let goallist = List.sort (compare_goals proof) goallist in 
117        (subst,(proof,(List.map (function g -> (g,depth)) goallist), sign)))
118     choices 
119 ;;
120
121 exception NoOtherChoices;;
122
123 let rec auto_single dbd proof goal ey ty depth width sign already_seen_goals
124  universe
125   =
126   if depth = 0 then [] else
127   if List.mem ty already_seen_goals then [] else
128   let already_seen_goals = ty::already_seen_goals in
129   let facts = (depth = 1) in  
130   let _,metasenv,p,_ = proof in
131     (* first of all we check if the goal has been already
132        inspected *)
133   assert (CicUtil.exists_meta goal metasenv);
134   let exitus =
135     try Hashtbl.find inspected_goals ty
136     with Not_found -> NotYetInspected in
137   let is_meta_closed = CicUtil.is_meta_closed ty in
138     begin
139       match exitus with
140           Yes (bo,_) ->
141             (*
142               debug_print (lazy "ALREADY PROVED!!!!!!!!!!!!!!!!!!!!!!!!!!!!");
143               debug_print (lazy (CicPp.ppterm ty));
144             *)
145             let subst_in =
146               (* if we just apply the subtitution, the type 
147                  is irrelevant: we may use Implicit, since it will 
148                  be dropped *)
149               CicMetaSubst.apply_subst 
150                 [(goal,(ey, bo, Cic.Implicit None))] in
151             let (proof,_) = 
152               ProofEngineHelpers.subst_meta_and_metasenv_in_proof 
153                 proof goal subst_in metasenv in
154               [(subst_in,(proof,[],sign))]
155         | No d when (d >= depth) -> 
156             (* debug_print (lazy "PRUNED!!!!!!!!!!!!!!!!!!!!!!!!!!!!"); *)
157             [] (* the empty list means no choices, i.e. failure *)
158         | No _ 
159         | NotYetInspected ->
160               debug_print (lazy ("CURRENT GOAL = " ^ CicPp.ppterm ty));
161               debug_print (lazy ("CURRENT PROOF = " ^ CicPp.ppterm p));
162               debug_print (lazy ("CURRENT HYP = " ^ CicPp.ppcontext ey));
163             let sign, new_sign =
164               if is_meta_closed then
165                 None, Some (MetadataConstraints.signature_of ty)
166               else sign,sign in (* maybe the union ? *)
167             let local_choices =
168               new_search_theorems 
169                 search_theorems_in_context dbd
170                 proof goal (depth-1) new_sign in
171             let global_choices =
172               new_search_theorems 
173                 (fun status -> 
174                    List.map snd
175                    (new_experimental_hint 
176                       ~dbd ~facts:facts ?signature:sign ~universe status))
177                 dbd proof goal (depth-1) new_sign in 
178             let all_choices =
179               local_choices@global_choices in
180             let sorted_choices = 
181               List.stable_sort
182                 (fun (_, (_, goals1, _)) (_, (_, goals2, _)) ->
183                    Pervasives.compare 
184                    (List.length goals1) (List.length goals2))
185                 all_choices in 
186               (match (auto_new dbd width already_seen_goals universe sorted_choices) 
187                with
188                    [] -> 
189                      (* no proof has been found; we update the
190                         hastable *)
191                      (* if is_meta_closed then *)
192                        Hashtbl.add inspected_goals ty (No depth);
193                      []
194                  | (subst,(proof,[],sign))::tl1 -> 
195                      (* a proof for goal has been found:
196                         in order to get the proof we apply subst to
197                         Meta[goal] *)
198                      if is_meta_closed  then
199                        begin 
200                          let irl = 
201                            CicMkImplicit.identity_relocation_list_for_metavariable ey in
202                          let meta_proof = 
203                            subst (Cic.Meta(goal,irl)) in
204                            Hashtbl.add inspected_goals 
205                              ty (Yes (meta_proof,depth));
206 (*
207                            begin
208                              let cty,_ = 
209                                CicTypeChecker.type_of_aux' metasenv ey meta_proof CicUniv.empty_ugraph
210                              in
211                                if not (cty = ty) then
212                                  begin
213                                    debug_print (lazy ("ty =  "^CicPp.ppterm ty));
214                                    debug_print (lazy ("cty =  "^CicPp.ppterm cty));
215                                    assert false
216                                  end
217                                    Hashtbl.add inspected_goals 
218                                    ty (Yes (meta_proof,depth));
219                            end;
220 *)
221                        end;
222                      (subst,(proof,[],sign))::tl1
223                  | _ -> assert false)
224     end
225       
226 and auto_new dbd width already_seen_goals universe = function
227   | [] -> []
228   | (subst,(proof, goals, sign))::tl ->
229       let _,metasenv,_,_ = proof in
230       let goals'=
231         List.filter (fun (goal, _) -> CicUtil.exists_meta goal metasenv) goals
232       in
233         auto_new_aux dbd 
234         width already_seen_goals universe ((subst,(proof, goals', sign))::tl)
235
236 and auto_new_aux dbd width already_seen_goals universe = function
237   | [] -> []
238   | (subst,(proof, [], sign))::tl -> (subst,(proof, [], sign))::tl
239   | (subst,(proof, (goal,0)::_, _))::tl -> 
240       auto_new dbd width already_seen_goals universe tl
241   | (subst,(proof, goals, _))::tl when 
242       (List.length goals) > width -> 
243       auto_new dbd width already_seen_goals universe tl 
244   | (subst,(proof, (goal,depth)::gtl, sign))::tl -> 
245       let _,metasenv,p,_ = proof in
246       let (_, ey ,ty) = CicUtil.lookup_meta goal metasenv in
247       match (auto_single dbd proof goal ey ty depth
248         (width - (List.length gtl)) sign already_seen_goals) universe
249       with
250           [] -> auto_new dbd width already_seen_goals universe tl 
251         | (local_subst,(proof,[],sign))::tl1 -> 
252             let new_subst f t = f (subst t) in
253             let is_meta_closed = CicUtil.is_meta_closed ty in
254             let all_choices =
255               if is_meta_closed then 
256                 (new_subst local_subst,(proof,gtl,sign))::tl
257               else
258                 let tl2 = 
259                   (List.map 
260                      (function (f,(p,l,s)) -> (new_subst f,(p,l@gtl,s))) tl1)
261                 in                       
262                   (new_subst local_subst,(proof,gtl,sign))::tl2@tl in
263               auto_new dbd width already_seen_goals universe all_choices
264         | _ -> assert false
265  ;; 
266
267 let default_depth = 5
268 let default_width = 3
269
270 (*
271 let auto_tac ?(depth=default_depth) ?(width=default_width) ~(dbd:HMysql.dbd)
272   ()
273 =
274   let auto_tac dbd (proof,goal) =
275   let universe = MetadataQuery.signature_of_goal ~dbd (proof,goal) in
276   Hashtbl.clear inspected_goals;
277   debug_print (lazy "Entro in Auto");
278   let id t = t in
279   let t1 = Unix.gettimeofday () in
280   match auto_new dbd width [] universe [id,(proof, [(goal,depth)],None)] with
281       [] ->  debug_print (lazy "Auto failed");
282         raise (ProofEngineTypes.Fail "No Applicable theorem")
283     | (_,(proof,[],_))::_ ->
284         let t2 = Unix.gettimeofday () in
285         debug_print (lazy "AUTO_TAC HA FINITO");
286         let _,_,p,_ = proof in
287         debug_print (lazy (CicPp.ppterm p));
288         Printf.printf "tempo: %.9f\n" (t2 -. t1);
289         (proof,[])
290     | _ -> assert false
291   in
292   ProofEngineTypes.mk_tactic (auto_tac dbd)
293 ;;
294 *)
295
296 let paramodulation_tactic = ref
297   (fun dbd ?full ?depth ?width status ->
298      raise (ProofEngineTypes.Fail (lazy "Not Ready yet...")));;
299
300 let term_is_equality = ref
301   (fun term -> debug_print (lazy "term_is_equality E` DUMMY!!!!"); false);;
302
303
304 let auto_tac ?(depth=default_depth) ?(width=default_width) ?paramodulation
305     ?full ~(dbd:HMysql.dbd) () =
306   let auto_tac dbd (proof, goal) =
307     let normal_auto () = 
308       let universe = MetadataQuery.signature_of_goal ~dbd (proof, goal) in
309       Hashtbl.clear inspected_goals;
310       debug_print (lazy "Entro in Auto");
311       let id t = t in
312       let t1 = Unix.gettimeofday () in
313       match
314         auto_new dbd width [] universe [id, (proof, [(goal, depth)], None)]
315       with
316         [] ->  debug_print(lazy "Auto failed");
317           raise (ProofEngineTypes.Fail (lazy "No Applicable theorem"))
318       | (_,(proof,[],_))::_ ->
319           let t2 = Unix.gettimeofday () in
320           debug_print (lazy "AUTO_TAC HA FINITO");
321           let _,_,p,_ = proof in
322           debug_print (lazy (CicPp.ppterm p));
323           debug_print (lazy (Printf.sprintf "tempo: %.9f\n" (t2 -. t1)));
324           (proof,[])
325       | _ -> assert false
326     in
327     let full = match full with None -> false | Some _ -> true in
328     let paramodulation_ok =
329       match paramodulation with
330       | None -> false
331       | Some _ ->
332           let _, metasenv, _, _ = proof in
333           let _, _, meta_goal = CicUtil.lookup_meta goal metasenv in
334           full || (!term_is_equality meta_goal)
335     in
336     if paramodulation_ok then (
337       debug_print (lazy "USO PARAMODULATION...");
338 (*       try *)
339       !paramodulation_tactic dbd ~depth ~width ~full (proof, goal)
340 (*       with ProofEngineTypes.Fail _ -> *)
341 (*         normal_auto () *)
342     ) else
343       normal_auto () 
344   in
345   ProofEngineTypes.mk_tactic (auto_tac dbd)
346 ;;