Building Streams out of Hot Air

Building sender streams out of senders

We're going to build an async stream and queue out of nothing but senders. For purposes of this talk, a stream is an infinite collection where you can only get the head element and the rest of the stream.

Along the way, we'll take a look at the last 80 years of computer science, including some current areas of active research.

Having a better idea of how senders -- and functions like them -- are grounded in theory gives us a better idea of how they can be used and where to look to borrow designs and insights.

We don't just borrow [syntax]; on occasion, [C++] has pursued other languages down alleyways to beat them unconscious and rifle their pockets for new [semantics].

---(with apologies to) James D. Nicoll

I'm going to show you even a more horrible thing, a definition of CONS in terms of nothing but air, hot air.

---Gerald Jay Sussman, Computational Objects

In C++, P2300 Senders are computations to be performed---"an object that describes work" (see Niebler et al. 2024, 4.3). Taking designs that suspend computation are a natural place to begin when planning senders. Models that do so in an otherwise strict evaluation environment can be easier to reason about for porting to C++ than from default lazy environments, such as Haskell.

By 'air', Sussman meant building a data structure out of nothing but higher order lambda expressions in scheme. This technique is also a common implementation technique for functional programming languages, and it turns out to be one of the ways pattern matching is supported.

This can be implemented directly using C++ lambda, something that is particularly easily now that recursive lambda is possible using deducing this. We start out by implementing Either, then Pair, Maybe, Boolean, and then we see how recursive types can be made, such as a cons list. The core of the pattern is closely related to generalized fold, or catamorphism, and it has deep connections to the Visitor pattern.

Changing perspective from inductive types, like list, to coinductive, infinite types, like stream, means looking at deconstruction, or observation, of codata. However, the pattern of dispatching to handlers remains the same, though with some slight inversion.

This guides us to a concrete Sender design that can be implemented as concrete sender types, rather than wrapping unnamed higher-order functions. This also helps avoid recursions in the type system, by hiding the uninteresting intermediate types being sent. This also provides an excuse to demonstrate implementing a sender. There are not enough examples, but writing a sender is intended to be within the scope of work for an intermediate C++ developer.

At the end of this talk, we will have an async queue and an async stream implemented using just senders.