# Of umbrellas, transducers, reactive streams & mushrooms (Pt.2)

A 5k-word deep look under the bonnet of Transducer Model S

This is part 2 of an ongoing series introducing & discussing projects of the thi.ng/umbrella monorepo. Other parts:

• Part 1 — Project & series overview
• Part 3 — Convolution, 1D/2D Cellular Automata
• Part 4 — Disjoint Sets, Graph analysis, Signed Distance Fields

As promised last time, in this installment we shall lay the technical foundations used throughout the rest of this tutorial series, to prepare for some terraforming of Shroomania, the mini-game going to be built up here. However, the game itself is just used to contextualize these more generally useful-to-know concepts, which for this part are: functional programming basics (some, this is not an FP tutorial as such), ES6 iterables, reducers & transducers. Since that’s already a lot of material (this post is 5k+ words), I’ve moved Cellular Automata & terrain generation to the next part of this series to cover them in more detail.

Higher order functions 101

There’s more to Functional programming than the often cited semi-scary terms from algebra and category theory (which we will largely avoid here, functors, monoids — I’m looking at you). Firstly, the ability to pass functions as arguments to other functions is a pre-requisite for any FP language. Functions here are first class citizens, are standalone and can be dealt with just like other types of data. Functions, which either accept other functions as arguments (inputs) and/or yield a new function as their result (output), are called Higher-order Functions (HOFs), and as such are one of the principal mechanisms for other concepts, including application, currying, composition, memoization, trampolining etc.

A basic example, familiar to probably anyone in the JS crowd:

HOFs are the bread & butter of processing data in a functional manner and a stylistic (though not always a performance) improvement over iterative code like this:

One of the obvious benefits of the functional version is the separation of iteration logic and the actual transformation task, which in the iterative version are fully entangled. Though, we will soon see how to separate this even further.

Using the built-in HOFs of `Array`, we can easily construct array transformation pipelines:

This construct works just fine, though is subtly hiding at least two issues:

1. It’s merely a clever fluent API application of the Array class’ prototype methods. Apart from `map` and `filter` being HOFs, the larger construct is not strictly functional. In other words, the individual processing steps are not standalone functions and they only work with arrays, but no other data types. E.g., there’s no `map` for objects, strings or sets…
2. Each transformation step creates a new (temporary) array, which in turn needs to be iterated over again. In the above example, the data flow is this:

For larger arrays and longer pipelines, these allocations can quickly add up and cause unnecessary pressure on the garbage collector. Yet, this is by far the most popular approach used in JS…

## Reductions

In addition to mapping (transforming) and filtering data collections, a so-called reduction is another fundamental (and more important) operation, i.e. a stepwise “boiling down” of a data source into a final single result:

As with `map`, `reduce` too processes the input array in a stepwise manner. Only here, the user-supplied function passed to `reduce` is always called with 2 arguments: the current intermediate result (often called accumulator) and the next value from the data source (i.e. the array to be reduced). The last argument (here, `0`) is the initial result and will be used as the accumulator in the reduction step of the first array value. Also, if the source array is empty, this initial value will be the final result of `reduce`.

In principle, we’ve now clarified what a reduction function is. Only finite data sources can be reduced, of course. The idea of a “single” result might initially feel misleading since a reduction itself can take many forms. In the next example, we compute a histogram of word frequencies. The histogram object is the single final value, but itself contains several sub-results (which could be reduced even further, e.g. summing up the values to obtain the total word count):

As an extension of `reduce`, and to lead on to our main topic, we could create a different version of `reduce`, one which wraps and augments our normal reduction function to produce an array of all intermediate results (not just the final one) and so possibly helps us better understand how the reduction process actually operates. Let’s call this function `reductions`:

At this point, one can argue that `reductions` somewhat behaves both as a `map`-like, as well as a `reduce`-like operation. In fact, we can re-implement `map` and `filter` (and maaany other operations) in terms of `reduce` like this:

And this, ladies and gentlemen, is the crucial insight leading us to transducers, an augmentation and generalization of reduction functions on <insert-hallucinogenic-drug-of-choice>…

## Transducers & Reducers

Maybe a direct result of one of the hard problems in CS (i.e. naming things), there’re multiple meanings of the word transduction, mostly not CS related at all. The one we’re dealing with here simply is an amalgamation of “transforming reducer” and was initially coined and implemented in Clojure by Rich Hickey as an extension of his earlier work on Reducers, and who succinctly summarized it as:

