On Fri, 1 Feb 2002, Jerzy Karczmarczuk wrote:

> 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.
[snip]

> 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.
[snip]

I'd still say "no". You don't need tail call optimization (TCO) to
implement have explicit continuations. And you don't need TCO to use
explicit, full, resumable continuations to use them to implement a variety
of control flow structures (exceptions, for example), and even have that
be somewhat practical. You do need them for general practical use of
Continuation Passing Style (CPS), and I agree that CPS is the best reason
to want them (in general, you're prolly better off implementing your
control flow with a less general mechanism).

Let me add a more informal, sloganny account of
continuations: continuations are "dynamic" closures. That is, just as
closures "close over" the lexical environment,  continuations "close
over" the *invoking* environment (the analogy is with dynamic scoping of
variables). By "freezing" a copy of the calling stack, continuations 
let you "continue" the compuation from that point any number of
times. (Sorta like snapshotting the image after a debugger popped
up. No matter what you do after that, you can always roll back to
that snapshotted moment and "continue" in a different (or the the
same!) way.) 

Making fully resumable, indefinite extent, multiply invokable
closures or continuations available to the host language is, in general,
more heavyweight than alternatives (at least for the implementer). But
when you need them, you need them.

(Note that a snapshot saves a lot more than the current continuation :))

Cheers,
Bijan Parsia.