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. 

category-code