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 params =
 318     try int_of_string (List.assoc name params) with
 319     | Not_found -> default_depth
 320     | Failure _ ->
 321         raise (ProofEngineTypes.Fail (lazy (name ^ " must be an integer")))
 322 ;;
 323
 324 let auto_tac ~params ~(dbd:HMysql.dbd) =
 325   (* argument parsing *)
 326   let depth = int "depth" params in
 327   let width = int "width" params in
 328   let paramodulation = bool "paramodulation" params in
 329   let full = bool "full" params in
 330   let superposition = bool "superposition" params in
 331   let target = string "target" params in
 332   let table = string "table" params in
 333   let subterms_only = bool "subterms_only" params in
 334   let caso_strano = bool "caso_strano" params in
 335   let demod_table = string "demod_table" params in
 336   (* the real tactic *)
 337   let auto_tac dbd (proof, goal) =
 338     let normal_auto () =
 339       let universe = MetadataQuery.signature_of_goal ~dbd (proof, goal) in
 340       Hashtbl.clear inspected_goals;
 341       debug_print (lazy "Entro in Auto");
 342       let id t = t in
 343       let t1 = Unix.gettimeofday () in
 344       match
 345         auto_new dbd width [] universe [id, (proof, [(goal, depth)], None)]
 346       with
 347         [] ->  debug_print(lazy "Auto failed");
 348           raise (ProofEngineTypes.Fail (lazy "No Applicable theorem"))
 349       | (_,(proof,[],_))::_ ->
 350           let t2 = Unix.gettimeofday () in
 351           debug_print (lazy "AUTO_TAC HA FINITO");
 352           let _,_,p,_ = proof in
 353           debug_print (lazy (CicPp.ppterm p));
 354           debug_print (lazy (Printf.sprintf "tempo: %.9f\n" (t2 -. t1)));
 355           (proof,[])
 356       | _ -> assert false
 357     in
 358     let paramodulation_ok =
 359       let _, metasenv, _, _ = proof in
 360       let _, _, meta_goal = CicUtil.lookup_meta goal metasenv in
 361       paramodulation && (full || (Equality.term_is_equality meta_goal))
 362     in
 363     if paramodulation_ok then (
 364       debug_print (lazy "USO PARAMODULATION...");
 365 (*       try *)
 366       try
 367         let rc = Saturation.saturate caso_strano dbd ~depth ~width ~full (proof, goal) in
 368         prerr_endline (Saturation.get_stats ());
 369         rc
 370       with exn ->
 371         prerr_endline (Saturation.get_stats ());
 372         raise exn
 373
 374 (*       with ProofEngineTypes.Fail _ -> *)
 375 (*         normal_auto () *)
 376     ) else
 377       normal_auto ()
 378   in
 379   match superposition with
 380   | true ->
 381       ProofEngineTypes.mk_tactic
 382        (Saturation.superposition_tac ~target ~table ~subterms_only ~demod_table)
 383   | _ -> ProofEngineTypes.mk_tactic (auto_tac dbd)
 384 ;;
 385
 386 (********************** applyS *******************)
 387
 388 let new_metasenv_and_unify_and_t dbd proof goal newmeta' metasenv' context term' ty termty goal_arity =
 389  let (consthead,newmetasenv,arguments,_) =
 390    ProofEngineHelpers.saturate_term newmeta' metasenv' context termty goal_arity in
 391  let term'' = match arguments with [] -> term' | _ -> Cic.Appl (term'::arguments) in
 392   let proof',metasenv =
 393    let (puri,metasenv,pbo,pty) = proof in
 394     (puri,newmetasenv,pbo,pty),metasenv
 395   in
 396    let proof'',goals =
 397     match LibraryObjects.eq_URI () with
 398     | Some uri ->
 399             ProofEngineTypes.apply_tactic
 400              (Tacticals.then_
 401                ~start:(PrimitiveTactics.letin_tac term''(*Tacticals.id_tac*))
 402                ~continuation:
 403                  (PrimitiveTactics.cut_tac
 404                    (CicSubstitution.lift 1
 405                     (Cic.Appl
 406                      [Cic.MutInd (uri,0,[]);
 407                       Cic.Sort Cic.Prop;
 408                       consthead;
 409                       ty])))) (proof',goal)
 410    | None -> raise (ProofEngineTypes.Fail (lazy "No equality defined"))
 411     in
 412      match goals with
 413         [g1;g2] ->
 414           let proof'',goals =
 415            ProofEngineTypes.apply_tactic
 416            (auto_tac ~params:["caso_strano","on";"paramodulation","on"] ~dbd) (proof'',g2)
 417           in
 418            let proof'',goals =
 419             ProofEngineTypes.apply_tactic
 420              (Tacticals.then_
 421               ~start:(EqualityTactics.rewrite_tac ~direction:`RightToLeft
 422                 ~pattern:(ProofEngineTypes.conclusion_pattern None) (Cic.Rel 1))
 423               ~continuation:(PrimitiveTactics.apply_tac (Cic.Rel 2))
 424              ) (proof'',g1)
 425            in
 426             proof'',
 427              (*CSC: Brrrr.... *)
 428              ProofEngineHelpers.compare_metasenvs ~oldmetasenv:metasenv
 429               ~newmetasenv:(let _,m,_,_ = proof'' in m)
 430       | _ -> assert false
 431
 432 let rec count_prods context ty =
 433  match CicReduction.whd context ty with
 434     Cic.Prod (n,s,t) -> 1 + count_prods (Some (n,Cic.Decl s)::context) t
 435   | _ -> 0
 436
 437 let applyS_tac ~dbd ~term (proof, goal) =
 438  let module T = CicTypeChecker in
 439  let module R = CicReduction in
 440  let module C = Cic in
 441   let (_,metasenv,_,_) = proof in
 442   let metano,context,ty = CicUtil.lookup_meta goal metasenv in
 443   let newmeta = ProofEngineHelpers.new_meta_of_proof ~proof in
 444    let exp_named_subst_diff,newmeta',newmetasenvfragment,term' =
 445     match term with
 446        C.Var (uri,exp_named_subst) ->
 447         let newmeta',newmetasenvfragment,exp_named_subst',exp_named_subst_diff =
 448          PrimitiveTactics.generalize_exp_named_subst_with_fresh_metas context newmeta uri
 449           exp_named_subst
 450         in
 451          exp_named_subst_diff,newmeta',newmetasenvfragment,
 452           C.Var (uri,exp_named_subst')
 453      | C.Const (uri,exp_named_subst) ->
 454         let newmeta',newmetasenvfragment,exp_named_subst',exp_named_subst_diff =
 455          PrimitiveTactics.generalize_exp_named_subst_with_fresh_metas context newmeta uri
 456           exp_named_subst
 457         in
 458          exp_named_subst_diff,newmeta',newmetasenvfragment,
 459           C.Const (uri,exp_named_subst')
 460      | C.MutInd (uri,tyno,exp_named_subst) ->
 461         let newmeta',newmetasenvfragment,exp_named_subst',exp_named_subst_diff =
 462          PrimitiveTactics.generalize_exp_named_subst_with_fresh_metas context newmeta uri
 463           exp_named_subst
 464         in
 465          exp_named_subst_diff,newmeta',newmetasenvfragment,
 466           C.MutInd (uri,tyno,exp_named_subst')
 467      | C.MutConstruct (uri,tyno,consno,exp_named_subst) ->
 468         let newmeta',newmetasenvfragment,exp_named_subst',exp_named_subst_diff =
 469          PrimitiveTactics.generalize_exp_named_subst_with_fresh_metas context newmeta uri
 470           exp_named_subst
 471         in
 472          exp_named_subst_diff,newmeta',newmetasenvfragment,
 473           C.MutConstruct (uri,tyno,consno,exp_named_subst')
 474      | _ -> [],newmeta,[],term
 475    in
 476    let metasenv' = metasenv@newmetasenvfragment in
 477    let termty,_ =
 478      CicTypeChecker.type_of_aux' metasenv' context term' CicUniv.empty_ugraph
 479    in
 480    let termty =
 481      CicSubstitution.subst_vars exp_named_subst_diff termty in
 482    let goal_arity = count_prods context ty in
 483    let res =
 484     new_metasenv_and_unify_and_t dbd proof goal
 485      newmeta' metasenv' context term' ty termty goal_arity
 486    in
 487     res
 488
 489 let applyS_tac ~dbd ~term =
 490  ProofEngineTypes.mk_tactic
 491   (fun status ->
 492     try applyS_tac ~dbd ~term status
 493     with
 494     | CicUnification.UnificationFailure msg
 495     | CicTypeChecker.TypeCheckerFailure msg ->
 496         raise (ProofEngineTypes.Fail msg))