Ramin Zabih, David McAllester, David Chapman
Extending functional Lisp with McCarthy’s non-deterministic operator AMB yields a language which can concisely express search problems. Dependency-directed backtracking is a powerful search strategy. We describe a non-deterministic Lisp dialect called SCHEMER and show that it can provide automatic dependency-directed backtracking. The resulting language provides a convenient interface to this efficient backtracking strategy.