Reducers and transducers Sep 6, 2017

As part of becoming more familiar with the Clojure programming language, I recently decided to immerse myself in “Functional Programming” (FP), “Immutability”, “Pure Functions”, and such. It’s been around for decades, but I’ve always shied away from it: too mind-bending / impractical / esoteric.

No more: I’m taking it in as fast as I can …

To be clear: Haskell and its monads are still way beyond me. But Clojure offers just the right mix of FP and immutable-vs-mutable state for my limited mind to understand why it makes sense and how to use it.

Coming from decades of procedural state-modifying programming, it’s a major shift in perspective. Man, this stuff is powerful!

So let me describe what I’ve been going through, i.e. the perspective of an FP-and-CLJ newbie, to illustrate what it’s all about.

Functional

A function takes arguments and produces a result. In programming, we’ve conflated this with procedures and subroutines, which look the same but can also modify some “state” locked up in the arguments. With OOP, we’ve taken it even further:

myObj.MyMethod(arg1, arg2)

The state is now hidden inside myObj, and the result of this call is usually that the state gets changed by it. This construct hides details (which is always nice), but also makes it considerably harder to reason about what’s going on.

First of all, the above notation is usually implemented using a hidden this pointer:

MyMethod(myObj, arg1, arg2)

Now let’s pick this apart a bit more:

newObj = MyMethod(myObj, arg1, arg2)

The change here, is that we make MyMethod return a new object, instead of modifying its args. In FP-speak: MyMethod is now pure.

Bear with me - there is a purpose…

(and no: it doesn’t lead to dog-slow code)

Immutable

We’ve now entered the realm of Functional Programming, where lots of stuff is passed around and is transformed along the way. From a non-FP state of mind, it seems ridiculously limited:

This is fine (using C notation):

int a = 1;
int b = a + 2;
int c = f(b,3);

But the following block is now disallowed:

int a = 1;
a += 2;
a = f(a,3);

It gets even crazier, we can’t even do this:

for (int i = 0; i < 3; ++i)
    printf("i = %d\n", i);

Map, Filter, Reduce

So how do you iterate? Well, you generate a sequence (far more general than an array, as it doesn’t have to be a memory-based), and apply your function to each element.

In imaginary pseudo-code:

function printf(value) {
    ...
}
map(printf, range(0, 3))

Note that in a truly strict FP-pure world, even printf is trouble, since it has side effects (namely: printing out something). But luckily, Clojure isn’t that extreme.

It turns out that repetition boils down to just one of these three basic operations:

The map and filter functions can also be implemented with reduce, by the way.

Reduction

Reduction is a very simple operation: think of “a+b+c+d+e”. Our operation is addition, and we’re somehow applying that to all the elements of the sequence “[a,b,c,d,e]”.

Here’s how it can be written in Clojure:

(reduce + 0 [a b c d e])

And here’s what happens:

In C’ish notation, reduction is a bit like:

a = f(a, b)
a = f(a, c)
a = f(a, d)
...

Which has some resemblance to calling an OO method a few times - interesting, eh?

Reduction is our hammer

Sooo … in the world of pure functions and immutable data structures, reduction can be viewed as applying different methods and arguments to state, or … to an object!

Another example is a Finite State Machine: some sort of “state”, which gets changed in response to new events and triggers. If we treat those events as a sequence, then it becomes a reduction in FP terms:

reduce(prev-state, [events...])

It doesn’t stop there: take an app with a user interface, having internal state (and a visible representation) that responds to user input. You guessed it: it’s a reduction, fed by user input. And a nice way to look at the React and Reagent development models.

There is in fact a huge range of programs which - in essence - act as reductions:

new-state = f(old-state, some-input)

Transducers

As recently as 2014, Clojure introduced the concept of Transducers. As so many “deep” concepts, it’s easier to understand once you have the right mental model:

Wait - hang in there, I promise it’s worth it! Keep in mind that even simple operations like “+” and “append” can act as reducers.

A transducer takes a reducer, and returns a (somehow) derived reducer. So instead of:

x' = f(x, y)

We now have a new reducer, acting like:

x' = t(f)(x, y)

The result of t(f) is a function (let’s call it g). When called as reducer, it gets evaluated in the following context, as usual:

x' = g(x, y)

This is surprisingly useful. That function g, which we are free to define as we please, has access to the x and y inputs, can apply f to them as it likes, and can further process f’s result before returning a value.

Some of the things a transducer can do:

In case you’re familiar with the concept: middleware can also be implemented as a transducer. It’s more or less the same idea.

The point of it all

Ok, so yeah, we can play games with all this, but why go there in the first place?

The value I see in it, is that FP offers a completely different way to split up and implement programming tasks. Iteration, transformation, and all sorts of other high-level concepts can be coded directly and independently of one another.

A web server, a state machine, a database operation: these are all reducers. They do different things, but their shape is similar!

Modifying an existing code base can be a lot less invasive if the new functionality fits the model of a transducer, inserted as needed.

Now that I’m starting to grok reducers and transducers, I’m seeing them pop up all over the place. As in … dataflow engine!

PS. For a great intro to Clojure transducers, see Tim Baldridge’s video on YouTube.

PPS. Tim again … about learning Clojure.

Weblog © Jean-Claude Wippler. Generated by Hugo.