“A transducer is a transformation from one reducing function to another.”

— Rich Hickey

I too like the more physics-oriented definition on Wikipedia:

“A transducer is a device that converts energy from one form to another.”

Data & code are our forms of energy and transducers are a powerful tool to transform either — after all, code is data and vice versa. Personally, using transducers (initially only in Clojure) not only has been one of the most eye-opening experiences about the beauty & elegance of the functional programming approach, but they too have turned out to be a super flexible key ingredient in the thi.ng/umbrella project and are used extensively by several of its packages.

There's already a number (dozens) of older transducer libraries available for JavaScript. With thi.ng/transducers (and its sibling packages) I was aiming for an alternative, more comprehensive, yet lightweight and OOP-free implementation, and one which fully embraces ES6 iterables. All transducers implemented by this package are heavily using TypeScript’s generics to allow building fully typed (end-to-end) transformation pipelines. With all the additions to TypeScript’s type inferencer over the last years, the use of generics also means we often don’t even have to declare argument types anymore.

More generally, the aim of transducers cleanly falls into the domain of Separation of Concerns, i.e. to separate the different processing stages of a reduction process and take into account that the user might not have supplied an initial reduction result (so it’s then the reducer’s responsibility to provide a default). Furthermore, unlike JavaScript’s built-in `Array.reduce()`, other versions, like Clojure’s `reduce` support the idea of early termination, i.e. the ability to not having to process the full input, and stop the reduction at any given moment by wrapping a result as `(reduced x)`. That’s a super useful feature as we will see later on.

Let’s summarize some other advantages of Transducers over the more traditional chained application of `Array.map()`, `Array.filter()` and `Array.reduce()` and variations of that theme, supplied by many related JS libs:

1. Transducers separate the actual transformation and (optional) reduction from their inputs. In other words, they do not deal with the process of obtaining a source value to transform, nor with the process applied to a transformed value — the latter is the role of Reducers (which we will discuss later). Rich Hickey’s key insight was that many common data processing operations can be expressed as a form of augmented reduction. The `Array.map()` operation, for example, can be logically split into: 1) the part obtaining a value from the data source (array), 2) the actual transformation of that value via the user-supplied function and 3) the piecewise construction of the result array (really a form of reduction, as we’ve seen earlier). Transducer functions exclusively only deal with the second step (transformation) and so have a much wider scope of application and are more reusable.
2. Transducers can be composed (using functional composition) to form re-usable transformation pipelines, which generally avoid (or at least drastically minimize) the creation of intermediate result arrays. This is amplified even more by using ES6 generators instead of large arrays as data source. In a multi-stage transformation pipeline, each new source value is processed as far as possible and then only reduced once (if at all).
3. Transducers can be executed in a single-step manner, i.e. only processing a single value instead of transforming an entire collection. This makes them amenable to use in async processes, yet still retain all the other benefits mentioned here.
4. Transducers are built around Reducers and can cause early termination of the entire processing pipeline. As with the previous point, this too enables interesting use cases, as we will see later on.
5. Transducers can lead to much better code reuse across the board (use cases) because there’s no reliance on certain input data types. This avoids the vast and IMHO partially unnecessary code repetition going on across the JS community. E.g. how many libraries with custom datatypes are re-implementing their own versions of `map`, `filter`, `reduce` etc.? thi.ng/transducers works with all ES6 iterables (i.e. arrays, strings, maps, sets, generators) and any other custom datatype which implements `Symbol.iterator` or the `IReducible` interface (a single function) to provide custom/optimized reduction logic. For array-like inputs (arrays, typed arrays, strings) a fast route is provided.
6. The separation of concerns in a transducer process makes it easy/easier to parallelize processing, at least partially, e.g. via workers. This too is helped by the fact that the majority of transformation functions are usually pure, i.e. only depend on their given arguments and do (usually) not mutate any global/external state.

Remember the definition of a transducer from earlier:

“A transducer is a transformation from one reducing function to another.”

Combining all these above qualities and requirements, we can finally take a look at a `Reducer` interface definition in TypeScript, the way it’s been implemented in the @thi.ng/transducers library:

So we have a 3-element array of simple functions, each responsible for a different processing stage. Based on some of the above examples, we can define some simple reducers like:

Not taking into account early termination for now, we could then write a basic version of `reduce` like this:

