]> matita.cs.unibo.it Git - helm.git/blob - helm/software/components/tactics/autoTactic.ml
Initial work on setoids:
[helm.git] / helm / software / components / 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 (* $Id$ *)
27
28  let debug = false
29  let debug_print s = if debug then prerr_endline (Lazy.force s)
30
31 (* let debug_print = fun _ -> () *)
32
33 (* Profiling code
34 let new_experimental_hint =
35  let profile = CicUtil.profile "new_experimental_hint" in
36  fun ~dbd ~facts ?signature ~universe status ->
37   profile.profile (MetadataQuery.new_experimental_hint ~dbd ~facts ?signature ~universe) status
38 *) let new_experimental_hint = MetadataQuery.new_experimental_hint
39
40 (* In this versions of auto_tac we maintain an hash table of all inspected
41    goals. We assume that the context is invariant for application. 
42    To this aim, it is essential to sall hint_verbose, that in turns calls
43    apply_verbose. *)
44
45 type exitus = 
46     No of int 
47   | Yes of Cic.term * int 
48   | NotYetInspected
49         
50 let inspected_goals = Hashtbl.create 503;;
51
52 let search_theorems_in_context status =
53   let (proof, goal) = status in
54   let module C = Cic 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 
62     | [] -> []
63     | hd::tl ->
64         let res =
65           (* we should check that the hypothesys has not been cleared *)
66           if List.nth context (n-1) = None then
67             None
68           else
69             try
70               let (subst,(proof, goal_list)) =
71                 PT.apply_tac_verbose ~term:(C.Rel n) status  
72               in
73               (* 
74                  let goal_list =
75                    List.stable_sort (compare_goal_list proof) goal_list in 
76               *)
77               Some (subst,(proof, goal_list))
78             with 
79              PET.Fail _ -> None 
80         in
81         (match res with
82         | Some res -> res::(find (n+1) tl)
83         | None -> find (n+1) tl)
84   in
85   try 
86     find 1 context
87   with Failure s -> []
88 ;;     
89
90
91 let compare_goals proof goal1 goal2 =
92   let _,metasenv,_,_ = proof in
93   let (_, ey1, ty1) = CicUtil.lookup_meta goal1 metasenv in
94   let (_, ey2, ty2) =  CicUtil.lookup_meta goal2 metasenv in
95   let ty_sort1,_ = CicTypeChecker.type_of_aux' metasenv ey1 ty1 
96                      CicUniv.empty_ugraph in
97   let ty_sort2,_ = CicTypeChecker.type_of_aux' metasenv ey2 ty2 
98                      CicUniv.empty_ugraph in
99   let prop1 =
100     let b,_ = CicReduction.are_convertible ey1 (Cic.Sort Cic.Prop) ty_sort1 
101                 CicUniv.empty_ugraph in
102       if b then 0 else 1
103   in
104   let prop2 =
105     let b,_ = CicReduction.are_convertible ey2 (Cic.Sort Cic.Prop) ty_sort2 
106                 CicUniv.empty_ugraph in
107       if b then 0 else 1
108   in
109   prop1 - prop2
110
111
112 let new_search_theorems f dbd proof goal depth sign =
113   let choices = f (proof,goal)
114   in 
115   List.map 
116     (function (subst,(proof, goallist)) ->
117        (* let goallist = reorder_goals dbd sign proof goallist in *)
118         let goallist = List.sort (compare_goals proof) goallist in 
119        (subst,(proof,(List.map (function g -> (g,depth)) goallist), sign)))
120     choices 
121 ;;
122
123 exception NoOtherChoices;;
124
125 let rec auto_single dbd proof goal ey ty depth width sign already_seen_goals
126  universe
127   =
128   if depth = 0 then [] else
129   if List.mem ty already_seen_goals then [] else
130   let already_seen_goals = ty::already_seen_goals in
131   let facts = (depth = 1) in  
132   let _,metasenv,p,_ = proof in
133     (* first of all we check if the goal has been already
134        inspected *)
135   assert (CicUtil.exists_meta goal metasenv);
136   let exitus =
137     try Hashtbl.find inspected_goals ty
138     with Not_found -> NotYetInspected in
139   let is_meta_closed = CicUtil.is_meta_closed ty in
140     begin
141       match exitus with
142           Yes (bo,_) ->
143             (*
144               debug_print (lazy "ALREADY PROVED!!!!!!!!!!!!!!!!!!!!!!!!!!!!");
145               debug_print (lazy (CicPp.ppterm ty));
146             *)
147             let subst_in =
148               (* if we just apply the subtitution, the type 
149                  is irrelevant: we may use Implicit, since it will 
150                  be dropped *)
151               CicMetaSubst.apply_subst 
152                 [(goal,(ey, bo, Cic.Implicit None))] in
153             let (proof,_) = 
154               ProofEngineHelpers.subst_meta_and_metasenv_in_proof 
155                 proof goal subst_in metasenv in
156               [(subst_in,(proof,[],sign))]
157         | No d when (d >= depth) -> 
158             (* debug_print (lazy "PRUNED!!!!!!!!!!!!!!!!!!!!!!!!!!!!"); *)
159             [] (* the empty list means no choices, i.e. failure *)
160         | No _ 
161         | NotYetInspected ->
162               debug_print (lazy ("CURRENT GOAL = " ^ CicPp.ppterm ty));
163               debug_print (lazy ("CURRENT PROOF = " ^ CicPp.ppterm p));
164               debug_print (lazy ("CURRENT HYP = " ^ CicPp.ppcontext ey));
165             let sign, new_sign =
166               if is_meta_closed then
167                 None, Some (MetadataConstraints.signature_of ty)
168               else sign,sign in (* maybe the union ? *)
169             let local_choices =
170               new_search_theorems 
171                 search_theorems_in_context dbd
172                 proof goal (depth-1) new_sign in
173             let global_choices =
174               new_search_theorems 
175                 (fun status -> 
176                    List.map snd
177                    (new_experimental_hint 
178                       ~dbd ~facts:facts ?signature:sign ~universe status))
179                 dbd proof goal (depth-1) new_sign in 
180             let all_choices =
181               local_choices@global_choices in
182             let sorted_choices = 
183               List.stable_sort
184                 (fun (_, (_, goals1, _)) (_, (_, goals2, _)) ->
185                    Pervasives.compare 
186                    (List.length goals1) (List.length goals2))
187                 all_choices in 
188               (match (auto_new dbd width already_seen_goals universe sorted_choices) 
189                with
190                    [] -> 
191                      (* no proof has been found; we update the
192                         hastable *)
193                      (* if is_meta_closed then *)
194                        Hashtbl.add inspected_goals ty (No depth);
195                      []
196                  | (subst,(proof,[],sign))::tl1 -> 
197                      (* a proof for goal has been found:
198                         in order to get the proof we apply subst to
199                         Meta[goal] *)
200                      if is_meta_closed  then
201                        begin 
202                          let irl = 
203                            CicMkImplicit.identity_relocation_list_for_metavariable ey in
204                          let meta_proof = 
205                            subst (Cic.Meta(goal,irl)) in
206                            Hashtbl.add inspected_goals 
207                              ty (Yes (meta_proof,depth));
208 (*
209                            begin
210                              let cty,_ = 
211                                CicTypeChecker.type_of_aux' metasenv ey meta_proof CicUniv.empty_ugraph
212                              in
213                                if not (cty = ty) then
214                                  begin
215                                    debug_print (lazy ("ty =  "^CicPp.ppterm ty));
216                                    debug_print (lazy ("cty =  "^CicPp.ppterm cty));
217                                    assert false
218                                  end
219                                    Hashtbl.add inspected_goals 
220                                    ty (Yes (meta_proof,depth));
221                            end;
222 *)
223                        end;
224                      (subst,(proof,[],sign))::tl1
225                  | _ -> assert false)
226     end
227       
228 and auto_new dbd width already_seen_goals universe = function
229   | [] -> []
230   | (subst,(proof, goals, sign))::tl ->
231       let _,metasenv,_,_ = proof in
232       let goals'=
233         List.filter (fun (goal, _) -> CicUtil.exists_meta goal metasenv) goals
234       in
235             auto_new_aux dbd 
236         width already_seen_goals universe ((subst,(proof, goals', sign))::tl)
237
238 and auto_new_aux dbd width already_seen_goals universe = function
239   | [] -> []
240   | (subst,(proof, [], sign))::tl -> (subst,(proof, [], sign))::tl
241   | (subst,(proof, (goal,0)::_, _))::tl -> 
242       auto_new dbd width already_seen_goals universe tl
243   | (subst,(proof, goals, _))::tl when 
244       (List.length goals) > width -> 
245       auto_new dbd width already_seen_goals universe tl 
246   | (subst,(proof, (goal,depth)::gtl, sign))::tl -> 
247       let _,metasenv,p,_ = proof in
248       let (_, ey ,ty) = CicUtil.lookup_meta goal metasenv in
249       match (auto_single dbd proof goal ey ty depth
250         (width - (List.length gtl)) sign already_seen_goals) universe
251       with
252           [] -> auto_new dbd width already_seen_goals universe tl 
253         | (local_subst,(proof,[],sign))::tl1 -> 
254             let new_subst f t = f (subst t) in
255             let is_meta_closed = CicUtil.is_meta_closed ty in
256             let all_choices =
257               if is_meta_closed then 
258                 (new_subst local_subst,(proof,gtl,sign))::tl
259               else
260                 let tl2 = 
261                   (List.map 
262                      (function (f,(p,l,s)) -> (new_subst f,(p,l@gtl,s))) tl1)
263                 in                         
264                   (new_subst local_subst,(proof,gtl,sign))::tl2@tl in
265               auto_new dbd width already_seen_goals universe all_choices
266         | _ -> assert false
267  ;; 
268
269 let default_depth = 5
270 let default_width = 3
271
272 (*
273 let auto_tac ?(depth=default_depth) ?(width=default_width) ~(dbd:HMysql.dbd)
274   ()
275 =
276   let auto_tac dbd (proof,goal) =
277   let universe = MetadataQuery.signature_of_goal ~dbd (proof,goal) in
278   Hashtbl.clear inspected_goals;
279   debug_print (lazy "Entro in Auto");
280   let id t = t in
281   let t1 = Unix.gettimeofday () in
282   match auto_new dbd width [] universe [id,(proof, [(goal,depth)],None)] with
283       [] ->  debug_print (lazy "Auto failed");
284         raise (ProofEngineTypes.Fail "No Applicable theorem")
285     | (_,(proof,[],_))::_ ->
286         let t2 = Unix.gettimeofday () in
287         debug_print (lazy "AUTO_TAC HA FINITO");
288         let _,_,p,_ = proof in
289         debug_print (lazy (CicPp.ppterm p));
290         Printf.printf "tempo: %.9f\n" (t2 -. t1);
291         (proof,[])
292     | _ -> assert false
293   in
294   ProofEngineTypes.mk_tactic (auto_tac dbd)
295 ;;
296 *)
297
298 (*
299 let paramodulation_tactic = ref
300   (fun dbd ?full ?depth ?width status ->
301      raise (ProofEngineTypes.Fail (lazy "Not Ready yet...")));;
302
303 let term_is_equality = ref
304   (fun term -> debug_print (lazy "term_is_equality E` DUMMY!!!!"); false);;
305 *)
306
307 let bool name params =
308     try let _ = List.assoc name params in true with
309     | Not_found -> false
310 ;; 
311
312 let string name params =
313     try List.assoc name params with
314     | Not_found -> ""
315 ;; 
316
317 let int name default params =
318     try int_of_string (List.assoc name params) with
319     | Not_found -> default
320     | Failure _ -> 
321         raise (ProofEngineTypes.Fail (lazy (name ^ " must be an integer")))
322 ;;  
323
324 (*
325 let callback_for_paramodulation dbd width depth t l =
326   let _,y,x,xx = t in 
327   let universe = MetadataQuery.universe_of_goals ~dbd t l in
328   let todo = List.map (fun g -> (g, depth)) l in
329   prerr_endline ("AUTO: " ^ CicPp.ppterm x ^ " : " ^ CicPp.ppterm xx);
330   prerr_endline ("MENV: " ^ CicMetaSubst.ppmetasenv [] y);
331   match auto_new dbd width [] universe [(fun x -> x), (t, todo, None)] with
332   | (_,(proof,[],_))::_ -> proof
333   | _ -> raise (Failure "xxx")
334 ;;
335 *)
336
337 let callback_for_paramodulation dbd flags proof commonctx ?universe cache l =
338   let _,metasenv,_,_ = proof in
339   let oldmetasenv = metasenv in
340   let universe = 
341     match universe with
342     | Some u -> u 
343     | None -> 
344       let universe = 
345         AutoTypes.universe_of_goals dbd proof l AutoTypes.empty_universe 
346       in
347       AutoTypes.universe_of_context commonctx metasenv universe 
348   in
349   match
350     Auto.auto_all_solutions universe cache commonctx metasenv l flags
351   with
352   | [],cache -> [],cache,universe
353   | solutions,cache -> 
354       let solutions = 
355         HExtlib.filter_map
356           (fun (subst,metasenv) ->
357             let opened = 
358               ProofEngineHelpers.compare_metasenvs 
359                 ~oldmetasenv ~newmetasenv:metasenv
360             in
361             if opened = [] then
362               Some subst
363                 else
364               None)
365           solutions
366       in
367        solutions,cache,universe
368 ;;
369
370 let auto_tac ~params ~(dbd:HMysql.dbd) (proof, goal) =
371   (* argument parsing *)
372   let depth = int "depth" AutoTypes.default_flags.AutoTypes.maxdepth params in
373   let width = int "width" AutoTypes.default_flags.AutoTypes.maxwidth params in
374   let timeout = string "timeout" params in
375   let paramodulation = bool "paramodulation" params in
376   let full = bool "full" params in
377   let superposition = bool "superposition" params in
378   let target = string "target" params in
379   let table = string "table" params in
380   let subterms_only = bool "subterms_only" params in
381   let caso_strano = bool "caso_strano" params in
382   let demod_table = string "demod_table" params in
383   let timeout = 
384     try Some (float_of_string timeout) with Failure _ -> None
385   in
386   match superposition with
387   | true -> 
388       (* this is the ugly hack to debug paramod *)
389       Saturation.superposition_tac 
390         ~target ~table ~subterms_only ~demod_table (proof,goal)
391   | false -> 
392       (* this is the real auto *)
393       let _, metasenv, _, _ = proof in
394       let _, context, goalty = CicUtil.lookup_meta goal metasenv in
395       let use_paramodulation = 
396         paramodulation && Equality.term_is_equality goalty
397       in
398       if use_paramodulation then
399         try
400           let rc = 
401            Saturation.saturate 
402             ~auto:(callback_for_paramodulation dbd) 
403             caso_strano dbd ~depth ~width ~full
404             ?timeout (proof, goal) 
405           in
406           prerr_endline (Saturation.get_stats ());rc
407         with exn ->
408           prerr_endline (Saturation.get_stats ());raise exn
409       else
410         let universe = 
411           AutoTypes.universe_of_goals dbd proof [goal] AutoTypes.empty_universe 
412         in 
413         let universe = (* we should get back a menv too XXX *)
414           AutoTypes.universe_of_context context metasenv universe 
415         in
416         let oldmetasenv = metasenv in
417         match
418           Auto.auto universe AutoTypes.cache_empty context metasenv [goal]
419             {AutoTypes.default_flags with 
420               AutoTypes.maxdepth = depth;
421               AutoTypes.maxwidth = width;
422 (*               AutoTypes.timeout = 0; *)
423             }
424         with
425         | None,cache -> 
426             raise (ProofEngineTypes.Fail (lazy "Auto gave up"))
427         | Some (subst,metasenv),cache -> 
428             let proof,metasenv = 
429               ProofEngineHelpers.subst_meta_and_metasenv_in_proof
430                 proof goal (CicMetaSubst.apply_subst subst) metasenv
431             in
432             let opened = 
433               ProofEngineHelpers.compare_metasenvs ~oldmetasenv
434                 ~newmetasenv:metasenv
435             in
436             proof,opened
437 ;;
438
439 let auto_tac ~params ~dbd =
440       ProofEngineTypes.mk_tactic (auto_tac ~params ~dbd)
441 ;;
442
443 (* {{{ **************** applyS *******************)
444
445 let new_metasenv_and_unify_and_t dbd proof goal newmeta' metasenv' context term' ty termty goal_arity =
446  let (consthead,newmetasenv,arguments,_) =
447    ProofEngineHelpers.saturate_term newmeta' metasenv' context termty goal_arity in
448  let term'' = match arguments with [] -> term' | _ -> Cic.Appl (term'::arguments) in
449   let proof',metasenv =
450    let (puri,metasenv,pbo,pty) = proof in
451     (puri,newmetasenv,pbo,pty),metasenv
452   in
453    let proof'',goals =
454     match LibraryObjects.eq_URI () with
455     | Some uri -> 
456             ProofEngineTypes.apply_tactic
457              (Tacticals.then_
458                ~start:(PrimitiveTactics.letin_tac term''(*Tacticals.id_tac*))
459                ~continuation:
460                  (PrimitiveTactics.cut_tac
461                    (CicSubstitution.lift 1
462                     (Cic.Appl
463                      [Cic.MutInd (uri,0,[]);
464                       Cic.Sort Cic.Prop;
465                       consthead;
466                       ty])))) (proof',goal)
467    | None -> raise (ProofEngineTypes.Fail (lazy "No equality defined"))
468     in
469      match goals with
470         [g1;g2] ->
471           let proof'',goals =
472            ProofEngineTypes.apply_tactic
473            (auto_tac ~params:["caso_strano","on";"paramodulation","on"] ~dbd) (proof'',g2)
474           in
475            let proof'',goals =
476             ProofEngineTypes.apply_tactic
477              (Tacticals.then_
478               ~start:(EqualityTactics.rewrite_tac ~direction:`RightToLeft
479                 ~pattern:(ProofEngineTypes.conclusion_pattern None) (Cic.Rel 1))
480               ~continuation:(PrimitiveTactics.apply_tac (Cic.Rel 2))
481              ) (proof'',g1)
482            in
483             proof'',
484              (*CSC: Brrrr.... *)
485              ProofEngineHelpers.compare_metasenvs ~oldmetasenv:metasenv
486               ~newmetasenv:(let _,m,_,_ = proof'' in m)
487       | _ -> assert false
488
489 let rec count_prods context ty =
490  match CicReduction.whd context ty with
491     Cic.Prod (n,s,t) -> 1 + count_prods (Some (n,Cic.Decl s)::context) t
492   | _ -> 0
493
494 let applyS_tac ~dbd ~term (proof, goal) =
495  let module T = CicTypeChecker in
496  let module R = CicReduction in
497  let module C = Cic in
498   let (_,metasenv,_,_) = proof in
499   let metano,context,ty = CicUtil.lookup_meta goal metasenv in
500   let newmeta = ProofEngineHelpers.new_meta_of_proof ~proof in
501    let exp_named_subst_diff,newmeta',newmetasenvfragment,term' =
502     match term with
503        C.Var (uri,exp_named_subst) ->
504         let newmeta',newmetasenvfragment,exp_named_subst',exp_named_subst_diff =
505          PrimitiveTactics.generalize_exp_named_subst_with_fresh_metas context newmeta uri
506           exp_named_subst
507         in
508          exp_named_subst_diff,newmeta',newmetasenvfragment,
509           C.Var (uri,exp_named_subst')
510      | C.Const (uri,exp_named_subst) ->
511         let newmeta',newmetasenvfragment,exp_named_subst',exp_named_subst_diff =
512          PrimitiveTactics.generalize_exp_named_subst_with_fresh_metas context newmeta uri
513           exp_named_subst
514         in
515          exp_named_subst_diff,newmeta',newmetasenvfragment,
516           C.Const (uri,exp_named_subst')
517      | C.MutInd (uri,tyno,exp_named_subst) ->
518         let newmeta',newmetasenvfragment,exp_named_subst',exp_named_subst_diff =
519          PrimitiveTactics.generalize_exp_named_subst_with_fresh_metas context newmeta uri
520           exp_named_subst
521         in
522          exp_named_subst_diff,newmeta',newmetasenvfragment,
523           C.MutInd (uri,tyno,exp_named_subst')
524      | C.MutConstruct (uri,tyno,consno,exp_named_subst) ->
525         let newmeta',newmetasenvfragment,exp_named_subst',exp_named_subst_diff =
526          PrimitiveTactics.generalize_exp_named_subst_with_fresh_metas context newmeta uri
527           exp_named_subst
528         in
529          exp_named_subst_diff,newmeta',newmetasenvfragment,
530           C.MutConstruct (uri,tyno,consno,exp_named_subst')
531      | _ -> [],newmeta,[],term
532    in
533    let metasenv' = metasenv@newmetasenvfragment in
534    let termty,_ = 
535      CicTypeChecker.type_of_aux' metasenv' context term' CicUniv.empty_ugraph
536    in
537    let termty =
538      CicSubstitution.subst_vars exp_named_subst_diff termty in
539    let goal_arity = count_prods context ty in
540    let res =
541     new_metasenv_and_unify_and_t dbd proof goal
542      newmeta' metasenv' context term' ty termty goal_arity
543    in
544     res
545
546 let applyS_tac ~dbd ~term =
547  ProofEngineTypes.mk_tactic
548   (fun status ->
549     try applyS_tac ~dbd ~term status
550     with 
551     | CicUnification.UnificationFailure msg
552     | CicTypeChecker.TypeCheckerFailure msg ->
553         raise (ProofEngineTypes.Fail msg))
554
555 (* }}} ********************************)
556
557 let pp_proofterm = Equality.pp_proofterm;;