Structure and Interpretation of Computer Programs (78 page)

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 
4.2
.

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 
2.2.3
and with infinite streams in
section 
3.5.3
. 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-element-of
, 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 
4.3.1
introduces
amb
and explains how it
supports nondeterminism through the evaluator's automatic search
mechanism. Section
4.3.2
presents examples of
nondeterministic programs, and section 
4.3.3
gives the details of how to implement the
amb
evaluator by
modifying the ordinary Scheme evaluator.

To extend Scheme to support nondeterminism, we introduce a new special
form called
amb
.
⁴³
The expression
(amb <
e
₁
> <
e
₂
>
...
<
e
_n
>)
returns the value of one of the
n
expressions <
e
_i
> “ambiguously.”
For example, the expression

(list (amb 1 2 3) (amb 'a 'b))

can have six possible values:

Amb
with no choices – the expression
(amb)
– is an
expression with no acceptable values. Operationally, we can think of
(amb)
as an expression that when evaluated causes the
computation to “fail”: The computation aborts and no value is
produced. Using this idea, we can express the requirement that a
particular predicate expression
p
must be true as follows:

(define (require p)
  (if (not p) (amb)))

With
amb
and
require
, we can implement the
an-element-of
procedure used above:

(define (an-element-of items)
  (require (not (null? items)))
  (amb (car items) (an-element-of (cdr items))))

An-element-of
fails if the list is empty. Otherwise it
ambiguously returns either the first element of the list or an element
chosen from the rest of the list.

We can also express infinite ranges of choices. The following
procedure potentially returns any integer greater than or equal to
some given 
n
:

(define (an-integer-starting-from n)
  (amb n (an-integer-starting-from (+ n 1))))

This is like the stream procedure
integers-starting-from
described in section 
3.5.2
, but with an important
difference: The stream procedure returns an object that represents the
sequence of all integers beginning with
n
, whereas the
amb
procedure returns a single integer.
⁴⁴

Abstractly, we can imagine that evaluating an
amb
expression
causes time to split into branches, where the computation continues on
each branch with one of the possible values of the expression. We say
that
amb
represents a
nondeterministic choice point
.
If we had a machine with a sufficient number of processors that could
be dynamically allocated, we could implement the search in a
straightforward way. Execution would proceed as in a sequential
machine, until an
amb
expression is encountered. At this point,
more processors would be allocated and initialized to continue all of
the parallel executions implied by the choice. Each processor would
proceed sequentially as if it were the only choice, until it either
terminates by encountering a failure, or it further subdivides, or
it finishes.
⁴⁵

On the other hand, if we have a machine that can execute
only one process (or a few concurrent processes),
we must consider the alternatives sequentially.
One could imagine modifying an evaluator
to pick at random a branch to follow whenever it encounters a choice
point. Random choice, however, can easily lead to failing values.
We might try running the evaluator over and over, making random
choices and hoping to find a non-failing value, but it is better to
systematically search
all possible execution paths.
The
amb
evaluator that we will develop and work with in this section
implements a systematic search as follows: When the evaluator
encounters an application of
amb
, it initially selects the first
alternative. This selection may itself lead to a further choice. The
evaluator will always initially choose the first alternative at each
choice point. If a choice results in a failure, then the evaluator
automagically
⁴⁶
backtracks
to the most recent choice point and tries the next
alternative. If it runs out of alternatives at any choice point, the
evaluator will back up to the previous choice point and resume from
there. This process leads to a search strategy known as
depth-first search
or
chronological backtracking
.
⁴⁷

The driver loop for the
amb
evaluator
has some unusual properties. It reads an
expression and prints the value of the first non-failing execution, as
in the
prime-sum-pair
example shown above. If we
want to see the value of the next successful execution, we can
ask the interpreter to backtrack and attempt to generate a second
non-failing execution. This is signaled by typing the symbol
try-again
. If any expression except
try-again
is given, the
interpreter will start a new problem, discarding the unexplored
alternatives in the previous problem. Here is a sample
interaction:

