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 isreducer -> 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:
- clojure (part of core, also parallel version)
- common lisp (transducers, series)
- scala (fs2, transducers library
- python (transducers, nice description)
- Wolfram ()
- javascript (see the reference in the paragraph above)
- ...
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)
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 libraryfs2
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
Post a Comment