Transducers – what are they? This is term from Clojure world. There is a classic video from inventor of this term Rich Hickey, and here is some manual page from closure’s docs. But I’ll try to explain all this the simplest possible way so you don’t have to watch all that stuff.

Also I will show my way to implement transducers using C++14 and a lot of examples how to use them.

The idea is simple – if You have sequential process and each inner step could be represented as functional composition of reducing functions – we could make ‘composer tools’ for it (high order functions) and call them transducers.

Perfect analogy from real world – baggage queue in airport. Each bag should go through several operations – check bag, wrap bag, get weight, pass bag, etc. Each iteration could be represented as some reducing function. And transducer is the way to make composition of operations – transduce one reducing function into another (producing desired composition).

So we can write chain of map, reduce, filter, limit, etc but in form of transducers. Instead of performing iterations each of them will produce composition of actions for single sequence element. And finally, when we execute whole functional chain there will be only one cycle through range.

There are already working libs for C++ available so you can play with transducers – one of them is open-source lib called Atria. Enjoy presentation about Atria from cppcon 2015.

But actually it’s not so complicated to implement your own version of transducers. My main aim was to integrate them into my working functional data processing scheme (which is described here). And also create the best possible syntax sugar to make life sweet.

Notice My implementation is a bit different from atria’s one – the difference will be explained below.

USAGE EXAMPLES

Let’s start with basic examples (which were at my slides from MeetingCPP 2015). Even if you are not familiar with basic ideas of functional processing the samples will still be quite readable.

First example is just composition of filter and map for primitive types. I took integers only as example, of course it’s not limited to them. The following example takes only even numbers from vector of ints and than adds one to each of them. Generally this could be done writing one or two circles with if condition inside, which would not be so readable. But we could use transducer here:

Second line creates transducer comp (which can be reusable), and last line is performing actual iteration. Output_rf is standard reducing function which just adds new element into provided list. Function into takes four arguments – first is initial state of accumulator, second one is composite transducer, third is initial reducing function and the last one is input range.

We can write same operation as one line:

Here we switched into with into_vector, which assumes that we accumulating items into empty vector. Once again, there is only one cycle inside this chain. As You can see this line is quite readable.

We could have multiple inputs:

Also we could have any range as input:

Any class which has begin()/end() interface could be used here.

Another one-liner to show that accumulator could be just one integer which could be used in place:

When you need to stop iterating due to some reason it’s possible to extend our transducers to make early termination. There are several ways to do so – this will be discussed further. Now the most obvious example – limit count of elements inside final accumulator.

Also we don’t have to put anything into result storage – here we just perform some function for each element using nullptr as accumulator.

As transducers could deal with any sequence of data (like UI events, network events, etc) it would be nice to have ability to resume iteration process.

As You can see in this example enumeration of strings was continued from right index. Sweet.

If You are not familiar with functional data processing concept at all, such examples might seem not so obvious. But trust me – after on hour playing with this syntax, everything will be perfectly readable.

Enough of examples – let’s proceed to possible implementation details:

IMPLEMENTATION

What do we need to implement transducers? Actually main essence could be written as several lines using C++14!

Function which returns function which returns another function… looks totally crazy.

But this is not only problem – Microsoft’s compiler produced internal compiler error on this part of code. So I peeked at Atria implementation and rewrote this code, converting each lambda into templated functor! Instead of several lines I got this (as I need cross-platform solution):

If You are using only Clang you can stay with previous implementation and be happy. 

This implementation already contains several assumptions. First it contains the way I choose to implement early termination. Each step() returns bool which is false when we need to terminate. Just that simple. And accumulator is passed by reference to step function.

This could be implemented by wrapping result state itself into wrapper struct and this way is described here – video.

Also I want to compose my transducers using functional chain, which was described here. But there is one important difference – when we compose reducing functions, the order of application is reversed. So we need to create reversed functional chain.

And to support piping into such chain we need to overload operator like this:

One more thing – if we have general functional piping overload (more details here), this overload will produce errors during compilation as compiler will not know what to do – just call your chain using provided argument or push new element into chain. To solve this ambiguous situation we just need to add some type traits and SFINAE:

Ok, let’s implement main iteration now:

Only complication here is the need to support several input ranges. So we pack iterators into tuple and increment them all as one step. Also we need additional function to compare two tuples to know when to stop (which I grabbed from atria):

All what’s left is to create several more convenient interfaces to call main iteration cycle. into and into_vector are probably the most obvious ways to use transducers from first examples, but they all just call main iteration function – fn_accum_impl.

The macro fn_make_universal converts functor into ‘universal’ functor which supports piping and currrying (that topic is described here).

Now we can just add a bit more of sample transducers (filter, enumerate, limit, each):

You could implement any custom transducer using this implementation as sketch.

CONCLUSION

Transducers combine long functional data processing chains into one iteration cycle. This is crucial when you need to process large amount of data or have sequence of realtime events.

Transducers are quite readable and simple to use (when you are familiar with primitive functional data processing chains). You need to write core of transducers only once (or You can grab one of libraries which already have suitable implementation).

I hope the benefits are obvious from samples. As one of ways to simplicity transducers were included into my presentation at MeetingCPP 2015 about fighting complexity in modern C++ (slides).