# amb

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.

## Implementation

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