Introducing Conduit: Lazy Sequences for C++

Conduit is a library that leverages the Coroutine TS to introduce lazy sequences to C++.

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!

Square Numbers

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:

auto squares = []() -> seq<int> {
  int x = 0;
  while (true) {
    co_yield x * x;
    ++x;
  }
};

The while (true) looks alarming, but don't worry! This function is a coroutine — it can suspend its execution and return control back to the caller, preventing 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.

Every seq can be used as an iterator:

int i = 0;
for (auto x : squares()) {
  std::cout << x << std::endl;
  if (i > 10) break; // squares is infinite, so we need to break
  ++i;
}

Or you can save a finite portion into a std::vector:

std::vector<int> v = range()
  >> take(5)
  >> toVector();
// v = { 0, 1, 2, 3, 4 }

Sequence Transformations

Things get really interesting once you start combining and transforming sequences:

// Sum of the first 10 squares
auto total = squares() >> take(10) >> sum();
 
// Jumps between the first 10 squares
auto jumps = squares()
  >> scan(0, [](auto x, auto y) { return y - x; })
  >> take(10);
 
// The obligatory fibonacci
auto fibonacci = []() -> seq<int> {
  int a = 0;
  int b = 1;
 
  while (true) {
    co_yield a;
    tie(a, b) = tuple{a + b, a};
  }
};
 
// Cumulative sum of 6 pseudo-random dice rolls
auto randoms = [](int seed) -> seq<double> {
  std::mt19937 engine(seed);
  std::uniform_real_distribution<> dist;
  while (true) {
    co_yield dist(engine);
  }
};
 
auto rolls = randoms(0)
  >> map([](auto x) { return ceil(x * 6); })
  >> scan(0, [](auto x, auto y) { return x + y; })
  >> take(6);

Many sequences are simple transformations of others, and Conduit lets us represent this with a terse syntax.

Compiler Optimization

A common criticism of lazy sequences is that they are far slower than transformations over vectors. However, with Clang and the Coroutine TS, these abstractions usually compile away entirely.

Consider this Fibonacci program:

auto fibonacci = []() -> seq<unsigned long long> {
  auto a = 0ll;
  auto b = 1ll;
 
  while (true) {
    co_yield a;
    tie(a, b) = tuple{a + b, a};
  }
};
 
static long N = 50;
 
int main() {
  auto n = N;
  auto items = fibonacci()
    >> drop(n - 10)
    >> take(n);
  unsigned long long result = 0;
 
  for (auto x : items) {
    result += x;
  }
 
  return result;
}

Clang optimizes this to just:

main: # @main
  mov eax, 511172301
  ret

The entire computation is evaluated at compile time!

Try Conduit

Conduit is available as a header-only library on GitHub. All you need is a C++ compiler with the Coroutine TS.

Related

• Conduit — Lazy Sequences for C++ — The project page with installation instructions and source code.
• C++ Coroutine TS — It's About Inversion of Control — How coroutines enable separation of concerns and maximum code reuse.
• Either vs Error-Codes — Another exploration of zero-overhead high-level abstractions in C++.