src/Pure/search.ML
changeset 5693 998af7667fa3
parent 4270 957c887b89b5
child 5754 98744e38ded1
equal deleted inserted replaced
5692:2e873c5f0e2c 5693:998af7667fa3
    30   val trace_ASTAR	: bool ref
    30   val trace_ASTAR	: bool ref
    31   val ASTAR	        : (thm -> bool) * (int->thm->int) -> tactic -> tactic
    31   val ASTAR	        : (thm -> bool) * (int->thm->int) -> tactic -> tactic
    32   val THEN_ASTAR	: tactic -> (thm->bool) * (int->thm->int) -> tactic
    32   val THEN_ASTAR	: tactic -> (thm->bool) * (int->thm->int) -> tactic
    33 			  -> tactic
    33 			  -> tactic
    34   val BREADTH_FIRST	: (thm -> bool) -> tactic -> tactic
    34   val BREADTH_FIRST	: (thm -> bool) -> tactic -> tactic
       
    35   val QUIET_BREADTH_FIRST	: (thm -> bool) -> tactic -> tactic
    35   end;
    36   end;
    36 
    37 
    37 structure Search : SEARCH = 
    38 structure Search : SEARCH = 
    38 struct
    39 struct
    39 
    40 
   212 (*Ordinary best-first search, with no initial tactic*)
   213 (*Ordinary best-first search, with no initial tactic*)
   213 val BEST_FIRST = THEN_BEST_FIRST all_tac;
   214 val BEST_FIRST = THEN_BEST_FIRST all_tac;
   214 
   215 
   215 (*Breadth-first search to satisfy satpred (including initial state) 
   216 (*Breadth-first search to satisfy satpred (including initial state) 
   216   SLOW -- SHOULD NOT USE APPEND!*)
   217   SLOW -- SHOULD NOT USE APPEND!*)
   217 fun BREADTH_FIRST satpred tac = 
   218 fun gen_BREADTH_FIRST message satpred (tac:tactic) = 
   218   let val tacf = Seq.list_of o tac;
   219   let val tacf = Seq.list_of o tac;
   219       fun bfs prfs =
   220       fun bfs prfs =
   220 	 (case  partition satpred prfs  of
   221 	 (case  partition satpred prfs  of
   221 	      ([],[]) => []
   222 	      ([],[]) => []
   222 	    | ([],nonsats) => 
   223 	    | ([],nonsats) => 
   223 		  (prs("breadth=" ^ string_of_int(length nonsats) ^ "\n");
   224 		  (message("breadth=" ^ string_of_int(length nonsats) ^ "\n");
   224 		   bfs (List.concat (map tacf nonsats)))
   225 		   bfs (List.concat (map tacf nonsats)))
   225 	    | (sats,_)  => sats)
   226 	    | (sats,_)  => sats)
   226   in (fn st => Seq.of_list (bfs [st])) end;
   227   in (fn st => Seq.of_list (bfs [st])) end;
       
   228 
       
   229 val BREADTH_FIRST = gen_BREADTH_FIRST prs;
       
   230 val QUIET_BREADTH_FIRST = gen_BREADTH_FIRST (K ());
   227 
   231 
   228 
   232 
   229 (*  Author: 	Norbert Voelker, FernUniversitaet Hagen
   233 (*  Author: 	Norbert Voelker, FernUniversitaet Hagen
   230     Remarks:    Implementation of A*-like proof procedure by modification
   234     Remarks:    Implementation of A*-like proof procedure by modification
   231 		of the existing code for BEST_FIRST and best_tac so that the 
   235 		of the existing code for BEST_FIRST and best_tac so that the