[Bese-devel] Re: arnesi call/cc usage examples

Mac Chan emailmac at gmail.com
Sat May 6 20:09:10 UTC 2006


So, going thru all the devel archives _again_ give me a few insight of
the semantics of call/cc.

Larry D'Anna's examples are quite helpful, but I have to modify his
examples to run in the latest arnesi:

(with-call/cc
  (print (let/cc k
           (print 'a)
           (kall k 'b)
           (print 'c)
           'd)))

;; Here is an example of how to use this construct to implement coroutines
;; It should print out the first 10 pyramid numbers.

(defmacro coro (&body body)
  (with-unique-names (coro)
    `(let (,coro)
      (with-call/cc
	(flet ((yield (x)
		 (let/cc k
		   (setq ,coro k)
		   x)))
	  (yield :ok)
	  , at body))
      #'(lambda (x) (kall ,coro x)))))

(let* ((tri-cr (coro (loop with num = 0
			   for i = 1 then (1+ i)
			   do (yield (incf num i)))))
       (pyr-cr (coro (loop with num = 0
			   do (yield (incf num (funcall tri-cr nil)))))))
  (loop for i from 1 to 10
	collect (funcall pyr-cr nil)))

;; (1 4 10 20 35 56 84 120 165 220)



So the first thing I want to try is to write the depth first search
using arnesi:

(defparameter t1 '(a (b (d h)) (c e (f i) g)))

(defparameter *saved* nil)

(defun/cc dft-node (tree)
  (cond ((null tree) (restart-search))
        ((not (consp tree)) tree)
        (t (call/cc
            (lambda (cc)
              (setf *saved*
                    (cons #'(lambda ()
                              (kall cc (dft-node (cdr tree))))
                          *saved*))
              (dft-node (car tree)))))))

(defun/cc restart-search ()
  (if (null *saved*)
      'done
      (let ((cont (car *saved*)))
        (setf *saved* (cdr *saved*))
        (funcall cont))))

ARNESI> (with-call/cc (dft-node t1))
A
ARNESI> (with-call/cc (restart-search))
B
ARNESI> (with-call/cc (restart-search))
D
ARNESI> (with-call/cc (restart-search))
H
ARNESI> (with-call/cc (restart-search))
C
ARNESI> (with-call/cc (restart-search))
E
ARNESI> (with-call/cc (restart-search))
F
ARNESI> (with-call/cc (restart-search))
I
ARNESI> (with-call/cc (restart-search))
G
ARNESI> (with-call/cc (restart-search))
DONE

So far, so good.

However, when I try to package up the automatic backtracking in a
function, it doesn't work.

(defun/cc dft2 (tree)
  (setf *saved* nil)
  (let ((node (dft-node tree)))
    (cond ((eq node 'done) nil)
          (t (print node)
             (restart-search)))))

ARNESI> (with-call/cc (dft2 t1))
A  ;;;; we want dft2 to return ABDHCEFIG instead

Whereas the _On Lisp_ dft2 example written in continuation passing
style work as advertised.

How to write dft2 so it will return all the results (ABDHCEFIG) at once?


There's also an example in the archives that I don't quite understand:

(defvar *k* nil)

(with-call/cc
  (dotimes (i 3)
    (let/cc k
      (setf *k* k)
      i)))
0
CL-USER> (kall *k*)
1
CL-USER> (kall *k*)
2
CL-USER> (kall *k*)
NIL


In PG's _On Lisp_, he usually cons the continuation into a global list
and pop one off one at a time when resuming the computation.

In the above example that Marco gave, how come repeating calling *k*
will return different result?  I assume that the last (setf *k* k)
will overwrite the previous (setf *k* k) so calling (kall *k*) should
always return the same thing??

Thanks,
-- Mac

(PS: I was wondering if having call/cc in Lisp implementation would be
a good thing? It will greatly simplify things so we don't have to
emulate it in user code)



More information about the bese-devel mailing list