Prev Up Next
To choose a number between 1 and 10, one could say
(amb 1 2 3 4 5 6 7 8 9 10)
To be sure, as a program, this will give 1, but
depending on the context, it could return any of the
mentioned numbers.
The procedure number-between is
a more abstract way to generate numbers from a given lo
to a given hi (inclusive):
(define number-between
(lambda (lo hi)
(let loop ((i lo))
(if (> i hi) (amb)
(amb i (loop (+ i 1)))))))
Thus (number-between 1 6) will first
generate 1. Should that fail, the loop iterates,
producing 2. Should that fail, we get 3, and
so on, until 6. After 6, loop is called with
the number 7, which being more than 6, invokes
(amb), which causes final failure. (Recall that
(amb) by itself guarantees
failure.) At this point, the program containing the
call to
(number-between 1 6) will backtrack to the
chronologically previous amb-call, and try to
satisfy that call in another fashion.
The guaranteed failure of (amb) can be used to program
assertions.
(define assert
(lambda (pred)
(if (not pred) (amb))))
The call (assert pred) insists that pred be
true. Otherwise it will cause the current amb choice
point to fail.5
Here is a procedure using assert that generates a prime
less than or equal to its argument hi:
(define gen-prime
(lambda (hi)
(let ((i (number-between 2 hi)))
(assert (prime? i))
i)))
This seems devilishly simple, except that when called as
a program with any number (say 20), it will produce the
uninteresting first solution, ie, 2.
We would certainly like to get all the solutions,
not just the first. In this case, we may want all
the primes below
20. One way is to explicitly call the failure
continuation left after the program has produced its first
solution. Thus,
(amb)
=> 3
This leaves yet another failure continuation, which can
be called again for yet another solution:
(amb)
=> 5
The problem with this method is that the program is
initially called at the Scheme prompt, and successive
solutions are also obtained by calling amb at the Scheme
prompt. In effect, we are using different programs (we
cannot predict how many!), carrying over information from a
previous program to the next. Instead, we would like to be
able to get these solutions as the return value of a
form that we can call in any context. To this end, we
define the
bag-of macro, which returns all
the successful instantiations of its argument. (If the argument
never succeeds, bag-of returns the empty list.)
Thus, we could say,
(bag-of
(gen-prime 20))
and it would return
(2 3 5 7 11 13 17 19)
The bag-of macro is defined as follows:
(define-macro bag-of
(lambda (e)
`(let ((+prev-amb-fail amb-fail)
(+results '()))
(if (call/cc
(lambda (+k)
(set! amb-fail (lambda () (+k #f)))
(let ((+v ,e))
(set! +results (cons +v +results))
(+k #t))))
(amb-fail))
(set! amb-fail +prev-amb-fail)
(reverse! +results))))
bag-of first saves away its entry amb-fail. It
redefines amb-fail to a local continuation +k created within an
if-test. Inside the test, the bag-of argument e
is evaluated.
If e succeeds, its result is collected
into a list called +results, and the local continuation
is called with the value #t. This causes the
if-test to succeed, causing e to be retried at its
next backtrack point. More results for e are obtained this
way, and they are all collected into +results.
Finally, when e fails, it will call the base
amb-fail, which is simply a call to the local
continuation with the value #f. This pushes control
past the if. We restore amb-fail to
its pre-entry value, and return the +results. (The
reverse! is simply to produce the results in the order
in which they were generated.)
5 SICP names this procedure
require. We use the identifier assert in order to
avoid confusion with the popular if informal use of
the identifier require for something else, viz, an
operator that loads code modules on a per-need basis.
Prev Up Next