Range comprehensions with C++ lazy generators

In the previous post we had a look at a recent proposal N4286 to add stackless coroutines to the C++ language and described the implementation prototype that ships with Visual Studio 2015 CTP.

We saw that coroutines can be used to implement lazy sequences. Lazy evaluation is a powerful tool and a pillar of functional programming; it gives the ability to construct potentially infinite data structures, and increases the performance by avoiding needless calculations. Many languages provide constructs to compute a series of elements generating them one at the time, only when they are requested. These are usually named sequences (https://msdn.microsoft.com/en-us/library/dd233209.aspx) in functional languages like Haskell or F#, generators in Python, iterator blocks in C#.

In the N4286 proposal a generator is a function that returns an object of type generator<T> and that contains at least one yield statement. For example, this is a generator for the Fibonacci sequence (the Hello World of generators) written with the notation of the VS2015 CTP:

generator<int> Fibonacci(int max)
{
    int a = 0;
    int b = 1;
    while (a <= max)
    {
        __yield_value a;
        int next = a + b;
        a = b;
        b = next;
    }
}

Query comprehensions and LINQ

Functional languages like Haskell have the concept of list comprehensions, syntactic constructs for creating a list by applying operators to other existing lists. Haskell is perfect to deal with infinite lists, thanks to its laziness, but even non-functional languages like Python and C# provide their version of query comprehensions.

In C#, of course, we have LINQ, whose design was heavily influenced by Haskell (Erik Meijer was one of the authors). The LINQ syntax is designed specifically to make it easy to apply a sequence of operations on the sequence monad IEnumerable<T>, in the form of queries.

It would be nice to have something similar in an eager language like C++. There are very interesting articles on this topic and I’d heartily suggest reading Bartosz Milewski’s “Getting Lazy with C++” and Eric Niebler’s “Range comprehensions”.

Let’s take an example from these two papers: let’s write a small Haskell program that prints the sequence of Pythagorean triples. A Pythagorean triple is a tuple of three positive integers, x, y, and z which satisfy the relation x*x + y*y = z*z.

main = print (take 10 triples)
triples = [(x, y, z) | z <- [1..]
                     , x <- [1..z]
                     , y <- [x..z]
                     , x^2 + y^2 == z^2]

In Haskell this code is very intuitive; we start with (possibly infinite) sequences of integers, and operate on them to generate a sequence of tuples, filtering only the tuples that satisfy the Pythagorean condition. Note that the act of taking only the first elements and the act of printing them are orthogonal to the act of generating the sequence.

The equivalent LINQ code for Pythagorean triples is not very different from the equivalent code in Haskell:

static IEnumerable<Tuple<int,int,int>> PythagoreanTriples(int max)
{
    return (from z in Enumerable.Range(1, max)
            from x in Enumerable.Range(1, z - 1)
            from y in Enumerable.Range(x, z - x)
            where x * x + y * y == z * z
            select new Tuple<int, int, int>(x, y, z));
}

This declarative query syntax is just syntactic sugar for the invocation of standard query operators (https://msdn.microsoft.com/en-us/library/bb397947.aspx) like Where, Select, GroupBy, Range, …, which are defined as extension methods of the Enumerable class.

The same function can be written as a simple iteration block, with a yield statement:

static IEnumerable<Tuple<int, int, int>> PythagoreanTriples(int max)
{
    foreach (var z in Enumerable.Range(1, max))
    {
        foreach (var x in Enumerable.Range(1, z - 1))
        {
            foreach (var y in Enumerable.Range(x, z - x))
            {
                if (x * x + y * y == z * z)
                {
                    yield return new Tuple<int, int, int>(x, y, z);
                }
            }
        }
    }
}

Query comprehensions in C++

Can we have something like LINQ in C++? This has been for some time a little holy grail for me; I tried to implement something with Fibers a long time ago but I didn’t really know what I was doing and the result was very kludgy.

But now the lazy, resumable generators proposed by N4286 seem perfect for this purpose; when coroutines will be fully supported by the language it could be interesting to think of a new library for query comprehensions that work on these generators.

We can use the VS2015 CTP prototype to experiment with this idea. How should a LINQ-like library for C++ look like? How would it work?

Like in LINQ, we want to write a set of operators that transform generator<T> sequences. Let’s start with a first one, a filtering operator Where that takes a generator and a predicate and returns the sequence of elements that satisfy the predicate. This can be done with a simple static function:

template<typename T, typename Pred>
static generator<T> Where(generator<T> gen, Pred pred)
{
    for (auto val : gen) {
        if (pred(val)) {
            __yield_value val;
        }
    }
}

We could very easily write other operators in the same way; for example, the Select operator, analogous to std::transform<> but that work on generators:

template<typename T, typename Fun>
static generator<typename std::result_of<Fun(T)>::type>
Select(generator<T> gen, Fun fun)
{
    for (auto val : gen) {
        __yield_value fun(val);
    }
}

This is also simple to write thanks to std::result_of that deduces the return type of Fun at compile time. Note that we cannot use automatic return type deduction here; at least in the first prototypes of VS2015 CTP we must explicitly return type generator<T>. This would not compile:

static auto Select(generator<T> gen, Fun fun) {}

Composability

Writing query operators is not very difficult. The problem is: how do we compose these operators? As an example, let’s say we want to take the sequence of all integers, filter the ones that are even and then transform them into a sequence of their string representation, like in figure:

We could do this in stages, starting with a generator that yields the sequence of integers:

generator<int> Integers()
{
    for (int i = 0; i <= INT_MAX; i++) {
        __yield_value i;
    }
}

We could either (1) apply the Where and Select operators one after the other:

    auto evenInts = Where(Integers(), [](int n) { return (n % 2) == 0; }); 
    auto evenIntStrs = Select(evenInts [](int n){ return std::to_string(n); })

or (2) we could try to put them together in a single expression:

    auto result = Select(
        Where(Integers(), [](int n) { return (n % 2) == 0; }),
        [](int n){ return std::to_string(n); });

But both choices are not great; the second one in particular quickly makes the code difficult to read and to maintain. Ideally, we would like these operators to be composable into a pipeline, as they are in LINQ:

var result = Range(1, Max)
    .Where(n => (n % 2) == 0)
    .Select(n => n.ToString());

If we were able to modify the code for generator<T>, we could do this by adding a predetermined set of operators directly in that class, in the standard library:

template <typename T>
class generator
{
    ...
    generator<T> Where(Pred pred)
    {
        for (auto val : *this) {
            if (pred(val)) {
                __yield_value val;
            }
        }
    }
    ...
}

But even so, the set of operators would not be easy to extend. What we really want is to have the ability to define and add new operators in our code, and have them compose seamlessly.

In C# the query operators are implemented as extension methods of the Enumerable class, which makes very easy to “plug” new operators simply by adding new extension methods. In C++ we don’t have extension methods. As alternative, we can follow the lead of Boost Range library that uses the pipe syntax (bitwise OR operator |) to compose the operations.

Therefore our goal will be being able to write query comprehensions as chains of pipe operators, in this form:

auto evenNumStrs = Range(1, Max)
    | Where([](int n) { return n % 2 == 0; })
    | Select([](int n) { return std::to_string(n); });

And now things get interesting: how to implement this? 🙂

A possible implementation

To be honest, at first I had really no idea. But, as Picasso once said, “good artists copy, great artists steal”: so I stole from a real artist. More precisely, I looked at the code of Eric Niebler’s range library, and it was a very interesting read. Here I am reusing some of his ideas, especially to implement a pipeline of operators. The resulting code is much simpler in my case, of course, because I only have to deal with the narrow scope of resumable generators.

So, let’s start from the beginning: as we said our goal is to be able to create pipelines of operations with the pipe operator |:

generator<int> evenNumbers = Integers() |
                             Where([](int n) { return n%2 == 0; });

We clearly need to overload the binary-OR operator | (). When its left argument is a generator, the second argument must be something of “pipeable” to a generator. Therefore, a call to a function like Where() must return “something pipeable”, whatever that means.

We can say that a type is pipeable if it implements a static method pipe(), with two arguments: a generator<T> and an instance of the pipeable type itself:

template<typename T, typename Pipeable>
auto operator|(generator<T>&& src, Pipeable&& pipe)
{
    return Pipeable::pipe(std::forward<generator<T>>(src),
                          std::forward<Pipeable>(pipe));
}

The next step could be to implement Where as a pipeable type. Rather than just a function, Where now becomes an invokable type, a class with a call operator that implements the logic to filter a sequence according to a predicate. And class Where should also have a static method pipe() that evaluates a pipe by invoking the call operator:

template<typename T>
struct Where
{
    template<typename Pred>
    generator<T> operator()(generator<T> gen, Pred pred)
    {
        for (auto val : gen) {
            if (pred(val)) {
                __yield_value val;
            }
        }
    }

    template<typename Pipe>
    static auto pipe(generator<T>&& src, Pipe&& pipe)
    {
        return operator()(src, pred); // pred ???
    }
};

But now the problem is: how do we pass the predicate to the pipe? Or, generalizing the question, since operators can have any number of arguments: how do we pass to the pipe all the arguments, if we have an expressions like this?

auto outputGen = inputGen | Op(arg1, arg2, ...);

Pipeable types

We need to complicate the design a little, leveraging the magic of variadic templates and std::bind. We introduce a type for pipeable objects (objects that can be at the right side of a pipe operator |), implemented as follows:

template<typename Binder>
struct pipeable
{
    // A forwarding call wrapper generated by std::bind.
    Binder _binder;

    pipeable(Binder pipeableBinder)
        : _binder(std::move(pipeableBinder))
    {
    }

    // Executes the call operator of a bound method, passing a generator
    // as placeholder argument.
    template<typename T, typename Pipe>
    static auto pipe(generator<T>&& gen, Pipe&& pipe)
    {
        return pipe._binder(std::forward<generator<T>>(gen));
    } 
};

Let’s look at this in more detail. Type pipeable<> has a template parameter Binder, which is an invokable type, the type of the objects returned when we call std::bind() to bind the call operator (of a type like Where) to a set of arguments.

Now, having an object op of class Where, a generator object and a predicate, we can call std::bind(op, sourceGenerator, predicate) and use the result to construct an instance of a pipeable object, so that pipeable::pipe() will call a method already bound to its arguments.

Class Where can now be simplified to have just a call operator:

template<typename T>
struct Where
{
    template<typename Pred>
    generator<T> operator()(generator<T> gen, Pred pred)
    {
        [...]
    }
};

Not all the arguments are early-bound though. When we construct the pipeable object, while the operator and the predicate are given, we don’t have a sourceGenerator to bind yet. This is the generator to which the operator is applied, i.e. the object that is at left side of the pipe and that is passed as argument to pipeable<T>::pipe(). So we need to do a little currying and use a std::bind placeholder in its stead:

std::bind(op, std::placeholders::_1, predicate);

The resulting workflow is the following:

// Given an input sequence,
auto gen = Integers();

// a predicate,
auto pred = [](int n){ return (n % 2) == 0; }

// and a query operator:
Where<int> opWhere;

// Binds the predicate to the operator
auto opWhereBoundToPred = std::bind(opWhere, std::placeholders::_1,
    std::move(pred));

// Creates a pipeable object
pipeable<decltype(binder)> pipeableWhereBoundToPred(opWhereBoundToPred);

// Now a pipe expression executes the operator replacing the placeholder with
// the input sequence:
gen | Where(pred) =>
gen | pipeableWhereBoundToPred =>
Pipeable::pipe(gen, pipeableWhereBoundToPred) =>
opWhereBoundToPred(gen)

Pipeable factories

The next step is to encapsulate all this logic into a class that acts as a factory for our pipeable types.

template<typename Op>
struct pipeable_factory
{
    // an invokable object of an operator class.
    Op _op;

    // Binds _op to its arguments, using a placeholder for the first argument.
    template<typename...Args>
    auto operator()(Args&&... args) const
    {
        return make_pipeable(std::bind(_op, std::placeholders::_1,
               std::move(args)...));
    }

private:
    template<typename Binder>
    static pipeable<Binder> make_pipeable(Binder pipeableBinder)
    {
        return { std::move(pipeableBinder) };
    }
};

Class pipeable_factory is templated on a query operator type (a type like class Where above) and it is also an invokable type. Its call operator uses the magic of variadic templates to accept a variable number of arguments and forward them to the std::bind function described before, then uses the result to instantiate and return a pipeable object.

So now in order to be able to execute an operator in a pipe expression like:

auto evenIntegers = Integers() | Where( [](int n) { return (n%2)==0; });

we just need to transform somehow Where(pred) into a pipeable_factory of the Where operator. We can do this very simply, by renaming the operator and constructing a single, constant instance of the pipeable_factory for Where:

struct where_op
{
    template<typename T, typename Pred>
    generator<T> operator()(generator<T> gen, Pred pred)
    {
        for (auto n : gen) {
	     if (pred(n)) {
                __yield_value n;
            }
        }
    }
};
constexpr pipeable_factory<where_op> Where{};

Now finally “gen | Where(pred)” works as expected: at the right side there is a factory which binds the predicate to where_op::operator() and constructs a pipeable object. Evaluating the pipe means invoking pipeable<>::pipe(), which calls the bound method replacing a placeholder with the generator object that is at the left side of the pipe. The result is that the pipe expression is evaluated as a call to where_op::operator(gen, pipe).

And since the result of this pipe expression can be itself a generator<>, and the bitwise-OR operator | is left-to-right associative, it we have also composability.

In other words, it is possible to chain a sequence of operators, exactly like LINQ does:

auto result = Integers() | Where(isEven) | Select(toString);

and we can iterate over the result with a simple range loop:

for (auto s in result) {
    cout << s << endl;
}

Here we have introduced a second operator, Select, which projects each element of a sequence into a new form by applying a transform function:

struct select_op
{
    template<typename T, typename Fun>
    generator<typename std::result_of<Fun(T)>::type>
    operator()(generator<T> gen, Fun fun)
    {
        for (auto n : gen) {
            __yield_value fun(n);
        }
    }
};
constexpr pipeable_factory<select_op> Select{};

More operators

Operators like Select and Where only take two arguments, a generator and a callable object. But we can have cases a little more challenging. For example the operator Zip, which “joins” two sequences together by applying a specified function to the corresponding i-th element of each sequence and producing a sequence of the results.

We could think of writing Zip in the same way, simply adding an additional argument for the second sequence:

class zip_op
{
public:
    template<typename TFirst, typename TSecond, typename Fun>
    generator<typename std::result_of<Fun(TFirst, TSecond)>::type>
      operator()(generator<TFirst> first,
                 generator<TSecond> second,
                 Fun resultSelector) const
    {
        auto it1 = first.begin();
        auto it2 = second.begin();
        while (it1 != first.end() && it2 != second.end()) {
            __yield_value resultSelector(*it1, *it2);
            ++it1;
            ++it2;
        }
    }
};
constexpr pipeable_factory<zip_op> Zip{};

But this would not compile (with VS2015 CTP) and I am not totally sure if it should. It fails to bind all the arguments to the variadic pipeable_factory::operator() seen before. I suspect that this could work if I could use return type deduction in zip_op::operator() but unfortunately this is not an option, since we need to explicitly return a generator<T> type.

What we can do instead is to write operator() as a variadic template function, which can take any number of arguments in its parameter pack. This function can use return type deduction as long as it does not really *implement* a resumable function but only *calls* a resumable function. To generalize the solution, we can put the variadic call operator in a base class generator_operator from which all our query operator should inherit. And each operator class will now lazily do its work in a resumable function exec() that returns a generator<T>.

Putting this idea into code, we have now:

// A generator operator is an invokable object templatized on
// an operator class. The template type Op represents a LINQ-like
// operator that works on lazy generators.
template <typename Op>
struct generator_operator
{
    template<typename Gen, typename... Rest>
    auto operator()(Gen&& gen, Rest&&... rest) const
    {
        return Op::exec(std::move(gen), std::move(rest)...);
    }
};

class select_op : public generator_operator<select_op>
{
    friend struct generator_operator<select_op>;

    template<typename T, typename Fun>
    static generator<typename std::result_of<Fun(T)>::type>
    exec(generator<T> gen, Fun fun)
    {
        for (auto n : gen) {
            __yield_value fun(n);
        }
    }
};
constexpr pipeable_factory<select_op> Select{};

class where_op : public generator_operator<where_op>
{
    friend struct generator_operator<where_op>;

    template<typename T, typename Fun>
    static generator<T> exec(generator<T> gen, Fun fun)
    {
        for (auto n : gen) {
            if (fun(n)) {
                __yield_value n;
            }
        }
    }
};
constexpr pipeable_factory<where_op> Where{};

Note that the operator classes are stateless, the exec function can be static and all the state is captured in the closures. The function exec can even be private, since it’s always called through the base generator_operator class, which is a friend of the operator class.

The result is quite clean, in my opinion: if we now want to add a new resumable operator all we have to do is to:

1. write a new generator_operator-derived class with a method exec that returns a generator<T>, and
2. declare a pipeable_factory<> for this new type.

More about generator<T>

So far nothing seems to prevent us from making these lazy operators work with any range type, even eager ranges, or with any type that defines begin() and end() methods that return input iterators.

However, we are using resumable functions to implement operators for lazy algorithms and we have seen that a resumable generator function can return only a type generator<T> and not auto. Class generator<T> has some other peculiarities that must be taken into account.

If we look at its code (in the header file C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\include\experimental\generator in the VS CTP) we see that class generator is moveable but not copyable.

template <typename _Ty, typename _Alloc = allocator<char> >
struct generator
{
    struct promise_type { ... };

    struct iterator { ... };

    iterator begin() {
        ...
        return {_Coro};
    }
    iterator end() {
        return {nullptr};
    }

    generator() = default;
    ~generator() { ... }

    generator(generator const&) = delete;
    generator& operator = (generator const&) = delete;

    generator(generator && _Right) : _Coro(_Right._Coro) {
        _Right._Coro = nullptr;
    }
    generator& operator = (generator && _Right) {
        if (&_Right != this) {
            _Coro = _Right._Coro;
            _Right._Coro = nullptr;
        }
    }

private:
    resumable_handle<promise_type> _Coro;
};

The copy constructor and copy assignment operators are deleted. To understand why, it is useful to look at a class diagram for the generator’s code:

Generators are based on stackless coroutines, which work (as described here) by allocating an activation frame, encapsulated by the class resumable_handler. In this design a resumable_handler provides the functionality to suspend and resume the execution of a function. Every instance of a generator<T> creates and owns a resumable_handler object, and shares a reference to this object with its iterators. This is why the generator<T> type cannot be copyable: we should never have two instances of a generator that refer to the same coroutine.

But the type can be moveable, so the move constructor and assignment operator are declared and work by transferring the ownership of the resumable_handler from one object to another.

The non-copyability must be taken into account in our implementation. Every time we pass a generator<T> in a function call, we need to pass an rvalue reference (generator<T>&&). The only, very important exception is in the generator_operator<> call operator. As we have seen, it is written like this:

template <typename Op>
struct generator_operator
{
    template<typename Gen, typename... Rest>
    auto operator()(Gen&& gen, Rest&&... rest) const
    {
        return Op::exec(std::move(gen), std::move(rest)...);
    }
};

We pass explicitly a rvalue reference to the call operator, but we must make sure that in the call to exec() the move constructor is called to pass the ownership of the resumable handler to a new instance of generator<T> allocated in the scope of the exec() resumable function:

struct where_op
{
    template<typename T, typename Pred>
    static generator<T> exec(generator<T> gen, Pred pred) {...}
};

Copying the rvalue reference would not work:

struct where_op
{
    template<typename T, typename Pred>
    static generator<T> exec(generator<T>&& gen, Pred pred) { ... }
};

This error is quite tricky and insidious to debug. The problem is that with resumable functions one must always make sure that the lifespan of the generator object surpasses the lifespan of the resumable function that uses that generator. Note that when we evaluate a pipe, like:

auto evenNumbers = Integers() | Where([](int n) { return n % 2 == 0; });

the generator’s destructor is called after the expression is evaluated, well before we can start iterating over the result. So, in the where_op::exec() coroutine we would have a reference to a deleted object. But if we use a move constructor instead, then there is a new generator<T> object that lives in the scope of the exec() function and that takes ownership of the resumable_handle. And since exec() is actually a resumable function, this new generator<T> object is allocated in the coroutine allocation frame and not on the stack. So, this generator<T> object lifespan coincides with the lifespan of the resumable function and everything works.

For all these reasons I designed the lazy operators to work only on generator<T>s, not on any kind of ranges (like STL containers). But it is very easy to write an adapter function that converts an eager range into a lazy generator:

template<typename Src, typename T = Src::value_type>
static generator<T> make_generator(const Src& src)
{
    for (const T& t : src) {
        __yield_value t;
    }
}

Examples

Do you still remember the problem from which we started? We can now finally write our own solution to the problem of generating the sequence of Pythagorean triples. What we miss is just an implementation of Range, to generate a sequence of integers:

generator<int> Range(int from, int count)
{
    for (int i = 0; i < count; i++)
    {
        __yield_value (from + i);
    }
}

And finally:

generator<tuple<int, int, int>> Triples(int max)
{
    for (auto z : Range(1, max - 1)) {
        for (auto x : Range(1, z - 1)) {
            for (auto y :
                Range(x, z - x) |
                Where([x, z](int y) { return x*x + y*y == z*z; }))
            {
                __yield_value tuple<int, int, int>(x, y, z);
            }
        }
    }
}

As another, and final, example we can write a (slow) prime numbers generator. We need an additional operator for this, the operator All that returns true if all the elements in a sequence satisfy a given predicate:

class all_op : public generator_operator<all_op>
{
    friend struct generator_operator<all_op>;

    template<typename T, typename Fun>
    static bool exec(generator<T> gen, Fun fun)
    {
        for (auto n : gen) {
            if (!fun(n)) {
                return false;
            }
        }
        return true;
    }
};
constexpr pipeable_factory<all_op> All{};

All shows that a lazy operator does not necessarily need to return a generator, it can return any type. With All we can finally write:

generator<int> Primes(int max)
{
    return Range(2, max - 1) | 
	    Where([](int i) {
               return Range(2, (int)sqrt(i)) |
                      All([i](int j) { return (i % j) != 0; });
	    });
}

But these are just few basic examples. If you are interested, you can find here:

the sources of this small library, with the implementation of a number of LINQ-like operators, like Aggregate, All, Any, Concat, Contains, Count, ElementAt, Empty, Except, First, Last, Max, Min, Range, Repeat, Reverse, Select, Skip, SkipWhile, Sum, Take, TakeWhile, Where, Zip.
The code is definitely not production-quality: error and exception handling are mostly absent, the unit tests are minimal. It is just an example of what we will be able to do with lazy generators, when they will become part of C++.