Teach Yourself Scheme: 14.2 Implementing 'amb' in Scheme (idea)

In our implementation of amb, we will favour amb's subexpressions from left to right. Ie, the first subexpression is chosen, and if it leads to overall failure, the second is picked, and so on. ambs occurring later in the control flow of the program are searched for alternates before backtracking to previous ambs. In other words, we perform a depth-first search of the amb choice tree, and whenever we brush against failure, we backtrack to the most recent node of the tree that offers a further choice. (This is called chronological backtracking.)

We first define a mechanism for setting the base failure continuation:

(define amb-fail '*)

(define initialize-amb-fail
  (lambda ()
    (set! amb-fail
      (lambda ()
        (error "amb tree exhausted")))))

(initialize-amb-fail)

When amb fails, it invokes the continuation bound at the time to amb-fail. This is the continuation invoked when all the alternates in the amb choice tree have been tried and were found to fail.

We define amb as a macro that accepts an indefinite number of subexpressions.

(define-macro amb
  (lambda alts...
    `(let ((+prev-amb-fail amb-fail))
       (call/cc
        (lambda (+sk)

          ,@(map (lambda (alt)
                   `(call/cc
                     (lambda (+fk)
                       (set! amb-fail
                         (lambda ()
                           (set! amb-fail +prev-amb-fail)
                           (+fk 'fail)))
                       (+sk ,alt))))
                 alts...)

          (+prev-amb-fail))))))

A call to amb first stores away, in +prev-amb-fail, the amb-fail value that was current at the time of entry. This is because the amb-fail variable will be set to different failure continuations as the various alternates are tried.

We then capture the amb's entry continuation +sk, so that when one of the alternates evaluates to a non-failing value, it can immediately exit the amb.

Each alternate alt is tried in sequence (the implicit-begin sequence of Scheme).

First, we capture the current continuation +fk, wrap it in a procedure and set amb-fail to that procedure. The alternate is then evaluated as (+sk alt). If alt evaluates without failure, its return value is fed to the continuation +sk, which immediately exits the amb call. If alt fails, it calls amb-fail. The first duty of amb-fail is to reset amb-fail to the value it had at the time of entry. It then invokes the failure continuation +fk, which causes the next alternate, if any, to be tried.

If all alternates fail, the amb-fail at amb entry, which we had stored in +prev-amb-fail, is called.

Prev Up Next