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