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 is_in_metasenv goal metasenv =
 124   try
 125     let (_, ey ,ty) =
 126       CicUtil.lookup_meta goal metasenv in
 127       true
 128   with CicUtil.Meta_not_found _ -> false
 129
 130 let rec auto_single dbd proof goal ey ty depth width sign already_seen_goals
 131  universe
 132   =
 133   if depth = 0 then [] else
 134   if List.mem ty already_seen_goals then [] else
 135   let already_seen_goals = ty::already_seen_goals in
 136   let facts = (depth = 1) in
 137   let _,metasenv,p,_ = proof in
 138     (* first of all we check if the goal has been already
 139        inspected *)
 140   assert (is_in_metasenv goal metasenv);
 141   let exitus =
 142     try Hashtbl.find inspected_goals ty
 143     with Not_found -> NotYetInspected in
 144   let is_meta_closed = CicUtil.is_meta_closed ty in
 145     begin
 146       match exitus with
 147           Yes (bo,_) ->
 148             (*
 149               debug_print (lazy "ALREADY PROVED!!!!!!!!!!!!!!!!!!!!!!!!!!!!");
 150               debug_print (lazy (CicPp.ppterm ty));
 151             *)
 152             let subst_in =
 153               (* if we just apply the subtitution, the type
 154                  is irrelevant: we may use Implicit, since it will
 155                  be dropped *)
 156               CicMetaSubst.apply_subst
 157                 [(goal,(ey, bo, Cic.Implicit None))] in
 158             let (proof,_) =
 159               ProofEngineHelpers.subst_meta_and_metasenv_in_proof
 160                 proof goal subst_in metasenv in
 161               [(subst_in,(proof,[],sign))]
 162         | No d when (d >= depth) ->
 163             (* debug_print (lazy "PRUNED!!!!!!!!!!!!!!!!!!!!!!!!!!!!"); *)
 164             [] (* the empty list means no choices, i.e. failure *)
 165         | No _
 166         | NotYetInspected ->
 167               debug_print (lazy ("CURRENT GOAL = " ^ CicPp.ppterm ty));
 168               debug_print (lazy ("CURRENT PROOF = " ^ CicPp.ppterm p));
 169               debug_print (lazy ("CURRENT HYP = " ^ CicPp.ppcontext ey));
 170             let sign, new_sign =
 171               if is_meta_closed then
 172                 None, Some (MetadataConstraints.signature_of ty)
 173               else sign,sign in (* maybe the union ? *)
 174             let local_choices =
 175               new_search_theorems
 176                 search_theorems_in_context dbd
 177                 proof goal (depth-1) new_sign in
 178             let global_choices =
 179               new_search_theorems
 180                 (fun status ->
 181                    List.map snd
 182                    (new_experimental_hint
 183                       ~dbd ~facts:facts ?signature:sign ~universe status))
 184                 dbd proof goal (depth-1) new_sign in
 185             let all_choices =
 186               local_choices@global_choices in
 187             let sorted_choices =
 188               List.stable_sort
 189                 (fun (_, (_, goals1, _)) (_, (_, goals2, _)) ->
 190                    Pervasives.compare
 191                    (List.length goals1) (List.length goals2))
 192                 all_choices in
 193               (match (auto_new dbd width already_seen_goals universe sorted_choices)
 194                with
 195                    [] ->
 196                      (* no proof has been found; we update the
 197                         hastable *)
 198                      (* if is_meta_closed then *)
 199                        Hashtbl.add inspected_goals ty (No depth);
 200                      []
 201                  | (subst,(proof,[],sign))::tl1 ->
 202                      (* a proof for goal has been found:
 203                         in order to get the proof we apply subst to
 204                         Meta[goal] *)
 205                      if is_meta_closed  then
 206                        begin
 207                          let irl =
 208                            CicMkImplicit.identity_relocation_list_for_metavariable ey in
 209                          let meta_proof =
 210                            subst (Cic.Meta(goal,irl)) in
 211                            Hashtbl.add inspected_goals
 212                              ty (Yes (meta_proof,depth));
 213 (*
 214                            begin
 215                              let cty,_ =
 216                                CicTypeChecker.type_of_aux' metasenv ey meta_proof CicUniv.empty_ugraph
 217                              in
 218                                if not (cty = ty) then
 219                                  begin
 220                                    debug_print (lazy ("ty =  "^CicPp.ppterm ty));
 221                                    debug_print (lazy ("cty =  "^CicPp.ppterm cty));
 222                                    assert false
 223                                  end
 224                                    Hashtbl.add inspected_goals
 225                                    ty (Yes (meta_proof,depth));
 226                            end;
 227 *)
 228                        end;
 229                      (subst,(proof,[],sign))::tl1
 230                  | _ -> assert false)
 231     end
 232
 233 and auto_new dbd width already_seen_goals universe = function
 234   | [] -> []
 235   | (subst,(proof, goals, sign))::tl ->
 236       let _,metasenv,_,_ = proof in
 237       let is_in_metasenv (goal, _) =
 238         try
 239           let (_, ey ,ty) = CicUtil.lookup_meta goal metasenv in
 240           true
 241         with CicUtil.Meta_not_found _ -> false
 242       in
 243       let goals'= List.filter is_in_metasenv goals in
 244         auto_new_aux dbd
 245         width already_seen_goals universe ((subst,(proof, goals', sign))::tl)
 246
 247 and auto_new_aux dbd width already_seen_goals universe = function
 248   | [] -> []
 249   | (subst,(proof, [], sign))::tl -> (subst,(proof, [], sign))::tl
 250   | (subst,(proof, (goal,0)::_, _))::tl ->
 251       auto_new dbd width already_seen_goals universe tl
 252   | (subst,(proof, goals, _))::tl when
 253       (List.length goals) > width ->
 254       auto_new dbd width already_seen_goals universe tl
 255   | (subst,(proof, (goal,depth)::gtl, sign))::tl ->
 256       let _,metasenv,p,_ = proof in
 257       let (_, ey ,ty) = CicUtil.lookup_meta goal metasenv in
 258       match (auto_single dbd proof goal ey ty depth
 259         (width - (List.length gtl)) sign already_seen_goals) universe
 260       with
 261           [] -> auto_new dbd width already_seen_goals universe tl
 262         | (local_subst,(proof,[],sign))::tl1 ->
 263             let new_subst f t = f (subst t) in
 264             let is_meta_closed = CicUtil.is_meta_closed ty in
 265             let all_choices =
 266               if is_meta_closed then
 267                 (new_subst local_subst,(proof,gtl,sign))::tl
 268               else
 269                 let tl2 =
 270                   (List.map
 271                      (function (f,(p,l,s)) -> (new_subst f,(p,l@gtl,s))) tl1)
 272                 in
 273                   (new_subst local_subst,(proof,gtl,sign))::tl2@tl in
 274               auto_new dbd width already_seen_goals universe all_choices
 275         | _ -> assert false
 276  ;;
 277
 278 let default_depth = 5
 279 let default_width = 3
 280
 281 (*
 282 let auto_tac ?(depth=default_depth) ?(width=default_width) ~(dbd:HMysql.dbd)
 283   ()
 284 =
 285   let auto_tac dbd (proof,goal) =
 286   let universe = MetadataQuery.signature_of_goal ~dbd (proof,goal) in
 287   Hashtbl.clear inspected_goals;
 288   debug_print (lazy "Entro in Auto");
 289   let id t = t in
 290   let t1 = Unix.gettimeofday () in
 291   match auto_new dbd width [] universe [id,(proof, [(goal,depth)],None)] with
 292       [] ->  debug_print (lazy "Auto failed");
 293         raise (ProofEngineTypes.Fail "No Applicable theorem")
 294     | (_,(proof,[],_))::_ ->
 295         let t2 = Unix.gettimeofday () in
 296         debug_print (lazy "AUTO_TAC HA FINITO");
 297         let _,_,p,_ = proof in
 298         debug_print (lazy (CicPp.ppterm p));
 299         Printf.printf "tempo: %.9f\n" (t2 -. t1);
 300         (proof,[])
 301     | _ -> assert false
 302   in
 303   ProofEngineTypes.mk_tactic (auto_tac dbd)
 304 ;;
 305 *)
 306
 307 let paramodulation_tactic = ref
 308   (fun dbd ?full ?depth ?width status ->
 309      raise (ProofEngineTypes.Fail (lazy "Not Ready yet...")));;
 310
 311 let term_is_equality = ref
 312   (fun term -> debug_print (lazy "term_is_equality E` DUMMY!!!!"); false);;
 313
 314
 315 let auto_tac ?(depth=default_depth) ?(width=default_width) ?paramodulation
 316     ?full ~(dbd:HMysql.dbd) () =
 317   let auto_tac dbd (proof, goal) =
 318     let normal_auto () =
 319       let universe = MetadataQuery.signature_of_goal ~dbd (proof, goal) in
 320       Hashtbl.clear inspected_goals;
 321       debug_print (lazy "Entro in Auto");
 322       let id t = t in
 323       let t1 = Unix.gettimeofday () in
 324       match
 325         auto_new dbd width [] universe [id, (proof, [(goal, depth)], None)]
 326       with
 327         [] ->  debug_print(lazy "Auto failed");
 328           raise (ProofEngineTypes.Fail (lazy "No Applicable theorem"))
 329       | (_,(proof,[],_))::_ ->
 330           let t2 = Unix.gettimeofday () in
 331           debug_print (lazy "AUTO_TAC HA FINITO");
 332           let _,_,p,_ = proof in
 333           debug_print (lazy (CicPp.ppterm p));
 334           debug_print (lazy (Printf.sprintf "tempo: %.9f\n" (t2 -. t1)));
 335           (proof,[])
 336       | _ -> assert false
 337     in
 338     let full = match full with None -> false | Some _ -> true in
 339     let paramodulation_ok =
 340       match paramodulation with
 341       | None -> false
 342       | Some _ ->
 343           let _, metasenv, _, _ = proof in
 344           let _, _, meta_goal = CicUtil.lookup_meta goal metasenv in
 345           full || (!term_is_equality meta_goal)
 346     in
 347     if paramodulation_ok then (
 348       debug_print (lazy "USO PARAMODULATION...");
 349 (*       try *)
 350       !paramodulation_tactic dbd ~depth ~width ~full (proof, goal)
 351 (*       with ProofEngineTypes.Fail _ -> *)
 352 (*         normal_auto () *)
 353     ) else
 354       normal_auto ()
 355   in
 356   ProofEngineTypes.mk_tactic (auto_tac dbd)
 357 ;;