Using a`for..of` loop automatically makes our `reduce` much more flexible, since we can now work with any ES6 iterable, including generators…

Above we defined the `Reducer` interface using generics, stating the reducer’s reducing function consumes values of type `B` and produces results of type `A`. For a `Transducer` the situation is similar, only we need a 3rd type, for which we use `any`, since for an individual transducer, we can’t prescribe what kind of result is being produced/reduced at the very end. If this is still unclear, the following examples will hopefully help.

…or in less formal terms, a transducer is a function which accepts a reducer accepting inputs of type `B`, and returns a new reducer accepting inputs of type `A` — a transformation of a reducer, indeed.

Now we can redefine `map` in transducer form (with types, for clarity):

Without going into even more detail now (there’re a lot of other blog posts about the topic), we‘ve reached the last remaining piece of the puzzle: `transduce`. This function is actually rather trivial and merely combines all the other elements discussed thus far: It takes the same arguments as `reduce`, with an additional transducer (like `map` above) as the first argument. It then simply composes the given transducer with the reduction step and then just delegates to `reduce`. The reason for this user-side separation between transduction and reduction steps will become more obvious very soon.

Some basic examples, both using the same transducer, but different reducers:

Earlier I mentioned that transducers can be composed to form transformation pipelines. Composition (together with Application) is one of the primary constructs in functional programming, in short: `comp(f,g)(x) = f(g(x))`. For that reason thi.ng/transducers provides an optimized `comp` function (which actually is part of the thi.ng/compose package), allowing arbitrary numbers of transducers to be combined.

In this next example, we’re using `comp` to compose the following transducers in series to perform some simplistic CSV parsing.

Important: The entire transducer pipeline is executed as far as possible for each line of the CSV string before the next line is processed. This is in direct contrast to the earlier mentioned popular array method chaining approach, in which each transformation step processes all inputs before passing the transformed result collection to the next step.

After splitting each CSV line into an array of strings, the `rename` transducer is used to convert each array into an object, using the column names provided in the first line. In isolation:

The `mapKeys` transducer takes an object of transformation functions and then for each input transforms the values of the given keys:

Altogether, the thi.ng/transducers base package provides ~60 different transducers, 25 reducers, and 22 iterators/generators. We will look at some of these next, but will also encounter more interesting ones over the coming parts of this article series. The package README and doc strings of various functions have many more examples too.

Additionally, there are the following extension packages, providing transducers and related functions for more specific use cases:

• thi.ng/transducers-binary: Binary data related (bits, bytes, structured data, hexdump, utf8, base64 etc.)
• thi.ng/transducers-stats: Technical/statistical/ inancial analysis transducers (moving averages, Bollinger bands, Donchian channel, MACD, RSI etc.)
• thi.ng/transducers-fsm: Finite State Machine transducer (soon will be merged/replaced by the more advanced thi.ng/fsm package)
• thi.ng/transducers-hdom: Transducer based thi.ng/hdom UI update (we will use this feature starting in one of the next articles)

## ES6 iterables

Browsing through various JavaScript repos on GitHub, it seems that ES6 generators (and more generally, `Symbol.iterator`) are seemingly rather under-appreciated (to put it mildly) in this community. I find this very odd since they both are some of my favorite features of the language and also play an important role as data sources in the context of transducers.

For example, many transformations require some form of counter input. So we could use one of the `range` generators to drive it:

Above we’ve used the ES6 spread operator purely for demonstration purposes, to force the evaluation of the range. However, this is only to see the results easier in the REPL. For transduction, we don’t require these ranges as arrays, but only need the input to be iterable (which includes ES6 generators). Using generators avoids the need & creation of those temporary counter arrays entirely!

The Es6 spread operator in an array is essentially a reduction operation:

In addition to simple numeric counters, there’re also 2D, 3D and normalized versions (see docs for details):

Normalized counters are useful for all sorts of use cases, e.g. here to compute vertices of a regular 2D polygon:

(The above `cossin` function computes both the cosine & sine of the given angle and scales result to `r` (radius))

To avoid/minimize boilerplate, most (not all) transducers and reducers in thi.ng/transducers support an optional source iterable. If this is given, the returned function will not be a transducer/reducer anymore, but instead becomes a transforming iterator of the input. So we could rewrite the above as:

Once we will start building a UI for our game, we will make more repeated use of this iterator feature. For now, just file it under “good to know”…

