I made srfi-171 [0], transducers for scheme. If you have any questions about them in general I can probably answer them. My version is pretty similar to the clojure version judging by the talks Rich Hickey gave on them.
May I offer a little code riff slicing FizzBuzz using transducers, as one would do in practice, in real code (as in not a screening interview round).
Demo One: Computation and Output format pulled apart
(def natural-nums (rest (range)))
(def fizz-buzz-xform
(comp (map basic-buzz)
(take 100))) ;; early termination
(transduce fizz-buzz-xform ;; calculate each step
conj ;; and use this output method
[] ;; to pour output into this data structure
natural-nums)
(transduce fizz-buzz-xform ;; calculate each step
str ;; and use this output method
"" ;; to catenate output into this string
natural-nums) ;; given this input
(defn suffix-comma [s] (str s ","))
(transduce (comp fizz-buzz-xform
(map suffix-comma)) ;; calculate each step
str ;; and use this output method
"" ;; to catenate output into this string
natural-nums) ;; given this input
The key insight behind transducers is that a ton of performance is lost not to bad algorithms or slow interpreters but to copying things around needlessly in memory, specifically through intermediate collections.
While the mechanics of transducers are interesting the bottom line is they allow you to fuse functions and basic conditional logic together in such a way that you transform a collection exactly once instead of n times, meaning new allocation happens only once. Once you start using them you begin to see intermediate collections everywhere.
Of course, in any language you can theoretically do everything in one hyperoptimized loop; transducers get you this loop without much of a compromise on keeping your program broken into simple, composable parts where intent is very clear. In fact your code ends up looking nearly identical (especially once you learn about eductions… cough).
Transducers work even better with a Clojure library called Injest. It has macros similar to the standard Clojure threading macros except Injest’s macros will recognize when you’re using transducers and automatically compose them correctly. You can even mix and match transducers and non-transducer functions and Injest will do its best to optimize the sequence of operations. And wait, there’s more! Injest has a parallelizing macro that will use transducers with the Clojure reducers library for simple and easy use of all your cores. Get it here: https://github.com/johnmn3/injest
Note: I’m not the author of Injest, just a satisfied programmer.
I've never quite wrapped my head around the full JVM Threading story (esp with the new VThreads). Does the Thread Pool system work well when you over-parallelize your workload? If it's thread-and-forget? Can you thread stuff in a library you write, even if the caller is threading stuff at a higher level?
Do you have any idea/guess why Injest hasn't been folded in to core? It seems a natural extension, so I worry if it has some hidden footgun
When I first read about transducers I was wowed. For example, if I want to walk all the files on my computer and find the duplicate photos in the whole file system, transducers provide a conveyor belt approach. And whether there are saving in terms of memory or anything, maybe. But the big win for me was to think about the problem as pipes instead of loops. And then if you could add conditionals and branches it is even easier to think about. At least I find it so.
I tried to implement transducers in JavaScript using yield and generators and that worked. That was before async/await, but now you can just `await readdir("/"); I'm unclear as to whether transducers offer significant advantages over async/await?
[[Note: I have a personal grudge against Java and since Clojure requires Java I just find myself unable to go down that road]]
You get this for free in Haskell, and you also save on not having to remember useless terminology for something that has no application on their own outside Foldables anyways.
Transducers are IMHO one of the most under-appreciated features of Clojure. Once you get to know them, building transducer pipelines becomes second nature. Then you realize that a lot of data processing can be expressed as a pipeline of transformations, and you end up with reusable components that can be applied in any context.
The fact that transducers are fast (you don't incur the cost of handling intermediate data structures, nor the GC costs afterwards) is icing on the cake at this point.
Much of the code I write begins with (into ...).
And in Clojure, like with anything that has been added to the language, anything related to transducers is a first-class citizen, so you can reasonably expect library functions to have all the additional arities.
[but don't try to write stateful transducers until you feel really comfortable with the concepts, they are really tricky and hard to get right]
I never understood what was so special about Clojure's Transducers. Isn't it essentially just applying a transformation on the lambda applied to a fold?
I am a fan of Christophe Grand's xforms library -- https://github.com/cgrand/xforms -- I find the transducer nexus function, by-key, to be particularly useful for eliminating clojure.core destructuring dances when one needs group-by with post-processing.
I think the misunderstanding is about iterators "not relying on concrete types". Rather, iterators are the concrete type. Consider the example transformation from the transducers page:
(def xf
(comp
(filter odd?)
(map inc)
(take 5)))
You'll see there's no notion of a concrete type that the transformation operates on. It can work with vectors, seqs, core.async channels, etc. Now consider how that could be written in JavaScript such that it works on arrays, sets, generators, iterators, etc. without having to first convert to another type (such as an iterator). That is what's meant about transducers not being tied to a concrete type.
20 comments
[ 3.4 ms ] story [ 43.2 ms ] threadI know a lot of people find them confusing.
0: https://srfi.schemers.org/srfi-171/srfi-171.html
https://web.archive.org/web/20161219045343/https://clojure.o...
Demo One: Computation and Output format pulled apart
Demos two and three for your further entertainment are here: https://www.evalapply.org/posts/n-ways-to-fizzbuzz-in-clojur...(edit: fix formatting, and kill dangling paren)
While the mechanics of transducers are interesting the bottom line is they allow you to fuse functions and basic conditional logic together in such a way that you transform a collection exactly once instead of n times, meaning new allocation happens only once. Once you start using them you begin to see intermediate collections everywhere.
Of course, in any language you can theoretically do everything in one hyperoptimized loop; transducers get you this loop without much of a compromise on keeping your program broken into simple, composable parts where intent is very clear. In fact your code ends up looking nearly identical (especially once you learn about eductions… cough).
Note: I’m not the author of Injest, just a satisfied programmer.
Do you have any idea/guess why Injest hasn't been folded in to core? It seems a natural extension, so I worry if it has some hidden footgun
I tried to implement transducers in JavaScript using yield and generators and that worked. That was before async/await, but now you can just `await readdir("/"); I'm unclear as to whether transducers offer significant advantages over async/await?
[[Note: I have a personal grudge against Java and since Clojure requires Java I just find myself unable to go down that road]]
The fact that transducers are fast (you don't incur the cost of handling intermediate data structures, nor the GC costs afterwards) is icing on the cake at this point.
Much of the code I write begins with (into ...).
And in Clojure, like with anything that has been added to the language, anything related to transducers is a first-class citizen, so you can reasonably expect library functions to have all the additional arities.
[but don't try to write stateful transducers until you feel really comfortable with the concepts, they are really tricky and hard to get right]
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
both solve the copying problem, and not relying on concrete types
so it's more than all tranducable types implement a common interface?
or the tranduceable operators depend on a small subset of generic functions?
https://github.com/arximboldi/zug
An interesting application in cursors in Lager:
https://github.com/arximboldi/lager