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