;; amb

;; FIXME: don't use global state in cat. use the assembly list/stack
;; to store the continuations.

;; uses thunks instead of delay/force because delayed values are only
;; evaluated once.

(define *backtrack* '())
(define (kill-amb!) (set! *backtrack* '()))
     
;; ambiguous lazy list
(define (amb-cons-thunk now thunk)
  (call/cc
   (lambda (return)
     (push! *backtrack*
            (lambda ()
              ;; (display "<backtracking>\n") 
              (return (thunk))))
     now)))

;; the syntax version, which delays the cdr by wrapping it in a thunk.
(define-syntax amb-cons
  (syntax-rules ()
    ((_ car cdr)
     (amb-cons-thunk car
                    (lambda () cdr)))))


(define (fail)
  ((pop! *backtrack*)))

;; the canonical amb operator for strict lists, in terms of the lazy amb-cons.
(define (amb . args)
  (match args
         (()           (fail))
         ((one)        one)
         ((one . more) (amb-cons one
                                 (apply amb more)))))

;; this creates a boundary between deterministic and non-deterministic
;; behaviour. if thunk returns or jumps out of the context, the
;; dynamicly bound variable will be restored.

(define (amb-drive thunk)
  (let* ((stack '())
         (switch! (lambda () (swap! *backtrack* stack))))
    (dynamic-wind switch! thunk switch!)))