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 = fun _ -> ()
  27
  28 (* Da rimuovere, solo per debug*)
  29 let print_context ctx =
  30     let print_name =
  31      function
  32         Cic.Name n -> n
  33       | Cic.Anonymous -> "_"
  34     in
  35      List.fold_right
  36       (fun i (output,context) ->
  37         let (newoutput,context') =
  38          match i with
  39             Some (n,Cic.Decl t) ->
  40               print_name n ^ ":" ^ CicPp.pp t context ^ "\n", (Some n)::context
  41           | Some (n,Cic.Def (t,None)) ->
  42               print_name n ^ ":=" ^ CicPp.pp t context ^ "\n", (Some n)::context
  43           | None ->
  44               "_ ?= _\n", None::context
  45           | Some (_,Cic.Def (_,Some _)) -> assert false
  46         in
  47          output^newoutput,context'
  48       ) ctx ("",[])
  49   ;;
  50
  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           try
  66             Some (PET.apply_tactic
  67                     (PT.apply_tac ~term:(C.Rel n)) status )
  68           with
  69             PET.Fail _ -> None in
  70         (match res with
  71           Some res -> res::(find (n+1) tl)
  72         | None -> find (n+1) tl)
  73   in
  74   try
  75     find 1 context
  76   with Failure s ->
  77     []
  78 ;;
  79
  80 let depth = 5;;
  81 let width = 3;;
  82
  83 let new_search_theorems f proof goal depth gtl sign =
  84   let choices = f (proof,goal)
  85   in
  86   List.map
  87     (function (proof, goallist) ->
  88        (proof,(List.map (function g -> (g,depth)) goallist)@gtl, sign))
  89     choices
  90 ;;
  91
  92 exception NoOtherChoices;;
  93 let rec auto dbd = function
  94     [] -> []
  95   | (proof, [], sign)::tl -> (proof, [], sign)::tl
  96   | (proof, (goal,0)::_, _)::tl -> auto dbd tl
  97   | (proof, (((goal,depth)::gtl) as allg), sign)::tl ->
  98       (* first we check if the metavariable has not been already
  99          closed as a side effect by some other application *)
 100       let facts = (depth = 1) in
 101       let name,metasenv,p,statement = proof in
 102       let meta_inf =
 103         (try
 104            let (_, ey ,ty) = CicUtil.lookup_meta goal metasenv in
 105              Some (ey, ty)
 106          with _ -> None) in
 107       match meta_inf with
 108           Some (ey, ty) ->
 109             (* the goal is still there *)
 110             (*
 111             debug_print ("CURRENT GOAL = " ^ (CicPp.ppterm ty));
 112             debug_print ("CURRENT PROOF = " ^ (CicPp.ppterm p));
 113             debug_print ("CURRENT HYP = " ^ (fst (print_context ey)));
 114             *)
 115             (* if the goal contains metavariables we use the input
 116                signature for at_most constraints *)
 117             let is_meta_closed = CicUtil.is_meta_closed ty in
 118             let sign, new_sign =
 119               if is_meta_closed then
 120                 None, Some (MetadataConstraints.signature_of ty)
 121               else sign,sign in (* maybe the union ? *)
 122             let local_choices =
 123               new_search_theorems
 124                 search_theorems_in_context
 125                 proof goal (depth-1) [] new_sign in
 126             let global_choices =
 127               new_search_theorems
 128                 (fun status ->
 129                    List.map snd
 130                    (MetadataQuery.hint
 131                       ~dbd ~facts:facts ?signature:sign status))
 132                 proof goal (depth-1) [] new_sign in
 133             (* we proceed depth-first on the current goal. This is
 134                a MAJOR optimization, since in case of success, and
 135                if the goal is meta_closed, we may just drop the alternatives
 136                tl1, avoiding useless backtracking. *)
 137             let all_choices =
 138               local_choices@global_choices in
 139               (match (auto dbd all_choices)
 140                with
 141                    [] -> auto dbd tl
 142                  | (proof,[],_)::tl1 ->
 143                      let all_choices =
 144                        let gtl' = List.map fst gtl in
 145                          if (gtl = [] || is_meta_closed) then
 146                            (proof,gtl,sign)::tl
 147                          else
 148                            let tl2 =
 149                              (List.map
 150                                 (function (p,l,s) -> (p,l@gtl,s)) tl1)
 151                            in
 152                              (proof,gtl,sign)::tl2@tl in
 153                        auto dbd all_choices
 154                  | _ -> assert false)
 155         | None -> auto dbd ((proof,gtl,sign)::tl)
 156 ;;
 157
 158
 159 let auto_tac  ?num ~(dbd:Mysql.dbd) =
 160   let auto_tac dbh (proof,goal) =
 161   debug_print "Entro in Auto";
 162   match (auto dbd [(proof, [(goal,depth)],None)]) with
 163       [] ->  debug_print("Auto failed");
 164         raise (ProofEngineTypes.Fail "No Applicable theorem")
 165     | (proof,[],_)::_ ->
 166         debug_print "AUTO_TAC HA FINITO";
 167         (proof,[])
 168     | _ -> assert false
 169   in
 170   ProofEngineTypes.mk_tactic (auto_tac dbd)
 171 ;;
 172
 173
 174 (************************** EXPERIMENTAL VERSION ****************************)
 175
 176 (* In this versions of auto_tac we maintain an hash table of all inspected
 177    goals. We assume that the context is invariant for application.
 178    To this aim, it is essential to sall hint_verbose, that in turns calls
 179    apply_verbose. *)
 180
 181
 182
 183 type exitus =
 184     No of int
 185   | Yes of Cic.term * int
 186   | NotYetInspected
 187
 188 let inspected_goals = Hashtbl.create 503;;
 189
 190 let search_theorems_in_context status =
 191   let (proof, goal) = status in
 192   let module C = Cic in
 193   let module R = CicReduction in
 194   let module S = CicSubstitution in
 195   let module PET = ProofEngineTypes in
 196   let module PT = PrimitiveTactics in
 197   let _,metasenv,_,_ = proof in
 198   let _,context,ty = CicUtil.lookup_meta goal metasenv in
 199   let rec find n = function
 200       [] -> []
 201     | hd::tl ->
 202         let res =
 203           try
 204             let (subst,(proof, goal_list)) =
 205               PT.apply_tac_verbose ~term:(C.Rel n) status  in
 206             (*
 207             let goal_list =
 208               List.stable_sort (compare_goal_list proof) goal_list in
 209             *)
 210             Some (subst,(proof, goal_list))
 211           with
 212             PET.Fail _ -> None in
 213         (match res with
 214           Some res -> res::(find (n+1) tl)
 215         | None -> find (n+1) tl)
 216   in
 217   try
 218     find 1 context
 219   with Failure s ->
 220     []
 221 ;;
 222
 223 (** splits a list of goals in three groups: closed propositional goals,
 224   open propositional goals and non proposotional goals *)
 225
 226 let split proof l =
 227   let _,metasenv,_,_ = proof in
 228   List.fold_left
 229     (fun (c,o,z,n) g ->
 230        try
 231          let (_, ey, ty) = CicUtil.lookup_meta g metasenv in
 232          let ty_sort,u =
 233            CicTypeChecker.type_of_aux' metasenv ey ty CicUniv.empty_ugraph in
 234          let b,_ =
 235            CicReduction.are_convertible ey (Cic.Sort Cic.Prop) ty_sort u in
 236            if b then
 237              (if CicUtil.is_meta_closed ty then
 238                 (g::c,o,z,n)
 239               else
 240                 (c,g::o,z,n))
 241            else (c,o,z,g::n)
 242        with
 243            CicUtil.Meta_not_found _ -> (c,o,g::z,n)
 244     )
 245     ([],[],[],[]) l
 246 ;;
 247
 248 let my_weight dbd sign proof g =
 249   let res =
 250     search_theorems_in_context (proof,g) in
 251    (* @
 252     (List.map snd (MetadataQuery.experimental_hint
 253       ~dbd ~facts:false ?signature:sign (proof,g))) in *)
 254   List.fold_left
 255     (fun n (_,(_,l)) -> n+(List.length l)+1)
 256     0 res
 257 ;;
 258
 259 let  add_weight dbd sign proof =
 260   List.map (function g -> (g,my_weight dbd sign proof g))
 261
 262 ;;
 263
 264
 265 (* let reorder_goals dbd sign proof goals =
 266   List.rev goals *)
 267
 268 (* let reorder_goals dbd sign proof goals =
 269   let (c,o,z,n) = split proof goals
 270   in c@o@n@z *)
 271
 272 let reorder_goals dbd sign proof goals =
 273   let (c,o,z,n) = split proof goals in
 274     match o with
 275         [] -> c@n@z
 276       | [g] ->c@[g]@n@z
 277       | l ->
 278           let l' = add_weight dbd sign proof l in
 279           c@(List.map fst (List.sort (fun (_,x) (_,y) -> x - y) l'))@n@z
 280
 281 let compare_goals proof goal1 goal2 =
 282   let _,metasenv,_,_ = proof in
 283   let (_, ey1, ty1) = CicUtil.lookup_meta goal1 metasenv in
 284   let (_, ey2, ty2) =  CicUtil.lookup_meta goal2 metasenv in
 285   let ty_sort1,_ = CicTypeChecker.type_of_aux' metasenv ey1 ty1
 286                      CicUniv.empty_ugraph in
 287   let ty_sort2,_ = CicTypeChecker.type_of_aux' metasenv ey2 ty2
 288                      CicUniv.empty_ugraph in
 289   let prop1 =
 290     let b,_ = CicReduction.are_convertible ey1 (Cic.Sort Cic.Prop) ty_sort1
 291                 CicUniv.empty_ugraph in
 292       if b then 0 else 1
 293   in
 294   let prop2 =
 295     let b,_ = CicReduction.are_convertible ey2 (Cic.Sort Cic.Prop) ty_sort2
 296                 CicUniv.empty_ugraph in
 297       if b then 0 else 1
 298   in
 299   prop1 - prop2
 300
 301
 302 let new_search_theorems f dbd proof goal depth sign =
 303   let choices = f (proof,goal)
 304   in
 305   List.map
 306     (function (subst,(proof, goallist)) ->
 307        (* let goallist = reorder_goals dbd sign proof goallist in *)
 308         let goallist = List.sort (compare_goals proof) goallist in
 309        (subst,(proof,(List.map (function g -> (g,depth)) goallist), sign)))
 310     choices
 311 ;;
 312
 313 exception NoOtherChoices;;
 314
 315 let is_in_metasenv goal metasenv =
 316   try
 317     let (_, ey ,ty) =
 318       CicUtil.lookup_meta goal metasenv in
 319       true
 320   with _ -> false
 321
 322 let rec auto_single dbd proof goal ey ty depth width sign already_seen_goals
 323   =
 324   if depth = 0 then [] else
 325   if List.mem ty already_seen_goals then [] else
 326   let already_seen_goals = ty::already_seen_goals in
 327   let facts = (depth = 1) in
 328   let _,metasenv,p,_ = proof in
 329     (* first of all we check if the goal has been already
 330        inspected *)
 331   assert (is_in_metasenv goal metasenv);
 332   let exitus =
 333     try Hashtbl.find inspected_goals ty
 334     with Not_found -> NotYetInspected in
 335   let is_meta_closed = CicUtil.is_meta_closed ty in
 336     begin
 337       match exitus with
 338           Yes (bo,_) ->
 339             (*
 340               debug_print "ALREADY PROVED!!!!!!!!!!!!!!!!!!!!!!!!!!!!";
 341               debug_print (CicPp.ppterm ty);
 342             *)
 343             let subst_in =
 344               (* if we just apply the subtitution, the type
 345                  is irrelevant: we may use Implicit, since it will
 346                  be dropped *)
 347               CicMetaSubst.apply_subst
 348                 [(goal,(ey, bo, Cic.Implicit None))] in
 349             let (proof,_) =
 350               ProofEngineHelpers.subst_meta_and_metasenv_in_proof
 351                 proof goal subst_in metasenv in
 352               [(subst_in,(proof,[],sign))]
 353         | No d when (d >= depth) ->
 354             (* debug_print "PRUNED!!!!!!!!!!!!!!!!!!!!!!!!!!!!"; *)
 355             [] (* the empty list means no choices, i.e. failure *)
 356         | No _
 357         | NotYetInspected ->
 358              (*
 359               debug_print ("CURRENT GOAL = " ^ (CicPp.ppterm ty));
 360               debug_print ("CURRENT PROOF = " ^ (CicPp.ppterm p));
 361               debug_print ("CURRENT HYP = " ^ (fst (print_context ey)));
 362              *)
 363             let sign, new_sign =
 364               if is_meta_closed then
 365                 None, Some (MetadataConstraints.signature_of ty)
 366               else sign,sign in (* maybe the union ? *)
 367             let local_choices =
 368               new_search_theorems
 369                 search_theorems_in_context dbd
 370                 proof goal (depth-1) new_sign in
 371             let global_choices = [] in
 372 (*
 373               new_search_theorems
 374                 (fun status ->
 375                    List.map snd
 376                    (MetadataQuery.experimental_hint
 377                       ~dbd ~facts:facts ?signature:sign status))
 378                 dbd proof goal (depth-1) new_sign in *)
 379             let all_choices =
 380               local_choices@global_choices in
 381             let sorted_choices =
 382               List.stable_sort
 383                 (fun (_, (_, goals1, _)) (_, (_, goals2, _)) ->
 384                    Pervasives.compare
 385                    (List.length goals1) (List.length goals2))
 386                 all_choices in
 387               (match (auto_new dbd width already_seen_goals sorted_choices)
 388                with
 389                    [] ->
 390                      (* no proof has been found; we update the
 391                         hastable *)
 392                      (* if is_meta_closed then *)
 393                        Hashtbl.add inspected_goals ty (No depth);
 394                      []
 395                  | (subst,(proof,[],sign))::tl1 ->
 396                      (* a proof for goal has been found:
 397                         in order to get the proof we apply subst to
 398                         Meta[goal] *)
 399                      if is_meta_closed  then
 400                        begin
 401                          let irl =
 402                            CicMkImplicit.identity_relocation_list_for_metavariable ey in
 403                          let meta_proof =
 404                            subst (Cic.Meta(goal,irl)) in
 405                            Hashtbl.add inspected_goals
 406                              ty (Yes (meta_proof,depth));
 407 (*
 408                            begin
 409                              let cty,_ =
 410                                CicTypeChecker.type_of_aux' metasenv ey meta_proof CicUniv.empty_ugraph
 411                              in
 412                                if not (cty = ty) then
 413                                  begin
 414                                    debug_print ("ty =  "^CicPp.ppterm ty);
 415                                    debug_print ("cty =  "^CicPp.ppterm cty);
 416                                    assert false
 417                                  end
 418                                    Hashtbl.add inspected_goals
 419                                    ty (Yes (meta_proof,depth));
 420                            end;
 421 *)
 422                        end;
 423                      (subst,(proof,[],sign))::tl1
 424                  | _ -> assert false)
 425     end
 426
 427 and auto_new dbd width already_seen_goals = function
 428     [] -> []
 429   | (subst,(proof, goals, sign))::tl ->
 430       let _,metasenv,_,_ = proof in
 431       let is_in_metasenv (goal, _) =
 432         try
 433           let (_, ey ,ty) =
 434             CicUtil.lookup_meta goal metasenv in
 435             true
 436         with _ -> false in
 437       let goals'= List.filter is_in_metasenv goals in
 438         auto_new_aux dbd width already_seen_goals
 439           ((subst,(proof, goals', sign))::tl)
 440
 441 and auto_new_aux dbd width already_seen_goals = function
 442   [] -> []
 443   | (subst,(proof, [], sign))::tl -> (subst,(proof, [], sign))::tl
 444   | (subst,(proof, (goal,0)::_, _))::tl ->
 445       auto_new dbd width already_seen_goals tl
 446   | (subst,(proof, goals, _))::tl when
 447       (List.length goals) > width+1 ->
 448       auto_new dbd width already_seen_goals tl
 449   | (subst,(proof, (goal,depth)::gtl, sign))::tl ->
 450       let maxdepthgoals,othergoals =
 451         let rec aux acc =
 452           function
 453               (g,d)::l when d=depth -> aux (g::acc) l
 454             |l -> (acc,l) in
 455           aux [goal] gtl in
 456       let _,metasenv,p,_ = proof in
 457       let len1 = List.length maxdepthgoals in
 458       let maxdepthgoals = reorder_goals dbd sign proof maxdepthgoals in
 459       let len2 = List.length maxdepthgoals in
 460         match maxdepthgoals with
 461           [] -> debug_print
 462             ("caso sospetto " ^ (string_of_int (List.length othergoals)) ^ " " ^ string_of_int depth);
 463             auto_new dbd
 464               width already_seen_goals((subst,(proof, othergoals, sign))::tl)
 465         | goal::tgs ->
 466             let  gtl = (List.map (fun x->(x,depth)) tgs)@othergoals in
 467               begin
 468       let meta_inf =
 469         try
 470           let (_, ey ,ty) =
 471             CicUtil.lookup_meta goal metasenv in
 472             Some (ey,ty)
 473         with _ -> None
 474       in
 475         match meta_inf with
 476           | Some (ey,ty) ->
 477             begin
 478             match (auto_single dbd proof goal ey ty depth
 479         (width - (List.length gtl) - (len1-len2)) sign already_seen_goals)
 480                 with
 481                     [] -> auto_new dbd width already_seen_goals tl
 482                   | (local_subst,(proof,[],sign))::tl1 ->
 483                       let new_subst f t = f (subst t) in
 484                       let is_meta_closed = CicUtil.is_meta_closed ty in
 485                       let all_choices =
 486                         if is_meta_closed then
 487                           (new_subst local_subst,(proof,gtl,sign))::tl
 488                         else
 489                           let tl2 =
 490                             (List.map
 491                                (function (f,(p,l,s)) -> (new_subst f,(p,l@gtl,s))) tl1)
 492                           in
 493                             (new_subst local_subst,(proof,gtl,sign))::tl2@tl in
 494                         auto_new dbd width already_seen_goals all_choices
 495                   | _ -> assert false
 496             end
 497           | None -> debug_print "caso none";
 498               auto_new
 499                 dbd width already_seen_goals ((subst,(proof, gtl, sign))::tl)
 500               end
 501 ;;
 502
 503
 504 let auto_tac_new  ~(dbd:Mysql.dbd) =
 505   let auto_tac dbd (proof,goal) =
 506   Hashtbl.clear inspected_goals;
 507   debug_print "Entro in Auto";
 508   let id t = t in
 509   match (auto_new dbd width [] [id,(proof, [(goal,depth)],None)]) with
 510       [] ->  debug_print("Auto failed");
 511         raise (ProofEngineTypes.Fail "No Applicable theorem")
 512     | (_,(proof,[],_))::_ ->
 513         debug_print "AUTO_TAC HA FINITO";
 514         let _,_,p,_ = proof in
 515         debug_print (CicPp.ppterm p);
 516         (proof,[])
 517     | _ -> assert false
 518   in
 519   ProofEngineTypes.mk_tactic (auto_tac dbd)
 520 ;;
 521
 522