src/Pure/search.ML
author wenzelm
Tue Sep 26 20:54:40 2017 +0200 (21 months ago)
changeset 66695 91500c024c7f
parent 62919 9eb0359d6a77
permissions -rw-r--r--
tuned;
wenzelm@23178
     1
(*  Title:      Pure/search.ML
wenzelm@60940
     2
    Author:     Lawrence C Paulson
wenzelm@60940
     3
    Author:     Norbert Voelker, FernUniversitaet Hagen
paulson@1588
     4
wenzelm@16179
     5
Search tacticals.
paulson@1588
     6
*)
paulson@1588
     7
paulson@2672
     8
infix 1 THEN_MAYBE THEN_MAYBE';
paulson@2672
     9
paulson@1588
    10
signature SEARCH =
wenzelm@32940
    11
sig
wenzelm@32940
    12
  val DEPTH_FIRST: (thm -> bool) -> tactic -> tactic
wenzelm@32940
    13
  val has_fewer_prems: int -> thm -> bool
wenzelm@32940
    14
  val IF_UNSOLVED: tactic -> tactic
wenzelm@32940
    15
  val SOLVE: tactic -> tactic
wenzelm@32940
    16
  val THEN_MAYBE: tactic * tactic -> tactic
wenzelm@32940
    17
  val THEN_MAYBE': ('a -> tactic) * ('a -> tactic) -> 'a -> tactic
wenzelm@32940
    18
  val DEPTH_SOLVE: tactic -> tactic
wenzelm@32940
    19
  val DEPTH_SOLVE_1: tactic -> tactic
wenzelm@38802
    20
  val THEN_ITER_DEEPEN: int -> tactic -> (thm -> bool) -> (int -> tactic) -> tactic
wenzelm@38802
    21
  val ITER_DEEPEN: int -> (thm -> bool) -> (int -> tactic) -> tactic
wenzelm@32940
    22
  val DEEPEN: int * int -> (int -> int -> tactic) -> int -> int -> tactic
wenzelm@32940
    23
  val THEN_BEST_FIRST: tactic -> (thm -> bool) * (thm -> int) -> tactic -> tactic
wenzelm@32940
    24
  val BEST_FIRST: (thm -> bool) * (thm -> int) -> tactic -> tactic
wenzelm@32940
    25
  val BREADTH_FIRST: (thm -> bool) -> tactic -> tactic
wenzelm@32940
    26
  val QUIET_BREADTH_FIRST: (thm -> bool) -> tactic -> tactic
wenzelm@32940
    27
  val THEN_ASTAR: tactic -> (thm -> bool) * (int -> thm -> int) -> tactic -> tactic
wenzelm@32940
    28
  val ASTAR: (thm -> bool) * (int -> thm -> int) -> tactic -> tactic
wenzelm@32940
    29
end;
paulson@1588
    30
wenzelm@32940
    31
structure Search: SEARCH =
paulson@1588
    32
struct
paulson@1588
    33
paulson@1588
    34
(**** Depth-first search ****)
paulson@1588
    35
paulson@1588
    36
(*Searches until "satp" reports proof tree as satisfied.
paulson@1588
    37
  Suppresses duplicate solutions to minimize search space.*)
wenzelm@23178
    38
fun DEPTH_FIRST satp tac =
wenzelm@60940
    39
  let
wenzelm@60940
    40
    fun depth used [] = NONE
wenzelm@60940
    41
      | depth used (q :: qs) =
wenzelm@60940
    42
          (case Seq.pull q of
wenzelm@60940
    43
            NONE => depth used qs
wenzelm@60940
    44
          | SOME (st, stq) =>
wenzelm@60940
    45
              if satp st andalso not (member Thm.eq_thm used st) then
wenzelm@60940
    46
                SOME (st, Seq.make (fn() => depth (st :: used) (stq :: qs)))
wenzelm@60940
    47
              else depth used (tac st :: stq :: qs));
wenzelm@62916
    48
  in fn st => Seq.make (fn () => depth [] [Seq.single st]) end;
paulson@1588
    49
paulson@1588
    50
paulson@1588
    51
(*Predicate: Does the rule have fewer than n premises?*)
wenzelm@59582
    52
fun has_fewer_prems n rule = Thm.nprems_of rule < n;
paulson@1588
    53
paulson@1588
    54
(*Apply a tactic if subgoals remain, else do nothing.*)
paulson@1588
    55
val IF_UNSOLVED = COND (has_fewer_prems 1) all_tac;
paulson@1588
    56
oheimb@5754
    57
(*Force a tactic to solve its goal completely, otherwise fail *)
oheimb@5754
    58
fun SOLVE tac = tac THEN COND (has_fewer_prems 1) all_tac no_tac;
oheimb@5754
    59
paulson@2672
    60
(*Execute tac1, but only execute tac2 if there are at least as many subgoals
paulson@2672
    61
  as before.  This ensures that tac2 is only applied to an outcome of tac1.*)
wenzelm@23178
    62
fun (tac1 THEN_MAYBE tac2) st =
wenzelm@59582
    63
  (tac1 THEN COND (has_fewer_prems (Thm.nprems_of st)) all_tac tac2) st;
paulson@2672
    64
paulson@2672
    65
fun (tac1 THEN_MAYBE' tac2) x = tac1 x THEN_MAYBE tac2 x;
paulson@2672
    66
paulson@1588
    67
(*Tactical to reduce the number of premises by 1.
paulson@1588
    68
  If no subgoals then it must fail! *)
paulson@3538
    69
fun DEPTH_SOLVE_1 tac st = st |>
wenzelm@59582
    70
  (case Thm.nprems_of st of
wenzelm@59582
    71
    0 => no_tac
wenzelm@59582
    72
  | n => DEPTH_FIRST (has_fewer_prems n) tac);
paulson@1588
    73
paulson@1588
    74
(*Uses depth-first search to solve ALL subgoals*)
paulson@1588
    75
val DEPTH_SOLVE = DEPTH_FIRST (has_fewer_prems 1);
paulson@1588
    76
paulson@1588
    77
paulson@1588
    78
paulson@2869
    79
(**** Iterative deepening with pruning ****)
paulson@1588
    80
paulson@1588
    81
fun has_vars (Var _) = true
wenzelm@60940
    82
  | has_vars (Abs (_, _, t)) = has_vars t
wenzelm@60940
    83
  | has_vars (f $ t) = has_vars f orelse has_vars t
paulson@1588
    84
  | has_vars _ = false;
paulson@1588
    85
paulson@1588
    86
(*Counting of primitive inferences is APPROXIMATE, as the step tactic
paulson@1588
    87
  may perform >1 inference*)
paulson@1588
    88
paulson@1588
    89
(*Pruning of rigid ancestor to prevent backtracking*)
wenzelm@23178
    90
fun prune (new as (k', np':int, rgd', stq), qs) =
wenzelm@60940
    91
  let
wenzelm@60940
    92
    fun prune_aux (qs, []) = new :: qs
wenzelm@60940
    93
      | prune_aux (qs, (k, np, rgd, q) :: rqs) =
wenzelm@60940
    94
          if np' + 1 = np andalso rgd then
wenzelm@60940
    95
             (*Use OLD k: zero-cost solution; see Stickel, p 365*)
wenzelm@62916
    96
             (k, np', rgd', stq) :: qs
wenzelm@60940
    97
          else prune_aux ((k, np, rgd, q) :: qs, rqs)
wenzelm@60940
    98
      fun take ([], rqs) = ([], rqs)
wenzelm@60940
    99
        | take (arg as ((k, np, rgd, stq) :: qs, rqs)) =
wenzelm@60940
   100
            if np' < np then take (qs, (k, np, rgd, stq) :: rqs) else arg;
wenzelm@60940
   101
  in prune_aux (take (qs, [])) end;
paulson@1588
   102
paulson@1588
   103
paulson@1588
   104
(*Depth-first iterative deepening search for a state that satisfies satp
paulson@1588
   105
  tactic tac0 sets up the initial goal queue, while tac1 searches it.
paulson@1588
   106
  The solution sequence is redundant: the cutoff heuristic makes it impossible
paulson@1588
   107
  to suppress solutions arising from earlier searches, as the accumulated cost
paulson@1588
   108
  (k) can be wrong.*)
wenzelm@62916
   109
fun THEN_ITER_DEEPEN lim tac0 satp tac1 st =
wenzelm@60940
   110
  let
wenzelm@62919
   111
    val counter = Unsynchronized.ref 0
wenzelm@62916
   112
    and tf = tac1 1
wenzelm@60940
   113
    and qs0 = tac0 st
paulson@1588
   114
     (*bnd = depth bound; inc = estimate of increment required next*)
wenzelm@60940
   115
    fun depth (bnd, inc) [] =
wenzelm@62916
   116
          if bnd > lim then NONE
paulson@22025
   117
          else
wenzelm@60940
   118
            (*larger increments make it run slower for the hard problems*)
wenzelm@62916
   119
            depth (bnd + inc, 10) [(0, 1, false, qs0)]
wenzelm@60940
   120
      | depth (bnd, inc) ((k, np, rgd, q) :: qs) =
wenzelm@60940
   121
          if k >= bnd then depth (bnd, inc) qs
paulson@1588
   122
          else
wenzelm@62919
   123
           (case (Unsynchronized.inc counter; Seq.pull q) of
wenzelm@60940
   124
             NONE => depth (bnd, inc) qs
wenzelm@60940
   125
           | SOME (st, stq) =>
wenzelm@60940
   126
              if satp st then (*solution!*)
wenzelm@60940
   127
                SOME(st, Seq.make (fn() => depth (bnd, inc) ((k, np, rgd, stq) :: qs)))
wenzelm@60940
   128
              else
wenzelm@60940
   129
                let
wenzelm@60940
   130
                  val np' = Thm.nprems_of st;
wenzelm@60940
   131
                  (*rgd' calculation assumes tactic operates on subgoal 1*)
wenzelm@60940
   132
                  val rgd' = not (has_vars (hd (Thm.prems_of st)));
wenzelm@60940
   133
                  val k' = k + np' - np + 1;  (*difference in # of subgoals, +1*)
wenzelm@60940
   134
                in
wenzelm@60940
   135
                  if k' + np' >= bnd then depth (bnd, Int.min (inc, k' + np' + 1 - bnd)) qs
wenzelm@60940
   136
                  else if np' < np (*solved a subgoal; prune rigid ancestors*)
wenzelm@60940
   137
                  then depth (bnd, inc) (prune ((k', np', rgd', tf st), (k, np, rgd, stq) :: qs))
wenzelm@60940
   138
                  else depth (bnd, inc) ((k', np', rgd', tf st) :: (k, np, rgd, stq) :: qs)
wenzelm@60940
   139
                end)
wenzelm@62916
   140
  in Seq.make (fn () => depth (0, 5) []) end;
paulson@1588
   141
wenzelm@38802
   142
fun ITER_DEEPEN lim = THEN_ITER_DEEPEN lim all_tac;
paulson@1588
   143
paulson@1588
   144
paulson@2869
   145
(*Simple iterative deepening tactical.  It merely "deepens" any search tactic
paulson@2869
   146
  using increment "inc" up to limit "lim". *)
wenzelm@38802
   147
fun DEEPEN (inc, lim) tacf m i =
wenzelm@33380
   148
  let
wenzelm@33380
   149
    fun dpn m st =
wenzelm@33380
   150
      st |>
wenzelm@33380
   151
       (if has_fewer_prems i st then no_tac
wenzelm@62916
   152
        else if m > lim then no_tac
wenzelm@62916
   153
        else tacf m i  ORELSE  dpn (m+inc))
paulson@2869
   154
  in  dpn m  end;
wenzelm@23178
   155
wenzelm@32940
   156
paulson@1588
   157
(*** Best-first search ***)
paulson@1588
   158
wenzelm@32940
   159
(*total ordering on theorems, allowing duplicates to be found*)
wenzelm@32940
   160
structure Thm_Heap = Heap
wenzelm@32940
   161
(
wenzelm@32940
   162
  type elem = int * thm;
wenzelm@59058
   163
  val ord = prod_ord int_ord (Term_Ord.term_ord o apply2 Thm.prop_of);
wenzelm@32940
   164
);
wenzelm@32940
   165
paulson@1588
   166
(*For creating output sequence*)
wenzelm@60940
   167
fun some_of_list [] = NONE
wenzelm@60940
   168
  | some_of_list (x :: l) = SOME (x, Seq.make (fn () => some_of_list l));
paulson@1588
   169
paulson@9094
   170
(*Check for and delete duplicate proof states*)
wenzelm@32940
   171
fun delete_all_min prf heap =
wenzelm@32940
   172
  if Thm_Heap.is_empty heap then heap
wenzelm@32940
   173
  else if Thm.eq_thm (prf, #2 (Thm_Heap.min heap))
wenzelm@32940
   174
  then delete_all_min prf (Thm_Heap.delete_min heap)
wenzelm@32940
   175
  else heap;
paulson@1588
   176
paulson@1588
   177
(*Best-first search for a state that satisfies satp (incl initial state)
paulson@1588
   178
  Function sizef estimates size of problem remaining (smaller means better).
paulson@1588
   179
  tactic tac0 sets up the initial priority queue, while tac1 searches it. *)
wenzelm@62916
   180
fun THEN_BEST_FIRST tac0 (satp, sizef) tac =
wenzelm@60940
   181
  let
wenzelm@60940
   182
    fun pairsize th = (sizef th, th);
wenzelm@60940
   183
    fun bfs (news, nprf_heap) =
wenzelm@60940
   184
      (case List.partition satp news of
wenzelm@60940
   185
        ([], nonsats) => next (fold_rev Thm_Heap.insert (map pairsize nonsats) nprf_heap)
wenzelm@60940
   186
      | (sats, _)  => some_of_list sats)
wenzelm@60940
   187
    and next nprf_heap =
wenzelm@60940
   188
      if Thm_Heap.is_empty nprf_heap then NONE
wenzelm@60940
   189
      else
wenzelm@60940
   190
        let
wenzelm@60940
   191
          val (n, prf) = Thm_Heap.min nprf_heap;
wenzelm@60940
   192
        in
wenzelm@60940
   193
          bfs (Seq.list_of (tac prf), delete_all_min prf (Thm_Heap.delete_min nprf_heap))
wenzelm@60940
   194
        end;
wenzelm@60940
   195
    fun btac st = bfs (Seq.list_of (tac0 st), Thm_Heap.empty)
wenzelm@62916
   196
  in fn st => Seq.make (fn () => btac st) end;
paulson@1588
   197
paulson@1588
   198
(*Ordinary best-first search, with no initial tactic*)
paulson@1588
   199
val BEST_FIRST = THEN_BEST_FIRST all_tac;
paulson@1588
   200
wenzelm@23178
   201
(*Breadth-first search to satisfy satpred (including initial state)
paulson@1588
   202
  SLOW -- SHOULD NOT USE APPEND!*)
wenzelm@60940
   203
fun gen_BREADTH_FIRST message satpred (tac: tactic) =
wenzelm@60940
   204
  let
wenzelm@60940
   205
    val tacf = Seq.list_of o tac;
wenzelm@60940
   206
    fun bfs prfs =
wenzelm@60940
   207
      (case List.partition satpred prfs of
wenzelm@60940
   208
        ([], []) => []
wenzelm@60940
   209
      | ([], nonsats) =>
wenzelm@60940
   210
          (message ("breadth=" ^ string_of_int (length nonsats));
wenzelm@60940
   211
           bfs (maps tacf nonsats))
wenzelm@60940
   212
      | (sats, _)  => sats);
wenzelm@60940
   213
  in fn st => Seq.of_list (bfs [st]) end;
paulson@1588
   214
wenzelm@12262
   215
val BREADTH_FIRST = gen_BREADTH_FIRST tracing;
wenzelm@5693
   216
val QUIET_BREADTH_FIRST = gen_BREADTH_FIRST (K ());
wenzelm@5693
   217
paulson@1588
   218
wenzelm@60940
   219
(*
wenzelm@60940
   220
  Implementation of A*-like proof procedure by modification
wenzelm@60940
   221
  of the existing code for BEST_FIRST and best_tac so that the
wenzelm@60940
   222
  current level of search is taken into account.
wenzelm@23178
   223
*)
paulson@1588
   224
wenzelm@60940
   225
(*Insertion into priority queue of states, marked with level*)
wenzelm@60940
   226
fun insert_with_level (lnth: int * int * thm) [] = [lnth]
wenzelm@60940
   227
  | insert_with_level (l, m, th) ((l', n, th') :: nths) =
wenzelm@60940
   228
      if  n < m then (l', n, th') :: insert_with_level (l, m, th) nths
wenzelm@60940
   229
      else if n = m andalso Thm.eq_thm (th, th') then (l', n, th') :: nths
wenzelm@60940
   230
      else (l, m, th) :: (l', n, th') :: nths;
paulson@1588
   231
paulson@1588
   232
(*For creating output sequence*)
wenzelm@60940
   233
fun some_of_list [] = NONE
wenzelm@60940
   234
  | some_of_list (x :: xs) = SOME (x, Seq.make (fn () => some_of_list xs));
paulson@1588
   235
wenzelm@62916
   236
fun THEN_ASTAR tac0 (satp, costf) tac =
wenzelm@60940
   237
  let
wenzelm@60940
   238
    fun bfs (news, nprfs, level) =
wenzelm@60940
   239
      let fun cost thm = (level, costf level thm, thm) in
wenzelm@60940
   240
        (case List.partition satp news of
wenzelm@60940
   241
          ([], nonsats) => next (fold_rev (insert_with_level o cost) nonsats nprfs)
wenzelm@60940
   242
        | (sats, _) => some_of_list sats)
wenzelm@60940
   243
      end
wenzelm@60940
   244
    and next [] = NONE
wenzelm@62916
   245
      | next ((level, n, prf) :: nprfs) = bfs (Seq.list_of (tac prf), nprfs, level + 1)
wenzelm@62916
   246
  in fn st => Seq.make (fn () => bfs (Seq.list_of (tac0 st), [], 0)) end;
paulson@1588
   247
paulson@1588
   248
(*Ordinary ASTAR, with no initial tactic*)
paulson@1588
   249
val ASTAR = THEN_ASTAR all_tac;
paulson@1588
   250
paulson@1588
   251
end;
paulson@1588
   252
paulson@1588
   253
open Search;