Introducing Conduit for C++: Lazy Sequences Using the Coroutine TS
Lazy sequences are an idea that’s very popular in the functional-programming community, but less common in the C++ world.
Simply put, a lazy sequence is one where the elements are computed as they are requested, rather than in advance.
This can lead to big efficiency gains since you only perform the computation required. It also allows you to represent infinite sequences, which of course could never fit into a vector!
Let’s see how Conduit works with some simple examples…
Everyone is familiar with square numbers, so this is a great place to start.
0, 1, 4, 9, 16, …
A Conduit sequence is defined using the
seq template. Here we have a sequence of ints:
You might see the
while (true) and be alarmed, but don’t worry! This function is a coroutine, meaning it can suspend its execution and return control back to the caller. This prevents an infinite loop.
The suspension point is
co_yield x * x. This statement saves the stack onto the heap for later reuse, returns the next sequence element and jumps execution back to the caller.
OK… but how do I use this in practice?
seq can be used as an iterator:
Alternatively, you can save the whole sequence into a
std::vector. Just be sure not to try this on an infinite sequence!
This is pretty cool, but things get really interesting once you start combining and transforming sequences. To give you some idea, look at how concisely these functions can be implemented…
As you can see, many sequences are simple transformations of others, and Conduit allows us to represent this with a terse syntax.
Alan Perlis once joked that LISP programmers know the value of everything and the cost of nothing. And indeed a common criticism of lazy sequences is that they are far slower than transformations over vectors.
LISP programmers know the value of everything and the cost of nothing. — Alan Perlis
However, with Clang and the Coroutine TS, we’ve found that these abstractions usually compile away!
For example, consider this Fibonacci program:
Incredibly, Clang optimizes this to just:
main: # @main
mov eax, 511172301
Want to contribute? We have an actively maintained list of issues over on the tracker. 💖