[Bese-devel] arnesi call/cc usage examples

[Mac Chan]

Hi,

I'm reading the the last few chapters of _On Lisp_. The
nondeterministic programs are pretty cool, but using the continuation
passing style is very convenient at times.

Since I'm still not very well versed in advanced lisp techniques, I
couldn't figure out by myself how to use the call/cc interpreter in
arnesi.

Could somebody try to dumb it down and explains in high level how it works?

Actually, if any kind soul can translate the following scheme examples
as described in _On Lisp_ to CL using the arnesi library, that'll
greatly help newbies alike to understand how to use it.

Thanks!
-- Mac

;; Figure 22.3 contains a pair of functions to guess two numbers which
;; sum to a number given by the caller.  The first function,
;; two-numbers, nondeterministically chooses two numbers and returns
;; them in a list. When we call parlor-trick, it calls two-numbers for
;; a list of two integers. Note that, in making its choice,
;; two-numbers doesn't have access to the number entered by the user.

;; Figure 22.3: Choice in a subroutine.

(define (two-numbers)
    (list (choose '(0 1 2 3 4 5))
          (choose '(0 1 2 3 4 5))))

(define (parlor-trick sum)
    (let ((nums (two-numbers)))
      (if (= (apply + nums) sum)
          `(the sum of , at nums)
          (fail))))


;; Figure 20.3: Tree traversal using continuations.

(define (dft tree)
    (cond ((null? tree) ())
          ((not (pair? tree)) (write tree))
          (else (dft (car tree))
                (dft (cdr tree)))))

(define *saved* ())

(define (dft-node tree)
    (cond ((null? tree) (restart))
          ((not (pair? tree)) tree)
          (else (call-with-current-continuation
                 (lambda (cc)
                   (set! *saved*
                         (cons (lambda ()
                                 (cc (dft-node (cdr tree))))
                               *saved*))
                   (dft-node (car tree)))))))

(define (restart)
    (if (null? *saved*)
        'done
        (let ((cont (car *saved*)))
          (set! *saved* (cdr *saved*))
          (cont))))

(define (dft2 tree)
    (set! *saved* ())
  (let ((node (dft-node tree)))
    (cond ((eq? node 'done) ())
          (else (write node)
                (restart)))))

;; Suppose nodes is bound to a list of nodes in a tree, and (kids n)
;; is a function which returns the descendants of node n, or #f if
;; there are none. We want to write a function (descent n1 n2) which
;; returns a list of nodes on some path from n1 to its descendant n2,
;; if there is one.

;; Figure 22.2: Nondeterministic tree search.

(define (descent n1 n2)
    (cond ((eq? n1 n2) (list n2))
          ((null? (kids n1)) (fail))
          (else (cons n1 (descent (choose (kids n1)) n2)))))