src/HOL/Tools/Sledgehammer/sledgehammer_mash.ML
author blanchet
Wed Dec 12 21:48:29 2012 +0100 (2012-12-12 ago)
changeset 50510 7e4f2f8d9b50
parent 50485 3c6ac2da2f45
child 50557 31313171deb5
permissions -rw-r--r--
export a pair of ML functions
blanchet@48380
     1
(*  Title:      HOL/Tools/Sledgehammer/sledgehammer_mash.ML
blanchet@48248
     2
    Author:     Jasmin Blanchette, TU Muenchen
blanchet@48248
     3
blanchet@48248
     4
Sledgehammer's machine-learning-based relevance filter (MaSh).
blanchet@48248
     5
*)
blanchet@48248
     6
blanchet@48381
     7
signature SLEDGEHAMMER_MASH =
blanchet@48248
     8
sig
blanchet@48251
     9
  type stature = ATP_Problem_Generate.stature
blanchet@48296
    10
  type fact = Sledgehammer_Fact.fact
blanchet@48296
    11
  type fact_override = Sledgehammer_Fact.fact_override
blanchet@48251
    12
  type params = Sledgehammer_Provers.params
blanchet@48288
    13
  type relevance_fudge = Sledgehammer_Provers.relevance_fudge
blanchet@48251
    14
  type prover_result = Sledgehammer_Provers.prover_result
blanchet@48251
    15
blanchet@48308
    16
  val trace : bool Config.T
blanchet@48319
    17
  val MaShN : string
blanchet@48379
    18
  val mepoN : string
blanchet@48379
    19
  val mashN : string
blanchet@48314
    20
  val meshN : string
blanchet@48392
    21
  val unlearnN : string
blanchet@48392
    22
  val learn_isarN : string
blanchet@50484
    23
  val learn_proverN : string
blanchet@48392
    24
  val relearn_isarN : string
blanchet@50484
    25
  val relearn_proverN : string
blanchet@48314
    26
  val fact_filters : string list
blanchet@48303
    27
  val escape_meta : string -> string
blanchet@48303
    28
  val escape_metas : string list -> string
blanchet@48308
    29
  val unescape_meta : string -> string
blanchet@48308
    30
  val unescape_metas : string -> string list
blanchet@50356
    31
  val encode_features : (string * real) list -> string
blanchet@48406
    32
  val extract_query : string -> string * (string * real) list
blanchet@50311
    33
  val mash_CLEAR : Proof.context -> unit
blanchet@50311
    34
  val mash_ADD :
blanchet@50311
    35
    Proof.context -> bool
blanchet@50356
    36
    -> (string * string list * (string * real) list * string list) list -> unit
blanchet@50311
    37
  val mash_REPROVE :
blanchet@50311
    38
    Proof.context -> bool -> (string * string list) list -> unit
blanchet@50311
    39
  val mash_QUERY :
blanchet@50356
    40
    Proof.context -> bool -> int -> string list * (string * real) list
blanchet@50311
    41
    -> (string * real) list
blanchet@50311
    42
  val mash_unlearn : Proof.context -> unit
blanchet@48378
    43
  val nickname_of : thm -> string
blanchet@50412
    44
  val find_suggested_facts :
