Amb is the 'ambiguous' [SICP "Amb and Search"] special form for non-deterministic computation. (AMB expression ...) may evaluate & return the value of any expression operand. As code continues, the set of values that it may have returned is typically narrowed with a (REQUIRE condition) procedure that ensures that condition holds true, backtracking if condition is false. For example,
(let ((a (amb 1 2))
(b (amb 1 2)))
(require (< a b))
(list a b))
This will return the list (1 2), because a value of 1 for a and a value of 2 for b are the only possible values, of the potential values given, that will make the condition (< a b) true.
This next example uses the (AMB-POSSIBILITY-LIST expression) special form implemented below, which returns a list of all possible answers expression may non-deterministically provide.
(amb-possibility-list (+ (amb 1 2) (amb 3 4))) ; => (4 5 5 6) ; i.e. (list (+ 1 3) (+ 1 4) (+ 2 3) (+ 2 4))
Amb was first proposed by John McCarthy, the inventor of LISP, in his 1963 paper A Basis for a Mathematical Theory of Computation (More of McCarthy's work can be found on his homepage). There is also a considerably sized section in SICP on the topic of amb & non-deterministic computation.
Amb can be implemented in terms of call-with-current-continuation for backtracking when a condition fails.
;;; FAIL is called to backtrack when a condition fails. At the top ;;; level, however, there is no more to backtrack, so we signal an ;;; error with SRFI 23. (define fail (lambda () (error "Amb tree exhausted"))) (define-syntax amb (syntax-rules () ((AMB) (FAIL)) ; Two shortcuts. ((AMB expression) expression) ((AMB expression ...) (LET ((FAIL-SAVE FAIL)) ((CALL-WITH-CURRENT-CONTINUATION ; Capture a continuation to (LAMBDA (K-SUCCESS) ; which we return possibles. (CALL-WITH-CURRENT-CONTINUATION (LAMBDA (K-FAILURE) ; K-FAILURE will try the next (SET! FAIL ; possible expression. (LAMBDA () (K-FAILURE #f))) (K-SUCCESS ; Note that the expression is (LAMBDA () ; evaluated in tail position expression)))) ; with respect to AMB. ... (SET! FAIL FAIL-SAVE) ; Finally, if this is reached, FAIL-SAVE))))))) ; we restore the saved FAIL. (define (require condition) (if (not condition) (fail))) ;;; As an auxiliary example, AMB-POSSIBILITY-LIST is a special form ;;; that returns a list of all values its input expression may return. (define-syntax amb-possibility-list (syntax-rules () ((AMB-POSSIBILITY-LIST expression) (LET ((VALUE-LIST '())) ;; This requires that AMB try its sub-forms left-to-right. (AMB (let ((VALUE expression)) (SET! VALUE-LIST (CONS VALUE VALUE-LIST)) (FAIL)) (REVERSE VALUE-LIST)))))) ; Order it nicely.