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