blanchet@48406
    45
    (string * 'a) list -> ('b * thm) list -> (('b * thm) * 'a) list
blanchet@48321
    46
  val mesh_facts :
blanchet@50383
    47
    int -> (real * ((('a * thm) * real) list * ('a * thm) list)) list
blanchet@50383
    48
    -> ('a * thm) list
blanchet@48251
    49
  val theory_ord : theory * theory -> order
blanchet@48251
    50
  val thm_ord : thm * thm -> order
blanchet@48251
    51
  val goal_of_thm : theory -> thm -> thm
blanchet@48321
    52
  val run_prover_for_mash :
blanchet@48318
    53
    Proof.context -> params -> string -> fact list -> thm -> prover_result
blanchet@48392
    54
  val features_of :
blanchet@50356
    55
    Proof.context -> string -> theory -> stature -> term list
blanchet@50356
    56
    -> (string * real) list
blanchet@50485
    57
  val isar_dependencies_of : string Symtab.table -> thm -> string list option
blanchet@50484
    58
  val prover_dependencies_of :
blanchet@50485
    59
    Proof.context -> params -> string -> int -> fact list -> string Symtab.table
blanchet@48665
    60
    -> thm -> bool * string list option
blanchet@50382
    61
  val weight_mash_facts : ('a * thm) list -> (('a * thm) * real) list
blanchet@50412
    62
  val find_mash_suggestions :
blanchet@50412
    63
    int -> (Symtab.key * 'a) list -> ('b * thm) list -> ('b * thm) list
blanchet@50440
    64
    -> ('b * thm) list -> ('b * thm) list * ('b * thm) list
blanchet@48406
    65
  val mash_suggested_facts :
blanchet@50383
    66
    Proof.context -> params -> string -> int -> term list -> term -> fact list
blanchet@50440
    67
    -> fact list * fact list
blanchet@48383
    68
  val mash_learn_proof :
blanchet@48384
    69
    Proof.context -> params -> string -> term -> ('a * thm) list -> thm list
blanchet@48384
    70
    -> unit
blanchet@48395
    71
  val mash_learn :
blanchet@48395
    72
    Proof.context -> params -> fact_override -> thm list -> bool -> unit
blanchet@50311
    73
  val is_mash_enabled : unit -> bool
blanchet@50311
    74
  val mash_can_suggest_facts : Proof.context -> bool
blanchet@50412
    75
  val generous_max_facts : int -> int
blanchet@48288
    76
  val relevant_facts :
blanchet@48292
    77
    Proof.context -> params -> string -> int -> fact_override -> term list
blanchet@48296
    78
    -> term -> fact list -> fact list
blanchet@48319
    79
  val kill_learners : unit -> unit
blanchet@48319
    80
  val running_learners : unit -> unit
blanchet@48248
    81
end;
blanchet@48248
    82
blanchet@48381
    83
structure Sledgehammer_MaSh : SLEDGEHAMMER_MASH =
blanchet@48248
    84
struct
blanchet@48249
    85
blanchet@48251
    86
open ATP_Util
blanchet@48251
    87
open ATP_Problem_Generate
blanchet@48251
    88
open Sledgehammer_Util
blanchet@48251
    89
open Sledgehammer_Fact
blanchet@48251
    90
open Sledgehammer_Provers
blanchet@48318
    91
open Sledgehammer_Minimize
blanchet@48381
    92
open Sledgehammer_MePo
blanchet@48251
    93
blanchet@48308
    94
val trace =
blanchet@48380
    95
  Attrib.setup_config_bool @{binding sledgehammer_mash_trace} (K false)
blanchet@48308
    96
fun trace_msg ctxt msg = if Config.get ctxt trace then tracing (msg ()) else ()
blanchet@48308
    97
blanchet@48319
    98
val MaShN = "MaSh"
blanchet@48319
    99
blanchet@48379
   100
val mepoN = "mepo"
blanchet@48314
   101
val mashN = "mash"
blanchet@48379
   102
val meshN = "mesh"
blanchet@48314
   103
blanchet@48379
   104
val fact_filters = [meshN, mepoN, mashN]
blanchet@48314
   105
blanchet@48392
   106
val unlearnN = "unlearn"
blanchet@48392
   107
val learn_isarN = "learn_isar"
blanchet@50484
   108
val learn_proverN = "learn_prover"
blanchet@48392
   109
val relearn_isarN = "relearn_isar"
blanchet@50484
   110
val relearn_proverN = "relearn_prover"
blanchet@48392
   111
blanchet@48394
   112
fun mash_model_dir () =
blanchet@50340
   113
  Path.explode "$ISABELLE_HOME_USER/mash" |> tap Isabelle_System.mkdir
blanchet@48394
   114
val mash_state_dir = mash_model_dir
blanchet@50310
   115
fun mash_state_file () = Path.append (mash_state_dir ()) (Path.explode "state")
blanchet@48251
   116
blanchet@48330
   117
blanchet@50311
   118
(*** Low-level communication with MaSh ***)
blanchet@50311
   119
blanchet@50311
   120
fun wipe_out_file file = (try (File.rm o Path.explode) file; ())
blanchet@50311
   121
blanchet@50335
   122
fun write_file banner (xs, f) path =
blanchet@50335
   123
  (case banner of SOME s => File.write path s | NONE => ();
blanchet@50335
   124
   xs |> chunk_list 500
blanchet@50335
   125
      |> List.app (File.append path o space_implode "" o map f))
blanchet@50319
   126
  handle IO.Io _ => ()
blanchet@50311
   127
blanchet@50311
   128
fun run_mash_tool ctxt overlord save max_suggs write_cmds read_suggs =
blanchet@50311
   129
  let
blanchet@50311
   130
    val (temp_dir, serial) =
blanchet@50311
   131
      if overlord then (getenv "ISABELLE_HOME_USER", "")
blanchet@50311
   132
      else (getenv "ISABELLE_TMP", serial_string ())
blanchet@50311
   133
    val log_file = if overlord then temp_dir ^ "/mash_log" else "/dev/null"
blanchet@50311
   134
    val err_file = temp_dir ^ "/mash_err" ^ serial
blanchet@50311
   135
    val sugg_file = temp_dir ^ "/mash_suggs" ^ serial
blanchet@50335
   136
    val sugg_path = Path.explode sugg_file
blanchet@50311
   137
    val cmd_file = temp_dir ^ "/mash_commands" ^ serial
blanchet@50335
   138
    val cmd_path = Path.explode cmd_file
blanchet@50311
   139
    val core =
blanchet@50311
   140
      "--inputFile " ^ cmd_file ^ " --predictions " ^ sugg_file ^
blanchet@50311
   141
      " --numberOfPredictions " ^ string_of_int max_suggs ^
blanchet@50311
   142
      (if save then " --saveModel" else "")
blanchet@50311
   143
    val command =
blanchet@50335
   144
      "\"$ISABELLE_SLEDGEHAMMER_MASH/src/mash.py\" --quiet --outputDir " ^
blanchet@50335
   145
      File.shell_path (mash_model_dir ()) ^ " --log " ^ log_file ^ " " ^ core ^
blanchet@50311
   146
      " >& " ^ err_file
blanchet@50311
   147
      |> tap (fn _ => trace_msg ctxt (fn () =>
blanchet@50311
   148
             case try File.read (Path.explode err_file) of
blanchet@50311
   149
               NONE => "Done"
blanchet@50311
   150
             | SOME "" => "Done"
blanchet@50311
   151
             | SOME s => "Error: " ^ elide_string 1000 s))
blanchet@50311
   152
    fun run_on () =
blanchet@50311
   153
      (Isabelle_System.bash command;
blanchet@50335
   154
       read_suggs (fn () => try File.read_lines sugg_path |> these))
blanchet@50311
   155
    fun clean_up () =
blanchet@50311
   156
      if overlord then ()
blanchet@50311
   157
      else List.app wipe_out_file [err_file, sugg_file, cmd_file]
blanchet@50311
   158
  in
blanchet@50335
   159
    write_file (SOME "") ([], K "") sugg_path;
blanchet@50335
   160
    write_file (SOME "") write_cmds cmd_path;
blanchet@50311
   161
    trace_msg ctxt (fn () => "Running " ^ command);
blanchet@50311
   162
    with_cleanup clean_up run_on ()
blanchet@50311
   163
  end
blanchet@48251
   164
blanchet@48308
   165
fun meta_char c =
blanchet@48251
   166
  if Char.isAlphaNum c orelse c = #"_" orelse c = #"." orelse c = #"(" orelse
blanchet@48251
   167
     c = #")" orelse c = #"," then
blanchet@48251
   168
    String.str c
blanchet@48251
   169
  else
blanchet@48251
   170
    (* fixed width, in case more digits follow *)
blanchet@48395
   171
    "%" ^ stringN_of_int 3 (Char.ord c)
blanchet@48251
   172
blanchet@48308
   173
fun unmeta_chars accum [] = String.implode (rev accum)
blanchet@48395
   174
  | unmeta_chars accum (#"%" :: d1 :: d2 :: d3 :: cs) =
blanchet@48308
   175
    (case Int.fromString (String.implode [d1, d2, d3]) of
blanchet@48308
   176
       SOME n => unmeta_chars (Char.chr n :: accum) cs
blanchet@48308
   177
     | NONE => "" (* error *))
blanchet@48395
   178
  | unmeta_chars _ (#"%" :: _) = "" (* error *)
blanchet@48308
   179
  | unmeta_chars accum (c :: cs) = unmeta_chars (c :: accum) cs
blanchet@48308
   180
blanchet@48308
   181
val escape_meta = String.translate meta_char
blanchet@48303
   182
val escape_metas = map escape_meta #> space_implode " "
blanchet@48315
   183
val unescape_meta = String.explode #> unmeta_chars []
blanchet@48315
   184
val unescape_metas =
blanchet@48315
   185
  space_explode " " #> filter_out (curry (op =) "") #> map unescape_meta
blanchet@48251
   186
blanchet@50356
   187
fun encode_feature (name, weight) =
blanchet@50389
   188
  escape_meta name ^
blanchet@50389
   189
  (if Real.== (weight, 1.0) then "" else "=" ^ Real.toString weight)
blanchet@50356
   190
blanchet@50356
   191
val encode_features = map encode_feature #> space_implode " "
blanchet@50356
   192
blanchet@50311
   193
fun str_of_add (name, parents, feats, deps) =
blanchet@50311
   194
  "! " ^ escape_meta name ^ ": " ^ escape_metas parents ^ "; " ^
blanchet@50356
   195
  encode_features feats ^ "; " ^ escape_metas deps ^ "\n"
blanchet@48669
   196
blanchet@50311
   197
fun str_of_reprove (name, deps) =
blanchet@50311
   198
  "p " ^ escape_meta name ^ ": " ^ escape_metas deps ^ "\n"
blanchet@50311
   199
blanchet@50311
   200
fun str_of_query (parents, feats) =
blanchet@50356
   201
  "? " ^ escape_metas parents ^ "; " ^ encode_features feats ^ "\n"
blanchet@48406
   202
blanchet@48406
   203
fun extract_suggestion sugg =
blanchet@48406
   204
  case space_explode "=" sugg of
blanchet@48406
   205
    [name, weight] =>
blanchet@50401
   206
    SOME (unescape_meta name, Real.fromString weight |> the_default 1.0)
blanchet@50401
   207
  | [name] => SOME (unescape_meta name, 1.0)
blanchet@48406
   208
  | _ => NONE
blanchet@48406
   209
blanchet@48311
   210
fun extract_query line =
blanchet@48311
   211
  case space_explode ":" line of
blanchet@48406
   212
    [goal, suggs] =>
blanchet@48406
   213
    (unescape_meta goal,
blanchet@48406
   214
     map_filter extract_suggestion (space_explode " " suggs))
blanchet@48312
   215
  | _ => ("", [])
blanchet@48311
   216
blanchet@50311
   217
fun mash_CLEAR ctxt =
blanchet@50311
   218
  let val path = mash_model_dir () in
blanchet@50311
   219
    trace_msg ctxt (K "MaSh CLEAR");
blanchet@50319
   220
    try (File.fold_dir (fn file => fn _ =>
blanchet@50319
   221
                           try File.rm (Path.append path (Path.basic file)))
blanchet@50319
   222
                       path) NONE;
blanchet@50311
   223
    ()
blanchet@50311
   224
  end
blanchet@50311
   225
blanchet@50311
   226
fun mash_ADD _ _ [] = ()
blanchet@50311
   227
  | mash_ADD ctxt overlord adds =
blanchet@50311
   228
    (trace_msg ctxt (fn () => "MaSh ADD " ^
blanchet@50311
   229
         elide_string 1000 (space_implode " " (map #1 adds)));
blanchet@50311
   230
     run_mash_tool ctxt overlord true 0 (adds, str_of_add) (K ()))
blanchet@50311
   231
blanchet@50311
   232
fun mash_REPROVE _ _ [] = ()
blanchet@50311
   233
  | mash_REPROVE ctxt overlord reps =
blanchet@50311
   234
    (trace_msg ctxt (fn () => "MaSh REPROVE " ^
blanchet@50311
   235
         elide_string 1000 (space_implode " " (map #1 reps)));
blanchet@50311
   236
     run_mash_tool ctxt overlord true 0 (reps, str_of_reprove) (K ()))
blanchet@50311
   237
blanchet@50311
   238
fun mash_QUERY ctxt overlord max_suggs (query as (_, feats)) =
blanchet@50356
   239
  (trace_msg ctxt (fn () => "MaSh QUERY " ^ encode_features feats);
blanchet@50311
   240
   run_mash_tool ctxt overlord false max_suggs
blanchet@50311
   241
       ([query], str_of_query)
blanchet@50311
   242
       (fn suggs =>
blanchet@50311
   243
           case suggs () of
blanchet@50311
   244
             [] => []
blanchet@50311
   245
           | suggs => snd (extract_query (List.last suggs)))
blanchet@50311
   246
   handle List.Empty => [])
blanchet@50311
   247
blanchet@50311
   248
blanchet@50311
   249
(*** Middle-level communication with MaSh ***)
blanchet@50311
   250
blanchet@50484
   251
datatype proof_kind =
blanchet@50484
   252
  Isar_Proof | Automatic_Proof | Isar_Proof_wegen_Prover_Flop
blanchet@50311
   253
blanchet@50311
   254
fun str_of_proof_kind Isar_Proof = "i"
blanchet@50484
   255
  | str_of_proof_kind Automatic_Proof = "a"
blanchet@50484
   256
  | str_of_proof_kind Isar_Proof_wegen_Prover_Flop = "x"
blanchet@50311
   257
blanchet@50311
   258
fun proof_kind_of_str "i" = Isar_Proof
blanchet@50484
   259
  | proof_kind_of_str "a" = Automatic_Proof
blanchet@50484
   260
  | proof_kind_of_str "x" = Isar_Proof_wegen_Prover_Flop
blanchet@50311
   261
blanchet@50311
   262
(* FIXME: Here a "Graph.update_node" function would be useful *)
blanchet@50311
   263
fun update_fact_graph_node (name, kind) =
blanchet@50311
   264
  Graph.default_node (name, Isar_Proof)
blanchet@50311
   265
  #> kind <> Isar_Proof ? Graph.map_node name (K kind)
blanchet@50311
   266
blanchet@50311
   267
fun try_graph ctxt when def f =
blanchet@50311
   268
  f ()
blanchet@50311
   269
  handle Graph.CYCLES (cycle :: _) =>
blanchet@50311
   270
         (trace_msg ctxt (fn () =>
blanchet@50311
   271
              "Cycle involving " ^ commas cycle ^ " when " ^ when); def)
blanchet@50311
   272
       | Graph.DUP name =>
blanchet@50311
   273
         (trace_msg ctxt (fn () =>
blanchet@50311
   274
              "Duplicate fact " ^ quote name ^ " when " ^ when); def)
blanchet@50311
   275
       | Graph.UNDEF name =>
blanchet@50311
   276
         (trace_msg ctxt (fn () =>
blanchet@50311
   277
              "Unknown fact " ^ quote name ^ " when " ^ when); def)
blanchet@50311
   278
       | exn =>
blanchet@50311
   279
         if Exn.is_interrupt exn then
blanchet@50311
   280
           reraise exn
blanchet@50311
   281
         else
blanchet@50311
   282
           (trace_msg ctxt (fn () =>
blanchet@50311
   283
                "Internal error when " ^ when ^ ":\n" ^
blanchet@50311
   284
                ML_Compiler.exn_message exn); def)
blanchet@50311
   285
blanchet@50311
   286
fun graph_info G =
blanchet@50311
   287
  string_of_int (length (Graph.keys G)) ^ " node(s), " ^
blanchet@50311
   288
  string_of_int (fold (Integer.add o length o snd) (Graph.dest G) 0) ^
blanchet@50311
   289
  " edge(s), " ^
blanchet@50311
   290
  string_of_int (length (Graph.minimals G)) ^ " minimal, " ^
blanchet@50311
   291
  string_of_int (length (Graph.maximals G)) ^ " maximal"
blanchet@50311
   292
blanchet@50311
   293
type mash_state = {fact_G : unit Graph.T, dirty : string list option}
blanchet@50311
   294
blanchet@50311
   295
val empty_state = {fact_G = Graph.empty, dirty = SOME []}
blanchet@50311
   296
blanchet@50311
   297
local
blanchet@50311
   298
blanchet@50485
   299
val version = "*** MaSh version 20121212a ***"
blanchet@50357
   300
blanchet@50357
   301
exception Too_New of unit
blanchet@50311
   302
blanchet@50311
   303
fun extract_node line =
blanchet@50311
   304
  case space_explode ":" line of
blanchet@50311
   305
    [head, parents] =>
blanchet@50311
   306
    (case space_explode " " head of
blanchet@50311
   307
       [kind, name] =>
blanchet@50311
   308
       SOME (unescape_meta name, unescape_metas parents,
blanchet@50311
   309
             try proof_kind_of_str kind |> the_default Isar_Proof)
blanchet@50311
   310
     | _ => NONE)
blanchet@50311
   311
  | _ => NONE
blanchet@50311
   312
blanchet@50311
   313
fun load _ (state as (true, _)) = state
blanchet@50311
   314
  | load ctxt _ =
blanchet@50311
   315
    let val path = mash_state_file () in
blanchet@50311
   316
      (true,
blanchet@50311
   317
       case try File.read_lines path of
blanchet@50311
   318
         SOME (version' :: node_lines) =>
blanchet@50311
   319
         let
blanchet@50311
   320
           fun add_edge_to name parent =
blanchet@50311
   321
             Graph.default_node (parent, Isar_Proof)
blanchet@50311
   322
             #> Graph.add_edge (parent, name)
blanchet@50311
   323
           fun add_node line =
blanchet@50311
   324
             case extract_node line of
blanchet@50311
   325
               NONE => I (* shouldn't happen *)
blanchet@50311
   326
             | SOME (name, parents, kind) =>
blanchet@50311
   327
               update_fact_graph_node (name, kind)
blanchet@50311
   328
               #> fold (add_edge_to name) parents
blanchet@50311
   329
           val fact_G =
blanchet@50357
   330
             case string_ord (version', version) of
blanchet@50357
   331
               EQUAL =>
blanchet@50357
   332
               try_graph ctxt "loading state" Graph.empty (fn () =>
blanchet@50357
   333
                   fold add_node node_lines Graph.empty)
blanchet@50357
   334
             | LESS => Graph.empty (* can't parse old file *)
blanchet@50357
   335
             | GREATER => raise Too_New ()
blanchet@50311
   336
         in
blanchet@50311
   337
           trace_msg ctxt (fn () =>
blanchet@50311
   338
               "Loaded fact graph (" ^ graph_info fact_G ^ ")");
blanchet@50311
   339
           {fact_G = fact_G, dirty = SOME []}
blanchet@50311
   340
         end
blanchet@50311
   341
       | _ => empty_state)
blanchet@50311
   342
    end
blanchet@50311
   343
blanchet@50311
   344
fun save _ (state as {dirty = SOME [], ...}) = state
blanchet@50311
   345
  | save ctxt {fact_G, dirty} =
blanchet@50311
   346
    let
blanchet@50311
   347
      fun str_of_entry (name, parents, kind) =
blanchet@50311
   348
        str_of_proof_kind kind ^ " " ^ escape_meta name ^ ": " ^
blanchet@50311
   349
        escape_metas parents ^ "\n"
blanchet@50311
   350
      fun append_entry (name, (kind, (parents, _))) =
blanchet@50311
   351
        cons (name, Graph.Keys.dest parents, kind)
blanchet@50311
   352
      val (banner, entries) =
blanchet@50311
   353
        case dirty of
blanchet@50311
   354
          SOME names =>
blanchet@50311
   355
          (NONE, fold (append_entry o Graph.get_entry fact_G) names [])
blanchet@50311
   356
        | NONE => (SOME (version ^ "\n"), Graph.fold append_entry fact_G [])
blanchet@50311
   357
    in
blanchet@50335
   358
      write_file banner (entries, str_of_entry) (mash_state_file ());
blanchet@50311
   359
      trace_msg ctxt (fn () =>
blanchet@50311
   360
          "Saved fact graph (" ^ graph_info fact_G ^
blanchet@50311
   361
          (case dirty of
blanchet@50311
   362
             SOME dirty =>
blanchet@50311
   363
             "; " ^ string_of_int (length dirty) ^ " dirty fact(s)"
blanchet@50311
   364
           | _ => "") ^  ")");
blanchet@50311
   365
      {fact_G = fact_G, dirty = SOME []}
blanchet@50311
   366
    end
blanchet@50311
   367
blanchet@50311
   368
val global_state =
blanchet@50311
   369
  Synchronized.var "Sledgehammer_MaSh.global_state" (false, empty_state)
blanchet@50311
   370
blanchet@50311
   371
in
blanchet@50311
   372
blanchet@50311
   373
fun mash_map ctxt f =
blanchet@50311
   374
  Synchronized.change global_state (load ctxt ##> (f #> save ctxt))
blanchet@50357
   375
  handle Too_New () => ()
blanchet@50311
   376
blanchet@50311
   377
fun mash_peek ctxt f =
blanchet@50357
   378
  Synchronized.change_result global_state
blanchet@50357
   379
      (perhaps (try (load ctxt)) #> `snd #>> f)
blanchet@50311
   380
blanchet@50311
   381
fun mash_get ctxt =
blanchet@50357
   382
  Synchronized.change_result global_state (perhaps (try (load ctxt)) #> `snd)
blanchet@50311
   383
blanchet@50311
   384
fun mash_unlearn ctxt =
blanchet@50311
   385
  Synchronized.change global_state (fn _ =>
blanchet@50311
   386
      (mash_CLEAR ctxt; (* also removes the state file *)
blanchet@50311
   387
       (true, empty_state)))
blanchet@50311
   388
blanchet@50311
   389
end
blanchet@50311
   390
blanchet@50311
   391
blanchet@50311
   392
(*** Isabelle helpers ***)
blanchet@50311
   393
blanchet@48378
   394
fun parent_of_local_thm th =
blanchet@48378
   395
  let
blanchet@48378
   396
    val thy = th |> Thm.theory_of_thm
blanchet@48378
   397
    val facts = thy |> Global_Theory.facts_of
blanchet@48378
   398
    val space = facts |> Facts.space_of
blanchet@48378
   399
    fun id_of s = #id (Name_Space.the_entry space s)
blanchet@48378
   400
    fun max_id (s', _) (s, id) =
blanchet@48378
   401
      let val id' = id_of s' in if id > id' then (s, id) else (s', id') end
blanchet@48378
   402
  in ("", ~1) |> Facts.fold_static max_id facts |> fst end
blanchet@48378
   403
blanchet@48378
   404
val local_prefix = "local" ^ Long_Name.separator
blanchet@48378
   405
blanchet@48378
   406
fun nickname_of th =
blanchet@48394
   407
  if Thm.has_name_hint th then
blanchet@48394
   408
    let val hint = Thm.get_name_hint th in
blanchet@48394
   409
      (* FIXME: There must be a better way to detect local facts. *)
blanchet@48394
   410
      case try (unprefix local_prefix) hint of
blanchet@48394
   411
        SOME suf =>
blanchet@48394
   412
        parent_of_local_thm th ^ Long_Name.separator ^ Long_Name.separator ^ suf
blanchet@48394
   413
      | NONE => hint
blanchet@48394
   414
    end
blanchet@48394
   415
  else
blanchet@50047
   416
    backquote_thm (Proof_Context.init_global (Thm.theory_of_thm th)) th
blanchet@48378
   417
blanchet@50412
   418
fun find_suggested_facts suggs facts =
blanchet@48330
   419
  let
blanchet@48378
   420
    fun add_fact (fact as (_, th)) = Symtab.default (nickname_of th, fact)
blanchet@48330
   421
    val tab = Symtab.empty |> fold add_fact facts
blanchet@48406
   422
    fun find_sugg (name, weight) =
blanchet@48406
   423
      Symtab.lookup tab name |> Option.map (rpair weight)
blanchet@48406
   424
  in map_filter find_sugg suggs end
blanchet@48311
   425
blanchet@50383
   426
fun scaled_avg [] = 0
blanchet@50383
   427
  | scaled_avg xs =
blanchet@48407
   428
    Real.ceil (100000000.0 * fold (curry (op +)) xs 0.0) div length xs
blanchet@48328
   429
blanchet@50383
   430
fun avg [] = 0.0
blanchet@50383
   431
  | avg xs = fold (curry (op +)) xs 0.0 / Real.fromInt (length xs)
blanchet@48313
   432
blanchet@50383
   433
fun normalize_scores _ [] = []
blanchet@50383
   434
  | normalize_scores max_facts xs =
blanchet@50383
   435
    let val avg = avg (map snd (take max_facts xs)) in
blanchet@50383
   436
      map (apsnd (curry Real.* (1.0 / avg))) xs
blanchet@50383
   437
    end
blanchet@50383
   438
blanchet@50383
   439
fun mesh_facts max_facts [(_, (sels, unks))] =
blanchet@48406
   440
    map fst (take max_facts sels) @ take (max_facts - length sels) unks
blanchet@48314
   441
  | mesh_facts max_facts mess =
blanchet@48314
   442
    let
blanchet@50383
   443
      val mess =
blanchet@50383
   444
        mess |> map (apsnd (apfst (normalize_scores max_facts #> `length)))
blanchet@48314
   445
      val fact_eq = Thm.eq_thm o pairself snd
blanchet@50383
   446
      fun score_in fact (global_weight, ((sel_len, sels), unks)) =
blanchet@50383
   447
        let
blanchet@50383
   448
          fun score_at j =
blanchet@50383
   449
            case try (nth sels) j of
blanchet@50383
   450
              SOME (_, score) => SOME (global_weight * score)
blanchet@50383
   451
            | NONE => NONE
blanchet@50383
   452
        in
blanchet@50383
   453
          case find_index (curry fact_eq fact o fst) sels of
blanchet@50383
   454
            ~1 => (case find_index (curry fact_eq fact) unks of
blanchet@50438
   455
                     ~1 => score_at (sel_len - 1)
blanchet@50383
   456
                   | _ => NONE)
blanchet@50383
   457
          | rank => score_at rank
blanchet@50383
   458
        end
blanchet@50383
   459
      fun weight_of fact = mess |> map_filter (score_in fact) |> scaled_avg
blanchet@48406
   460
      val facts =
blanchet@50383
   461
        fold (union fact_eq o map fst o take max_facts o snd o fst o snd) mess
blanchet@50383
   462
             []
blanchet@48314
   463
    in
blanchet@48406
   464
      facts |> map (`weight_of) |> sort (int_ord o swap o pairself fst)
blanchet@48328
   465
            |> map snd |> take max_facts
blanchet@48314
   466
    end
blanchet@48312
   467
blanchet@50394
   468
fun thy_feature_of s = ("y" ^ s, 0.5 (* FUDGE *))
blanchet@50435
   469
fun const_feature_of s = ("c" ^ s, 4.0 (* FUDGE *))
blanchet@50435
   470
fun free_feature_of s = ("f" ^ s, 5.0 (* FUDGE *))
blanchet@50396
   471
fun type_feature_of s = ("t" ^ s, 0.5 (* FUDGE *))
blanchet@50396
   472
fun class_feature_of s = ("s" ^ s, 0.25 (* FUDGE *))
blanchet@50394
   473
fun status_feature_of status = (string_of_status status, 0.5 (* FUDGE *))
blanchet@50390
   474
val local_feature = ("local", 2.0 (* FUDGE *))
blanchet@50391
   475
val lams_feature = ("lams", 0.5 (* FUDGE *))
blanchet@50391
   476
val skos_feature = ("skos", 0.5 (* FUDGE *))
blanchet@48251
   477
blanchet@48324
   478
fun theory_ord p =
blanchet@48324
   479
  if Theory.eq_thy p then
blanchet@48324
   480
    EQUAL
blanchet@48324
   481
  else if Theory.subthy p then
blanchet@48324
   482
    LESS
blanchet@48324
   483
  else if Theory.subthy (swap p) then
blanchet@48324
   484
    GREATER
blanchet@48324
   485
  else case int_ord (pairself (length o Theory.ancestors_of) p) of
blanchet@48324
   486
    EQUAL => string_ord (pairself Context.theory_name p)
blanchet@48324
   487
  | order => order
blanchet@48324
   488
blanchet@50382
   489
fun thm_ord p =
blanchet@50382
   490
  case theory_ord (pairself theory_of_thm p) of
blanchet@50359
   491
    EQUAL =>
blanchet@50359
   492
    (* Hack to put "xxx_def" before "xxxI" and "xxxE" *)
blanchet@50382
   493
    string_ord (pairself nickname_of (swap p))
blanchet@50359
   494
  | ord => ord
blanchet@48324
   495
blanchet@48392
   496
val freezeT = Type.legacy_freeze_type
blanchet@48392
   497
blanchet@48392
   498
fun freeze (t $ u) = freeze t $ freeze u
blanchet@48392
   499
  | freeze (Abs (s, T, t)) = Abs (s, freezeT T, freeze t)
blanchet@48392
   500
  | freeze (Var ((s, _), T)) = Free (s, freezeT T)
blanchet@48392
   501
  | freeze (Const (s, T)) = Const (s, freezeT T)
blanchet@48392
   502
  | freeze (Free (s, T)) = Free (s, freezeT T)
blanchet@48392
   503
  | freeze t = t
blanchet@48392
   504
blanchet@48392
   505
fun goal_of_thm thy = prop_of #> freeze #> cterm_of thy #> Goal.init
blanchet@48392
   506
blanchet@48392
   507
fun run_prover_for_mash ctxt params prover facts goal =
blanchet@48392
   508
  let
blanchet@48392
   509
    val problem =
blanchet@48392
   510
      {state = Proof.init ctxt, goal = goal, subgoal = 1, subgoal_count = 1,
blanchet@48392
   511
       facts = facts |> map (apfst (apfst (fn name => name ())))
blanchet@48392
   512
                     |> map Untranslated_Fact}
blanchet@48392
   513
  in
blanchet@48399
   514
    get_minimizing_prover ctxt MaSh (K (K ())) prover params (K (K (K "")))
blanchet@48392
   515
                          problem
blanchet@48392
   516
  end
blanchet@48392
   517
blanchet@48326
   518
val bad_types = [@{type_name prop}, @{type_name bool}, @{type_name fun}]
blanchet@48326
   519
blanchet@48398
   520
val logical_consts =
blanchet@48398
   521
  [@{const_name prop}, @{const_name Pure.conjunction}] @ atp_logical_consts
blanchet@48398
   522
blanchet@50393
   523
fun interesting_terms_types_and_classes ctxt thy_name prover term_max_depth
blanchet@48318
   524
                                        type_max_depth ts =
blanchet@48251
   525
  let
blanchet@50392
   526
    val thy = Proof_Context.theory_of ctxt
blanchet@50393
   527
    val fixes = map snd (Variable.dest_fixes ctxt)
blanchet@50392
   528
    val classes = Sign.classes_of thy
blanchet@48318
   529
    fun is_bad_const (x as (s, _)) args =
blanchet@48398
   530
      member (op =) logical_consts s orelse
blanchet@48318
   531
      fst (is_built_in_const_for_prover ctxt prover x args)
blanchet@48304
   532
    fun add_classes @{sort type} = I
blanchet@50392
   533
      | add_classes S =
blanchet@50392
   534
        fold (`(Sorts.super_classes classes)
blanchet@50392
   535
              #> swap #> op ::
blanchet@50392
   536
              #> subtract (op =) @{sort type}
blanchet@50392
   537
              #> map class_feature_of
blanchet@50392
   538
              #> union (op = o pairself fst)) S
blanchet@48251
   539
    fun do_add_type (Type (s, Ts)) =
blanchet@50356
   540
        (not (member (op =) bad_types s)
blanchet@50356
   541
         ? insert (op = o pairself fst) (type_feature_of s))
blanchet@48251
   542
        #> fold do_add_type Ts
blanchet@48304
   543
      | do_add_type (TFree (_, S)) = add_classes S
blanchet@48304
   544
      | do_add_type (TVar (_, S)) = add_classes S
blanchet@48251
   545
    fun add_type T = type_max_depth >= 0 ? do_add_type T
blanchet@50339
   546
    fun patternify_term _ ~1 _ = []
blanchet@50339
   547
      | patternify_term args _ (Const (x as (s, _))) =
blanchet@50356
   548
        if is_bad_const x args then [] else [s]
blanchet@50393
   549
      | patternify_term _ depth (Free (s, _)) =
blanchet@50393
   550
        if depth = term_max_depth andalso member (op =) fixes s then
blanchet@50393
   551
          [thy_name ^ Long_Name.separator ^ s]
blanchet@50393
   552
        else
blanchet@50393
   553
          []
blanchet@50339
   554
      | patternify_term _ 0 _ = []
blanchet@50339
   555
      | patternify_term args depth (t $ u) =
blanchet@50339
   556
        let
blanchet@50339
   557
          val ps = patternify_term (u :: args) depth t
blanchet@50339
   558
          val qs = "" :: patternify_term [] (depth - 1) u
blanchet@50383
   559
        in map_product (fn p => fn "" => p | q => p ^ "(" ^ q ^ ")") ps qs end
blanchet@50339
   560
      | patternify_term _ _ _ = []
blanchet@50393
   561
    fun add_term_pattern feature_of =
blanchet@50393
   562
      union (op = o pairself fst) o map feature_of oo patternify_term []
blanchet@50393
   563
    fun add_term_patterns _ ~1 _ = I
blanchet@50393
   564
      | add_term_patterns feature_of depth t =
blanchet@50393
   565
        add_term_pattern feature_of depth t
blanchet@50393
   566
        #> add_term_patterns feature_of (depth - 1) t
blanchet@50393
   567
    fun add_term feature_of = add_term_patterns feature_of term_max_depth
blanchet@48251
   568
    fun add_patterns t =
blanchet@48251
   569
      let val (head, args) = strip_comb t in
blanchet@48251
   570
        (case head of
blanchet@50393
   571
           Const (_, T) => add_term const_feature_of t #> add_type T
blanchet@50393
   572
         | Free (_, T) => add_term free_feature_of t #> add_type T
blanchet@48251
   573
         | Var (_, T) => add_type T
blanchet@48251
   574
         | Abs (_, T, body) => add_type T #> add_patterns body
blanchet@48251
   575
         | _ => I)
blanchet@48251
   576
        #> fold add_patterns args
blanchet@48251
   577
      end
blanchet@48326
   578
  in [] |> fold add_patterns ts end
blanchet@48251
   579
blanchet@48251
   580
fun is_exists (s, _) = (s = @{const_name Ex} orelse s = @{const_name Ex1})
blanchet@48251
   581
blanchet@50396
   582
val term_max_depth = 1
blanchet@50396
   583
val type_max_depth = 1
blanchet@48251
   584
blanchet@48251
   585
(* TODO: Generate type classes for types? *)
blanchet@48385
   586
fun features_of ctxt prover thy (scope, status) ts =
blanchet@50393
   587
  let val thy_name = Context.theory_name thy in
blanchet@50393
   588
    thy_feature_of thy_name ::
blanchet@50393
   589
    interesting_terms_types_and_classes ctxt thy_name prover term_max_depth
blanchet@50393
   590
        type_max_depth ts
blanchet@50393
   591
    |> status <> General ? cons (status_feature_of status)
blanchet@50393
   592
    |> scope <> Global ? cons local_feature
blanchet@50393
   593
    |> exists (not o is_lambda_free) ts ? cons lams_feature
blanchet@50393
   594
    |> exists (exists_Const is_exists) ts ? cons skos_feature
blanchet@50393
   595
  end
blanchet@48251
   596
blanchet@50434
   597
(* Too many dependencies is a sign that a decision procedure is at work. There
blanchet@50434
   598
   isn't much to learn from such proofs. *)
blanchet@50434
   599
val max_dependencies = 20
blanchet@50484
   600
blanchet@50484
   601
val prover_dependency_default_max_facts = 50
blanchet@48251
   602
blanchet@48438
   603
(* "type_definition_xxx" facts are characterized by their use of "CollectI". *)
blanchet@48441
   604
val typedef_deps = [@{thm CollectI} |> nickname_of]
blanchet@48438
   605
blanchet@48438
   606
(* "Rep_xxx_inject", "Abs_xxx_inverse", etc., are derived using these facts. *)
blanchet@48438
   607
val typedef_ths =
blanchet@48438
   608
  @{thms type_definition.Abs_inverse type_definition.Rep_inverse
blanchet@48438
   609
         type_definition.Rep type_definition.Rep_inject
blanchet@48438
   610
         type_definition.Abs_inject type_definition.Rep_cases
blanchet@48438
   611
         type_definition.Abs_cases type_definition.Rep_induct
blanchet@48438
   612
         type_definition.Abs_induct type_definition.Rep_range
blanchet@48438
   613
         type_definition.Abs_image}
blanchet@48438
   614
  |> map nickname_of
blanchet@48438
   615
blanchet@48441
   616
fun is_size_def [dep] th =
blanchet@48441
   617
    (case first_field ".recs" dep of
blanchet@48441
   618
       SOME (pref, _) =>
blanchet@48441
   619
       (case first_field ".size" (nickname_of th) of
blanchet@48441
   620
          SOME (pref', _) => pref = pref'
blanchet@48441
   621
        | NONE => false)
blanchet@48441
   622
     | NONE => false)
blanchet@48441
   623
  | is_size_def _ _ = false
blanchet@48441
   624
blanchet@48441
   625
fun trim_dependencies th deps =
blanchet@48668
   626
  if length deps > max_dependencies then
blanchet@48438
   627
    NONE
blanchet@48438
   628
  else
blanchet@48668
   629
    SOME (if deps = typedef_deps orelse
blanchet@48668
   630
             exists (member (op =) typedef_ths) deps orelse
blanchet@48668
   631
             is_size_def deps th then
blanchet@48668
   632
            []
blanchet@48668
   633
          else
blanchet@48668
   634
            deps)
blanchet@48251
   635
blanchet@48441
   636
fun isar_dependencies_of all_names th =
blanchet@48441
   637
  th |> thms_in_proof (SOME all_names) |> trim_dependencies th
blanchet@48404
   638
blanchet@50484
   639
fun prover_dependencies_of ctxt (params as {verbose, max_facts, ...}) prover
blanchet@50484
   640
                           auto_level facts all_names th =
blanchet@48392
   641
  case isar_dependencies_of all_names th of
blanchet@48665
   642
    SOME [] => (false, SOME [])
blanchet@48392
   643
  | isar_deps =>
blanchet@48392
   644
    let
blanchet@48392
   645
      val thy = Proof_Context.theory_of ctxt
blanchet@48392
   646
      val goal = goal_of_thm thy th
blanchet@48392
   647
      val (_, hyp_ts, concl_t) = ATP_Util.strip_subgoal ctxt goal 1
blanchet@48392
   648
      val facts = facts |> filter (fn (_, th') => thm_ord (th', th) = LESS)
blanchet@48392
   649
      fun fix_name ((_, stature), th) = ((fn () => nickname_of th, stature), th)
blanchet@48392
   650
      fun is_dep dep (_, th) = nickname_of th = dep
blanchet@48392
   651
      fun add_isar_dep facts dep accum =
blanchet@48392
   652
        if exists (is_dep dep) accum then
blanchet@48392
   653
          accum
blanchet@48392
   654
        else case find_first (is_dep dep) facts of
blanchet@48392
   655
          SOME ((name, status), th) => accum @ [((name, status), th)]
blanchet@48392
   656
        | NONE => accum (* shouldn't happen *)
blanchet@48392
   657
      val facts =
blanchet@50484
   658
        facts
blanchet@50484
   659
        |> mepo_suggested_facts ctxt params prover
blanchet@50484
   660
               (max_facts |> the_default prover_dependency_default_max_facts)
blanchet@50484
   661
               NONE hyp_ts concl_t
blanchet@50484
   662
        |> fold (add_isar_dep facts) (these isar_deps)
blanchet@50484
   663
        |> map fix_name
blanchet@48392
   664
    in
blanchet@48404
   665
      if verbose andalso auto_level = 0 then
blanchet@48392
   666
        let val num_facts = length facts in
blanchet@48392
   667
          "MaSh: " ^ quote prover ^ " on " ^ quote (nickname_of th) ^
blanchet@48392
   668
          " with " ^ string_of_int num_facts ^ " fact" ^ plural_s num_facts ^
blanchet@48392
   669
          "."
blanchet@48392
   670
          |> Output.urgent_message
blanchet@48392
   671
        end
blanchet@48392
   672
      else
blanchet@48392
   673
        ();
blanchet@48392
   674
      case run_prover_for_mash ctxt params prover facts goal of
blanchet@48392
   675
        {outcome = NONE, used_facts, ...} =>
blanchet@48404
   676
        (if verbose andalso auto_level = 0 then
blanchet@48392
   677
           let val num_facts = length used_facts in
blanchet@48392
   678
             "Found proof with " ^ string_of_int num_facts ^ " fact" ^
blanchet@48392
   679
             plural_s num_facts ^ "."
blanchet@48392
   680
             |> Output.urgent_message
blanchet@48392
   681
           end
blanchet@48392
   682
         else
blanchet@48392
   683
           ();
blanchet@48665
   684
         case used_facts |> map fst |> trim_dependencies th of
blanchet@48665
   685
           NONE => (false, isar_deps)
blanchet@50484
   686
         | prover_deps => (true, prover_deps))
blanchet@48665
   687
      | _ => (false, isar_deps)
blanchet@48392
   688
    end
blanchet@48251
   689
blanchet@48251
   690
blanchet@48251
   691
(*** High-level communication with MaSh ***)
blanchet@48251
   692
blanchet@48407
   693
fun num_keys keys = Graph.Keys.fold (K (Integer.add 1)) keys 0
blanchet@48400
   694
blanchet@48407
   695
fun maximal_in_graph fact_G facts =
blanchet@48316
   696
  let
blanchet@48378
   697
    val facts = [] |> fold (cons o nickname_of o snd) facts
blanchet@48407
   698
    val tab = Symtab.empty |> fold (fn name => Symtab.default (name, ())) facts
blanchet@48407
   699
    fun insert_new seen name =
blanchet@48407
   700
      not (Symtab.defined seen name) ? insert (op =) name
blanchet@48407
   701
    fun find_maxes _ (maxs, []) = map snd maxs
blanchet@48407
   702
      | find_maxes seen (maxs, new :: news) =
blanchet@48407
   703
        find_maxes
blanchet@48407
   704
            (seen |> num_keys (Graph.imm_succs fact_G new) > 1
blanchet@48407
   705
                     ? Symtab.default (new, ()))
blanchet@48407
   706
            (if Symtab.defined tab new then
blanchet@48407
   707
               let
blanchet@48407
   708
                 val newp = Graph.all_preds fact_G [new]
blanchet@48407
   709
                 fun is_ancestor x yp = member (op =) yp x
blanchet@48407
   710
                 val maxs =
blanchet@48407
   711
                   maxs |> filter (fn (_, max) => not (is_ancestor max newp))
blanchet@48407
   712
               in
blanchet@48407
   713
                 if exists (is_ancestor new o fst) maxs then
blanchet@48407
   714
                   (maxs, news)
blanchet@48407
   715
                 else
blanchet@48407
   716
                   ((newp, new)
blanchet@48407
   717
                    :: filter_out (fn (_, max) => is_ancestor max newp) maxs,
blanchet@48407
   718
                    news)
blanchet@48407
   719
               end
blanchet@48407
   720
             else
blanchet@48407
   721
               (maxs, Graph.Keys.fold (insert_new seen)
blanchet@48407
   722
                                      (Graph.imm_preds fact_G new) news))
blanchet@48407
   723
  in find_maxes Symtab.empty ([], Graph.maximals fact_G) end
blanchet@48316
   724
blanchet@48400
   725
fun is_fact_in_graph fact_G (_, th) =
blanchet@48400
   726
  can (Graph.get_node fact_G) (nickname_of th)
blanchet@48320
   727
blanchet@50383
   728
(* use MePo weights for now *)
blanchet@50383
   729
val weight_raw_mash_facts = weight_mepo_facts
blanchet@50383
   730
val weight_mash_facts = weight_raw_mash_facts
blanchet@50383
   731
blanchet@50383
   732
(* FUDGE *)
blanchet@50383
   733
fun weight_of_proximity_fact rank =
blanchet@50398
   734
  Math.pow (1.3, 15.5 - 0.2 * Real.fromInt rank) + 15.0
blanchet@50383
   735
blanchet@50383
   736
fun weight_proximity_facts facts =
blanchet@50383
   737
  facts ~~ map weight_of_proximity_fact (0 upto length facts - 1)
blanchet@50382
   738
blanchet@50440
   739
val max_proximity_facts = 100
blanchet@50440
   740
blanchet@50440
   741
fun find_mash_suggestions max_facts suggs facts chained raw_unknown =
blanchet@50412
   742
  let
blanchet@50412
   743
    val raw_mash =
blanchet@50412
   744
      facts |> find_suggested_facts suggs
blanchet@50412
   745
            (* The weights currently returned by "mash.py" are too spaced out to
blanchet@50412
   746
               make any sense. *)
blanchet@50412
   747
            |> map fst
blanchet@50440
   748
    val proximity =
blanchet@50440
   749
      facts |> sort (thm_ord o pairself snd o swap)
blanchet@50440
   750
            |> take max_proximity_facts
blanchet@50412
   751
    val mess =
blanchet@50435
   752
      [(0.80 (* FUDGE *), (map (rpair 1.0) chained, [])),
blanchet@50440
   753
       (0.16 (* FUDGE *), (weight_raw_mash_facts raw_mash, raw_unknown)),
blanchet@50435
   754
       (0.04 (* FUDGE *), (weight_proximity_facts proximity, []))]
blanchet@50440
   755
    val unknown =
blanchet@50440
   756
      raw_unknown
blanchet@50440
   757
      |> fold (subtract (Thm.eq_thm_prop o pairself snd)) [chained, proximity]
blanchet@50440
   758
  in (mesh_facts max_facts mess, unknown) end
blanchet@50412
   759
blanchet@48406
   760
fun mash_suggested_facts ctxt ({overlord, ...} : params) prover max_facts hyp_ts
blanchet@48406
   761
                         concl_t facts =
blanchet@48301
   762
  let
blanchet@48302
   763
    val thy = Proof_Context.theory_of ctxt
blanchet@48434
   764
    val (fact_G, suggs) =
blanchet@48699
   765
      mash_peek ctxt (fn {fact_G, ...} =>
blanchet@48434
   766
          if Graph.is_empty fact_G then
blanchet@48434
   767
            (fact_G, [])
blanchet@48434
   768
          else
blanchet@48434
   769
            let
blanchet@48434
   770
              val parents = maximal_in_graph fact_G facts
blanchet@48434
   771
              val feats =
blanchet@48434
   772
                features_of ctxt prover thy (Local, General) (concl_t :: hyp_ts)
blanchet@48434
   773
            in
blanchet@50383
   774
              (fact_G, mash_QUERY ctxt overlord max_facts (parents, feats))
blanchet@48434
   775
            end)
blanchet@50397
   776
    val chained = facts |> filter (fn ((_, (scope, _)), _) => scope = Chained)
blanchet@50383
   777
    val unknown = facts |> filter_out (is_fact_in_graph fact_G)
blanchet@50412
   778
  in find_mash_suggestions max_facts suggs facts chained unknown end
blanchet@48249
   779
blanchet@48668
   780
fun add_wrt_fact_graph ctxt (name, parents, feats, deps) (adds, graph) =
blanchet@48316
   781
  let
blanchet@48316
   782
    fun maybe_add_from from (accum as (parents, graph)) =
blanchet@48321
   783
      try_graph ctxt "updating graph" accum (fn () =>
blanchet@48321
   784
          (from :: parents, Graph.add_edge_acyclic (from, name) graph))
blanchet@48669
   785
    val graph = graph |> Graph.default_node (name, Isar_Proof)
blanchet@48316
   786
    val (parents, graph) = ([], graph) |> fold maybe_add_from parents
blanchet@48407
   787
    val (deps, _) = ([], graph) |> fold maybe_add_from deps
blanchet@48404
   788
  in ((name, parents, feats, deps) :: adds, graph) end
blanchet@48306
   789
blanchet@48668
   790
fun reprove_wrt_fact_graph ctxt (name, deps) (reps, graph) =
blanchet@48668
   791
  let
blanchet@48668
   792
    fun maybe_rep_from from (accum as (parents, graph)) =
blanchet@48668
   793
      try_graph ctxt "updating graph" accum (fn () =>
blanchet@48668
   794
          (from :: parents, Graph.add_edge_acyclic (from, name) graph))
blanchet@50484
   795
    val graph = graph |> update_fact_graph_node (name, Automatic_Proof)
blanchet@48668
   796
    val (deps, _) = ([], graph) |> fold maybe_rep_from deps
blanchet@48668
   797
  in ((name, deps) :: reps, graph) end
blanchet@48668
   798
blanchet@48669
   799
fun flop_wrt_fact_graph name =
blanchet@50484
   800
  update_fact_graph_node (name, Isar_Proof_wegen_Prover_Flop)
blanchet@48669
   801
blanchet@48384
   802
val learn_timeout_slack = 2.0
blanchet@48318
   803
blanchet@48384
   804
fun launch_thread timeout task =
blanchet@48383
   805
  let
blanchet@48384
   806
    val hard_timeout = time_mult learn_timeout_slack timeout
blanchet@48384
   807
    val birth_time = Time.now ()
blanchet@48384
   808
    val death_time = Time.+ (birth_time, hard_timeout)
blanchet@48442
   809
    val desc = ("Machine learner for Sledgehammer", "")
blanchet@48384
   810
  in Async_Manager.launch MaShN birth_time death_time desc task end
blanchet@48384
   811
blanchet@48400
   812
fun freshish_name () =
blanchet@48400
   813
  Date.fmt ".%Y_%m_%d_%H_%M_%S__" (Date.fromTimeLocal (Time.now ())) ^
blanchet@48400
   814
  serial_string ()
blanchet@48400
   815
blanchet@48384
   816
fun mash_learn_proof ctxt ({overlord, timeout, ...} : params) prover t facts
blanchet@48384
   817
                     used_ths =
blanchet@48384
   818
  if is_smt_prover ctxt prover then
blanchet@48384
   819
    ()
blanchet@48384
   820
  else
blanchet@48403
   821
    launch_thread timeout (fn () =>
blanchet@48403
   822
        let
blanchet@48403
   823
          val thy = Proof_Context.theory_of ctxt
blanchet@48403
   824
          val name = freshish_name ()
blanchet@48403
   825
          val feats = features_of ctxt prover thy (Local, General) [t]
blanchet@48403
   826
          val deps = used_ths |> map nickname_of
blanchet@48403
   827
        in
blanchet@48699
   828
          mash_peek ctxt (fn {fact_G, ...} =>
blanchet@48434
   829
              let val parents = maximal_in_graph fact_G facts in
blanchet@48434
   830
                mash_ADD ctxt overlord [(name, parents, feats, deps)]
blanchet@48434
   831
              end);
blanchet@48434
   832
          (true, "")
blanchet@48403
   833
        end)
blanchet@48383
   834
wenzelm@50450
   835
fun sendback sub = Active.sendback_markup (sledgehammerN ^ " " ^ sub)
blanchet@48392
   836
blanchet@48392
   837
val commit_timeout = seconds 30.0
blanchet@48332
   838
blanchet@50485
   839
(* The timeout is understood in a very relaxed fashion. *)
blanchet@48404
   840
fun mash_learn_facts ctxt (params as {debug, verbose, overlord, ...}) prover
blanchet@50484
   841
                     auto_level run_prover learn_timeout facts =
blanchet@48304
   842
  let
blanchet@48318
   843
    val timer = Timer.startRealTimer ()
blanchet@48392
   844
    fun next_commit_time () =
blanchet@48392
   845
      Time.+ (Timer.checkRealTimer timer, commit_timeout)
blanchet@48699
   846
    val {fact_G, ...} = mash_get ctxt
blanchet@50485
   847
    val facts = facts |> sort (thm_ord o pairself snd)
blanchet@48400
   848
    val (old_facts, new_facts) =
blanchet@48667
   849
      facts |> List.partition (is_fact_in_graph fact_G)
blanchet@48308
   850
  in
blanchet@50484
   851
    if null new_facts andalso (not run_prover orelse null old_facts) then
blanchet@48404
   852
      if auto_level < 2 then
blanchet@50484
   853
        "No new " ^ (if run_prover then "automatic" else "Isar") ^
blanchet@50484
   854
        " proofs to learn." ^
blanchet@50484
   855
        (if auto_level = 0 andalso not run_prover then
blanchet@50484
   856
           "\n\nHint: Try " ^ sendback learn_proverN ^
blanchet@50484
   857
           " to learn from automatic provers."
blanchet@48404
   858
         else
blanchet@48404
   859
           "")
blanchet@48392
   860
      else
blanchet@48392
   861
        ""
blanchet@48308
   862
    else
blanchet@48304
   863
      let
blanchet@50485
   864
        val all_names = build_all_names nickname_of facts
blanchet@48439
   865
        fun deps_of status th =
blanchet@48439
   866
          if status = Non_Rec_Def orelse status = Rec_Def then
blanchet@48439
   867
            SOME []
blanchet@50484
   868
          else if run_prover then
blanchet@50484
   869
            prover_dependencies_of ctxt params prover auto_level facts all_names
blanchet@50484
   870
                                   th
blanchet@48665
   871
            |> (fn (false, _) => NONE | (true, deps) => deps)
blanchet@48404
   872
          else
blanchet@48439
   873
            isar_dependencies_of all_names th
blanchet@48669
   874
        fun do_commit [] [] [] state = state
blanchet@48699
   875
          | do_commit adds reps flops {fact_G, dirty} =
blanchet@48392
   876
            let
blanchet@48699
   877
              val was_empty = Graph.is_empty fact_G
blanchet@48404
   878
              val (adds, fact_G) =
blanchet@48668
   879
                ([], fact_G) |> fold (add_wrt_fact_graph ctxt) adds
blanchet@48668
   880
              val (reps, fact_G) =
blanchet@48668
   881
                ([], fact_G) |> fold (reprove_wrt_fact_graph ctxt) reps
blanchet@48669
   882
              val fact_G = fact_G |> fold flop_wrt_fact_graph flops
blanchet@48699
   883
              val dirty =
blanchet@48699
   884
                case (was_empty, dirty, reps) of
blanchet@48699
   885
                  (false, SOME names, []) => SOME (map #1 adds @ names)
blanchet@48699
   886
                | _ => NONE
blanchet@48404
   887
            in
blanchet@48404
   888
              mash_ADD ctxt overlord (rev adds);
blanchet@48404
   889
              mash_REPROVE ctxt overlord reps;
blanchet@48699
   890
              {fact_G = fact_G, dirty = dirty}
blanchet@48404
   891
            end
blanchet@48669
   892
        fun commit last adds reps flops =
blanchet@48404
   893
          (if debug andalso auto_level = 0 then
blanchet@48404
   894
             Output.urgent_message "Committing..."
blanchet@48404
   895
           else
blanchet@48404
   896
             ();
blanchet@48669
   897
           mash_map ctxt (do_commit (rev adds) reps flops);
blanchet@48404
   898
           if not last andalso auto_level = 0 then
blanchet@48404
   899
             let val num_proofs = length adds + length reps in
blanchet@48404
   900
               "Learned " ^ string_of_int num_proofs ^ " " ^
blanchet@50484
   901
               (if run_prover then "automatic" else "Isar") ^ " proof" ^
blanchet@48404
   902
               plural_s num_proofs ^ " in the last " ^
blanchet@48392
   903
               string_from_time commit_timeout ^ "."
blanchet@48392
   904
               |> Output.urgent_message
blanchet@48392
   905
             end
blanchet@48392
   906
           else
blanchet@48392
   907
             ())
blanchet@48404
   908
        fun learn_new_fact _ (accum as (_, (_, _, _, true))) = accum
blanchet@48439
   909
          | learn_new_fact ((_, stature as (_, status)), th)
blanchet@48404
   910
                           (adds, (parents, n, next_commit, _)) =
blanchet@48318
   911
            let
blanchet@48378
   912
              val name = nickname_of th
blanchet@48332
   913
              val feats =
blanchet@48385
   914
                features_of ctxt prover (theory_of_thm th) stature [prop_of th]
blanchet@48439
   915
              val deps = deps_of status th |> these
blanchet@48394
   916
              val n = n |> not (null deps) ? Integer.add 1
blanchet@48404
   917
              val adds = (name, parents, feats, deps) :: adds
blanchet@48404
   918
              val (adds, next_commit) =
blanchet@48392
   919
                if Time.> (Timer.checkRealTimer timer, next_commit) then
blanchet@48669
   920
                  (commit false adds [] []; ([], next_commit_time ()))
blanchet@48392
   921
                else
blanchet@48404
   922
                  (adds, next_commit)
blanchet@48404
   923
              val timed_out = Time.> (Timer.checkRealTimer timer, learn_timeout)
blanchet@48404
   924
            in (adds, ([name], n, next_commit, timed_out)) end
blanchet@48404
   925
        val n =
blanchet@48404
   926
          if null new_facts then
blanchet@48404
   927
            0
blanchet@48404
   928
          else
blanchet@48404
   929
            let
blanchet@48404
   930
              val last_th = new_facts |> List.last |> snd
blanchet@48404
   931
              (* crude approximation *)
blanchet@48404
   932
              val ancestors =
blanchet@48404
   933
                old_facts
blanchet@48404
   934
                |> filter (fn (_, th) => thm_ord (th, last_th) <> GREATER)
blanchet@48407
   935
              val parents = maximal_in_graph fact_G ancestors
blanchet@48404
   936
              val (adds, (_, n, _, _)) =
blanchet@48404
   937
                ([], (parents, 0, next_commit_time (), false))
blanchet@48404
   938
                |> fold learn_new_fact new_facts
blanchet@48669
   939
            in commit true adds [] []; n end
blanchet@48404
   940
        fun relearn_old_fact _ (accum as (_, (_, _, true))) = accum
blanchet@48439
   941
          | relearn_old_fact ((_, (_, status)), th)
blanchet@48669
   942
                             ((reps, flops), (n, next_commit, _)) =
blanchet@48404
   943
            let
blanchet@48404
   944
              val name = nickname_of th
blanchet@48669
   945
              val (n, reps, flops) =
blanchet@48439
   946
                case deps_of status th of
blanchet@48669
   947
                  SOME deps => (n + 1, (name, deps) :: reps, flops)
blanchet@48669
   948
                | NONE => (n, reps, name :: flops)
blanchet@48669
   949
              val (reps, flops, next_commit) =
blanchet@48404
   950
                if Time.> (Timer.checkRealTimer timer, next_commit) then
blanchet@48669
   951
                  (commit false [] reps flops; ([], [], next_commit_time ()))
blanchet@48404
   952
                else
blanchet@48669
   953
                  (reps, flops, next_commit)
blanchet@48404
   954
              val timed_out = Time.> (Timer.checkRealTimer timer, learn_timeout)
blanchet@48669
   955
            in ((reps, flops), (n, next_commit, timed_out)) end
blanchet@48404
   956
        val n =
blanchet@50484
   957
          if not run_prover orelse null old_facts then
blanchet@48404
   958
            n
blanchet@48404
   959
          else
blanchet@48404
   960
            let
blanchet@48668
   961
              val max_isar = 1000 * max_dependencies
blanchet@48669
   962
              fun kind_of_proof th =
blanchet@48668
   963
                try (Graph.get_node fact_G) (nickname_of th)
blanchet@48669
   964
                |> the_default Isar_Proof
blanchet@48406
   965
              fun priority_of (_, th) =
blanchet@48668
   966
                random_range 0 max_isar
blanchet@48669
   967
                + (case kind_of_proof th of
blanchet@48669
   968
                     Isar_Proof => 0
blanchet@50484
   969
                   | Automatic_Proof => 2 * max_isar
blanchet@50484
   970
                   | Isar_Proof_wegen_Prover_Flop => max_isar)
blanchet@48404
   971
                - 500 * (th |> isar_dependencies_of all_names
blanchet@48404
   972
                            |> Option.map length
blanchet@48404
   973
                            |> the_default max_dependencies)
blanchet@48404
   974
              val old_facts =
blanchet@48406
   975
                old_facts |> map (`priority_of)
blanchet@48404
   976
                          |> sort (int_ord o pairself fst)
blanchet@48404
   977
                          |> map snd
blanchet@48669
   978
              val ((reps, flops), (n, _, _)) =
blanchet@48669
   979
                (([], []), (n, next_commit_time (), false))
blanchet@48404
   980
                |> fold relearn_old_fact old_facts
blanchet@48669
   981
            in commit true [] reps flops; n end
blanchet@48318
   982
      in
blanchet@48404
   983
        if verbose orelse auto_level < 2 then
blanchet@48404
   984
          "Learned " ^ string_of_int n ^ " nontrivial " ^
blanchet@50484
   985
          (if run_prover then "automatic" else "Isar") ^ " proof" ^ plural_s n ^
blanchet@48319
   986
          (if verbose then
blanchet@48319
   987
             " in " ^ string_from_time (Timer.checkRealTimer timer)
blanchet@48319
   988
           else
blanchet@48319
   989
             "") ^ "."
blanchet@48319
   990
        else
blanchet@48319
   991
          ""
blanchet@48318
   992
      end
blanchet@48308
   993
  end
blanchet@48304
   994
blanchet@48404
   995
fun mash_learn ctxt (params as {provers, timeout, ...}) fact_override chained
blanchet@50484
   996
               run_prover =
blanchet@48316
   997
  let
blanchet@48396
   998
    val css = Sledgehammer_Fact.clasimpset_rule_table_of ctxt
blanchet@48395
   999
    val ctxt = ctxt |> Config.put instantiate_inducts false
blanchet@48395
  1000
    val facts =
blanchet@48396
  1001
      nearly_all_facts ctxt false fact_override Symtab.empty css chained []
blanchet@48396
  1002
                       @{prop True}
blanchet@48404
  1003
    val num_facts = length facts
blanchet@48404
  1004
    val prover = hd provers
blanchet@50484
  1005
    fun learn auto_level run_prover =
blanchet@50484
  1006
      mash_learn_facts ctxt params prover auto_level run_prover infinite_timeout
blanchet@50484
  1007
                       facts
blanchet@48404
  1008
      |> Output.urgent_message
blanchet@48316
  1009
  in
blanchet@50484
  1010
    if run_prover then
blanchet@50340
  1011
      ("MaShing through " ^ string_of_int num_facts ^ " fact" ^
blanchet@50484
  1012
       plural_s num_facts ^ " for automatic proofs (" ^ quote prover ^
blanchet@50484
  1013
       " timeout: " ^ string_from_time timeout ^
blanchet@50484
  1014
       ").\n\nCollecting Isar proofs first..."
blanchet@50340
  1015
       |> Output.urgent_message;
blanchet@50340
  1016
       learn 1 false;
blanchet@50484
  1017
       "Now collecting automatic proofs. This may take several hours. You can \
blanchet@50340
  1018
       \safely stop the learning process at any point."
blanchet@50340
  1019
       |> Output.urgent_message;
blanchet@50340
  1020
       learn 0 true)
blanchet@50340
  1021
    else
blanchet@50340
  1022
      ("MaShing through " ^ string_of_int num_facts ^ " fact" ^
blanchet@50340
  1023
       plural_s num_facts ^ " for Isar proofs..."
blanchet@50340
  1024
       |> Output.urgent_message;
blanchet@50340
  1025
       learn 0 false)
blanchet@48316
  1026
  end
blanchet@48249
  1027
blanchet@50311
  1028
fun is_mash_enabled () = (getenv "MASH" = "yes")
blanchet@50311
  1029
fun mash_can_suggest_facts ctxt = not (Graph.is_empty (#fact_G (mash_get ctxt)))
blanchet@50311
  1030
blanchet@50383
  1031
(* Generate more suggestions than requested, because some might be thrown out
blanchet@50383
  1032
   later for various reasons. *)
blanchet@50383
  1033
fun generous_max_facts max_facts = max_facts + Int.min (50, max_facts)
blanchet@50383
  1034
blanchet@48318
  1035
(* The threshold should be large enough so that MaSh doesn't kick in for Auto
blanchet@48318
  1036
   Sledgehammer and Try. *)
blanchet@48318
  1037
val min_secs_for_learning = 15
blanchet@48318
  1038
blanchet@48321
  1039
fun relevant_facts ctxt (params as {learn, fact_filter, timeout, ...}) prover
blanchet@48321
  1040
        max_facts ({add, only, ...} : fact_override) hyp_ts concl_t facts =
blanchet@48314
  1041
  if not (subset (op =) (the_list fact_filter, fact_filters)) then
blanchet@48314
  1042
    error ("Unknown fact filter: " ^ quote (the fact_filter) ^ ".")
blanchet@48314
  1043
  else if only then
blanchet@48289
  1044
    facts
blanchet@48321
  1045
  else if max_facts <= 0 orelse null facts then
blanchet@48288
  1046
    []
blanchet@48288
  1047
  else
blanchet@48288
  1048
    let
blanchet@48327
  1049
      fun maybe_learn () =
blanchet@48384
  1050
        if learn andalso not (Async_Manager.has_running_threads MaShN) andalso
blanchet@48384
  1051
           Time.toSeconds timeout >= min_secs_for_learning then
blanchet@48384
  1052
          let val timeout = time_mult learn_timeout_slack timeout in
blanchet@48384
  1053
            launch_thread timeout
blanchet@48404
  1054
                (fn () => (true, mash_learn_facts ctxt params prover 2 false
blanchet@48392
  1055
                                                  timeout facts))
blanchet@48319
  1056
          end
blanchet@48318
  1057
        else
blanchet@48318
  1058
          ()
blanchet@48314
  1059
      val fact_filter =
blanchet@48314
  1060
        case fact_filter of
blanchet@48379
  1061
          SOME ff => (() |> ff <> mepoN ? maybe_learn; ff)
blanchet@48318
  1062
        | NONE =>
blanchet@48407
  1063
          if is_smt_prover ctxt prover then
blanchet@48407
  1064
            mepoN
blanchet@50229
  1065
          else if is_mash_enabled () then
blanchet@48407
  1066
            (maybe_learn ();
blanchet@48407
  1067
             if mash_can_suggest_facts ctxt then meshN else mepoN)
blanchet@48407
  1068
          else
blanchet@48407
  1069
            mepoN
blanchet@48288
  1070
      val add_ths = Attrib.eval_thms ctxt add
blanchet@48292
  1071
      fun prepend_facts ths accepts =
blanchet@48288
  1072
        ((facts |> filter (member Thm.eq_thm_prop ths o snd)) @
blanchet@48292
  1073
         (accepts |> filter_out (member Thm.eq_thm_prop ths o snd)))
blanchet@48293
  1074
        |> take max_facts
blanchet@48406
  1075
      fun mepo () =
blanchet@50382
  1076
        mepo_suggested_facts ctxt params prover max_facts NONE hyp_ts concl_t
blanchet@50382
  1077
                             facts
blanchet@50382
  1078
        |> weight_mepo_facts
blanchet@48314
  1079
      fun mash () =
blanchet@50383
  1080
        mash_suggested_facts ctxt params prover (generous_max_facts max_facts)
blanchet@50383
  1081
            hyp_ts concl_t facts
blanchet@50440
  1082
        |>> weight_mash_facts
blanchet@48314
  1083
      val mess =
blanchet@50383
  1084
        [] |> (if fact_filter <> mashN then cons (0.5, (mepo (), [])) else I)
blanchet@50440
  1085
           |> (if fact_filter <> mepoN then cons (0.5, (mash ())) else I)
blanchet@48288
  1086
    in
blanchet@48313
  1087
      mesh_facts max_facts mess
blanchet@48288
  1088
      |> not (null add_ths) ? prepend_facts add_ths
blanchet@48288
  1089
    end
blanchet@48288
  1090
blanchet@48319
  1091
fun kill_learners () = Async_Manager.kill_threads MaShN "learner"
blanchet@48319
  1092
fun running_learners () = Async_Manager.running_threads MaShN "learner"
blanchet@48319
  1093
blanchet@48248
  1094
end;