Amb using continuations

Question

I have just started studying Racket/Scheme continuations and found a helpful resource - Matt Mights page. I understood everything till the nondeterministic Amb example. Can anyone explain me how continuations work in this example? Currently looks like black magic for me.

; current-continuation : -> continuation
(define (current-continuation) 
  (call-with-current-continuation 
   (lambda (cc)
     (cc cc))))

; fail-stack : list[continuation]
(define fail-stack '())

; fail : -> ...
(define (fail)
  (if (not (pair? fail-stack))
      (error "back-tracking stack exhausted!")
      (begin
        (let ((back-track-point (car fail-stack)))
          (set! fail-stack (cdr fail-stack))
          (back-track-point back-track-point)))))

; amb : list[a] -> a
(define (amb choices)
  (let ((cc (current-continuation)))
    (cond
      ((null? choices) (fail))
      ((pair? choices)
       (let ((choice (car choices)))
         (set! choices (cdr choices))
         (set! fail-stack (cons cc fail-stack))
         choice)))))

; (assert condition) will cause
; condition to be true, and if there
; is no way to make it true, then
; it signals and error in the program.
(define (assert condition)
  (if (not condition)
      (fail)
      #t))

; The following prints (4 3 5)
(let ((a (amb (list 1 2 3 4 5 6 7)))
      (b (amb (list 1 2 3 4 5 6 7)))
      (c (amb (list 1 2 3 4 5 6 7))))

  ; We're looking for dimensions of a legal right
  ; triangle using the Pythagorean theorem:
  (assert (= (* c c) (+ (* a a) (* b b))))

  (display (list a b c))
  (newline)

  ; And, we want the second side to be the shorter one:
  (assert (< b a))

  ; Print out the answer:
  (display (list a b c))
  (newline))

Answer 1

Oh boy...this code looks like its trying to use continuations to do proper error handling. Which is...technically...possible. But honestly, since you said you were doing this in Racket and not just scheme, it would be much better to just use Racket's exception handling mechanism directly.

But I will break down the pieces of the program.

First, the general algorithm is:

• Assume a, b, and c are the first item in their respective lists.

• If when running code, you reach an assert that fails, go back in time and assume that c is actually the next thing in the list.

• If you've gone back in time enough to the point where you have run out of c possibilities, try the second item for b. Repeat until you run out of possibilities for b, then do the same for a.

Basically, its just a backtracking search algorithm that uses continuations in an attempt to look fancy.

The function

(define (current-continuation) 
  (call-with-current-continuation 
   (lambda (cc)
     (cc cc))))

Just grabs the current continuation. Basically you can think of it as a snapshot in time, which you can access by calling it as a function. So you can do:

(let ([cc (current-continuation)])
  ...)

Now in that block calling cc will rewind the computation to that point, replacing cc with what you passed into it. So if you were to, say, pass cc into it, like:

(let ([cc (current-continuation)])
  (cc cc))

your program would loop.

(define fail-stack '())

; fail : -> ...
(define (fail)
  (if (not (pair? fail-stack))
      (error "back-tracking stack exhausted!")
      (begin
        (let ((back-track-point (car fail-stack)))
          (set! fail-stack (cdr fail-stack))
          (back-track-point back-track-point)))))

; (assert condition) will cause
; condition to be true, and if there
; is no way to make it true, then
; it signals and error in the program.
(define (assert condition)
  (if (not condition)
      (fail)
      #t))  

This just keeps a stack of continuations to call when an assert fails.

; amb : list[a] -> a
(define (amb choices)
  (let ((cc (current-continuation)))
    (cond
      ((null? choices) (fail))
      ((pair? choices)
       (let ((choice (car choices)))
         (set! choices (cdr choices))
         (set! fail-stack (cons cc fail-stack))
         choice)))))

This sets up the space that can be explored.

; The following prints (4 3 5)
(let ((a (amb (list 1 2 3 4 5 6 7)))
      (b (amb (list 1 2 3 4 5 6 7)))
      (c (amb (list 1 2 3 4 5 6 7))))

  ; We're looking for dimensions of a legal right
  ; triangle using the Pythagorean theorem:
  (assert (= (* c c) (+ (* a a) (* b b))))

  (display (list a b c))
  (newline)

  ; And, we want the second side to be the shorter one:
  (assert (< b a))

  ; Print out the answer:
  (display (list a b c))
  (newline))

And this does the actual search, and prints out the results.