;;; Amb-Eval input:
(prime-sum-pair '(1 3 5 8) '(20 35 110))
;;; Starting a new problem
;;; Amb-Eval value:
(3 20)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(3 110)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(8 35)
;;; Amb-Eval input:
try-again
;;; There are no more values of
(prime-sum-pair (quote (1 3 5 8)) (quote (20 35 110)))
;;; Amb-Eval input:
(prime-sum-pair '(19 27 30) '(11 36 58))
;;; Starting a new problem
;;; Amb-Eval value:
(30 11)

Exercise 4.35.
  
Write a procedure
an-integer-between
that returns an integer
between two given bounds. This can be used to implement a
procedure that finds Pythagorean triples,
i.e., triples of integers (
i
,
j
,
k
) between the given bounds such
that
i
<
j
and
i
²
+
j
²
=
k
²
, as follows:

(define (a-pythagorean-triple-between low high)
  (let ((i (an-integer-between low high)))
    (let ((j (an-integer-between i high)))
      (let ((k (an-integer-between j high)))
        (require (= (+ (* i i) (* j j)) (* k k)))
        (list i j k)))))

Exercise 4.36.
  
Exercise 
3.69
discussed how to generate
the stream of
all
Pythagorean triples, with no upper bound on the
size of the integers to be searched. Explain why simply replacing
an-integer-between
by
an-integer-starting-from
in the procedure in
exercise 
4.35
is not an adequate way to
generate arbitrary Pythagorean triples. Write a procedure that
actually will accomplish this. (That is, write a procedure for which
repeatedly typing
try-again
would in principle eventually
generate all Pythagorean triples.)

Exercise 4.37.
  
Ben Bitdiddle claims that the following method for generating
Pythagorean triples is more efficient than the one in
exercise 
4.35
. Is he correct? (Hint: Consider
the number of possibilities that must be explored.)

(define (a-pythagorean-triple-between low high)
  (let ((i (an-integer-between low high))
        (hsq (* high high)))
    (let ((j (an-integer-between i high)))
      (let ((ksq (+ (* i i) (* j j))))
        (require (>= hsq ksq))
        (let ((k (sqrt ksq)))
          (require (integer? k))
          (list i j k))))))

Section 
4.3.3
describes the implementation of
the
amb
evaluator. First, however, we give some examples of how
it can be used. The advantage of nondeterministic programming is that
we can suppress the details of how search is carried out, thereby
expressing our programs at a higher level of abstraction.

The following puzzle (taken from Dinesman 1968) is typical of a large
class of simple logic puzzles:

Baker, Cooper, Fletcher, Miller, and Smith live on different floors of
an apartment house that contains only five floors. Baker does not
live on the top floor. Cooper does not live on the bottom floor.
Fletcher does not live on either the top or the bottom floor. Miller
lives on a higher floor than does Cooper. Smith does not live on a
floor adjacent to Fletcher's. Fletcher does not live on a floor
adjacent to Cooper's. Where does everyone live?

We can determine who lives on each floor in a straightforward way by
enumerating all the possibilities and imposing the given
restrictions:
⁴⁸

(define (multiple-dwelling)
  (let ((baker (amb 1 2 3 4 5))
        (cooper (amb 1 2 3 4 5))
        (fletcher (amb 1 2 3 4 5))
        (miller (amb 1 2 3 4 5))
        (smith (amb 1 2 3 4 5)))
    (require
     (distinct? (list baker cooper fletcher miller smith)))
    (require (not (= baker 5)))
    (require (not (= cooper 1)))
    (require (not (= fletcher 5)))
    (require (not (= fletcher 1)))
    (require (> miller cooper))
    (require (not (= (abs (- smith fletcher)) 1)))
    (require (not (= (abs (- fletcher cooper)) 1)))
    (list (list 'baker baker)
          (list 'cooper cooper)
          (list 'fletcher fletcher)
          (list 'miller miller)
          (list 'smith smith))))