Why wasn't yield added to C++0x?

Question

I have been using yield in many of my Python programs, and it really clears up the code in many cases. I blogged about it and it is one of my site's popular pages.

C# also offers yield – it is implemented via state-keeping in the caller side, done through an automatically generated class that keeps the state, local variables of the function, etc.

I am currently reading about C++0x and its additions; and while reading about the implementation of lambdas in C++0x, I find out that it was done via automatically generated classes too, equipped with operator() storing the lambda code. The natural question formed in my mind: they did it for lambdas, why didn't they consider it for support of "yield", too?

Surely they can see the value of co-routines... so I can only guess that they think macro-based implementations (such as Simon Tatham's) as an adequate substitute. They are not, however, for many reasons: callee-kept state, non-reentrant, macro-based (that alone is reason enough), etc.

Edit: yield doesn't depend on garbage collection, threads, or fibers. You can read Simon's article to see that I am talking about the compiler doing a simple transformation, such as:

int fibonacci() {
    int a = 0, b = 1;
    while (true) {
        yield a;
        int c = a + b;
        a = b;
        b = c;
    }
}

Into:

struct GeneratedFibonacci {
    int state;
    int a, b;

    GeneratedFibonacci() : state (0), a (0), b (1) {}

    int operator()() {
        switch (state) {
        case 0:
            state = 1;
            while (true) {
                return a;

        case 1:
                int c = a + b;
                a = b;
                b = c;
            }
        }
    }
}

Garbage collection? No. Threads? No. Fibers? No. Simple transformation? Arguably, yes.

Answer 1

They did it for lambdas, why didn't they consider it for supporting yield, too?

Check the papers. Did anyone propose it?

...I can only guess that they consider macro-based implementations to be an adequate substitute.

Not necessarily. I'm sure they know such macro solutions exist, but replacing them isn't enough motivation, on its own, to get new features passed.

---

Even though there are various issues around a new keyword, those could be overcome with new syntax, such as was done for lambdas and using auto as a function return type.

Radically new features need strong drivers (i.e. people) to fully analyze and push features through the committee, as they will always have plenty of people skeptical of a radical change. So even absent what you would view as a strong technical reason against a yield construct, there may still not have been enough support.

But fundamentally, the C++ standard library has embraced a different concept of iterators than you'd see with yield. Compare to Python's iterators, which only require two operations:

1. an_iter.next() returns the next item or raises StopIteration (next() builtin included in 2.6 instead of using a method)
2. iter(an_iter) returns an_iter (so you can treat iterables and iterators identically in functions)

C++'s iterators are used in pairs (which must be the same type), are divided into categories, it would be a semantic shift to transition into something more amenable to a yield construct, and that shift wouldn't fit well with concepts (which has since been dropped, but that came relatively late). For example, see the rationale for (justifiably, if disappointingly) rejecting my comment on changing range-based for loops to a form that would make writing this different form of iterator much easier.

To concretely clarify what I mean about different iterator forms: your generated code example needs another type to be the iterator type plus associated machinery for getting and maintaining those iterators. Not that it couldn't be handled, but it's not as simple as you may at first imagine. The real complexity is the "simple transformation" respecting exceptions for "local" variables (including during construction), controlling lifetime of "local" variables in local scopes within the generator (most would need to be saved across calls), and so forth.

Answer 2

I can't say why they didn't add something like this, but in the case of lambdas, they weren't just added to the language either.

They started life as a library implementation in Boost, which proved that

• lambdas are widely useful: a lot of people will use them when they're available, and that
• a library implementation in C++03 suffers a number of shortcomings.

Based on this, the committee decided to adopt some kind of lambdas in C++0x, and I believe they initially experimented with adding more general language features to allow a better library implementation than Boost has.

And eventually, they made it a core language feature, because they had no other choice: because it wasn't possible to make a good enough library implementation.

New core language features aren't simply added to the language because they seem like a good idea. The committee is very reluctant to add them, and the feature in question really needs to prove itself. It must be shown that the feature is:

• possible to implement in the compiler,
• going to solve a real need, and
• that a library implementation wouldn't be good enough.

In the case if a yield keyword, we know that the first point can be solved. As you've shown, it is a fairly simple transformation that can be done mechanically.

The second point is tricky. How much of a need for this is there? How widely used are the library implementations that exist? How many people have asked for this, or submitted proposals for it?

The last point seems to pass too. At least in C++03, a library implementation suffers some flaws, as you pointed out, which could justify a core language implementation. Could a better library implementation be made in C++0x though?

So I suspect the main problem is really a lack of interest. C++ is already a huge language, and no one wants it to grow bigger unless the features being added are really worth it. I suspect that this just isn't useful enough.

Answer 3

Adding a keyword is always tricky, because it invalidates previously valid code. You try to avoid that in a language with a code base as large as C++.

The evolution of C++ is a public process. If you feel yield should be in there, formulate an appropriate request to the C++ standard committee.

You will get your answer, directly from the people who made the decision.

Answer 4

So it looks like it didn't make it into C++11, or C++14, but might be on its way to C++17. Take a look at the lecture C++ Coroutines, a negative overhead abstraction from CppCon2015 and the paper here.

To summarize, they are working to extend c++ functions to have yield and await as features of functions. Looks like they have an initial implementation in Visual Studio 2015, not sure if clang has an implementation yet. Also it seems their may be some issues with using yield and await as the keywords.

The presentation is interesting because he speaks about how much it simplified networking code, where you are waiting for data to come in to continue the sequence of processing. Surprisingly, it looks like using these new coroutines results in faster/less code than what one would do today. It's a great presentation.

The resumable functions proposal for C++ can be found here.

Answer 5

In general, you can track what's going on by the committee papers, although it's better for keeping track rather than looking up a specific issue.

One thing to remember about the C++ committee is that it is a volunteer committee, and can't accomplish everything it wants to. For example, there was no hash-type map in the original standard, because they couldn't manage to make it in time. It could be that there was nobody on the committee who cared enough about yield and what it does to make sure the work got done.

The best way to find out would be to ask an active committee member.

Answer 6

Well, for such a trivial example as that, the only problem I see is that std::type_info::hash_code() is not specified constexpr. I believe a conforming implementation could still make it so and support this. Anyway the real problem is obtaining unique identifiers, so there might be another solution. (Obviously I borrowed your "master switch" construct, thanks.)

#define YIELD(X) do { \
    constexpr size_t local_state = typeid([](){}).hash_code(); \
    return (X); state = local_state; case local_state: ; } \
