src/HOL/Tools/Sledgehammer/sledgehammer_provers.ML
changeset 41242 8edeb1dbbc76
parent 41241 7d07736aaaf6
child 41256 0e7d45cc005f
equal deleted inserted replaced
41241:7d07736aaaf6 41242:8edeb1dbbc76
    31      expect: string}
    31      expect: string}
    32 
    32 
    33   datatype prover_fact =
    33   datatype prover_fact =
    34     Untranslated_Fact of (string * locality) * thm |
    34     Untranslated_Fact of (string * locality) * thm |
    35     ATP_Translated_Fact of
    35     ATP_Translated_Fact of
    36       translated_formula option * ((string * locality) * thm)
    36       translated_formula option * ((string * locality) * thm) |
       
    37     SMT_Weighted_Fact of (string * locality) * (int option * thm)
    37 
    38 
    38   type prover_problem =
    39   type prover_problem =
    39     {state: Proof.state,
    40     {state: Proof.state,
    40      goal: thm,
    41      goal: thm,
    41      subgoal: int,
    42      subgoal: int,
    42      subgoal_count: int,
    43      subgoal_count: int,
    43      facts: prover_fact list}
    44      facts: prover_fact list,
       
    45      smt_head: (string * locality) SMT_Solver.smt_filter_head_result option}
    44 
    46 
    45   type prover_result =
    47   type prover_result =
    46     {outcome: failure option,
    48     {outcome: failure option,
    47      used_facts: (string * locality) list,
    49      used_facts: (string * locality) list,
    48      run_time_in_msecs: int option,
    50      run_time_in_msecs: int option,
    54   val smt_max_iters : int Unsynchronized.ref
    56   val smt_max_iters : int Unsynchronized.ref
    55   val smt_iter_fact_frac : real Unsynchronized.ref
    57   val smt_iter_fact_frac : real Unsynchronized.ref
    56   val smt_iter_time_frac : real Unsynchronized.ref
    58   val smt_iter_time_frac : real Unsynchronized.ref
    57   val smt_iter_min_msecs : int Unsynchronized.ref
    59   val smt_iter_min_msecs : int Unsynchronized.ref
    58   val smt_monomorph_limit : int Unsynchronized.ref
    60   val smt_monomorph_limit : int Unsynchronized.ref
    59   val smt_weights : bool Unsynchronized.ref
       
    60   val smt_min_weight : int Unsynchronized.ref
       
    61   val smt_max_weight : int Unsynchronized.ref
       
    62   val smt_max_index : int Unsynchronized.ref
       
    63   val smt_weight_curve : (int -> int) Unsynchronized.ref
       
    64 
    61 
    65   val das_Tool : string
    62   val das_Tool : string
       
    63   val select_smt_solver : string -> Proof.context -> Proof.context
    66   val is_smt_prover : Proof.context -> string -> bool
    64   val is_smt_prover : Proof.context -> string -> bool
    67   val is_prover_available : Proof.context -> string -> bool
    65   val is_prover_available : Proof.context -> string -> bool
    68   val is_prover_installed : Proof.context -> string -> bool
    66   val is_prover_installed : Proof.context -> string -> bool
    69   val default_max_relevant_for_prover : Proof.context -> string -> int
    67   val default_max_relevant_for_prover : Proof.context -> string -> int
    70   val is_built_in_const_for_prover :
    68   val is_built_in_const_for_prover :
    74   val relevance_fudge_for_prover : Proof.context -> string -> relevance_fudge
    72   val relevance_fudge_for_prover : Proof.context -> string -> relevance_fudge
    75   val dest_dir : string Config.T
    73   val dest_dir : string Config.T
    76   val problem_prefix : string Config.T
    74   val problem_prefix : string Config.T
    77   val measure_run_time : bool Config.T
    75   val measure_run_time : bool Config.T
    78   val untranslated_fact : prover_fact -> (string * locality) * thm
    76   val untranslated_fact : prover_fact -> (string * locality) * thm
       
    77   val smt_weighted_fact :
       
    78     prover_fact -> (string * locality) * (int option * thm)
    79   val available_provers : Proof.context -> unit
    79   val available_provers : Proof.context -> unit
    80   val kill_provers : unit -> unit
    80   val kill_provers : unit -> unit
    81   val running_provers : unit -> unit
    81   val running_provers : unit -> unit
    82   val messages : int option -> unit
    82   val messages : int option -> unit
    83   val get_prover : Proof.context -> bool -> string -> prover
    83   val get_prover : Proof.context -> bool -> string -> prover
   100 
   100 
   101 (* Identifier to distinguish Sledgehammer from other tools using
   101 (* Identifier to distinguish Sledgehammer from other tools using
   102    "Async_Manager". *)
   102    "Async_Manager". *)
   103 val das_Tool = "Sledgehammer"
   103 val das_Tool = "Sledgehammer"
   104 
   104 
       
   105 val unremotify = perhaps (try (unprefix remote_prefix))
       
   106 
       
   107 val select_smt_solver =
       
   108   Context.proof_map o SMT_Config.select_solver o unremotify
       
   109 
   105 fun is_smt_prover ctxt name =
   110 fun is_smt_prover ctxt name =
   106   let val smts = SMT_Solver.available_solvers_of ctxt in
   111   let val smts = SMT_Solver.available_solvers_of ctxt in
   107     case try (unprefix remote_prefix) name of
   112     case try (unprefix remote_prefix) name of
   108       SOME suffix => member (op =) smts suffix andalso
   113       SOME base => member (op =) smts base andalso
   109                      SMT_Solver.is_remotely_available ctxt suffix
   114                    SMT_Solver.is_remotely_available ctxt base
   110     | NONE => member (op =) smts name
   115     | NONE => member (op =) smts name
   111   end
   116   end
   112 
   117 
   113 fun is_prover_available ctxt name =
   118 fun is_prover_available ctxt name =
   114   let val thy = ProofContext.theory_of ctxt in
   119   let val thy = ProofContext.theory_of ctxt in
   131   end
   136   end
   132 
   137 
   133 fun default_max_relevant_for_prover ctxt name =
   138 fun default_max_relevant_for_prover ctxt name =
   134   let val thy = ProofContext.theory_of ctxt in
   139   let val thy = ProofContext.theory_of ctxt in
   135     if is_smt_prover ctxt name then
   140     if is_smt_prover ctxt name then
   136       SMT_Solver.default_max_relevant ctxt
   141       SMT_Solver.default_max_relevant ctxt (unremotify name)
   137           (perhaps (try (unprefix remote_prefix)) name)
       
   138     else
   142     else
   139       #default_max_relevant (get_atp thy name)
   143       #default_max_relevant (get_atp thy name)
   140   end
   144   end
   141 
   145 
   142 (* These are either simplified away by "Meson.presimplify" (most of the time) or
   146 (* These are either simplified away by "Meson.presimplify" (most of the time) or
   144 val atp_irrelevant_consts =
   148 val atp_irrelevant_consts =
   145   [@{const_name False}, @{const_name True}, @{const_name Not},
   149   [@{const_name False}, @{const_name True}, @{const_name Not},
   146    @{const_name conj}, @{const_name disj}, @{const_name implies},
   150    @{const_name conj}, @{const_name disj}, @{const_name implies},
   147    @{const_name HOL.eq}, @{const_name If}, @{const_name Let}]
   151    @{const_name HOL.eq}, @{const_name If}, @{const_name Let}]
   148 
   152 
   149 fun is_built_in_const_for_prover ctxt name (s, T) args =
   153 fun is_built_in_const_for_prover ctxt name =
   150   if is_smt_prover ctxt name then SMT_Builtin.is_builtin_ext ctxt (s, T) args
   154   if is_smt_prover ctxt name then
   151   else member (op =) atp_irrelevant_consts s
   155     ctxt |> select_smt_solver name |> SMT_Builtin.is_builtin_ext
       
   156   else
       
   157     K o member (op =) atp_irrelevant_consts o fst
   152 
   158 
   153 (* FUDGE *)
   159 (* FUDGE *)
   154 val atp_relevance_fudge =
   160 val atp_relevance_fudge =
   155   {allow_ext = true,
   161   {allow_ext = true,
   156    worse_irrel_freq = 100.0,
   162    worse_irrel_freq = 100.0,
   228    timeout: Time.time,
   234    timeout: Time.time,
   229    expect: string}
   235    expect: string}
   230 
   236 
   231 datatype prover_fact =
   237 datatype prover_fact =
   232   Untranslated_Fact of (string * locality) * thm |
   238   Untranslated_Fact of (string * locality) * thm |
   233   ATP_Translated_Fact of translated_formula option * ((string * locality) * thm)
   239   ATP_Translated_Fact of
       
   240     translated_formula option * ((string * locality) * thm) |
       
   241   SMT_Weighted_Fact of (string * locality) * (int option * thm)
   234 
   242 
   235 type prover_problem =
   243 type prover_problem =
   236   {state: Proof.state,
   244   {state: Proof.state,
   237    goal: thm,
   245    goal: thm,
   238    subgoal: int,
   246    subgoal: int,
   239    subgoal_count: int,
   247    subgoal_count: int,
   240    facts: prover_fact list}
   248    facts: prover_fact list,
       
   249    smt_head: (string * locality) SMT_Solver.smt_filter_head_result option}
   241 
   250 
   242 type prover_result =
   251 type prover_result =
   243   {outcome: failure option,
   252   {outcome: failure option,
   244    message: string,
   253    message: string,
   245    used_facts: (string * locality) list,
   254    used_facts: (string * locality) list,
   270 
   279 
   271 (* generic TPTP-based ATPs *)
   280 (* generic TPTP-based ATPs *)
   272 
   281 
   273 fun untranslated_fact (Untranslated_Fact p) = p
   282 fun untranslated_fact (Untranslated_Fact p) = p
   274   | untranslated_fact (ATP_Translated_Fact (_, p)) = p
   283   | untranslated_fact (ATP_Translated_Fact (_, p)) = p
   275 fun atp_translated_fact ctxt (Untranslated_Fact p) = translate_atp_fact ctxt p
   284   | untranslated_fact (SMT_Weighted_Fact (info, (_, th))) = (info, th)
   276   | atp_translated_fact _ (ATP_Translated_Fact q) = q
   285 fun atp_translated_fact _ (ATP_Translated_Fact p) = p
       
   286   | atp_translated_fact ctxt fact =
       
   287     translate_atp_fact ctxt (untranslated_fact fact)
       
   288 fun smt_weighted_fact (SMT_Weighted_Fact p) = p
       
   289   | smt_weighted_fact fact = untranslated_fact fact |> apsnd (pair NONE)
   277 
   290 
   278 fun int_opt_add (SOME m) (SOME n) = SOME (m + n)
   291 fun int_opt_add (SOME m) (SOME n) = SOME (m + n)
   279   | int_opt_add _ _ = NONE
   292   | int_opt_add _ _ = NONE
   280 
   293 
   281 fun overlord_file_location_for_prover prover =
   294 fun overlord_file_location_for_prover prover =
   469 val smt_iter_fact_frac = Unsynchronized.ref 0.5
   482 val smt_iter_fact_frac = Unsynchronized.ref 0.5
   470 val smt_iter_time_frac = Unsynchronized.ref 0.5
   483 val smt_iter_time_frac = Unsynchronized.ref 0.5
   471 val smt_iter_min_msecs = Unsynchronized.ref 5000
   484 val smt_iter_min_msecs = Unsynchronized.ref 5000
   472 val smt_monomorph_limit = Unsynchronized.ref 4
   485 val smt_monomorph_limit = Unsynchronized.ref 4
   473 
   486 
   474 fun smt_filter_loop ({debug, verbose, timeout, ...} : params) remote state i =
   487 fun smt_filter_loop name ({debug, verbose, overlord, timeout, ...} : params)
       
   488                     state i smt_head =
   475   let
   489   let
   476     val ctxt = Proof.context_of state
   490     val ctxt = Proof.context_of state
       
   491     val (remote, base) =
       
   492       case try (unprefix remote_prefix) name of
       
   493         SOME base => (true, base)
       
   494       | NONE => (false, name)
       
   495     val repair_context =
       
   496       select_smt_solver base
       
   497       #> Config.put SMT_Config.verbose debug
       
   498       #> (if overlord then
       
   499             Config.put SMT_Config.debug_files
       
   500                        (overlord_file_location_for_prover name
       
   501                         |> (fn (path, base) => path ^ "/" ^ base))
       
   502           else
       
   503             I)
       
   504       #> Config.put SMT_Config.monomorph_limit (!smt_monomorph_limit)
       
   505     val state = state |> Proof.map_context repair_context
       
   506 
   477     fun iter timeout iter_num outcome0 time_so_far facts =
   507     fun iter timeout iter_num outcome0 time_so_far facts =
   478       let
   508       let
   479         val timer = Timer.startRealTimer ()
   509         val timer = Timer.startRealTimer ()
   480         val ms = timeout |> Time.toMilliseconds
   510         val ms = timeout |> Time.toMilliseconds
   481         val iter_timeout =
   511         val iter_timeout =
   496             ()
   526             ()
   497         val birth = Timer.checkRealTimer timer
   527         val birth = Timer.checkRealTimer timer
   498         val _ =
   528         val _ =
   499           if debug then Output.urgent_message "Invoking SMT solver..." else ()
   529           if debug then Output.urgent_message "Invoking SMT solver..." else ()
   500         val (outcome, used_facts) =
   530         val (outcome, used_facts) =
   501           SMT_Solver.smt_filter_head state facts i
   531           (case (iter_num, smt_head) of
       
   532              (1, SOME head) => head |> apsnd (apfst (apsnd repair_context))
       
   533            | _ => SMT_Solver.smt_filter_head state facts i)
   502           |> SMT_Solver.smt_filter_tail iter_timeout remote
   534           |> SMT_Solver.smt_filter_tail iter_timeout remote
   503           |> (fn {outcome, used_facts} => (outcome, used_facts))
   535           |> (fn {outcome, used_facts} => (outcome, used_facts))
   504           handle exn => if Exn.is_interrupt exn then
   536           handle exn => if Exn.is_interrupt exn then
   505                           reraise exn
   537                           reraise exn
   506                         else
   538                         else
   563 fun can_apply_metis debug state i ths =
   595 fun can_apply_metis debug state i ths =
   564   can_apply smt_metis_timeout
   596   can_apply smt_metis_timeout
   565             (Config.put Metis_Tactics.verbose debug
   597             (Config.put Metis_Tactics.verbose debug
   566              #> (fn ctxt => Metis_Tactics.metis_tac ctxt ths)) state i
   598              #> (fn ctxt => Metis_Tactics.metis_tac ctxt ths)) state i
   567 
   599 
   568 val smt_weights = Unsynchronized.ref true
   600 fun run_smt_solver auto name (params as {debug, verbose, ...}) minimize_command
   569 val smt_weight_min_facts = 20
   601         ({state, subgoal, subgoal_count, facts, smt_head, ...}
   570 
   602          : prover_problem) =
   571 (* FUDGE *)
       
   572 val smt_min_weight = Unsynchronized.ref 0
       
   573 val smt_max_weight = Unsynchronized.ref 10
       
   574 val smt_max_index = Unsynchronized.ref 200
       
   575 val smt_weight_curve = Unsynchronized.ref (fn x : int => x * x)
       
   576 
       
   577 fun smt_fact_weight j num_facts =
       
   578   if !smt_weights andalso num_facts >= smt_weight_min_facts then
       
   579     SOME (!smt_max_weight
       
   580           - (!smt_max_weight - !smt_min_weight + 1)
       
   581             * !smt_weight_curve (Int.max (0, !smt_max_index - j - 1))
       
   582             div !smt_weight_curve (!smt_max_index))
       
   583   else
       
   584     NONE
       
   585 
       
   586 fun run_smt_solver auto name (params as {debug, verbose, overlord, ...})
       
   587         minimize_command
       
   588         ({state, subgoal, subgoal_count, facts, ...} : prover_problem) =
       
   589   let
   603   let
   590     val (remote, suffix) =
   604     val ctxt = Proof.context_of state
   591       case try (unprefix remote_prefix) name of
   605     val facts = facts |> map smt_weighted_fact
   592         SOME suffix => (true, suffix)
       
   593       | NONE => (false, name)
       
   594     val repair_context =
       
   595       Context.proof_map (SMT_Config.select_solver suffix)
       
   596       #> Config.put SMT_Config.verbose debug
       
   597       #> (if overlord then
       
   598             Config.put SMT_Config.debug_files
       
   599                        (overlord_file_location_for_prover name
       
   600                         |> (fn (path, base) => path ^ "/" ^ base))
       
   601           else
       
   602             I)
       
   603       #> Config.put SMT_Config.monomorph_limit (!smt_monomorph_limit)
       
   604     val state = state |> Proof.map_context repair_context
       
   605     val thy = Proof.theory_of state
       
   606     val num_facts = length facts
       
   607     val facts =
       
   608       facts ~~ (0 upto num_facts - 1)
       
   609       |> map (fn (fact, j) =>
       
   610                  fact |> untranslated_fact
       
   611                       |> apsnd (pair (smt_fact_weight j num_facts)
       
   612                                 o Thm.transfer thy))
       
   613     val {outcome, used_facts, run_time_in_msecs} =
   606     val {outcome, used_facts, run_time_in_msecs} =
   614       smt_filter_loop params remote state subgoal facts
   607       smt_filter_loop name params state subgoal smt_head facts
   615     val (chained_lemmas, other_lemmas) = split_used_facts (map fst used_facts)
   608     val (chained_lemmas, other_lemmas) = split_used_facts (map fst used_facts)
   616     val outcome = outcome |> Option.map failure_from_smt_failure
   609     val outcome = outcome |> Option.map failure_from_smt_failure
   617     val message =
   610     val message =
   618       case outcome of
   611       case outcome of
   619         NONE =>
   612         NONE =>
   620         let
   613         let
   621           val (method, settings) =
   614           val (method, settings) =
   622             if can_apply_metis debug state subgoal (map snd used_facts) then
   615             if can_apply_metis debug state subgoal (map snd used_facts) then
   623               ("metis", "")
   616               ("metis", "")
   624             else
   617             else
   625               ("smt", if suffix = SMT_Config.solver_of @{context} then ""
   618               let val base = unremotify name in
   626                       else "smt_solver = " ^ maybe_quote suffix)
   619                 ("smt", if base = SMT_Config.solver_of ctxt then ""
       
   620                         else "smt_solver = " ^ maybe_quote base)
       
   621               end
   627         in
   622         in
   628           try_command_line (proof_banner auto)
   623           try_command_line (proof_banner auto)
   629               (apply_on_subgoal settings subgoal subgoal_count ^
   624               (apply_on_subgoal settings subgoal subgoal_count ^
   630                command_call method (map fst other_lemmas)) ^
   625                command_call method (map fst other_lemmas)) ^
   631           minimize_line minimize_command
   626           minimize_line minimize_command