`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.