Re: [boost] Continuations in C++

From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2007-09-26 06:53:36

On 9/25/07, Daniel Gutson <danielgutson_at_[hidden]> wrote:
> Hi Mathias,
>   thanks for answering.
>
> I found such library in Vault, so it´s not in another place, right?

You mean boost-coroutine in the concurrency folder of the vault?
[http://tinyurl.com/278qca]

You can also find the documentation here:

  http://www.crystalclearsoftware.com/soc/coroutine/index.html

And access the SVN here:

  http://svn.boost.org/trac/boost/browser/sandbox/SOC/2006/coroutine

Note that the name is misleading. Boost.Coroutine is not yet a boost
library. I haven't even submitted it for review yet (even if it is
practically finished and the documentation almost done) for lack of
time.

>
> I found also the continuation namespace, but as far as I saw, yes this
> is a generalization of the concept, but focused in coroutines, and
> somehow (as far as I understand) in concurrent programming.
>

Well, coroutines and one-shot continuations are dual as there is a
simple transformation from one to the other [1].  On the other hand,
the word 'continuation' alone in computer science usually refers to
true restartable continuations which are *extremely* hard to do in C++
(you would need a way to copy the stack reliably). The UNIX fork()
syscall is what get closer to true continuations in the C world
(except that it also copy the global state, but you can get around
that).

What you are showing in your example are simple stack less (you can't
yield from inside a call stack) coroutines. My coroutine library
supports the stackfull variant of coroutines. It cannot be implemented
within the standard C++, so it uses a range of OS specific services
(make_context and Win32 Fibers) or custom assembler. They could also
be implemented fairly portably on top of boost.thread, but I haven't
done so yet. I expect such an implementation to be fairly slow.

Boost.coroutine is definitely not focused on concurrent programming.
In fact the documentation states clearly that often coroutines are
mistaken for poor man threads, which they are not. Threads and
coroutines are orthogonal. One of the library example is in fact the
classic factorial and it looks like this (namespaces stripped for
simplicity):

  typedef coroutine<double()> coroutine_type;
  size_t factorial(coroutine_type::self& self) {
           double n = 0;
           double n_bang = 1;
           self.yield(n_bang);
           while(true) {
             n_bang = n_bang * ++n;
             self.yield(n_bang);
           }
 }
         
  int main() {
          coroutine_type fact(factorial);
           for(int i = 0; i <100; i++)
          std::cout <<i<<"!= "<<fact()<<"\n";
  }

> The concept I´m referring here (which, of course could be incorrect)
> is not related with concurrent programming, multithreading or
> iterators, but the ability to specify an execution flow without using
> a stack (I´m somewhat messed with embedding programming), and a neat
> support for iterative algorithms implementations.

Boost.Coroutine provides yield_next which is the equivalent of
your set_next, but that is just syntactic sugar, because a coroutine
library without yield_next is just as powerful one without. Yield_next
could be emulated by just returning the next coroutine to jump to.

I provide it in the library because it is slightly more efficient to
be implement natively (you save a stack switch and an indirect call).

BTW, yield next is just a more powerful variant of goto, which means
that you are more likely of shooting yourself in the foot :)

gpd

[1] http://www.inf.puc-rio.br/~roberto/docs/corosblp.pdf