Transducers

Transducers

Transducers were introduced into clojure many years ago. The term transducers is not unique to clojure. The type signature provided on the clojure page is reducer -> reducer where reducer is {state, value} -> state. Using functional language terminology, a transducer is a reducer combinator--you can create new reducers from other reducers. A reducer can be thought of as a functional fold. Hence, a transducer is just a transformational pass over an input sequence with a final reduce operation e.g. sum. If implemented correctly, transducers can reduce the number of passes and the amount of intermediate results compared to naive implementations--improving memory usage and in theory, processing performance.
There are other functional concepts involved in transducers as well including currying. A good read, using javascript, is included here: https://hackernoon.com/partial-application-of-functions-dbe7d9b80760#.v84qwq432. Transducers are also related to lenses.
There is also a broad set of terminology associated with this such as pointfree or tacit programming. See this Wikipedia entry.
Different languages represent the concept differently:
I first encountered transducers in Mathematica where in recent versions, transducers (called "Query") were introduced so you could specify the algorithm of a desired operation independent of the actual target sequence/list type. You could build up the operators and then apply them to Dataset. The idea of efficient iteration over a series and applying multiple operations independently of the actual series to be used is a much older concept and was first broached in the loop macro in common lisp and even earlier in common lisp and Rich Water's series lisp package--late 70's!

Scala

There is a nice scala transducers library. Here's the repl:
@ import $ivy.`de.knutwalker:transducers-scala_2.11:latest.version`
@ import scalax.transducers._ 
@ import scalax.transducers._
@ val xform = filter[Int](_ < 10).map(_ + 1) 
xform: Transducer[Int, Int] = (filter).(map)
@ into[List].run(xform)(Stream(1,2,3)) 
res3: List[Int] = List(2, 3, 4)
I'm using the 2.11 version althoug the amm version I am using is 2.12.
You can also use fs2, which has a different API, but allows you to separate out algorithm from the specific input and final reduction operation. Note that haskell, which scala has some parallels to, introduced machines and pipes libraries that prceeded fs2 (and scalaz machines).

Common Lisp

A trasnducers library is available for sbcl. It does not compile out of the box, I had to comment out the :vector reference in the transdurers.asd file.
;; no exported symbols in transducer's ASD file!
(in-package :transducers)
(defvar *transducer-symbols* '(filter take drop comp transduce sequence))
(in-package :cl-user)
(import transducers::*transducer-symbols*)

(let ((xf (comp
    (filter #'evenp)
    (take 2)
    (drop 1)))
      (coll '(1 2 3 4 5 6 7 8)))
  (transduce xf #'+ coll))
;; 4

Transducers and other abstractions

A nice benefit of trasducers is that they can separate the algorithm from the actual application of the algorithm. It's a good idea of course. The scala library fs2 allows you to abstract the algorithm as well. In fact, streams libraries and their cousins (like monifu) are focused on the same thing. While they often discuss the "reactive" abstraction for handling back-pressure and such, the streams libraries allow you to abstract out the operations from the application of the algorithm. streams libraries also focus on composing processing logic--one of the objectives of transducers. Of course, separating the algorithm from its inputs can be accomplished many different ways, e.g. writing a function or a macro.
In fs2, you can also control at fine grained level, the concurrent/parallel aspect of processing. It's easy to imagine that each xform (in clojure language) could operate in parallel. One of the "reimplementations" does exactly that. One such approach could be to use CPS-style processing where each "little" event loop reads from a queue the element processed by the proceeding "little" event loop.
In fs2, you can compose the operators in fs2 without references the specific input stream:
@ pipe.take[Task, Int](2) andThen pipe.lift[Task, Int, Int]{_ + 1}  
res13: Stream[Task, Int] => Stream[Task, Int] = scala.Function1$$Lambda$2331/956074603@1cde05bc

Comments

Popular posts from this blog

quick note on scala.js, react hooks, monix, auth

zio environment and modules pattern: zio, scala.js, react, query management

user experience, scala.js, cats-effect, IO