src/Pure/search.ML
author paulson
Fri Nov 01 15:15:39 1996 +0100 (1996-11-01)
changeset 2143 093bbe6d333b
parent 1588 fff3738830f5
child 2672 85d7e800d754
permissions -rw-r--r--
Replaced min by Int.min
paulson@1588
     1
(*  Title: 	search
paulson@1588
     2
    ID:         $Id$
paulson@1588
     3
    Author: 	Lawrence C Paulson and Norbert Voelker
paulson@1588
     4
paulson@1588
     5
Search tacticals
paulson@1588
     6
*)
paulson@1588
     7
paulson@1588
     8
signature SEARCH =
paulson@1588
     9
  sig
paulson@1588
    10
  val trace_DEPTH_FIRST	: bool ref
paulson@1588
    11
  val DEPTH_FIRST	: (thm -> bool) -> tactic -> tactic
paulson@1588
    12
  val DEPTH_SOLVE	: tactic -> tactic
paulson@1588
    13
  val DEPTH_SOLVE_1	: tactic -> tactic
paulson@1588
    14
  val ITER_DEEPEN	: (thm->bool) -> (int->tactic) -> tactic
paulson@1588
    15
  val THEN_ITER_DEEPEN	: tactic -> (thm->bool) -> (int->tactic) -> tactic
paulson@1588
    16
paulson@1588
    17
  val has_fewer_prems	: int -> thm -> bool   
paulson@1588
    18
  val IF_UNSOLVED	: tactic -> tactic
paulson@1588
    19
  val trace_BEST_FIRST	: bool ref
paulson@1588
    20
  val BEST_FIRST	: (thm -> bool) * (thm -> int) -> tactic -> tactic
paulson@1588
    21
  val THEN_BEST_FIRST	: tactic -> (thm->bool) * (thm->int) -> tactic
paulson@1588
    22
			  -> tactic
paulson@1588
    23
  val trace_ASTAR	: bool ref
paulson@1588
    24
  val ASTAR	        : (thm -> bool) * (int->thm->int) -> tactic -> tactic
paulson@1588
    25
  val THEN_ASTAR	: tactic -> (thm->bool) * (int->thm->int) -> tactic
paulson@1588
    26
			  -> tactic
paulson@1588
    27
  val BREADTH_FIRST	: (thm -> bool) -> tactic -> tactic
paulson@1588
    28
  end;
paulson@1588
    29
paulson@1588
    30
structure Search : SEARCH = 
paulson@1588
    31
struct
paulson@1588
    32
paulson@1588
    33
(**** Depth-first search ****)
paulson@1588
    34
paulson@1588
    35
val trace_DEPTH_FIRST = ref false;
paulson@1588
    36
paulson@1588
    37
(*Searches until "satp" reports proof tree as satisfied.
paulson@1588
    38
  Suppresses duplicate solutions to minimize search space.*)
paulson@1588
    39
fun DEPTH_FIRST satp tac = 
paulson@1588
    40
 let val tac = tracify trace_DEPTH_FIRST tac
paulson@1588
    41
     fun depth used [] = None
paulson@1588
    42
       | depth used (q::qs) =
paulson@1588
    43
	  case Sequence.pull q of
paulson@1588
    44
	      None         => depth used qs
paulson@1588
    45
	    | Some(st,stq) => 
paulson@1588
    46
		if satp st andalso not (gen_mem eq_thm (st, used))
paulson@1588
    47
		then Some(st, Sequence.seqof
paulson@1588
    48
			         (fn()=> depth (st::used) (stq::qs)))
paulson@1588
    49
		else depth used (tac st :: stq :: qs)
paulson@1588
    50
  in  traced_tac (fn st => depth [] ([Sequence.single st]))  end;
paulson@1588
    51
paulson@1588
    52
paulson@1588
    53
paulson@1588
    54
(*Predicate: Does the rule have fewer than n premises?*)
paulson@1588
    55
fun has_fewer_prems n rule = (nprems_of rule < n);
paulson@1588
    56
paulson@1588
    57
(*Apply a tactic if subgoals remain, else do nothing.*)
paulson@1588
    58
val IF_UNSOLVED = COND (has_fewer_prems 1) all_tac;
paulson@1588
    59
paulson@1588
    60
(*Tactical to reduce the number of premises by 1.
paulson@1588
    61
  If no subgoals then it must fail! *)
