Anthony Hannan:


> Is tail recursion required for continuations?  I really don't understand
> continuations, can you give me some pointers?

Scott Crosby says:

> Tail recursion is not needed for continuations. You only need closures,
> but without tail recursions, continuations-style programming can overflow
> the stack much easier.
> 
> Continuations are basically when you have a 'what do I do next' argument.
> Normally, thats implicit, but not always. A stack of frames is a
> continuation.. Or, an error handler is a continuation.


I would be more categorical and I would say YES. Otherwise there is no point
whatsoever in speaking about them. They are functional models of "goto".
I won't argue with Scott, just tell a few more words from a different
perspective.

For a functional language instead of having a function
f x = {do something with x, return a result}

you define
f x cont = {something is done with x and as the LAST operation, the *function*
            cont is called with the result of previous work as the argument}

The function "cont" calls 'its' continuation at the end.
If this is pushed to the limits, *ALL* calls are terminal.

Instead of computing sqrt(x*x + y*y) you define
f x y cont = 
 mult x x (lambda(a) -> 
   mult y y (lambda(b) ->
     add a b  (lambda(c) ->
       sqrt c cont )))

which can be streamlined by the code generator as
a:=x*x
b:=y*y
c:=a+b
output (sqrt c)
and that's why the CPS is used heavily (well, not so...) in compilation. It
is a code adapted rather to *register* machines than to the stack-based ones.
 
If there is a real recursion in the algorithm, something must be stacked
manually by the function (stacked physically with the transmission of
the stack, or the creation of a functional object on the heap; this object
contains the "stacked" data, it must be a fully-fledged closure), but the 
control flow is linear. All the loops, repeat *all*, are realized through
continuations, and this includes infinite loops as well. So, without tail
call optimization it won't work.

Some links/papers

http://entropy.uark.edu/~jdfulto/cps.html
http://library.readscheme.org/page6.html
http://www.swiss.ai.mit.edu/projects/amorphous/hlsim/node92.html
http://citeseer.nj.nec.com/12127.html

and many others.

BTW, I am *SURE* that in Smalltalk it would be possible to rewrite the
compiler in the CPS style, and also to include the equivalent of the
super-powerful call/cc construct in Scheme.

The question is: << cui bono >>? Would anybody be happier with? (The
members of the Satanic Sect of Believers in The Fundamental Role of the
Debugger would be rather less happy...)

Jerzy Karczmarczuk
Caen, France