(load "macros.scm")

;; continuation stack
(define *paths* '())

;; evaluate thunk nondeterministically.

;; this returns first possible solution. running (fail)
;; returns the next possible solution, until #f is returned
;; when all solutions are exhausted.

(define (with-choose thunk)
  (call/cc
   (lambda (done)
     (call/cc 
      (lambda (last)
	(set! *paths* (list last))
	(done (thunk))))
     (done #f))))

;; try next search (fail / backtrack)
(define (fail) ((pop *paths*) #f))

;; enter nonderministic choise point
(define (choose choices)
  (if (eq? '() choices) 
      (fail)
      (call/cc 
       (lambda (choose-now)
	 (call/cc 
	  (lambda (next)
	    (push *paths* next)
	    (choose-now (car choices))))
	 (choose (cdr choices))))))

;; declare a restriction (fail -> try next)
(define (require predicate)
  (if (not predicate) (fail)))


;; TEST
;; run a nondeterministic program
(define (choose-test)
  (let ((solution 
	 (with-choose
	  (lambda ()
	    (let ((args 
		   (list 
		    (choose '(1 2 3)) 
		    (choose '(4 5 6)))))
	      (require (= 7 (apply + args)))
	      args)))))

    ;; print solution if not false, then fail
    ;; this will print all solutions
    (if solution 
	(begin
	  (display solution)
	  (newline)
	  (fail)))))