paulson@1588
    62
fun DEPTH_SOLVE_1 tac = STATE
paulson@1588
    63
 (fn st => 
paulson@1588
    64
    (case nprems_of st of
paulson@1588
    65
	0 => no_tac
paulson@1588
    66
      | n => DEPTH_FIRST (has_fewer_prems n) tac));
paulson@1588
    67
paulson@1588
    68
(*Uses depth-first search to solve ALL subgoals*)
paulson@1588
    69
val DEPTH_SOLVE = DEPTH_FIRST (has_fewer_prems 1);
paulson@1588
    70
paulson@1588
    71
paulson@1588
    72
paulson@1588
    73
(**** Iterative deepening ****)
paulson@1588
    74
paulson@1588
    75
fun has_vars (Var _) = true
paulson@1588
    76
  | has_vars (Abs (_,_,t)) = has_vars t
paulson@1588
    77
  | has_vars (f$t) = has_vars f orelse has_vars t
paulson@1588
    78
  | has_vars _ = false;
paulson@1588
    79
paulson@1588
    80
(*Counting of primitive inferences is APPROXIMATE, as the step tactic
paulson@1588
    81
  may perform >1 inference*)
paulson@1588
    82
paulson@1588
    83
(*Pruning of rigid ancestor to prevent backtracking*)
paulson@1588
    84
