paulson@1588: (* Title: search paulson@1588: ID: $Id$ paulson@1588: Author: Lawrence C Paulson and Norbert Voelker paulson@1588: paulson@1588: Search tacticals paulson@1588: *) paulson@1588: paulson@2672: infix 1 THEN_MAYBE THEN_MAYBE'; paulson@2672: paulson@1588: signature SEARCH = paulson@1588: sig paulson@2869: val DEEPEN : int*int -> (int->int->tactic) -> int -> int -> tactic paulson@2869: paulson@2672: val THEN_MAYBE : tactic * tactic -> tactic paulson@2672: val THEN_MAYBE' : ('a -> tactic) * ('a -> tactic) -> ('a -> tactic) paulson@2672: paulson@1588: val trace_DEPTH_FIRST : bool ref paulson@1588: val DEPTH_FIRST : (thm -> bool) -> tactic -> tactic paulson@1588: val DEPTH_SOLVE : tactic -> tactic paulson@1588: val DEPTH_SOLVE_1 : tactic -> tactic paulson@1588: val ITER_DEEPEN : (thm->bool) -> (int->tactic) -> tactic paulson@1588: val THEN_ITER_DEEPEN : tactic -> (thm->bool) -> (int->tactic) -> tactic paulson@1588: paulson@1588: val has_fewer_prems : int -> thm -> bool paulson@1588: val IF_UNSOLVED : tactic -> tactic oheimb@5754: val SOLVE : tactic -> tactic oheimb@8149: val DETERM_UNTIL_SOLVED: tactic -> tactic paulson@1588: val trace_BEST_FIRST : bool ref paulson@1588: val BEST_FIRST : (thm -> bool) * (thm -> int) -> tactic -> tactic paulson@1588: val THEN_BEST_FIRST : tactic -> (thm->bool) * (thm->int) -> tactic paulson@1588: -> tactic paulson@1588: val trace_ASTAR : bool ref paulson@1588: val ASTAR : (thm -> bool) * (int->thm->int) -> tactic -> tactic paulson@1588: val THEN_ASTAR : tactic -> (thm->bool) * (int->thm->int) -> tactic paulson@1588: -> tactic paulson@1588: val BREADTH_FIRST : (thm -> bool) -> tactic -> tactic wenzelm@5693: val QUIET_BREADTH_FIRST : (thm -> bool) -> tactic -> tactic paulson@1588: end; paulson@1588: paulson@9094: wenzelm@9411: (** Instantiation of heaps for best-first search **) paulson@9094: wenzelm@9411: (*total ordering on theorems, allowing duplicates to be found*) wenzelm@9411: structure ThmHeap = wenzelm@9411: HeapFun (type elem = int * thm wenzelm@9411: val ord = Library.prod_ord Library.int_ord wenzelm@9411: (Term.term_ord o Library.pairself (#prop o Thm.rep_thm))); paulson@9094: paulson@9094: paulson@1588: structure Search : SEARCH = paulson@1588: struct paulson@1588: paulson@1588: (**** Depth-first search ****) paulson@1588: paulson@1588: val trace_DEPTH_FIRST = ref false; paulson@1588: paulson@1588: (*Searches until "satp" reports proof tree as satisfied. paulson@1588: Suppresses duplicate solutions to minimize search space.*) paulson@1588: fun DEPTH_FIRST satp tac = paulson@1588: let val tac = tracify trace_DEPTH_FIRST tac skalberg@15531: fun depth used [] = NONE paulson@1588: | depth used (q::qs) = wenzelm@4270: case Seq.pull q of skalberg@15531: NONE => depth used qs skalberg@15531: | SOME(st,stq) => paulson@1588: if satp st andalso not (gen_mem eq_thm (st, used)) skalberg@15531: then SOME(st, Seq.make paulson@1588: (fn()=> depth (st::used) (stq::qs))) paulson@1588: else depth used (tac st :: stq :: qs) wenzelm@4270: in traced_tac (fn st => depth [] ([Seq.single st])) end; paulson@1588: paulson@1588: paulson@1588: paulson@1588: (*Predicate: Does the rule have fewer than n premises?*) paulson@1588: fun has_fewer_prems n rule = (nprems_of rule < n); paulson@1588: paulson@1588: (*Apply a tactic if subgoals remain, else do nothing.*) paulson@1588: val IF_UNSOLVED = COND (has_fewer_prems 1) all_tac; paulson@1588: oheimb@5754: (*Force a tactic to solve its goal completely, otherwise fail *) oheimb@5754: fun SOLVE tac = tac THEN COND (has_fewer_prems 1) all_tac no_tac; oheimb@5754: oheimb@8149: (*Force repeated application of tactic until goal is solved completely *) oheimb@8149: val DETERM_UNTIL_SOLVED = DETERM_UNTIL (has_fewer_prems 1); oheimb@8149: paulson@2672: (*Execute tac1, but only execute tac2 if there are at least as many subgoals paulson@2672: as before. This ensures that tac2 is only applied to an outcome of tac1.*) paulson@3538: fun (tac1 THEN_MAYBE tac2) st = paulson@3538: (tac1 THEN COND (has_fewer_prems (nprems_of st)) all_tac tac2) st; paulson@2672: paulson@2672: fun (tac1 THEN_MAYBE' tac2) x = tac1 x THEN_MAYBE tac2 x; paulson@2672: paulson@1588: (*Tactical to reduce the number of premises by 1. paulson@1588: If no subgoals then it must fail! *) paulson@3538: fun DEPTH_SOLVE_1 tac st = st |> paulson@1588: (case nprems_of st of paulson@1588: 0 => no_tac paulson@3538: | n => DEPTH_FIRST (has_fewer_prems n) tac); paulson@1588: paulson@1588: (*Uses depth-first search to solve ALL subgoals*) paulson@1588: val DEPTH_SOLVE = DEPTH_FIRST (has_fewer_prems 1); paulson@1588: paulson@1588: paulson@1588: paulson@2869: (**** Iterative deepening with pruning ****) paulson@1588: paulson@1588: fun has_vars (Var _) = true paulson@1588: | has_vars (Abs (_,_,t)) = has_vars t paulson@1588: | has_vars (f$t) = has_vars f orelse has_vars t paulson@1588: | has_vars _ = false; paulson@1588: paulson@1588: (*Counting of primitive inferences is APPROXIMATE, as the step tactic paulson@1588: may perform >1 inference*) paulson@1588: paulson@1588: (*Pruning of rigid ancestor to prevent backtracking*) paulson@1588: fun prune (new as (k', np':int, rgd', stq), qs) = paulson@1588: let fun prune_aux (qs, []) = new::qs paulson@1588: | prune_aux (qs, (k,np,rgd,q)::rqs) = paulson@1588: if np'+1 = np andalso rgd then paulson@1588: (if !trace_DEPTH_FIRST then wenzelm@12262: tracing ("Pruning " ^ paulson@1588: string_of_int (1+length rqs) ^ " levels") paulson@1588: else (); paulson@1588: (*Use OLD k: zero-cost solution; see Stickel, p 365*) paulson@1588: (k, np', rgd', stq) :: qs) paulson@1588: else prune_aux ((k,np,rgd,q)::qs, rqs) paulson@1588: fun take ([], rqs) = ([], rqs) paulson@1588: | take (arg as ((k,np,rgd,stq)::qs, rqs)) = paulson@1588: if np' < np then take (qs, (k,np,rgd,stq)::rqs) paulson@1588: else arg paulson@1588: in prune_aux (take (qs, [])) end; paulson@1588: paulson@1588: paulson@1588: (*Depth-first iterative deepening search for a state that satisfies satp paulson@1588: tactic tac0 sets up the initial goal queue, while tac1 searches it. paulson@1588: The solution sequence is redundant: the cutoff heuristic makes it impossible paulson@1588: to suppress solutions arising from earlier searches, as the accumulated cost paulson@1588: (k) can be wrong.*) paulson@1588: fun THEN_ITER_DEEPEN tac0 satp tac1 = traced_tac (fn st => paulson@1588: let val countr = ref 0 paulson@1588: and tf = tracify trace_DEPTH_FIRST (tac1 1) paulson@1588: and qs0 = tac0 st paulson@1588: (*bnd = depth bound; inc = estimate of increment required next*) paulson@1588: fun depth (bnd,inc) [] = wenzelm@12262: (tracing (string_of_int (!countr) ^ paulson@1588: " inferences so far. Searching to depth " ^ paulson@1588: string_of_int bnd); paulson@1588: (*larger increments make it run slower for the hard problems*) paulson@1588: depth (bnd+inc, 10)) [(0, 1, false, qs0)] paulson@1588: | depth (bnd,inc) ((k,np,rgd,q)::qs) = paulson@1588: if k>=bnd then depth (bnd,inc) qs paulson@1588: else paulson@1588: case (countr := !countr+1; paulson@1588: if !trace_DEPTH_FIRST then wenzelm@12262: tracing (string_of_int np ^ paulson@1588: implode (map (fn _ => "*") qs)) paulson@1588: else (); wenzelm@4270: Seq.pull q) of skalberg@15531: NONE => depth (bnd,inc) qs skalberg@15531: | SOME(st,stq) => paulson@1588: if satp st (*solution!*) skalberg@15531: then SOME(st, Seq.make paulson@1588: (fn()=> depth (bnd,inc) ((k,np,rgd,stq)::qs))) paulson@1588: paulson@1588: else paulson@1588: let val np' = nprems_of st paulson@1588: (*rgd' calculation assumes tactic operates on subgoal 1*) paulson@1588: val rgd' = not (has_vars (hd (prems_of st))) paulson@1588: val k' = k+np'-np+1 (*difference in # of subgoals, +1*) paulson@1588: in if k'+np' >= bnd paulson@2143: then depth (bnd, Int.min(inc, k'+np'+1-bnd)) qs paulson@1588: else if np' < np (*solved a subgoal; prune rigid ancestors*) paulson@1588: then depth (bnd,inc) paulson@1588: (prune ((k', np', rgd', tf st), (k,np,rgd,stq) :: qs)) paulson@1588: else depth (bnd,inc) ((k', np', rgd', tf st) :: paulson@1588: (k,np,rgd,stq) :: qs) paulson@1588: end paulson@1588: in depth (0,5) [] end); paulson@1588: paulson@1588: val ITER_DEEPEN = THEN_ITER_DEEPEN all_tac; paulson@1588: paulson@1588: paulson@2869: (*Simple iterative deepening tactical. It merely "deepens" any search tactic paulson@2869: using increment "inc" up to limit "lim". *) paulson@2869: fun DEEPEN (inc,lim) tacf m i = paulson@14160: let fun dpn m st = paulson@14160: st |> (if has_fewer_prems i st then no_tac paulson@14160: else if m>lim then paulson@14160: (warning "Search depth limit exceeded: giving up"; paulson@14160: no_tac) paulson@14160: else (warning ("Search depth = " ^ string_of_int m); paulson@14160: tacf m i ORELSE dpn (m+inc))) paulson@2869: in dpn m end; paulson@14160: paulson@1588: (*** Best-first search ***) paulson@1588: paulson@1588: val trace_BEST_FIRST = ref false; paulson@1588: paulson@1588: (*For creating output sequence*) skalberg@15531: fun some_of_list [] = NONE skalberg@15531: | some_of_list (x::l) = SOME (x, Seq.make (fn () => some_of_list l)); paulson@1588: paulson@9094: (*Check for and delete duplicate proof states*) paulson@9094: fun deleteAllMin prf heap = wenzelm@9411: if ThmHeap.is_empty heap then heap wenzelm@9411: else if eq_thm (prf, #2 (ThmHeap.min heap)) wenzelm@9411: then deleteAllMin prf (ThmHeap.delete_min heap) paulson@9094: else heap; paulson@1588: paulson@1588: (*Best-first search for a state that satisfies satp (incl initial state) paulson@1588: Function sizef estimates size of problem remaining (smaller means better). paulson@1588: tactic tac0 sets up the initial priority queue, while tac1 searches it. *) paulson@1588: fun THEN_BEST_FIRST tac0 (satp, sizef) tac1 = paulson@1588: let val tac = tracify trace_BEST_FIRST tac1 paulson@1588: fun pairsize th = (sizef th, th); paulson@9094: fun bfs (news,nprf_heap) = skalberg@15570: (case List.partition satp news of skalberg@15574: ([],nonsats) => next(foldr ThmHeap.insert skalberg@15574: nprf_heap (map pairsize nonsats)) paulson@1588: | (sats,_) => some_of_list sats) paulson@9094: and next nprf_heap = skalberg@15531: if ThmHeap.is_empty nprf_heap then NONE paulson@9094: else wenzelm@9411: let val (n,prf) = ThmHeap.min nprf_heap paulson@9094: in if !trace_BEST_FIRST wenzelm@12262: then tracing("state size = " ^ string_of_int n) paulson@1588: else (); paulson@9094: bfs (Seq.list_of (tac prf), wenzelm@9411: deleteAllMin prf (ThmHeap.delete_min nprf_heap)) paulson@9094: end wenzelm@9411: fun btac st = bfs (Seq.list_of (tac0 st), ThmHeap.empty) paulson@1588: in traced_tac btac end; paulson@1588: paulson@1588: (*Ordinary best-first search, with no initial tactic*) paulson@1588: val BEST_FIRST = THEN_BEST_FIRST all_tac; paulson@1588: paulson@1588: (*Breadth-first search to satisfy satpred (including initial state) paulson@1588: SLOW -- SHOULD NOT USE APPEND!*) wenzelm@5693: fun gen_BREADTH_FIRST message satpred (tac:tactic) = wenzelm@4270: let val tacf = Seq.list_of o tac; paulson@1588: fun bfs prfs = skalberg@15570: (case List.partition satpred prfs of paulson@1588: ([],[]) => [] paulson@1588: | ([],nonsats) => wenzelm@5956: (message("breadth=" ^ string_of_int(length nonsats)); paulson@2672: bfs (List.concat (map tacf nonsats))) paulson@1588: | (sats,_) => sats) wenzelm@4270: in (fn st => Seq.of_list (bfs [st])) end; paulson@1588: wenzelm@12262: val BREADTH_FIRST = gen_BREADTH_FIRST tracing; wenzelm@5693: val QUIET_BREADTH_FIRST = gen_BREADTH_FIRST (K ()); wenzelm@5693: paulson@1588: paulson@1588: (* Author: Norbert Voelker, FernUniversitaet Hagen paulson@1588: Remarks: Implementation of A*-like proof procedure by modification paulson@1588: of the existing code for BEST_FIRST and best_tac so that the paulson@1588: current level of search is taken into account. paulson@1588: *) paulson@1588: paulson@1588: (*Insertion into priority queue of states, marked with level *) paulson@1588: fun insert_with_level (lnth: int*int*thm, []) = [lnth] paulson@1588: | insert_with_level ((l,m,th), (l',n,th')::nths) = paulson@1588: if n some_of_list l)); paulson@1588: paulson@1588: val trace_ASTAR = ref false; paulson@1588: paulson@1588: fun THEN_ASTAR tac0 (satp, costf) tac1 = paulson@1588: let val tf = tracify trace_ASTAR tac1; paulson@1588: fun bfs (news,nprfs,level) = paulson@1588: let fun cost thm = (level, costf level thm, thm) skalberg@15570: in (case List.partition satp news of paulson@1588: ([],nonsats) skalberg@15574: => next (foldr insert_with_level nprfs (map cost nonsats)) paulson@1588: | (sats,_) => some_of_list sats) paulson@1588: end and skalberg@15531: next [] = NONE paulson@1588: | next ((level,n,prf)::nprfs) = paulson@1588: (if !trace_ASTAR wenzelm@12262: then tracing("level = " ^ string_of_int level ^ paulson@1588: " cost = " ^ string_of_int n ^ paulson@1588: " queue length =" ^ string_of_int (length nprfs)) paulson@1588: else (); wenzelm@4270: bfs (Seq.list_of (tf prf), nprfs,level+1)) wenzelm@4270: fun tf st = bfs (Seq.list_of (tac0 st), [], 0) paulson@1588: in traced_tac tf end; paulson@1588: paulson@1588: (*Ordinary ASTAR, with no initial tactic*) paulson@1588: val ASTAR = THEN_ASTAR all_tac; paulson@1588: paulson@1588: end; paulson@1588: paulson@1588: open Search;