Yield in C++11

A hacky trick you can pull with mutable lambdas and switch statements.

Python has the yield keyword for making generators. C++23 has std::generator, but at the time I'm writing this, no compilers support it. And even when compilers do start supporting it, it'll take some time for projects to update to a newer standard.

What do we need for a generator?

What we're looking for in a generator is to be able to yield a value from within a function, suspend execution of the function, and resume it later. This means we need our position in the function and our local variables to remain unchanged between the suspension and resuming of the function.

Lambda function copy captures.

Copy caputures of a lambda function will give us variables that will keep their values as long as the function object is alive, so we can replace all of our local variables with these. In order to be able to modify the values of the copy captures, we need to specify that our lambda is mutable.

To differentiate between yielding a value versus the generator finishing, returning an std::optional would probably be the most readable – the generator either yields a value, or it doesn't. However, std::optional is a feature of C++17, so we can instead hack our way around it with pointers. We can have the variable we want to return as another copy capture so it won't be destroyed, and return a pointer to it. We can return a nullptr to signify that we're done.

Finally, we need to be able to save and resume our position in the code. We can have another copy capture be our “instruction pointer”, but how do we jump back to our saved position upon resuming the generator? We need some sort of multi-way conditional jump...

Switch statement shenanigans.

In C-like languages, case labels are just that: labels, like the kind you see in assembly. That's why most typical uses of switch statements will come with a break at the end of each case – otherwise, execution will fallthrough to the next case. Fallthrough can be abused for some very interesting code, like Duff's device. Here, we'll use it for jumping back to our saved position.

Putting it all together.

There is a fibonacci sequence generator on cppreference's page on coroutines, so I took that code and re-implemented it using the techniques discussed above.

#include <iostream>
#include <functional>

std::function<std::uint64_t*()> fibonacci_sequence(unsigned n) {
  int ip = 0;
  std::uint64_t a, b, s;
  unsigned i;
  return [=]() mutable -> std::uint64_t* { switch (ip) { case 0:
    if (n == 0)
      return nullptr;

    if (n > 94)
      throw std::runtime_error("Too big Fibonacci sequence. Elements would overflow.");

    ip = 1; return &(s = 0); case 1: ;

    if (n == 1)
      return nullptr;

    ip = 2; return &(s = 1); case 2: ;

    if (n == 2)
      return nullptr;

    a = 0;
    b = 1;
    for (i = 2; i < n; i++) {
      s = a + b;
      ip = 3; return &s; case 3: ;
      a = b;
      b = s;
    }
    default: return nullptr;
  }};
}

int main() {
  auto gen = fibonacci_sequence(10);
  for (int j = 0; auto gen_val = gen(); j++) {
    std::cout << "fib(" << j << ")=" << *gen_val << '\n';
  }
}
    

And after no complaints during compilation:

$ g++ cpp11_yield.cpp -std=gnu++11
$ ./a
fib(0)=0
fib(1)=1
fib(2)=1
fib(3)=2
fib(4)=3
fib(5)=5
fib(6)=8
fib(7)=13
fib(8)=21
fib(9)=34
    

Can we do recursive generators?

Yes.