Prev Up Next

McCarthy's nondeterministic operator amb is as old as Lisp itself, although it is present in no Lisp. amb takes zero or more expressions, and makes a nondeterministic (or ``ambiguous'') choice among them, preferring those choices that cause the program to converge meaningfully. Here we will explore an embedding of amb in Scheme that makes a depth-first selection of the ambiguous choices, and uses Scheme's control operator call/cc to backtrack for alternate choices. The result is an elegant backtracking strategy that can be used for searching problem spaces directly in Scheme without recourse to an extended language. The embedding recalls the continuation strategies used to implement Prolog-style logic programming, but is sparer because the operator provided is much like a Scheme boolean operator, does not require special contexts for its use, and does not rely on linguistic infrastructure such as logic variables and unification.

Log in or register to write something here or to contact authors.