Re: continuation efficiency

[Marius Vollmer]

address@hidden (Thomas Bushnell, BSG) writes:

> I.  Is A substantially worse than B:
> 
>     A: (call/cc (lambda (c) (do-something)))
>     B: (do-something)

As Martin said, A is substantially worse than B.

As a work around, you could use the (non-standard) `catch/throw' combo:

    (define (call/ec proc)
     (let ((tag (gensym)))
       (catch tag
         (lambda () (proc (lambda (val) (throw tag val))))
         (lambda (tag val) val))))

(call/ec stands for call-with-escape-continuation) Then, use call/ec
instead of call/cc.  It is cheaper than call/cc since it does not copy
the stack.  In return, it only allows `upward' invokations of
Actually, I think we should have call/ec as a builtin.  I have a
longish proposal about call/cc, call/ec, dynamic-wind, etc.  Appended
below.

>     A: (call/cc (lambda (c) (do-some-things) (c do-something)))
>     B: (begin (do-some-things) (do-something))

Shouldn't that be

      A: (call/cc (lambda (c) (do-some-things) (c (do-something))))

(i.e. invoking do-something as opposed to returning it), else A and B
do not evaluate to the same value.

> Does the following expression (which runs forever) run forever, or
> does it run out of space?  (The astute will notice a connection
> between this question and number I above.)
> 
> (letrec
>   ((whizzie 
>    (lambda (argument)
>     (argument (call/cc whizzie)))))
>   (call/cc whizzie))

Hmm, the call (call/cc whizzie) inside whizzie is not in a tail
position so I would not expect this to run in constant space,
regardless of call/cc.  I see it as analogous to

    (define (whizzie arg) (identity (whizzie arg)))

compared to

    (define (whizzie arg) (whizzie arg))

The first does not run in constant space while the latter does.


- - - - - 
[from an older article, comments in brackets.]

If you people can tolerate more incoherent ramblings about
continuations and what I think of them, here is some more.  (I will
sound as if Guile doesn't have anything like catch/throw or error.
This is to start from a clean slate.)

