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:

• you can’t change state, i.e. …
• you can’t (re-) assign variables
• you can’t even fill or modify arrays!

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:

• map takes a function and a sequence, and applies the function to each element - and if you need it: it returns a new sequence of all results

• filter takes a function and a sequence, and returns a sequence with elements for which the function returned true

• reduce takes a function, a starting value, and a sequence, and produces the reduction - this one takes a bit more effort to wrap your mind around, but it’s extremely useful and common

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:

• take 0 and the first element (a), apply +, and remember the outcome
• take that outcome, and the next element (b), apply +, and remember the new outcome
• rinse and repeat, until we’ve added the last element (e) and get a final outcome - that’s our final result
• all intermediate results are discarded

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:

• A reducer is a function of the form:

  x' = f(x, y)

  It can be used to “reduce” a sequence, by taking the successive elements and applying them one by one:

  x' = f(x, y1)
  x'' = f(x', y2)
  x''' = f(x'', y3)

• A transducer is a function which takes a reducer and returns another reducer.

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:

• log calls, arguments, and/or results
• only call f in some cases, not in all
• call f more than once
• modify x or y before passing to f
• modify the result from f
• (de-)compression, en-/decryption

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.