-

Transducers FTW!

May 13 2015, Verona

Massimiliano Mantione

Credits

Rich Hickey
(Transducers in Clojure)

Kevin Beaty
(Transducers in Ramda, and much more)

Erik Meijer
(Duality Talk)

About Myself

An enthusiast software engineer

Passionate about languages and compilers

Worked in the V8 team in Google

Overall, worked on JIT compilers for +7 years

Now working on scalable, fault tolerant,
web facing distributed systems

Javascript and me

I started as a Javascript hater

When I sow Javascript for the 1st time (in 1995) I vowed that I would never touch such an abomination, even with a 10 feet pole

Eventually, I changed my mind, but...

Let's change subject!

What are we talking about?

Transducers!

Functional programming

Functional programming in Javascript

Transducers fit into...

Utility libraries for base algorithms

Approaches to [a]synchronous data processing

Hope you'll have fun!

Functional Programming is...

a fashionable trend!

What does it mean?

First-class and higher-order functions

Pure functions (no side effects)

Describe what to compute and not how to do it

Less object oriented

No mutable objects

General functions instead of specific methods

No entanglement of code and state

Why is underscore.js popular?

Functional approach (no monkey patching)

Provides useful functions that...

  • say what you want to do (each, map, filter...)
  • instead of writing loops (how to do it)

Seriously...


Take the30 days no-loop
challenge!

Isn't lodash better?


No flame wars, please!

It improves:

  • completeness
  • performance
  • coherence
  • customizability

Otherwise, it is really similar

What about Ramda?

It makes functional best practices even simpler

Function composition is useful if you have useful building blocks to compose

Rambda makes currying the default, making it easy to build the building blocks!

Let's prove the point

var incompleteTasks = tasks.filter(task => !task.complete);
var incompleteTasks = _.filter(tasks, {complete: false});
var incomplete = R.filter(R.where({complete: false});
var incompleteTasks = incomplete(tasks);

Enter transducers

Composable algorithmic transformations

Decoupled from input or output sources

They compose directly (like functions)

  • no awareness of input or creation
  • no need of intermediate aggregates

Transducer building blocks

Stepper

Transformer

Transducer

reduce and transduce

Stepper

Stepper<I,E> :: (I, E) -> I

A function that takes a initial value and an element, and returns a new value for the initial item

It is the typical argument of reduce

Transformer

Transformer<I,E,R> :: {
  init :: () -> I
  step :: Stepper<I,E>
  result :: I -> R
}

Three functions, like e generalized stepper (with added begin and completion handlers)

Reduce

(the base transformation)

TransformerOrStepper :: Transformer | Stepper
reduce<I,E,R> :: (
    TransformerOrStepper<I,E,R> // transformation
    I                           // initial value
    Iterator<E>                 // input sequence
  ) -> R                        // result

Transducer

Transducer :: TransformerOrStepper -> Transformer

A function that transforms a transformer into another transformer

(let that sink in...)

It transforms transformers!

Transduce

(the generalized transformation)

transduce<I,E,R> :: (
    Transducer<I,E,R> // transformation
    Stepper<I,E>      // result builder
    I?                // initial value
    Iterator<E>       // input sequence
  ) -> R              // result

What's the trick?

A transformer can also be a simple stepper

Particularly, it can be an "reducer" that scans a sequence building a result value

Typically a "reducer transformer" is the terminal point of a transduce chain

Let's see some

real code!

What about async?

What does "async computation" mean?

Many say it is about push vs pull

I don't fully buy it

Let's see why

Push and Pull are Dual

What does dual mean?

It is similar to De Morgan's laws for
or and and

Reverse the direction of every function!

getter - setter

// getter<T> (pull)
() -> T
// setter<T> (push)
T -> ()

Iterable - Observable

Iterable<T> :: {
  '@@iterator' :: Iterator<T>
}

Observable<T> :: {
  Subscribe :: Observer<T> -> (() -> ())
}

Iterator - Observer

Iterator<T> :: {
  next :: () -> ({done :: bool, value :: T} | throws Error)
}

Observer<T> :: {
  onNext :: T -> ()
  onCompleted :: () -> ()
  onError :: Error -> ()
}

What do Observer and Iterator
have in common?

Both specify what to do in case of

  • next value
  • completion
  • error

What changes is just the push vs pull

The good news

Remember that transducers don't care about the sequence they operate on?

They work in push contexts, too!

And they work unmodified!

Let's see...

So far, so well...

...but what about async?

A push API looks async, but when the push happens the code is synchronous

So, what construct is really async?

Promises

Promise<T> :: {
  next :: T -> ()
  error :: Error -> ()
}

A promise represents a future value

It models a latency between the value availability and the moment when the code is ready to handle it

...or vice versa!

An async sequence

Implemented using promises

AsyncSequence<T> :: Promise<AsyncSequenceElement<T>>
AsyncSequenceElement<T> :: {
  value :: T?
  done :: bool?
  error :: Error?
  next :: AsyncSequence<T>
}

Push and Pull, async style

Like the regular push-pull duality...

...but with promises thrown in to model latency

getter - setter

// async-getter<T> (pull)
() -> Promise<T>
// async-setter<T> (push)
Promise<T> -> ()

Iterator - Observer

An Iterator that gives promises

An observer that expects promises

Note that ramda and underarm
already support this model!

Takeaway

Transducers model composable and reusable transformations of sequences of values

Several modern libraries are starting to support them

Push and Pull are dual

Async is properly represented by promises

That's All, Folks

code, docs and slides are on github

twitter: @M_a_s_s_i, #metascript

Thanks for following!