## Multiple inputs

The overall usage pattern of a reduction is the usual:

input → process → output

But what if we want to consume data from multiple sources? For that reason, most FP libraries/languages have a so-called `zip` operator, which combines multiple inputs into tuples, like so:

zip only yields values until one of its inputs is exhausted. In the above code, both `range` and `choices` are infinite, however `"abcd"` isn’t…

## Multiple outputs

Sometimes, a transformation needs to produce multiple results for a single input, either in series or in parallel. thi.ng/transducers has several options for each (not all & not all options discussed here/yet):

Also falling under this category is the idea of functional juxtaposition, i.e. a higher-order function, which takes a number of transformation functions and returns a new function, which when called, applies all given functions to the input and returns a tuple (array) of the results:

That same concept can also be applied to execute multiple transducers for each input and that way, create a kind of multiple processing lane system (maybe temporarily only and fused back later on…). The higher-order transducers `multiplex` and `multiplexObj` are doing exactly that:

Note: Because a moving average of period `n` can only produce values after `n` inputs, we have to skip `n-1` inputs here, because `multiplex` does no filtering and so the first 4 results each are: `[undefined, undefined, undefined]`.

## Infinity & early termination

Infinity is a unique aspect of generator-based data sources, not achievable with the purely-array based data transformation approach. E.g. here’re some easy ways to crash your browser tab/node REPL:

All of these (and more) are examples of infinite generators. `range`, when called without arguments, yields an infinite sequence of monotonically increasing values, which of course can’t fit into a memory-cached array. Yet, there’re many dynamic programming use cases, where we might want to work with an initially infinite source, but then somehow stop when a given condition occurs (see Douglas Adams’ Hitchhikers Guide to the Galaxy for literary example). This is why `reduce` in thi.ng/tranducers also provides several operators to bail out of a transduction/reduction process.

take

This transducer consumes a maximum of `n` given values, then terminates the entire reduction process:

takeWhile

This transducer terminates when the given predicate returns false. `iterate` is another infinite generator…

converge

Similar to `takeWhile`, but the predicate is given 2 values: the previous and current input. Terminates when predicate returns true.

There’re many other options available, however, this post is already getting too long and I will have to defer you until the next articles and/or the readme files for further examples. Under the hood, this early-termination-on-demand is achieved by a transducer wrapping its result in `reduced()`, just as it’s done in the Clojure version as well.

The presence of such a wrapped result value will then stop downstream propagation of the result to any other transformations in the pipeline and terminate the overall reduction process entirely. Only the “completion” function of the given reducer will still be executed to finalize the overall result.

## Laziness & stepwise execution

In the `take` example, we’ve seen the use of `iterator`, which is an alternative way to `transduce` to execute transducers. A watchful reader might have noticed though that we did not provide a reducer to this function. In fact, the signature for `iterator` is:

The reducer is omitted, because, here the iterator itself is fulfilling the reduction role, producing transformed values via the standard ES6 iterator protocol. However, being a generator, obtaining transformed values is a pull (not push) based operation. In other words, we only want to process/transform new values from the actual data source, when a downstream / userland process demands it.

To achieve this, `iterator` uses the `step` (higher-order) function, which we can also use directly:

Here we can see that the returned step function returns nothing if the wrapped transducer did not produce any value(s). As we’ve seen earlier, some transducers can also produce multiple results per input. In this case, the stepper returns an array of results:

Another example (taken from the thi.ng/lsys package) illustrating laziness:

At this point, `expanded` is completely unrealized and nothing more than a recipe for a composed, future computation. It’s a generator. Only once we start requesting values from that generator is when the expansion process actually starts/runs:

## Outlook

Even though we’ve just merely scratched the surface here, I hope this article provided some more clarity about the basics of this (IMHO) fascinating topic. In the next part, we will put some of these concepts to more practical use by combining them will Cellular Automata to produce the terrain for our game.

Lastly, if you have any questions or feedback about any of the projects mentioned, please do get in touch via Twitter, the GH issue tracker and/or join our Discord channel.

Other parts:

• Part 1 — Project & series overview
• Part 3 — Convolution, 1D/2D Cellular Automata
• Part 4 — Disjoint Sets, Graph analysis, Signed Distance Fields

--

--

## More from thi.ng

Computational design, data, TypeScript, Clojure/script, C

## Get the Medium app

Computational design, data, TypeScript, Clojure/script, C