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))

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,

=> 3

This leaves yet another failure continuation, which can be called again for yet another solution:

=> 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,

  (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))))
       (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

Log in or register to write something here or to contact authors.