In this section, we extend the Scheme evaluator to support a
programming paradigm called nondeterministic computing by
building into the evaluator a facility to support automatic search.
This is a much more profound change to the language than the
introduction of lazy evaluation in section ![[*]](../image/cross_ref_motif.gif)
.
Nondeterministic computing, like stream processing, is useful for
``generate and test'' applications. Consider the task of starting with
two lists of positive integers and finding a pair of integers--one
from the first list and one from the second list--whose sum is prime.
We saw how to handle this with finite sequence operations in
section and with infinite streams in
section . Our approach was to generate
the sequence of all possible pairs and filter these to select the
pairs whose sum is prime. Whether we actually generate the entire
sequence of pairs first as in chapter 2, or interleave the generating
and filtering as in chapter 3, is immaterial to the essential image of
how the computation is organized.
The nondeterministic approach evokes a different image. Imagine simply that we choose (in some way) a number from the first list and a number from the second list and require (using some mechanism) that their sum be prime. This is expressed by following procedure:
(define (prime-sum-pair list1 list2)
(let ((a (an-element-of list1))
(b (an-element-of list2)))
(require (prime? (+ a b)))
(list a b)))
It might seem as if this procedure merely restates the problem,
rather than specifying a way to solve it. Nevertheless, this is
a legitimate nondeterministic program.
![[*]](../image/foot_motif.gif)
The key idea here is that expressions in a nondeterministic language can have more than one possible value. For instance, an-element-of might return any element of the given list. Our nondeterministic program evaluator will work by automatically choosing a possible value and keeping track of the choice. If a subsequent requirement is not met, the evaluator will try a different choice, and it will keep trying new choices until the evaluation succeeds, or until we run out of choices. Just as the lazy evaluator freed the programmer from the details of how values are delayed and forced, the nondeterministic program evaluator will free the programmer from the details of how choices are made.
It is instructive to contrast the different images of time evoked by nondeterministic evaluation and stream processing. Stream processing uses lazy evaluation to decouple the time when the stream of possible answers is assembled from the time when the actual stream elements are produced. The evaluator supports the illusion that all the possible answers are laid out before us in a timeless sequence. With nondeterministic evaluation, an expression represents the exploration of a set of possible worlds, each determined by a set of choices. Some of the possible worlds lead to dead ends, while others have useful values. The nondeterministic program evaluator supports the illusion that time branches, and that our programs have different possible execution histories. When we reach a dead end, we can revisit a previous choice point and proceed along a different branch.
The nondeterministic program evaluator implemented below is called the amb evaluator because it is based on a new special form called amb. We can type the above definition of prime-sum-pair at the amb evaluator driver loop (along with definitions of prime?, an-elementof, and require) and run the procedure as follows:
;;; Amb-Eval input: (prime-sum-pair '(1 3 5 8) '(20 35 110)) ;;; Starting a new problem ;;; Amb-Eval value: (3 20)The value returned was obtained after the evaluator repeatedly chose elements from each of the lists, until a successful choice was made.
Section introduces amb and explains how it
supports nondeterminism through the evaluator's automatic search
mechanism. Section presents examples of
nondeterministic programs, and section
gives the details of how to implement the amb evaluator by
modifying the ordinary Scheme evaluator.