amb.scm

;; amb.scm - Nondeterminism using call/cc <3

(define (fail)
  (error 'require "no solutions"))

(define backtrack fail)

(define (require ok)
  (if (not ok)
      (backtrack)))

;; Return one of the values in `values` such that all future `(require)` calls
;; are satisfied.
(define (amb . values)
  (let ((backtrack-further backtrack))
    (call/cc (lambda (ctn)
               (define (next values)
                 (if (null? values)
                     (backtrack-further)
                     (begin (set! backtrack
                                  (lambda () (next (cdr values))))
                            (ctn (car values)))))
               (next values)))))