speed up binary minimizer in practice by preferring the first half of the used facts (which are likelier to be relevant) to the second half
1 (* Title: HOL/Tools/Sledgehammer/sledgehammer_minimize.ML
2 Author: Philipp Meyer, TU Muenchen
3 Author: Jasmin Blanchette, TU Muenchen
5 Minimization of fact list for Metis using external provers.
8 signature SLEDGEHAMMER_MINIMIZE =
10 type locality = ATP_Translate.locality
11 type play = ATP_Reconstruct.play
12 type params = Sledgehammer_Provers.params
14 val binary_min_facts : int Config.T
16 string -> params -> bool -> int -> int -> Proof.state
17 -> ((string * locality) * thm list) list
18 -> ((string * locality) * thm list) list option
19 * ((unit -> play) * (play -> string) * string)
21 params -> int -> (Facts.ref * Attrib.src list) list -> Proof.state -> unit
24 structure Sledgehammer_Minimize : SLEDGEHAMMER_MINIMIZE =
31 open Sledgehammer_Util
32 open Sledgehammer_Filter
33 open Sledgehammer_Provers
35 (* wrapper for calling external prover *)
38 let val n = length names in
39 string_of_int n ^ " fact" ^ plural_s n ^
41 ": " ^ (names |> map fst |> sort_distinct string_ord
47 fun print silent f = if silent then () else Output.urgent_message (f ())
49 fun test_facts ({debug, verbose, overlord, provers, max_mono_iters,
50 max_new_mono_instances, type_enc, isar_proof,
51 isar_shrink_factor, preplay_timeout, ...} : params)
52 silent (prover : prover) timeout i n state facts =
55 print silent (fn () =>
56 "Testing " ^ n_facts (map fst facts) ^
57 (if verbose then " (timeout: " ^ string_from_time timeout ^ ")"
59 val {goal, ...} = Proof.goal state
61 facts |> maps (fn (n, ths) => ths |> map (Untranslated_Fact o pair n))
63 {debug = debug, verbose = verbose, overlord = overlord, blocking = true,
64 provers = provers, type_enc = type_enc, sound = true,
65 relevance_thresholds = (1.01, 1.01), max_relevant = SOME (length facts),
66 max_mono_iters = max_mono_iters,
67 max_new_mono_instances = max_new_mono_instances, isar_proof = isar_proof,
68 isar_shrink_factor = isar_shrink_factor, slicing = false,
69 timeout = timeout, preplay_timeout = preplay_timeout, expect = ""}
71 {state = state, goal = goal, subgoal = i, subgoal_count = n,
72 facts = facts, smt_filter = NONE}
73 val result as {outcome, used_facts, run_time_in_msecs, ...} =
74 prover params (K (K "")) problem
79 SOME failure => string_for_failure failure
82 (if length used_facts = length facts then ""
83 else " with " ^ n_facts used_facts) ^
84 (case run_time_in_msecs of
86 " (" ^ string_from_time (Time.fromMilliseconds ms) ^ ")"
91 (* minimalization of facts *)
93 (* The sublinear algorithm works well in almost all situations, except when the
94 external prover cannot return the list of used facts and hence returns all
95 facts as used. In that case, the binary algorithm is much more appropriate.
96 We can usually detect the situation by looking at the number of used facts
97 reported by the prover. *)
98 val binary_min_facts =
99 Attrib.setup_config_int @{binding sledgehammer_minimize_binary_min_facts}
102 fun sublinear_minimize _ [] p = p
103 | sublinear_minimize test (x :: xs) (seen, result) =
104 case test (xs @ seen) of
105 result as {outcome = NONE, used_facts, ...} : prover_result =>
106 sublinear_minimize test (filter_used_facts used_facts xs)
107 (filter_used_facts used_facts seen, result)
108 | _ => sublinear_minimize test xs (x :: seen, result)
110 fun binary_minimize test xs =
112 fun pred xs = #outcome (test xs : prover_result) = NONE
113 fun min _ _ [] = raise Empty
114 | min _ _ [s0] = [s0]
117 val (l0, r0) = chop ((length xs + 1) div 2) xs
119 val _ = warning (replicate_string depth " " ^ "{ " ^
120 "sup: " ^ n_facts (map fst sup))
121 val _ = warning (replicate_string depth " " ^ " " ^
122 "xs: " ^ n_facts (map fst xs))
123 val _ = warning (replicate_string depth " " ^ " " ^
124 "l0: " ^ n_facts (map fst l0))
125 val _ = warning (replicate_string depth " " ^ " " ^
126 "r0: " ^ n_facts (map fst r0))
129 if pred (sup @ l0) then
130 min (depth + 1) sup l0
131 else if pred (sup @ r0) then
132 min (depth + 1) sup r0
135 val l = min (depth + 1) (sup @ r0) l0
136 val r = min (depth + 1) (sup @ l) r0
140 |> tap (fn _ => warning (replicate_string depth " " ^ "}"))
144 [x] => if pred [] then [] else [x]
148 (* Give the external prover some slack. The ATP gets further slack because the
149 Sledgehammer preprocessing time is included in the estimate below but isn't
150 part of the timeout. *)
151 val slack_msecs = 200
153 fun minimize_facts prover_name (params as {timeout, ...}) silent i n state
156 val ctxt = Proof.context_of state
157 val prover = get_prover ctxt Minimize prover_name
158 val msecs = Time.toMilliseconds timeout
159 val _ = print silent (fn () => "Sledgehammer minimizer: " ^
160 quote prover_name ^ ".")
161 fun do_test timeout = test_facts params silent prover timeout i n state
162 val timer = Timer.startRealTimer ()
164 (case do_test timeout facts of
165 result as {outcome = NONE, used_facts, ...} =>
167 val time = Timer.checkRealTimer timer
169 Int.min (msecs, Time.toMilliseconds time + slack_msecs)
170 |> Time.fromMilliseconds
171 val facts = filter_used_facts used_facts facts
172 val (min_facts, {preplay, message, message_tail, ...}) =
173 if length facts >= Config.get ctxt binary_min_facts then
174 binary_minimize (do_test new_timeout) facts
176 sublinear_minimize (do_test new_timeout) facts ([], result)
177 val _ = print silent (fn () => cat_lines
178 ["Minimized to " ^ n_facts (map fst min_facts)] ^
179 (case length (filter (curry (op =) Chained o snd o fst) min_facts) of
181 | n => "\n(including " ^ string_of_int n ^ " chained)") ^ ".")
182 in (SOME min_facts, (preplay, message, message_tail)) end
183 | {outcome = SOME TimedOut, preplay, ...} =>
186 fn _ => "Timeout: You can increase the time limit using the \
187 \\"timeout\" option (e.g., \"timeout = " ^
188 string_of_int (10 + msecs div 1000) ^ "\").",
190 | {preplay, message, ...} =>
191 (NONE, (preplay, prefix "Prover error: " o message, "")))
193 (NONE, (K (Failed_to_Play Metis), fn _ => "Error: " ^ msg, ""))
196 fun run_minimize (params as {provers, ...}) i refs state =
198 val ctxt = Proof.context_of state
199 val reserved = reserved_isar_keyword_table ()
200 val chained_ths = normalize_chained_theorems (#facts (Proof.goal state))
203 |> maps (map (apsnd single) o fact_from_ref ctxt reserved chained_ths)
205 case subgoal_count state of
206 0 => Output.urgent_message "No subgoal!"
207 | n => case provers of
208 [] => error "No prover is set."
211 minimize_facts prover params false i n state facts
212 |> (fn (_, (preplay, message, message_tail)) =>
213 message (preplay ()) ^ message_tail
214 |> Output.urgent_message))