In this page there is a comment after the post that gives a very short implementation of amb
as a procedure:
(define (amb-backtrack)
(error "no solution found"))
(define (amb . args)
(call/cc (lambda (return)
(let ((backtrack amb-backtrack))
(map (lambda (x)
(call/cc (lambda (k)
(set! amb-backtrack k)
(return x))))
args)
(backtrack 'fail)))))
But I usually see amb
implemented as a macro -- in the schemers.org FAQ, and also in Dorai Sitaram's book:
(define amb-fail '*)
(define initialize-amb-fail
(lambda ()
(set! amb-fail
(lambda ()
(error "amb tree exhausted")))))
(initialize-amb-fail)
(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))))))
So -- the macro version is longer, and a little harder to understand. I could not see any advantages of it over the procedure version, and of course I would rather use a procedure than a macro. Is there anything I missed?
The difference is that a procedure call always evaluates all the arguments.
(amb 1 (very-expensive-computation))
will, with the procedure version of amb
, perform the very-expensive-computation
, then yield 1
. If yielding 1
suffices for all further computation, then you've wasted a lot of time on a computation whose result value is never used. Even worse things happen, as @Eli Barzilay mentions in a comment, when amb
is used to model an infinite non-determinism such as generating all natural numbers.
The macro version avoids this and its behavior is therefore closer to that of non-deterministic programming languages such as Prolog.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With