Re: [boost] [SoC] Presentation of Boost.Coroutine

From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2006-09-14 13:43:15

On 9/14/06, Jose <jmalv04_at_[hidden]> wrote:
> On 9/14/06, Giovanni Piero Deretta <gpderetta_at_[hidden]> wrote:
> >
> > A continuation can be restored multiple times, and this behaviour is
> > for example used to implement back button handling (the continuation
> > relative to the previous page state is saved, so it can be restored
> > when the previous state is reloaded).
> >
> > I do not see how this could be implemented with coroutines
> > automatically unless coroutines where deepcopy-able (you could copy a
> > coroutine and then resome that copy). Unfortuantely it is not feasible
> > to make deep copies of them in the current language.
>
>
> I don't understand what you mean by "automatically" .
> Also why is not
> feasible
> to make deep copies ?
>I don't know enough to understand that the back
> button results in full continuations and the other cases don't.
>

Full continuations store the execution state when captured. You can
restart them later and recapture the execution state in a new
continuation without invalidating the previous continuation. Thus you
get automatic backtracking (continuations are extremely good a that):
you store a continuation for each state you might want to backtrack
later and you are done. Coroutines (and one shot continuations)
cannot. If a one shot continuation is restarted, it cannot be
restarted one more time, thus they are not useful for backtracking.
You need to implement backtracking by hands. It is not tivial.

When the user clicks on the back button it wants to return to a
previous state even if it did some progress since then. Full
continuations are great to implement this.

All other cases (that i can think of now) need to capture the current
execution state only to restore it when more input from the user come
in. There is no need to restart a continuation more than once. In
practice this is one of the most obvious use cases for coroutines.
Continuations are just used to implement them.

> > As far as i can see, this is the only place where the 'fullness'
> > aspect of web continuations is used. If you can handle the back button
> > problem in some other way or simply ignore the problem, then
> > coroutines are a good way to implement web continuations.
>
>
> >From reading "Revisiting Coroutines",  I thought full continuations could
> be created from coroutines, not just partial continuations but I must be
> mistaken.
>

Yes, the paper only talks about equivalence of coroutines with one
shot continuations and semicontinuations.

>  http://rifers.org/wiki/display/RIFE/Web+continuations
> See the section on "Different continuation handling models" for info
> on how rife does this to fully support the back-button

In practice they use copyable coroutines. If a coroutine is copyable,
you can copy it and restart the copy. Thus the original keep its
execution state and is not invalidated. With copyable coroutines you
could infact implement full continuations. Unfortunately copyable
coroutines are hard and extremely expensive. RIFE has the advantage of
being java-only, so they only need to target one (virtual)
architecture. They (or at least i think this is how it works) can
preprocess the bytecode and make copies of all local objects by
invoking clone (remember that all java objects carry type information
with them, except builtins, but this can be memcopyed safely) in a
specific execution frame: as far as I understand you can call pause()
*only* inside processElement() . This is even more restrictive than
stackless coroutines. This limitation is not to get a performance hit
in other code (probably to limit the amount of state to be copyed and
the number of frames to be analized). As a final limitation, you
cannot have backtracking if some local objects are not Cloneable (most
are though).

These are a too great limitation for a general purpose library like
mine (even RIFE provieds a way to disable full continuations with
setCloneContinuation(false)). Also walking the stack to search for
object to copy cannot be implemented portably (or even non portably),
unless one where to be restricted to never allocate non builtin stack
objects and have all heap allocated objects inherit from a common
base. This would kill performance, would be a very non iodimatic c++
and still be hard to do and very fragile.

Theoretically compiler support could make coroutine copying possible
and even relatively cheap (no much more than the cost of copying every
single local object in scope) . In fact some compilers know at every
moment the set of all objects alive in the stack for unwinding
purposes.

For the time being my library is stuck with non-copyable coroutines.

--
Giovanni P. Deretta