RE: continuations

["Kenneth Dickey" <address@hidden>]

I'll take a shot at it.  Continuations are a source of great expressive
power and confusion.  
 
As you point out, logically a continuation is a control context
representing "the rest of the program". 
 
The "square egg" explanation is that you capture/copy the stack at the
point of call so that you can go back and re-execute it later, perhaps
multiple times.  
 
Continuations are related to CPS (Continuation Passing Style).  Which are
continuations built by hand (er, closure ;^).
 
E.g. 
(define (factorial n) (if (< n 2) 1 (* n (factorial (- n 1)))
 
One can think of the stack at the maximum depth of (factorial 5) as:
 
(factorial 5) => (* 5 (* 4 (* 3 (* 2 (factorial 1)))))
 
in CPS form of factorial is:
 
(define (fact n k) ;; k is the continuation, a one argument block closure.
   (if (< n 2) 
       (k 1)
       (fact (- n 1) (lambda (result) (k (* result n))
 
So each "stack frame" is a procedure which does "the rest of the
computation", i.e. do the multiply and return a value to "the rest of the
computation".
 
If you capture this continuation, you can do something else, apply it later
zero or more times.
 
So if we capture a contination and return it instead of a value this
procedure represents the "rest of the computation", the last bit of which
is:
 
  (* 5 (* 4 (* 3 (* 2 []))))
 
Where [] represents the "hole" where the continuation was captured.
 
OK, hold on to your seat.  Here is where it gets tricky.
 
> (define (call/cc-fact n)
    ;; define an "exit procedure" to return the inner continuation
    (call-with-current-continuation 
      (lambda (exit) 
       (letrec ( 
        (cc/fact
         (lambda (n)                                    
           (if (< n 2)    
              (call-with-current-continuation
                  ;; return inner continuation
                  (lambda (k) (exit (lambda (n) (k n)))))
              (* n (cc/fact (- n 1)))))) 
                )
        (cc/fact n)))))
 
> (call/cc-fact 5)
#<procedure #x14532A>
 
> (define k (call/cc-fact 5)) ;; captures (* 5 (* 4 (* 3 (* 2 []))))

> (define k2 k)
 
> (k 1)
 
> k
120

> k2
#<procedure k2>

> (k2 5)

> k
600

Wow!
 
So what happened was this.  Call/cc-fact captured the outer (exit)
continuation **at the point where k was about to be defined**.  When we
invoked the continuation (k 1) then the result was computed at the point
where (define k []) was being executed.
 
So after invoking (k 1) we had the effect of (define k 120).

After (k2 5) we re-defined k as (* 5 4 3 2 5) => 600.
 
So (call-with-current-continuation <proc>) packages up the "control
context" and hands that as a procedure/closure of one argument to the
<proc>.
 
Continuations are very useful in implementing debugging, handling
interrupts, REPL command levels, and multithreading.  [Hey, I got an
interrupt, let me capture the continuation, service the interrupt and get
back to you.  Actually, I have a higher priority thread, so let me invoke
that thread's continuation instead and remember this one's continuation for
later].
 
Continuations really are too powerful.  There are a great many papers
written on how to constrain this power.

Hope the above helps,
-KenD

> [Original Message]
> From: KELLEHER,KEVIN (Non-HP-Roseville,ex1) <kevin_kelleher@non.hp.com>
> To: <ll1-discuss@ai.mit.edu>
 > Date: 2/1/2002 11:37:56 AM
> Subject: continuations
>
> 
> Continuations may be as simple as can be,
> but I cannot grasp the concept or their use.
> 
> I've been reading Kent Dibvig's "The Scheme Programming
> Language" (among other things) but I just don't get it.
> 
> Could someone suggest a paper I could read (perhaps from 
> http://library.readscheme.org/page6.html)?
> 
> I'm reminded of how obtuse the use of pointers seemed to
> me when I was learning C.  Many explanations limited
> themselves to the statement that a pointer is an address,
> as if that said it all.  It does explain everything, but only
> if you already understand it.  If you don't, the statement
> is gibberish.  You can't jump from that terse statement
> to making a linked list.
> 
> Kevin Kelleher


--- K