C++11 Coroutines Proposal

A proposal for coroutines in C++11

1. Motivation

Coroutines are related to continuations, a powerful programming concept which gives more control over the workflow of a program. In fact, coroutines cover most useful use cases of continuations.

The idea of coroutines is to "pause" the current calculation to give the control to another calculation, until that other routine gives the control back. The difference with a function call is that both routines keep their context active so that they can switch context multiple times without losing track of where they are. Hence the name coroutine.

Use cases of coroutines include: generators, visitor pattern, progress indicators, feedback loops, multiplexing, multilayered architecture and cooperative multitasking.

Suggested reading:

Donald Knuth, The Art of Computer Programming, Volume 1, Addison-Wesley, ISBN 0-201-89683-4. Section 1.4.2.
http://www.dabeaz.com/generators-uk/
http://www.dabeaz.com/coroutines/
http://lambda-the-ultimate.org/node/2868

2. Changes to the language

This proposal introduces a new keyword, yield.

The addition of yield makes programs using coroutines easier to read and comprehend. An alternative proposal which does not modify the grammar is presented at the end of this document.

The yield instruction first appeared in CLU, an early programming language developed by Barbara Liskov and her MIT students in 1974 and 1975.

3. Generator function

We define a function which role is to yield values until there is no value left to yield. This is called a generator function.

The yield keyword is used to yield a value in a similar way to return. In contrast with return, yield initiates a context switch and the code that follows it is reachable.

Since a generator function can only be used in the context of coroutines, its signature must reflect that it is a generator function. This is done by appending yields followed by the type of the yielded values to its signature. Any valid return type including void is allowed. Calling the function returns a std::generator object based on the generator function.

Note that return is allowed in a generator function but if it returns a value, that value needs to be accessed separately. Only yield can yield a value.

Example of generator function:

void numbers() yields int {
    for (int n = 1; n <= INT_MAX; ++n)
    {
        yield n;
    }
}

4. Generator type

A generator function is used to create instances of std::generator. A std::generator object can be used to iterate over the yielded values or control the generator function by resuming its execution or aborting it.

The definition of the std::generator type is:

template< class Y, class R, class... Args >
class generator< R(Args...), Y >;

Where R(Args...) yields Y is the signature of the generator function and constraints is a list of generator functions to pick from. If constraints is empty the generator function can be any generator function satisfying the signature.

The std::generator class defines the following functions:

Public constructor:

generator(std::function< R(Args...) yields Y > gen_func, Args... FArgs) explicit;

Context switch function and operator:

Y pop();

Y operator()();

Note: the two are equivalent.

Production status function:

bool empty() const noexcept;

Return value accessor:

R result() const;

Note: this throws an exception if the function did not end with return. State indicator function:

enum class statuscode {send, receive, ended, error};

enum statuscode state() const noexcept;

Note: if state() is error, both result() and next invocation of operator () will throw an exception associated with the error.

Abort function:

void clear();

Note: if there are more values, the clear() function initiates a context switch to unwind the generator stack. Following calls to clear() have no effect. If an exception is thrown in the generator, the clear() function silently discards it. Use state() to check for previously thrown exceptions prior to calling clear().

Iterator conversion:

iterator< Y > begin() const noexcept;

iterator< Y > end() const noexcept;

Destructor:

~generator();

Note: the destructor calls clear() to unwind the generator stack.

5. Example

int main(int n, char args[])
{
    std::generator< void(), int, numbers > counter = numbers();

    cout << "First value = " << counter() << std::endl;
    cout << "Second value = " << counter() << std::endl;

    for (int i = 0; i < 5 && !counter.empty(); ++i)
    {
        cout << counter() << std::endl;
    }
    counter.clear();
    return 0;
}

Output:

First value = 1
Second value = 2
3
4
5
6
7

6. Return values

The generator methods return values are according to the following table:

Event	empty()	state()	operator ()
yield v	false	send	v
throw e	false	error	throw e
return	true	ended	throw std::end_of_yield
gen()	true	receive	throw std::coroutine_out_of_sync

Note: gen() in the above table is a call to a generator.
Note: calling clear() on a generator has the same effect as doing return in the generator function.

7. Coroutine

A generator may need to get input from a source to produce values. This can be done by passing another generator function as argument to the generator function (generator chaining).

In many applications, the consumer function needs to send feedback to the generator function, for example to influence the next yielded value.

