Prev Up Next
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