(*  An alternative version of depth-first search, which uses exceptions
    Arguments (in order):
      a list of operators (each is a condition-action pair),
      a goal (a predicate that is true when a state satisfies the goal)
      a list of open states
    Result: a state that satisfies the goal
*)

exception backtrack;

fun applyOp ((Condition,Action),State) =
if   (Condition State)
then (Action State)
else raise backtrack
;

(* In the definition of depth-first search that follows, the local
   function (dfs) actually implements the search algorithm.  The rest of
   the definition of depth_first serves only to set-up the parameter values
   for the initial call to dfs and to provide a "context" for dfs (e.g. the
   set of all possible operators (Operators)).
*)

fun depth_first (Operators,Goal,InitialState) =
let
    fun dfs ([],State) = raise backtrack
     |  dfs (HeadOp::OtherOps,State) =
            if (Goal State)
            then State
            else dfs (Operators,applyOp (HeadOp,State))
                 handle backtrack => dfs (OtherOps,State)
in
    dfs (Operators,InitialState)
end;


(* Simple example.
   States are pairs of integers less than or equal to 9.
   There are two operators, one to increment each integer.
   The goal is to find a pair whose product is 12.
   From an initial state of (0,0), depth-first should find (6,2).
*)

fun inc_first   (x,y) = (x+1,y);
fun inc_second  (x,y) = (x,y+1);
fun leq9_first  (x,_) = (x <= 9);
fun leq9_second (_,x) = (x <= 9);
val op1 = (leq9_first, inc_first);
val op2 = (leq9_second,inc_second);
fun equals12 (x,y) = x*y=12;

val df = depth_first   ([op1,op2],equals12,(0,0));