Subject: What are Continuations? (in the context of FP)

From: Shlomi Fish <[email-masked]>
Date: Sun, 30 Dec 2001 20:21:55 +0200 (IST)

What exactly are continuations, in the context of Functional Programming.
I could not find any page on the Internet that really explains what they
are. For instance, their entry from the comp.lang.functional FAQ is
missing.

I saw some examples from them and from what I saw they were arguments to
functions who were themselves dynamic references to functions, which were
manipulated somehow. But I'd like a more detailed explanation.

Regards,

	Shlomi Fish

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"

---

From: Omer Musaev <[email-masked]>
Date: Mon, 31 Dec 2001 19:26:35 +0200

> -----Original Message-----
> From: Shlomi Fish [mailto:[email-masked]]
> Sent: Sunday, December 30, 2001 8:22 PM
> To: Hackers-IL
> Subject: [hackers-il] What are Continuations? (in the context of FP)
> 
> 
> 

Continuation is a state of computational process. Continuation Passing 
is a method of programming by extending a state of a computational process
instead of collecting nessesary data for later processing. It is used mostly
in internals of interpreters or compilers. Similar approach can be found in 
Command Pattern [3] 

> manipulated somehow. But I'd like a more detailed explanation.

You were misleaded by implementation of a concept of storing a 
state of a computation in a high-order argument. 

Consider factorial function:

In scheme it is:

;; snippet 1 
(define (recursive-factorial n)
   (cond 
      (( zero? n ) 1 )
      (else ( * n ( recursive-factorial ( sub1 n ) ) ) ) ) )

(recursive-factorial n )
;; end of snippet 1

Now CPS form:

In scheme it is:

;; snippet 2
(define (cps-factorial n cont )
   ( cond 
      (( zero? n ) ( cont 1 ) )
      ( else ( cps-factorial ( sub1 n ) (lambda (x) ( * n ( cont x ) ) ) ) )
) )

(define (final-cont x) x ) 

(cps-factorial n final-cont ) 
;; end of snippet 2 

First, notice that nothing has to be kept on stack. This enables compiler 
to apply "tail call elimination" pattern of optimization here.

In addition notice that state of computation, which is passed on stack in 
first snippet, is now passed as an s-expression. This s-expression is a 
continuation we are talking about.

Now there is obvious question:
Why should anyone use CPS form, and not accumulator form, like in:

;; snippet 3

(define (acc-factorial n )
   (define (acc-factorial-inner n acc)
     ( cond 
        (( zero? n ) acc )
        ( else (acc-factorial-inner (sub1 n) (* n acc ) ) ) ) ) )
   (acc-factorial-inner n 1 ) )

(acc-factorial n )
;; end of snippet 3 

The answer is 1) that conversion into CPS can be performed for any 
recursive function, while conversion to accumulated form can,
if at all, be used on ordinals only and 2) that abovementioned conversion 
to CPS form can be performed automatically [1].

More examples can be found at [2]
Hope that this answer helps.

References:

[1] Essentials of Programming Languages, 8.2 
    http://www.mhhe.com/catalogs/0070224439.mhtml

[2] sample code from abovementioned book
    http://www.cs.indiana.edu/eopl/code/interps/  

[3] The Command Pattern
    http://www-white.media.mit.edu/~tpminka/patterns/Command.html

-- 
Omer Mussaev
Software Developer
Mercury Interactive / Topaz Prism R&D
Application Team