This is the mail archive of the guile@cygnus.com mailing list for the guile project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: searching an explanation: call/cc and 'do' strangeness


Firstly, the idea of call/cc is simple when you get it right.  The
usual problem is that people don't know exactly what a continuation
is.

Here's an attempt at a quick explanation:

  Continuations
  -------------

  A continuation is a property of an expression E inside a containing
  expression P:

    P = (... (... E ...) ...)

  It is a procedure which represents everything that will happen from
  the point in execution time when E returns its value.  It takes the
  value that would normally be supplied by E as its single argument
  and then proceeds as if the value had been supplied by E.

  It is often correct to say that the continuation of E above is:

    (lambda (x) (... (... x ...) ...))

  I say "often" because the continuation, in fact, also captures the
  things that happened around P, for example the exit to the repl
  loop.

  call/cc
  -------

  `call/cc' takes a "receiver" as argument.  (A receiver is simply a
  procedure which takes a continuation as argument.)
  `call/cc' captures it's own continuation and passes it to the
  receiver, i.e., `call/cc' applies the receiver to its own
  continuation.

  This means that if, as a consequence of the evaluation of the
  receiver body, at any later time the continuation is called with an
  argument x, evaluation will continue as if x was returned by the
  `call/cc' expression.  In fact, this is what will happen.
  
  A strange thing about this is that if we call the continuation
  multiple times, the `call/cc' expression will return multiple times.

  Example
  -------

  (define set-counter! #f)

  ;; WARNING There's a dog burried in this code
  (define counter
    (let ((c (call/cc (lambda (continuation)
			(set! set-counter! continuation)
			0))))
    (lambda ()
      (set! c (+ 1 c))
      c)))

  Now let's see how this code behaves

  > (counter)
  1
  > (counter)
  2
  > (set-counter! 0)
  > (counter)
  1

  Everything seems OK, right?

  BUT!

  > (define (counter) 'foo)
  > (set-counter! 0)
  > (counter)
  1

  !!! We had redefined counter to return `foo'.  What has happened?
  Answer: `call/cc' captured it's continuation, i.e. everything that
  will happen when `call/cc' returns.  This includes the definition of
  `counter', which means that each call to `set-counter!' will
  redefine `counter'.

  This shows that some care is needed when using call/cc.

  To avoid unexpected side-effects when using `call/cc': Be very
  strict when using `call/cc'.

  Always be aware that calling a continuation is essentially
  the same thing as a "jump" into a previous state of evaluation.

  Also note that that state of evaluation doesn't include the values
  of variables.

Here are two suggestions on how to handle your specific problem:

;;; Dahl-Hoare Korutiner
;;;
;;;   Described by
;;;
;;;   Christopher T. Haynes och Daniel P. Friedman
;;;
;;;   "Continuations and Coroutines", 1984
;;;
;;; Modified to take arbitrary number of arguments
;;; by Joacim Halén 950410
;;;

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

(define make-coroutine
  (lambda (f)
    (call/cc
     (lambda (maker)
       (let ((lcs '*) (cc '*))
         (let ((resume (lambda (dest . args)
                         (call/cc
                          (lambda (k)
                            (set! lcs k)
                            (apply dest (cons cc args))))))
               (detach (lambda args
                         (call/cc
                          (lambda (k)
                            (set! lcs k)
                            (apply cc args))))))
           (detach
            ((f resume detach)
             (call/cc
              (lambda (k)
                (set! lcs k)
                (maker (lambda (cont . args)
                         (set! cc cont)
                         (apply lcs args)))))))))))))

(define call
  (lambda (dest . args)
    (call/cc
     (lambda (k)
       (apply dest (cons k args))))))

;;; Version with one coroutine

(define scopeWalkDemo
  (let ((coroutine #f))
    (lambda (beginp)
      (if beginp
	  (set! coroutine
		(make-coroutine
		 (lambda (resume detach)
		   (lambda (init)
		     (let ((l (list 'cow 'horse 'pig )))
		       (do ((i 0 (+ i 1)))
			   ((= i (length l)))
			 (detach (list-ref l i)))))))))
      (call coroutine #f))))

(define v-demo (make-vector 3))

(define (test)
  (do ((j 0 (1+ j))
       (cont #t)
       (tmp #f))	
      ((>= j 3)) 
    (write-line (list cont j v-demo))
    (set! tmp (scopeWalkDemo cont))
    (vector-set! v-demo j tmp)
    (set! cont #f)))

;;; Version with two cooperating coroutines

(define (scopeWalkDemo2)
  (make-coroutine
   (lambda (resume detach)
     (lambda (caller)
       (detach)
       (let ((l (list 'cow 'horse 'pig )))
	 (do ((i 0 (+ i 1)))
	     ((= i (length l)))
	   (resume caller (list-ref l i))))))))

(define (test2)
  (let* ((walker (scopeWalkDemo2))
	 (user
	  (make-coroutine
	   (lambda (resume detach)
	     (lambda (init)
	       (do ((j 0 (1+ j))
		    (cont #t)
		    (tmp #f))
		   ((>= j 3)) 
		 (write-line (list cont j v-demo))
		 (set! tmp (resume walker #f))
		 (vector-set! v-demo j tmp)
		 (set! cont #f)))))))
    (call walker user) ; Pass caller
    (call user #f)))