while (0)

Usage:

struct GeneratedFibonacci {
    size_t state;
    int a, b;

    GeneratedFibonacci() : state (0), a (0), b (1) {}

    int operator()() {
        switch (state) {
        case 0:
            while (true) {
                YIELD( a );
                int c = a + b;
                a = b;
                b = c;
            }
        }
    }
}

Hmm, they would also need to guarantee that the hash isn't 0. No biggie there either. And a DONE macro is easy to implement.

---

The real problem is what happens when you return from a scope with local objects. There is no hope of saving off a stack frame in a C-based language. The solution is to use a real coroutine, and C++0x does directly address that with threads and futures.

Consider this generator/coroutine:

void ReadWords() {
    ifstream f( "input.txt" );

    while ( f ) {
        string s;
        f >> s;
        yield s;
    }
}

If a similar trick is used for yield, f is destroyed at the first yield, and it's illegal to continue the loop after it, because you can't goto or switch past a non-POD object definition.

Answer 7

there have been several implementation of coroutines as user-space libraries. However, and here is the deal, those implementations rely on non-standard details. For example, nowhere on the c++ standard is specified how stack frames are kept. Most implementations just copy the stack because that is how most c++ implementations work

regarding standards, c++ could have helped coroutine support by improving the specification of stack frames.

Actually 'adding' it to the language doesn't sound a good idea to me, because that would stick you with a 'good enough' implementation for most cases that is entirely compiler-dependent. For the cases where using a coroutine matters, this is not acceptable anyways

Answer 8

agree with @Potatoswatter first.

To support coroutine is not the same thing as support for lambdas and not that simple transformation like played with Duff's device.

You need full asymmetric coroutines (stackful) to work like generators in Python. The implementation of Simon Tatham's and Chris' are both stackless while Boost.Coroutine is a stackfull one though it's heavy.

Unfortunately, C++11 still do not have yield for coroutines yet, maybe C++1y ;)

PS: If you really like Python-style generators, have a look at this.