fun prune (new as (k', np':int, rgd', stq), qs) = 
paulson@1588
    85
    let fun prune_aux (qs, []) = new::qs
paulson@1588
    86
          | prune_aux (qs, (k,np,rgd,q)::rqs) =
paulson@1588
    87
	      if np'+1 = np andalso rgd then
paulson@1588
    88
		  (if !trace_DEPTH_FIRST then
paulson@1588
    89
		       writeln ("Pruning " ^ 
paulson@1588
    90
				string_of_int (1+length rqs) ^ " levels")
paulson@1588
    91
		   else ();
paulson@1588
    92
		   (*Use OLD k: zero-cost solution; see Stickel, p 365*)
paulson@1588
    93
		   (k, np', rgd', stq) :: qs)
paulson@1588
    94
	      else prune_aux ((k,np,rgd,q)::qs, rqs)
paulson@1588
    95
        fun take ([], rqs) = ([], rqs)
paulson@1588
    96
	  | take (arg as ((k,np,rgd,stq)::qs, rqs)) = 
paulson@1588
    97
	        if np' < np then take (qs, (k,np,rgd,stq)::rqs)
paulson@1588
    98
		            else arg
paulson@1588
    99
    in  prune_aux (take (qs, []))  end;
paulson@1588
   100
paulson@1588
   101
paulson@1588
   102
(*Depth-first iterative deepening search for a state that satisfies satp
paulson@1588
   103
  tactic tac0 sets up the initial goal queue, while tac1 searches it.
paulson@1588
   104
  The solution sequence is redundant: the cutoff heuristic makes it impossible
paulson@1588
   105
  to suppress solutions arising from earlier searches, as the accumulated cost
paulson@1588
   106
  (k) can be wrong.*)
paulson@1588
   107
fun THEN_ITER_DEEPEN tac0 satp tac1 = traced_tac (fn st => 
paulson@1588
   108
 let val countr = ref 0
paulson@1588
   109
     and tf = tracify trace_DEPTH_FIRST (tac1 1)
paulson@1588
   110
     and qs0 = tac0 st
paulson@1588
   111
     (*bnd = depth bound; inc = estimate of increment required next*)
paulson@1588
   112
     fun depth (bnd,inc) [] = 
paulson@1588
   113
	     (writeln (string_of_int (!countr) ^ 
paulson@1588
   114
		       " inferences so far.  Searching to depth " ^ 
paulson@1588
   115
		       string_of_int bnd);
paulson@1588
   116
	      (*larger increments make it run slower for the hard problems*)
paulson@1588
   117
	      depth (bnd+inc, 10)) [(0, 1, false, qs0)]
paulson@1588
   118
       | depth (bnd,inc) ((k,np,rgd,q)::qs) =
paulson@1588
   119
	  if k>=bnd then depth (bnd,inc) qs
paulson@1588
   120
          else
paulson@1588
   121
	  case (countr := !countr+1;
paulson@1588
   122
		if !trace_DEPTH_FIRST then
paulson@1588
   123
		    writeln (string_of_int np ^ 
paulson@1588
   124
			     implode (map (fn _ => "*") qs))
paulson@1588
   125
		else ();
paulson@1588
   126
		Sequence.pull q) of
paulson@1588
   127
	     None         => depth (bnd,inc) qs
paulson@1588
   128
	   | Some(st,stq) => 
paulson@1588
   129
	       if satp st	(*solution!*)
paulson@1588
   130
	       then Some(st, Sequence.seqof
paulson@1588
   131
			 (fn()=> depth (bnd,inc) ((k,np,rgd,stq)::qs)))
paulson@1588
   132
paulson@1588
   133
	       else 
paulson@1588
   134
               let val np' = nprems_of st
paulson@1588
   135
		     (*rgd' calculation assumes tactic operates on subgoal 1*)
paulson@1588
   136
                   val rgd' = not (has_vars (hd (prems_of st)))
paulson@1588
   137
                   val k' = k+np'-np+1  (*difference in # of subgoals, +1*)
paulson@1588
   138
               in  if k'+np' >= bnd 
paulson@2143
   139
		   then depth (bnd, Int.min(inc, k'+np'+1-bnd)) qs
paulson@1588
   140
		   else if np' < np (*solved a subgoal; prune rigid ancestors*)
paulson@1588
   141
                   then depth (bnd,inc) 
paulson@1588
   142
		         (prune ((k', np', rgd', tf st), (k,np,rgd,stq) :: qs))
paulson@1588
   143
	           else depth (bnd,inc) ((k', np', rgd', tf st) :: 
paulson@1588
   144
					 (k,np,rgd,stq) :: qs)
paulson@1588
   145
	       end
paulson@1588
   146
  in depth (0,5) [] end);
paulson@1588
   147
paulson@1588
   148
val ITER_DEEPEN = THEN_ITER_DEEPEN all_tac;
paulson@1588
   149
paulson@1588
   150
paulson@1588
   151
(*** Best-first search ***)
paulson@1588
   152
paulson@1588
   153
val trace_BEST_FIRST = ref false;
paulson@1588
   154
paulson@1588
   155
(*Insertion into priority queue of states *)
paulson@1588
   156
fun insert (nth: int*thm, []) = [nth]
paulson@1588
   157
  | insert ((m,th), (n,th')::nths) = 
paulson@1588
   158
      if  n<m then (n,th') :: insert ((m,th), nths)
paulson@1588
   159
      else if  n=m andalso eq_thm(th,th')
paulson@1588
   160
              then (n,th')::nths
paulson@1588
   161
              else (m,th)::(n,th')::nths;
paulson@1588
   162
paulson@1588
   163
(*For creating output sequence*)
paulson@1588
   164
fun some_of_list []     = None
paulson@1588
   165
  | some_of_list (x::l) = Some (x, Sequence.seqof (fn () => some_of_list l));
paulson@1588
   166
paulson@1588
   167
paulson@1588
   168
(*Best-first search for a state that satisfies satp (incl initial state)
paulson@1588
   169
  Function sizef estimates size of problem remaining (smaller means better).
paulson@1588
   170
  tactic tac0 sets up the initial priority queue, while tac1 searches it. *)
paulson@1588
   171
fun THEN_BEST_FIRST tac0 (satp, sizef) tac1 = 
paulson@1588
   172
  let val tac = tracify trace_BEST_FIRST tac1
paulson@1588
   173
      fun pairsize th = (sizef th, th);
paulson@1588
   174
      fun bfs (news,nprfs) =
paulson@1588
   175
	   (case  partition satp news  of
paulson@1588
   176
		([],nonsats) => next(foldr insert
paulson@1588
   177
					(map pairsize nonsats, nprfs)) 
paulson@1588
   178
	      | (sats,_)  => some_of_list sats)
paulson@1588
   179
      and next [] = None
paulson@1588
   180
        | next ((n,prf)::nprfs) =
paulson@1588
   181
	    (if !trace_BEST_FIRST 
paulson@1588
   182
	       then writeln("state size = " ^ string_of_int n ^ 
paulson@1588
   183
		         "  queue length =" ^ string_of_int (length nprfs))  
paulson@1588
   184
               else ();
paulson@1588
   185
	     bfs (Sequence.list_of_s (tac prf), nprfs))
paulson@1588
   186
      fun btac st = bfs (Sequence.list_of_s (tac0 st),  [])
paulson@1588
   187
  in traced_tac btac end;
paulson@1588
   188
paulson@1588
   189
(*Ordinary best-first search, with no initial tactic*)
paulson@1588
   190
val BEST_FIRST = THEN_BEST_FIRST all_tac;
paulson@1588
   191
paulson@1588
   192
(*Breadth-first search to satisfy satpred (including initial state) 
paulson@1588
   193
  SLOW -- SHOULD NOT USE APPEND!*)
paulson@1588
   194
fun BREADTH_FIRST satpred tac = 
paulson@1588
   195
  let val tacf = Sequence.list_of_s o tac;
paulson@1588
   196
      fun bfs prfs =
paulson@1588
   197
	 (case  partition satpred prfs  of
paulson@1588
   198
	      ([],[]) => []
paulson@1588
   199
	    | ([],nonsats) => 
paulson@1588
   200
		  (prs("breadth=" ^ string_of_int(length nonsats) ^ "\n");
paulson@1588
   201
		   bfs (flat (map tacf nonsats)))
paulson@1588
   202
	    | (sats,_)  => sats)
paulson@1588
   203
  in (fn st => Sequence.s_of_list (bfs [st])) end;
paulson@1588
   204
paulson@1588
   205
paulson@1588
   206
(*  Author: 	Norbert Voelker, FernUniversitaet Hagen
paulson@1588
   207
    Remarks:    Implementation of A*-like proof procedure by modification
paulson@1588
   208
		of the existing code for BEST_FIRST and best_tac so that the 
paulson@1588
   209
		current level of search is taken into account.
paulson@1588
   210
*)		
paulson@1588
   211
paulson@1588
   212
(*Insertion into priority queue of states, marked with level *)
paulson@1588
   213
fun insert_with_level (lnth: int*int*thm, []) = [lnth]
paulson@1588
   214
  | insert_with_level ((l,m,th), (l',n,th')::nths) = 
paulson@1588
   215
      if  n<m then (l',n,th') :: insert_with_level ((l,m,th), nths)
paulson@1588
   216
      else if  n=m andalso eq_thm(th,th')
paulson@1588
   217
              then (l',n,th')::nths
paulson@1588
   218
              else (l,m,th)::(l',n,th')::nths;
paulson@1588
   219
paulson@1588
   220
(*For creating output sequence*)
paulson@1588
   221
fun some_of_list []     = None
paulson@1588
   222
  | some_of_list (x::l) = Some (x, Sequence.seqof (fn () => some_of_list l));
paulson@1588
   223
paulson@1588
   224
val trace_ASTAR = ref false; 
paulson@1588
   225
paulson@1588
   226
fun THEN_ASTAR tac0 (satp, costf) tac1 = 
paulson@1588
   227
  let val tf = tracify trace_ASTAR tac1;   
paulson@1588
   228
      fun bfs (news,nprfs,level) =
paulson@1588
   229
      let fun cost thm = (level, costf level thm, thm)
paulson@1588
   230
      in (case  partition satp news  of
paulson@1588
   231
            ([],nonsats) 
paulson@1588
   232
		 => next (foldr insert_with_level (map cost nonsats, nprfs))
paulson@1588
   233
          | (sats,_)  => some_of_list sats)
paulson@1588
   234
      end and    
paulson@1588
   235
      next []  = None
paulson@1588
   236
        | next ((level,n,prf)::nprfs)  =
paulson@1588
   237
            (if !trace_ASTAR 
paulson@1588
   238
               then writeln("level = " ^ string_of_int level ^
paulson@1588
   239
			 "  cost = " ^ string_of_int n ^ 
paulson@1588
   240
                         "  queue length =" ^ string_of_int (length nprfs))  
paulson@1588
   241
               else ();
paulson@1588
   242
             bfs (Sequence.list_of_s (tf prf), nprfs,level+1))
paulson@1588
   243
      fun tf st = bfs (Sequence.list_of_s (tac0 st), [], 0)
paulson@1588
   244
  in traced_tac tf end;
paulson@1588
   245
paulson@1588
   246
(*Ordinary ASTAR, with no initial tactic*)
paulson@1588
   247
val ASTAR = THEN_ASTAR all_tac;
paulson@1588
   248
paulson@1588
   249
end;
paulson@1588
   250
paulson@1588
   251
open Search;