[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: address@hidden, "KELLEHER,KEVIN (Non-HP-Roseville,ex1)" <address@hidden>*Subject*: RE: continuations*From*: "Kenneth Dickey" <address@hidden>*Date*: Thu, 31 Jan 2002 17:37:17 +1100*Reply-to*: address@hidden*Sender*: 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

- Prev by Date:
**continuations** - Next by Date:
**Re: continuations** - Previous by thread:
**Re: continuations** - Next by thread:
**RE: continuations** - Index(es):