Login/Register
Why wasn't yield added to C++0x?
Asked Answered
Solved c++c++11yieldc++17
V

8

30

EDIT, 11 years after I asked this question: I feel vindicated for asking! C++20 finally did something close enough.

The original question follows below.

--

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.

Visualize answered 5/10, 2010 at 14:6 Comment(16)
Keep in mind that "anything can be done" in languages like C and C++, just because it's easy to emulate manually for a simple example, doesn't make it easy to incorporate into the syntax. Take Boost for example, it does crazy stuff with C++, but the lengths they goto are crazy behind the scenes. Even when ideas in Boost are incorporated into standard C++ they are implemented completely differently. (take a look at unique_ptr, lambdas and variable parameters stuff) – Mullis
Because nobody wrote an official proposal for it. – Bust
Your original transformation of the generator had a bug: it never progressed into state 1. Fixed that and applied Duff's device. – Huntsville
FWIW, your blog post's class Permutation can be written as a single generator function. There's also a straight-forward implementation of a permutation generator (in C++ as std::next_permutation, does require strict weak ordering and starting from sorted data if you want all permutations), so that's perhaps not a convincing example. – Huntsville
The most amazing thing about C#'s yield statement is not the implementation, but the fact that you can step through it in the VS debugger. – Illuminometer
@Roger Pate: I didn't use Duff's device in the original version, because some people may freak out looking at a jump inside a switch. As for the STL permutation, the last phrase from my blog was: "The code above doesn't use any kind of library... It simply uses language features to implement what we need. Now try writing the same functionality in plain C++, without using any library (STL permutations or otherwise) ...". So yes, there is a solution in the STL library for the specific problem, but yield allows you to solve ANY such kind of problem, using a language keyword, a generic tool. – Visualize
@ttsiodras: I mention next_permutation because it very simply does the job without a generator. Therefore, permutations is perhaps not a convincing example of why generators are useful. Has nothing to do with it being in a library, and I can write next_permutation in less than ten lines of readable code without using any library. – Huntsville
@Roger Pate: Not in as clear a manner as "yield" allows, not even close. The whole point of the post is that yield allows optimal, clarity-wise, code, with minimal effort. – Visualize
"Optimal clarity" is subjective. I can agree generators are nice and wish that C++ had them, while still having an opinion on whether a particular example justifying their use is convincing or not. :) – Huntsville
@ttsiodras: I have to agree with @Roger Pate on this, generators are nice, but I never "needed" them until encountering Python. They're a nice extra, but the problem with adding more features is less people know about them. Less is more and all that. That being said, I'd still like to see generators in C++, everything else has been smushed into the language, may as well keep going. – Mullis
@ttsiodras: You have caller and callee backwards (which I had fixed). The caller is the user of the generator, the callee is the generator code itself. – Huntsville
@Roger: I did the same fix a bit earlier - our commits probably merged or something :-) – Visualize
@Matt: "less is more" definitely doesn't fit this discussion/rant: lambdas were added, via automatic class generation - so I don't see any reason to "discriminate" against "yield". The executive summary, as I get it, is: "we go where the committee majority wants to go", which is fine, democratic, and all that - and has some major drawbacks, like lambdas coming into C++ last (Python, Perl, C#, Haskell, Ocaml, etc have them for a decade now) and "yield" and other things are still in the future (if ever). – Visualize
@ttsiodras: My less is more comment was a general preference. It's obviously not the case in C++, and as I vaguely put it, it's too late for C++ anyway. I'm saying that I'm not against the addition of yield, the language is already a mess. I honestly believe that adding more crap to C++ will just make it more appealing to most people, it's already lost the interest of the parsimonious language fans. I should add that lambda's seem more convenient than yield. – Mullis
porpose it for the next version! – Himmler
Just wanted to point out that the currently selected answer is no longer valid. The feature was proposed, and the feature is in the current compilers (clang and VC14) as a technical specification. Coroutine support is slated for after c++17 – Isiah
H
7

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.

Huntsville answered 6/10, 2010 at 13:3 Comment(9)
Addressing: "Check the papers. Did anyone propose it?" - Well, if no-one in the C++ commitee realizes the benefits of coroutines/yield (in e.g. optimal async work in heavy-duty socket servers, LINQ-style queries, etc), it is no wonder that other languages are taking hold, dooming C++ to gradual extinction. As for iterators, they are not necessarily part of this discussion - yield stands on its own just fine without iterators, as a different way to return results. I am out of comment space - and prety much convinced that even obvious things, like yield, are "out-of-scope" for commitee-thinking. – Visualize
@ttsiodras: Look at those papers sometime, and the things that go into them. Not much is out of scope for committee thinking. If you were to join the Committee and push for something like yield and work hard to make it work in the language and listen to other people's objections, it would be in the next standard. That's just like everybody else's pet feature that didn't get included. – Neuman
@ttsiodras: Iterators are a central feature of the standard library, but are treated as a feature of the language core (e.g. look at the 0x range-based for-loop; also why they were designed as a superset of pointers). I think any proposal of generators/yield that wasn't compatible with C++'s concept of iterators would be asked to be revised to make it so. – Huntsville
@ttsiodras: There bigger problems plaguing C++ than lack of features. Emphasis on gradual, the only language that will die slower than C++, is C. – Mullis
@David: All due respect, but "yield" is not my pet feature. Scheme, Perl, Python, C#, Ruby - shall I go on? Unless you consider "lambdas" and functional programming pet features, too. – Visualize
@Matt: You are probably right - hence this rant. I will be waiting for yield for another decade :-( (just as I have been waiting for lambdas...) – Visualize
@ttsiodras: I've apparently been unclear here: "pet feature" doesn't refer to something useless, or something you created, but a feature you really want in a programming language. For example, in a COBOL discussion my pet feature would be user-defined functions that return a value, which is clearly useful, clearly not my idea, and present in more programming languages than yield. Different people have different pet features, most of which would be useful. Since they're all work to get right, and nobody wants to add too many, some get left out. – Neuman
@ttsiodras: why wait? Submit a proposal for it to be added. ;) – Ansley
The proposal does exist, and will likely make it in to c++17. Look up resumable functions: open-std.org/JTC1/SC22/WG21/docs/papers/2014/n4286.pdf – Isiah
A
22

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.

Ansley answered 13/12, 2010 at 17:43 Comment(2)
Language extensions can work without too much pain. In the Haskell compiler GHC, there is an incredible number of language extensions, and they work well because they are defined as transformations on a theoretic, simple, intermediate language. That means that the semantics are straight forward to reason about, although there can be lots of bells and whistles regarding syntax. – Saberhagen
@user239558: of course they can. But that doesn't really solve the problems I outlined – Ansley
C
8

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.

Cotta answered 5/10, 2010 at 14:16 Comment(3)
This is very believable. The ECMAScript committee went out of their way not to introduce a new keyword. EX: Object.defineProperty and "use strict"; – Brauer
Writing the proposal would be great, but it's too late to get such a feature into 0x. – Huntsville
This could have been in added without a keyword - as a library function. So -1. – Tiffany
H
7

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.

Huntsville answered 6/10, 2010 at 13:3 Comment(9)
Addressing: "Check the papers. Did anyone propose it?" - Well, if no-one in the C++ commitee realizes the benefits of coroutines/yield (in e.g. optimal async work in heavy-duty socket servers, LINQ-style queries, etc), it is no wonder that other languages are taking hold, dooming C++ to gradual extinction. As for iterators, they are not necessarily part of this discussion - yield stands on its own just fine without iterators, as a different way to return results. I am out of comment space - and prety much convinced that even obvious things, like yield, are "out-of-scope" for commitee-thinking. – Visualize
@ttsiodras: Look at those papers sometime, and the things that go into them. Not much is out of scope for committee thinking. If you were to join the Committee and push for something like yield and work hard to make it work in the language and listen to other people's objections, it would be in the next standard. That's just like everybody else's pet feature that didn't get included. – Neuman
@ttsiodras: Iterators are a central feature of the standard library, but are treated as a feature of the language core (e.g. look at the 0x range-based for-loop; also why they were designed as a superset of pointers). I think any proposal of generators/yield that wasn't compatible with C++'s concept of iterators would be asked to be revised to make it so. – Huntsville
@ttsiodras: There bigger problems plaguing C++ than lack of features. Emphasis on gradual, the only language that will die slower than C++, is C. – Mullis
@David: All due respect, but "yield" is not my pet feature. Scheme, Perl, Python, C#, Ruby - shall I go on? Unless you consider "lambdas" and functional programming pet features, too. – Visualize
@Matt: You are probably right - hence this rant. I will be waiting for yield for another decade :-( (just as I have been waiting for lambdas...) – Visualize
@ttsiodras: I've apparently been unclear here: "pet feature" doesn't refer to something useless, or something you created, but a feature you really want in a programming language. For example, in a COBOL discussion my pet feature would be user-defined functions that return a value, which is clearly useful, clearly not my idea, and present in more programming languages than yield. Different people have different pet features, most of which would be useful. Since they're all work to get right, and nobody wants to add too many, some get left out. – Neuman
@ttsiodras: why wait? Submit a proposal for it to be added. ;) – Ansley
The proposal does exist, and will likely make it in to c++17. Look up resumable functions: open-std.org/JTC1/SC22/WG21/docs/papers/2014/n4286.pdf – Isiah
I
7

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.

Isiah answered 5/2, 2016 at 13:46 Comment(1)
See also open-std.org/JTC1/SC22/WG21/docs/papers/2015/p0099r0.pdf and open-std.org/JTC1/SC22/WG21/docs/papers/2015/p0114r0.pdf and open-std.org/JTC1/SC22/WG21/docs/papers/2015/p0158r0.html – Shannashannah
N
2

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.

Neuman answered 5/10, 2010 at 14:34 Comment(6)
I am sort of prejudiced against committees - it is my "feeling" that languages designed by committees are usually... problematic. You would be right in arguing that I should therefore leave C++ and C++0x behind me, and focus on Python and Perl and other "benevolent dictator" languages... but I can't. What really bothered me and made me write this question to SO, was that they did the work for lambdas, and didn't take one small step to do it for co-routines, too.... (sigh)... C++, always some steps behind others... (with the exception of templates) – Visualize
@ttsiodras: My 2 languages are Python and C. C is just the bare minimum, you aren't sucked into any stupidness, and it's blazing fast and can do anything. The other is Python, for the reasons you've given. One guy has his finger on the pulse, and I like the way he thinks. C++ is a mess. – Mullis
@ttsiodras: If you're truly prejudiced against committees, you're free to fork off from C++ and make your own language. If you're very good and provide something useful, you'll attract other people who will use the language you've created. After a while, you might decide that some of these other people have good ideas too for how the language you've created should evolve; invite some of them to help you, and you've got a committee. Aaaargh! :-) Committees aren't anything to be afraid of per se but not all are equal; some really suck. – Outmoded
@ttsiodras: I think C++ is proof that design by committee can work. They've done a good job so far, and while yes, they've screwed up occasionally, I think the same can be said for any "benevolent dictator". If anything, I'd argue that most of the cases where they screwed up were when they tried to act like benevolent dictators. – Ansley
@jalf: My pettest peeve is vector<bool>, and of course there's export, which both were cases of the Committee pushing something and acting as benevolent dictator. – Neuman
exactly. (and yeah, I had those two "features" in mind as well ;)) – Ansley
S
2

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.

Swop answered 9/10, 2010 at 19:47 Comment(3)
Thanks for answering, but you are not telling me anything I didn't already know - yes, we can emulate some aspects of yield with macros, and Simon (the linked article in my original text) did this years ago. The problem is that this is not enough, as both I and you pointed out. And since C++0x added support for lambdas by adding automatic class generation to the compiler, and "yield" would require exactly the same thing, I just lament its absence. That's all. – Visualize
@ttsiodras: No, "yield" requires saving and restoring the stack frame, or equivalently a coroutine. In C languages that is equivalent to threading. In C++ if you want a generator object with that syntax, you must spawn a thread and synchronize it. And C++0x did add native support for that. – Swop
Hmm, just got one upvote, 2 years later! At a glance, typeid([](){}) is not a valid way to get a compile-time random number. Perhaps my compile-time counters answer would work, though. – Swop
R
1

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

Rounds answered 13/12, 2010 at 16:31 Comment(0)
C
0

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.

Corcovado answered 26/3, 2013 at 7:56 Comment(0)

© 2022 - 2024 — McMap. All rights reserved.