Re: So, what the heck is a continuation anyway?

[address@hidden (Gregory T. Sullivan)]

>>>>> "MF" == Matthias Felleisen <matthias@ccs.neu.edu> writes:

 MF> Pls check out Andrew Appel's SML of New Jersey compiler. He
 MF> documented the compiler in a book called "compiling with
 MF> continuations." It's a bit dated.

 MF> Notice that "continuation" in his book title is different from
 MF> the one the list is discussing right now.

Having (finally) caught up on ll1-discuss, there are a few comments
about continuations that I haven't yet seen made...

Appel's book uses a CPS (continuation passing style) intermediate
representation (IR), and he shows that CPS is amenable to compiler
analysis and manipulation.  Indeed, Kelsey [1] has shown a strong
correspondence between CPS and the more familiar Static Single
Assignment (SSA) form used in many compilers.

A closely related point is that if you write an interpreter in CPS,
you get "call/cc for free".  Guy's examples demonstrate this point
beautifully.  Now my points:

(1) Neither of the above CPS ideas -- using a CPS IR or implementing
    your interpreter in CPS -- is essential for implementing
    continuations in the language (but both make it easy).

    Furthermore, writing programs in continuation passing style
    requires only first class functions -- in fact, if you write in
    CPS you don't need call/cc at all.

(2) If you are considering providing continuations at the VM level,
    you may consider distinguishing between downward continuations and
    general continuations (that may be returned upwards).  If you know
    a continuation is downward-only, it is very cheap to implement.
    The first two examples in the R5RS documentation for call/cc
    (available in info format at [2]) are downward continuations:

     (call-with-current-continuation
       (lambda (exit)
         (for-each (lambda (x)
                     (if (negative? x)
                         (exit x)))
                   '(54 0 37 -3 245 19))
         #t))                               ==>  -3
     
     (define list-length
       (lambda (obj)
         (call-with-current-continuation
           (lambda (return)
             (letrec ((r
                       (lambda (obj)
                         (cond ((null? obj) 0)
                               ((pair? obj)
                                (+ (r (cdr obj)) 1))
                               (else (return #f))))))
               (r obj))))))


(3) The one thing I use upward continuations for is enabling
    "resumable exceptions":  At the throw site, the current
    continuation is captured and passed to whatever handler catches
    the exception.  If you want to resume execution where you threw,
    just invoke the captured continuation.  

    If all you want is simple exceptions, where the handler stack is
    dynamically unwound til a handler is caught, and execution resumes
    in the handler's dynamic extent, then downward continuations are
    all that's needed.

--

[1] A Correspondence between Continuation Passing Style and Static
    Single Assignment Form (1995)
    http://citeseer.nj.nec.com/kelsey95correspondence.html

[2] ftp://ftp-swiss.ai.mit.edu/pub/scm/r5rs.info.tar.gz

-- 
Greg      gregs@ai.mit.edu (617)253-5807
Sullivan  http://www.ai.mit.edu/~gregs/