src/HOL/Tools/Sledgehammer/sledgehammer_minimize.ML
changeset 48798 9152e66f98da
parent 48796 0f94b8b69e79
child 48799 5c9356f8c968
equal deleted inserted replaced
48797:e65385336531 48798:9152e66f98da
   126     fun min _ [] p = p
   126     fun min _ [] p = p
   127       | min timeout (x :: xs) (seen, result) =
   127       | min timeout (x :: xs) (seen, result) =
   128         case test timeout (xs @ seen) of
   128         case test timeout (xs @ seen) of
   129           result as {outcome = NONE, used_facts, run_time, ...}
   129           result as {outcome = NONE, used_facts, run_time, ...}
   130           : prover_result =>
   130           : prover_result =>
   131           min (new_timeout timeout run_time) (filter_used_facts used_facts xs)
   131           min (new_timeout timeout run_time)
   132               (filter_used_facts used_facts seen, result)
   132               (filter_used_facts true used_facts xs)
       
   133               (filter_used_facts false used_facts seen, result)
   133         | _ => min timeout xs (x :: seen, result)
   134         | _ => min timeout xs (x :: seen, result)
   134   in min timeout xs ([], result) end
   135   in min timeout (rev xs) ([], result) end
   135 
   136 
   136 fun binary_minimize test timeout result xs =
   137 fun binary_minimize test timeout result xs =
   137   let
   138   let
   138     fun min depth (result as {run_time, ...} : prover_result) sup
   139     fun min depth (result as {run_time, ...} : prover_result) sup
   139             (xs as _ :: _ :: _) =
   140             (xs as _ :: _ :: _) =
   152           val depth = depth + 1
   153           val depth = depth + 1
   153           val timeout = new_timeout timeout run_time
   154           val timeout = new_timeout timeout run_time
   154         in
   155         in
   155           case test timeout (sup @ l0) of
   156           case test timeout (sup @ l0) of
   156             result as {outcome = NONE, used_facts, ...} =>
   157             result as {outcome = NONE, used_facts, ...} =>
   157             min depth result (filter_used_facts used_facts sup)
   158             min depth result (filter_used_facts true used_facts sup)
   158                       (filter_used_facts used_facts l0)
   159                       (filter_used_facts true used_facts l0)
   159           | _ =>
   160           | _ =>
   160             case test timeout (sup @ r0) of
   161             case test timeout (sup @ r0) of
   161               result as {outcome = NONE, used_facts, ...} =>
   162               result as {outcome = NONE, used_facts, ...} =>
   162               min depth result (filter_used_facts used_facts sup)
   163               min depth result (filter_used_facts true used_facts sup)
   163                         (filter_used_facts used_facts r0)
   164                         (filter_used_facts true used_facts r0)
   164             | _ =>
   165             | _ =>
   165               let
   166               let
   166                 val (sup_r0, (l, result)) = min depth result (sup @ r0) l0
   167                 val (sup_r0, (l, result)) = min depth result (sup @ r0) l0
   167                 val (sup, r0) =
   168                 val (sup, r0) =
   168                   (sup, r0) |> pairself (filter_used_facts (map fst sup_r0))
   169                   (sup, r0)
       
   170                   |> pairself (filter_used_facts true (map fst sup_r0))
   169                 val (sup_l, (r, result)) = min depth result (sup @ l) r0
   171                 val (sup_l, (r, result)) = min depth result (sup @ l) r0
   170                 val sup = sup |> filter_used_facts (map fst sup_l)
   172                 val sup = sup |> filter_used_facts true (map fst sup_l)
   171               in (sup, (l @ r, result)) end
   173               in (sup, (l @ r, result)) end
   172         end
   174         end
   173 (*
   175 (*
   174         |> tap (fn _ => warning (replicate_string depth " " ^ "}"))
   176         |> tap (fn _ => warning (replicate_string depth " " ^ "}"))
   175 *)
   177 *)
   181          result as {outcome = NONE, ...} => ([], result)
   183          result as {outcome = NONE, ...} => ([], result)
   182        | _ => ([x], result))
   184        | _ => ([x], result))
   183     | p => p
   185     | p => p
   184   end
   186   end
   185 
   187 
   186 fun is_fact_chained ((_, (sc, _)), _) = sc = Chained
       
   187 
       
   188 fun minimize_facts do_learn prover_name (params as {learn, timeout, ...}) silent
   188 fun minimize_facts do_learn prover_name (params as {learn, timeout, ...}) silent
   189                    i n state facts =
   189                    i n state facts =
   190   let
   190   let
   191     val ctxt = Proof.context_of state
   191     val ctxt = Proof.context_of state
   192     val prover =
   192     val prover =
   193       get_prover ctxt (if silent then Auto_Minimize else Minimize) prover_name
   193       get_prover ctxt (if silent then Auto_Minimize else Minimize) prover_name
   194     fun test timeout = test_facts params silent prover timeout i n state
   194     fun test timeout = test_facts params silent prover timeout i n state
   195     val (chained, non_chained) = List.partition is_fact_chained facts
   195     val (chained, non_chained) = List.partition is_fact_chained facts
   196     (* Push chained facts to the back, so that they are less likely to be kicked
   196     (* Pull chained facts to the front, so that they are less likely to be
   197        out by the linear minimization algorithm. *)
   197        kicked out by the minimization algorithms (cf. "rev" in
       
   198        "linear_minimize"). *)
   198     val facts = non_chained @ chained
   199     val facts = non_chained @ chained
   199   in
   200   in
   200     (print silent (fn () => "Sledgehammer minimizer: " ^
   201     (print silent (fn () => "Sledgehammer minimizer: " ^
   201                             quote prover_name ^ ".");
   202                             quote prover_name ^ ".");
   202      case test timeout facts of
   203      case test timeout facts of
   203        result as {outcome = NONE, used_facts, run_time, ...} =>
   204        result as {outcome = NONE, used_facts, run_time, ...} =>
   204        let
   205        let
   205          val facts = filter_used_facts used_facts facts
   206          val facts = filter_used_facts true used_facts facts
   206          val min =
   207          val min =
   207            if length facts >= Config.get ctxt binary_min_facts then
   208            if length facts >= Config.get ctxt binary_min_facts then
   208              binary_minimize
   209              binary_minimize
   209            else
   210            else
   210              linear_minimize
   211              linear_minimize
   305       val (used_facts, (preplay, message, _)) =
   306       val (used_facts, (preplay, message, _)) =
   306         if minimize then
   307         if minimize then
   307           minimize_facts do_learn minimize_name params
   308           minimize_facts do_learn minimize_name params
   308                          (mode <> Normal orelse not verbose) subgoal
   309                          (mode <> Normal orelse not verbose) subgoal
   309                          subgoal_count state
   310                          subgoal_count state
   310                          (filter_used_facts used_facts
   311                          (filter_used_facts true used_facts
   311                               (map (apsnd single o untranslated_fact) facts))
   312                               (map (apsnd single o untranslated_fact) facts))
   312           |>> Option.map (map fst)
   313           |>> Option.map (map fst)
   313         else
   314         else
   314           (SOME used_facts, (preplay, message, ""))
   315           (SOME used_facts, (preplay, message, ""))
   315     in
   316     in