Re: Demystifying Continuations

[Paul Graham <address@hidden>]

You're right, continuations are not hard to understand at
the level of implementation.  They're stacks plus program
counters.  What gets mind-bending is what you can do with
them.  Nondeterministic algorithms, for example.  Or
continuations called on themselves.

A good analogy would be Euler's formula.  e, i, pi, and 
-1 are not hard to represent.  But the fact that e^i*pi = -1
seems to me very uncanny.

--pg

--David Simmons wrote:
> Hi All,
> 
> Coming from a Smalltalk implementers background, I have found myself
> quite confused by the plethora of almost mystical descriptions
> surrounding the term "continuation" in popular CS literature. 
> 
> To my less enlightened brain, continuations seem to be a very simple
> concept that is much more easily understood in terms of stacks,
> call-chains, and frames (activation-records/contexts).
> 
> Simply put, from all I've read and all I can tell they are:
> 
> A cloneable reified objectification of a stack (call-chain w/closures).
> 
> In other words, the stack is objectified as a collection of
> pending/in-progress function/method calls. 
> 
> The collection elements are pending function/methods (call-chain)
> frames/activation-records [typically linked from child to parent].
> 
> The frames/activation-records are closures. Meaning that all their local
> state is captured within the aggregate that represents the
> frame/activation-record/context.
> 
> Since (in a Smalltalk implementation) these things are all objects, we
> can copy them (cloneable). And, in Smalltalk, a <Context> is executable
> and otherwise manipulatable through a wide range of MOP facilities. 
> 
> We can start, restart, or otherwise configure a context anyway we want.
> In most Smalltalks the entire debugger architecture is built through the
> use of contexts and related MOP services.
> 
> So a callcc idea is really just a return to the currently configured
> "previous context".  Where, in statically typed and compiled languages
> we typically have not access to the stack nor do we have an
> objectification of the stack that allows us to restructure it
> dynamically through MOP/Context services.
> ================
> 
> Having said all that, have I described and/or captured what a
> continuation is? Are there any special nuances I have left out?
> 
> -- SIDE NOTE ON NATIVE THREADS --
> Further noting that since a continuation is really a capturing of state
> both "for" and "within" a given execution context, there are technical
> issues with creating continuations on native OS threads. 
> 
> Where a native OS thread had significant thread-local state, and
> OS/Process characteristics that a "classic" continuation architecture
> would not include. On systems like Win32 we can use fibers to create an
> efficient continuation architecture [where we can copy in/out stack
> ranges and TIB information]. 
> 
> This allows us to create generally safe continuations that include
> native DLL/EXE library calls within the call-chain.
> -- END SIDE NOTE ON NATIVE THREADS --
> 
> -- Dave S. [SmallScript Corp]
> 
> SmallScript for the AOS & .NET Platforms
> David.Simmons@SmallScript.com | http://www.smallscript.org
>