RE: Demystifying Continuations

["David Simmons" <address@hidden>]

> -----Original Message-----
> From: Avi Bryant [mailto:avi@beta4.com]
> Sent: Thursday, March 21, 2002 7:08 PM
> To: David Simmons
> Cc: ll1-discuss@ai.mit.edu
> Subject: Re: Demystifying Continuations
> 
> On Thu, 21 Mar 2002, David Simmons wrote:
> 
> > 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).
> 
> <snip>
> 
> > 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.
> 
> Yup.  In fact, I make very heavy use of this approach in my Squeak web
> framework (http://beta4.com/seaside).  The implementation of
> continuations and call/cc that I use is around 8 or 9 lines of code.
> 
> However, your point about native threads is quite apt - simply copying
the
> context objects to get continuations only works in fairly
straightforward
> VMs like Squeak's.  I've been unable to get continuations working in
> smalltalks like Smalltalk/X or Smalltalk MT that have a closer
> relationship to the C stack (to Cincom's credit, the VW JIT handles
them
> just fine - but then VW doesn't have native threading).
> 
> Have you tried implementing call/cc in SmallScript?  Will you?  Among
> other things, it would be nice to have another target to port my
framework
> to...

To be straightforward, this is exactly why I made this posting. I am
interested in providing a system that supports full context abstractions
that can be used to one degree or another with a pre-emptive native
threading model and foreign function mechanisms. 

My goals here are AOS in the long term, I am not imminently about to
implement them in their full glory. I am very satisfied with the current
context mechanisms and their capabilities for addressing almost all
standard/classical uses of context objects.

For many years I had been sure that I understood continuations. However,
in an effort to become more formally educated and knowledgeable with
regard to functional languages I started digging more deeply. I read
explanations of continuations that began to leave me feeling like I was
missing something or perhaps was just not seeing a higher principle. I
have observed numerous threads of discussion over the last year, where
people tried to explain continuations. Some of them were people whom I
know very well. 

In almost every case [people threads or literature] I was left with the
sense that maybe I did not really understand continuations. Maybe I was
missing some nuance. The explanations did not satisfactorily describe
what they were or define their semantics in basic terms. Instead they
often said what could be done with them and provided examples of using
them -- from which one was suppose to infer the rest. 

But, as a VM architect, I need to understand the exact semantics. From
that starting point, I can see how to implement them or to extend and
generalize their principles with other aspects of a sophisticated
execution model provided in a general dynamic language VM design.

Some background on my work...

AOS VM v1-2 and its Smalltalk dialect was implemented on the MacOS circa
1991+. It provided true pre-emptive green threads and offered full
context manipulation services. And was the first pre-emptively threaded
Smalltalk -- and had corresponding pre-emptive thread safe frameworks.
Including persisting of contexts and migrating them across machines in
real-time. This was one of the key ideas behind the "Agent" part of the
Agents Object System (AOS).

In moving to AOS v3 Win32 circa 1996+ I felt it was essential to support
native pre-emptive threads. Therefore, the v3 system provided full
pre-emptive native thread integration -- and was the first pre-emptive
natively threaded Smalltalk. This led to a number of implementation
quandaries that were "apparently" not reconcilable with persistable
green threads and full contexts -- as you allude to in your comments
regarding Smalltalk/X and MT.

In designing AOS v4, I went back to first principles. I designed and
re-built everything from scratch. I re-examined just about every
assumption or idea about dynamic language and object system
implementation. The v4 AOS architecture is quite an evolution from its
predecessors. 

One of the driving technical forces in starting over was to reduce
complexity and eliminate the mono-lithic nature of Smalltalk. This was
essential to fit into a componentized world and meet the demands of
scripting and just-in-time system integration/composition.

Ok, so that was a quick rundown on some of the philosophy and history.
The long and short of it is that I can clone stack ranges. A fiber
allows one to have multiple stacks. A process can be configured to
re-use the same virtual addresses. 

Therefore, it is possible to create full-contexts (continuations) on
native threads within a running process. It may also be possible to
persist them, migrate them, and restore them on a given platform. This
is one of the things I am interested in exploring in the long term. So
that one can mix the benefits of lightweight fibers, and lighter weight
contexts, with the hardware advantages of SMP based pre-emptive native
OS level threading and synchronization.

Depending on how old you are, this idea is very similar to the unix
style approach that was used to build fast-startup versions of
applications like TeX. That probably dates me back to the 70's and 80's.
But the idea was that you could take a snapshot of a running process in
virtual memory and then just re-load it with minimal custom re-hooking.
This all worked because a process would load everything into the same
virtual address space every time.

Which is basically the same technique one needs to use to support
contexts/continuations on a native thread. Put another way, this is the
same kind of frame walking and manipulation characteristics that an
edit-and-continue debugger needs to have for supporting a statically
typed and compiled language like C++.

-- Dave S. [www.smallscript.org]

> 
> Cheers,
> Avi