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