According to my current thinking (which changes every day, but that
wont stop me from posting it anyway), call/cc with dynamic-wind is
fine as long as we don't seriously consider `exceptions' (or more
generally, `non-local-exits').

Contrary to what I said in an earlier post, I now think that cleanup
actions _are_ important in reaction non-local exits.  Using
dynamic-wind can not provide these cleanup actions since the `leave'
thunk can not know whether the control flow will return eventually.
Thus, dynamic-wind is only useful for changes to the system that have
a dynamic extent.  Examples are setting global parameters like the
current ports or the current module (eek!).

For cleanup actions in reaction to non-local exits, we need an
additional mechanism, a second pair of functions.  Lets call them
call/ec and escape-protect.  Call/ec is what we are talking about all
the time, it will provide an escape procedure that will jump back to
the continuation of the call to call/ec.  On its way, it will run all
`escape handlers' established by escape-protect (in addition to
running the `leave' thunks of active dynamic-winds).  Once an escape
handler has been run, the corresponding escape-protect activation can
not be re-entered.  Thus, an escape handler is guaranteed to run at
most once, and once it has run, its body will not be re-activated
again.

We will also need a condition system of some sort.  With this, I mean
the establishment of catch points that will catch certain kinds of
exceptional situations.  Raising such an exception corresponds to
finding the right escape procedure and invoking it. [I now think that
exception handlers should be conceptually separate from escape
procedures.  The my-catch and my-throw procedures below should be
ignored.]

The important thing here is that continuations created by call/cc do
not run the escape handlers established by escape-protect.

Here is a possible, naive implementation, going from call/cc and
dynamic-wind to catch and throw.  This is not in any way meant to
replace the stuff we already have, only to help me make my thoughts
more concrete and to have a basis for discussing the fine points.
When we agree upon some semantics that are different from what we have
now, we can modify Guile to implement them efficiently.

    ;;; call/ec and escape-protect

    (define escape-handlers '())

    (define (make-handler thunk)
      (cons #t thunk))

    (define (handler-active? h)
      (car h))

    (define (run-handler h)
      (set-car! h #f)
      ((cdr h)))

    (define (escape-protect body leave)
      (let* ((my-handler (make-handler leave))
             (other-handlers (cons my-handler escape-handlers))
             (swap (lambda ()
                     (let ((t escape-handlers))
                       (set! escape-handlers other-handlers)
                       (set! other-handlers t)))))
        (dynamic-wind
            (lambda ()
              (if (not (handler-active? my-handler))
                  (error "re-entering already escaped escape-protect"))
              (swap))
            (lambda ()
              (body)
              (run-handler my-handler))
            swap)))

    (define (call-with-escape-continuation proc)
      (let* ((valid #t)
             (source-handlers escape-handlers)
             (val (call-with-current-continuation
                   (lambda (k)
                     (proc (lambda (v)
                             (set! source-handlers escape-handlers)
                             (k v)))))))
        (if (not valid)
            (error "escape continuation called from invalid context"))
        (set! valid #f)
        (do ((handlers source-handlers (cdr handlers)))
            ((eq? handlers escape-handlers))
          (run-handler (car handlers)))
        val))

    ;;; catch and throw

    (define catchers '())

    (define (make-catcher tag receiver)
      (cons tag receiver))

    (define (catcher-match? tag catcher)
      (or (eq? #t (car catcher)) (eq? tag (car catcher))))

    (define (throw-to-catcher catcher args)
      ((cdr catcher) (cons #f args)))

    (define (my-catch tag body handler)
      (let ((val (call-with-escape-continuation
                  (lambda (k)
                    (let* ((my-catcher (make-catcher tag k))
                           (other-catchers (cons my-catcher catchers))
                           (swap (lambda ()
                                   (let ((t catchers))
                                     (set! catchers other-catchers)
                                     (set! other-catchers t)))))
                      (dynamic-wind
                          swap
                          (lambda ()
                            (cons #t (body)))
                          swap))))))
        (if (car val)
            (cdr val)
            (begin
              (apply handler (cdr val))))))

    (define (my-throw tag . args)
      (let loop ((c catchers))
        (cond
         ((null? c)
          (format #t "PANIC: no catcher for tag ~A.\n" tag)
          (exit 1))
         ((catcher-match? tag (car c))
          (throw-to-catcher (car c) (cons tag args)))
         (else
          (loop (cdr c))))))

    ;;; Test

    (define call/ec call-with-escape-continuation)

    (define-macro (let/ec var . body)
      `(call/ec (lambda (,var) ,@body)))

    ;; basic call/ec

    (define (t1)
      (let/ec return
        (return 1)
        2))

    (format #t "t1: ~A\n" (t1))

    ;; escape-protect

    (define (t2)
      (let/ec return
        (t3 return)
        'foo))

    (define (t3 return)
      (escape-protect
       (lambda () (t4 return))
       (lambda () (display "t3: protect\n"))))

    (define cont #f)
    (define ret #f)

    (define (t4 return)
      (call-with-current-continuation
       (lambda (k)
         (set! cont k)
         (set! ret return)
         (return 'bar))))

    (format #t "t2: ~A\n" (t2))

    ;; At this point:
    ;;
    ;; (cont 12) => ERROR: re-entering already escaped escape-protect
    ;; (ret 12) => ERROR: escape continuation called from invalid context

    ;; catch and throw

    (define (t5)
      (my-catch #t
        (lambda ()
          (my-throw 'fooo 1 2 3))
        (lambda args
          (pk 'caught args)
          (my-throw 'foo 4 5 6))))

    (t5)

A fine point: the `leave' thunks of escape-protect run in the context
of the call/ec, not in the context of the escape-protect.  This might
be a feature or a bug.  It should be fixable anyway. [Especially when
we have a integrated escape-protect, dynamic-wind implementation.]