Variations on a Scheme--Nondeterministic Computing

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 .

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.

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.