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.