To send this feedback a coroutine is used. Its role is to feed data into an associated generator function accessed by the generator, in the manner of a single value-deep FIFO pipe pair.

The definition of the std::coroutine type is:

template< class T > coroutine< T >;

The class std::coroutine defines the following functions:

Public constructor:

coroutine();

Context switch function:

void push(T value);

void operator ()(T value);

Consumer status function:

bool ready() const noexcept;

Associated generator accessor:

std::generator< T() > get_receiver() const noexcept;

Destructor:

~coroutine();

8. Example

void fib(const std::generator< void(), int > &b) yields int
{
    for (int a = 1; a > 0; a += b())
    {
        yield a;
    }
}

int main(int n, char args[])
{
    std::coroutine< int > feeder;
    std::generator< void(), int, fib > a = fib(feeder.get_receiver());

    for (int b = 1; b < 10; b = a())
    {
        feeder.push(b);
        cout << b << std::endl;
    }
    return 0;
}

Output:

9. Minimal Implementation

There is more than one possible implementation of the proposal.

This section introduces a minimal implementation of coroutines. All implementations are required to provide at least the features of this minimal implementation as noted.

9.1 Compiler support

For the minimal implementation the compiler must be able to calculate the stack size required by a generator function (excluding function calls) ahead of time. This may put restrictions on the instructions allowed in the generator function body.

9.2 Consumer function

The consumer function designates the function which invokes the generator.

In the minimal implementation the generator must be copied to the consumer function stack before it can be invoked.

Being able to invoke a generator copied to the stack is a Minimal Implementation requirement.

The minimal implementation wraps the consumer function in a trampoline. The generator function takes an object which has access to the trampoline as implicit first argument.

Passing an implicit value as first argument of the generator function is a Minimal Implementation requirement. The semantics of this first argument are implementation-dependent.

9.3 Context switch

When a context switch occurs, the target frame pointer is saved in a register and the control is given to the trampoline.

The trampoline gives the control to either the generator or the consumer function.

The stack pointer does not change, so function calls grow the stack and restore it on exit as normal. In the minimal implementation the generator runs in constant stack size. Note that yield can only be used inside the generator body.

It is a Minimal Implementation requirement that the generator and the consumer function can make function calls between context switches.

9.4 Generator function

In the minimal implementation, the generator function uses a predetermined part of the stack area allocated by the consumer function as its stack frame.

On invocation, it runs up to a context switch (yield or generator invocation) or up to termination. This determines the result of the empty(), state() and pop() functions as described in section 6.

If a yield is reached, the generator function stores the yield value and gives control to the trampoline. In the same fashion, an exception is not immediately thrown but stored for next call to operator ().

If the generator is not terminated operator () resumes the execution of the generator function until next event, then gives the control back to the trampoline.

Since the generator function uses the area allocated for itself in the consumer function stack, with the minimal implementation, invoking the generator function does not return a value in the usual sense.

This illustration shows how it works:

Coroutine stack organisation

9.5 Generator scope

A function can allocate a generator in the heap and return it, but with the minimal implementation the generator must be copied to the consumer function stack before use. The trampoline frame pointer needs to be adjusted when copying. Only constrained generators can be returned in this fashion thanks to the known bounds to their required stack size.

Alternative proposal

One downside of the above proposal is that it requires extension to the syntax.

An alternative without this downside is discussed below. It is compatible with the above proposal, that is, if this proposal is adopted then yield can be introduced on top of it.

1. Changes to the generator function

Instead of using yield to yield values, the generator function pushes them to a coroutine. The coroutine is passed as first argument. The type of the coroutine indicates what is the type of yielded values, which no longer appears after yields in the signature of the generator function.

2. Changes to the consumer function

Since the generator function no longer returns a generator, the constructor is used instead. The constructor takes the generator function and the additional arguments, and forwards these arguments to the generator function using the coroutine associated with the generator as first argument.

3. Example

void numbers(const std::coroutine< int > &produce)
{
    for (int n = 1; n <= INT_MAX; ++n)
    {
        produce(n);
    }
}

int main(int n, char args[])
{
    std::generator< void(), int, numbers > counter(numbers);

    cout << "First value = " << counter() << std::endl;
    cout << "Second value = " << counter() << std::endl;

    for (int i = 0; i < 5 && !counter.empty(); ++i)
    {
        cout << counter() << std::endl;
    }
    counter.clear();
    return 0;
}