Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Transducers are coming to Clojure

blog.cognitect.com

Post reply on HN
Print view View original

31–40 of 103 posts

Re: Transducers are coming to Clojure

#31

Post by zem »

richhickey wrote: post #16
graycat wrote: post #15

I'm sorry, but from the OP I can't be at all sure I can understand notation such as: ;;reducing function signature whatever, input -> whatever or ;;transducer signature (whatever, input -> whatever) -> (whatever, input -> whatever) Or, in mathematics there is some notation f: A --> B where A and B are sets and f is a function. This notation means that for each element x in set A, function f returns value f(x) in set…

a la Haskell: ;;reducing fn x->a->x ;;transducer fn (x->a->x)->(x->b->x)

or, to steal ashley yakeley's marvellous quip, "every sufficiently well-documented lisp program contains an ML program in its comments" (:

Re: Transducers are coming to Clojure

#32

Post by swannodette »

unlogic wrote: post #29
swannodette wrote: post #27

Earlier quoted context omitted.

It's a pretty well considered tradeoff in my opinion - no existing code breaks while at the same time all the transformation functions now have the same semantic interpretation when used in different contexts. The alternative would be to replicate the notion of `map`, `filter`, etc. again and again as occurred with reducers and higher level core.async operations on channels.

My argument is why not making it look like: (comp (transducer map inc) (transducer filter even?)) Of course, it's more typing and doesn't look as nice as single-arity map, but it goes along quite well with (partial map inc). I can be wrong but to this date Clojure didn't have a function that produces completely different things based on arity, did it?

Not sure how what you're suggesting could possibly work unless transducer has a table of fn to transducer - this doesn't sound like a good idea. I recommend looking at the implementations which have landed in Clojure master to see what I'm talking about.

Re: Transducers are coming to Clojure

#33

Post by richhickey »

taliesinb wrote: post #30
swannodette wrote: post #27

Earlier quoted context omitted.

It's a pretty well considered tradeoff in my opinion - no existing code breaks while at the same time all the transformation functions now have the same semantic interpretation when used in different contexts. The alternative would be to replicate the notion of `map`, `filter`, etc. again and again as occurred with reducers and higher level core.async operations on channels.

We just did exactly the same thing in the Wolfram Language, for similar reasons (we called these things "operator forms" rather than "transducers") [0] One major side effect has been to mitigate the kinds of heavy nesting you see in functional languages like WL and Clojure. Personally I think the resulting code resembles the phrase structure of English much more closely. It's a huge readability win. The original moti…

I'm not seeing anything that looks like a reducing function transformer there. That all looks like variants of ordinary function composition, currying and partial application. Is there someplace that shows 'operator forms' acting as functions with this signature: (x->a->x)->(x->a->x)?

Re: Transducers are coming to Clojure

#34

Post by nohat00 »

> "these transformers were never exposed a la carte, instead being encapsulated by the macrology of reducers."

What does 'macrology' mean in this context? Is this a common usage? Or a novel application of a word that ordinarily means "long and tedious talk without much substance"

Re: Transducers are coming to Clojure

#35

Post by lmm »

tel wrote: post #13

This sort of reminds me of the Church-encoded form of a list. newtype Fold a = Fold (forall r . (a -> r -> r) -> r -> r) fold :: [a] -> Fold a fold xs = Fold (spin xs) where spin [] cons nil = nil spin (a:as) cons nil = cons a (spin as cons nil) refold :: Fold a -> [a] refold (Fold f) = f (:) [] Notably, since `fold` and `refold` are isomorphisms then we can do everything we can do to `[a]` to `Fold a` map :: (a -> b…

So is this actually just the Free monad?

Re: Transducers are coming to Clojure

#36

Post by prospero »

nohat00 wrote: post #34

> "these transformers were never exposed a la carte, instead being encapsulated by the macrology of reducers." What does 'macrology' mean in this context? Is this a common usage? Or a novel application of a word that ordinarily means "long and tedious talk without much substance"

It means that reducers were some macro sugar atop the underlying mechanism described in the post. See https://github.com/clojure/clojure/blob/master/src/clj/cloju...

Re: Transducers are coming to Clojure

#37

Post by taliesinb »

richhickey wrote: post #33
taliesinb wrote: post #30

Earlier quoted context omitted.

We just did exactly the same thing in the Wolfram Language, for similar reasons (we called these things "operator forms" rather than "transducers") [0] One major side effect has been to mitigate the kinds of heavy nesting you see in functional languages like WL and Clojure. Personally I think the resulting code resembles the phrase structure of English much more closely. It's a huge readability win. The original moti…

I'm not seeing anything that looks like a reducing function transformer there. That all looks like variants of ordinary function composition, currying and partial application. Is there someplace that shows 'operator forms' acting as functions with this signature: (x->a->x)->(x->a->x)?

WL doesn't yet have a laziness/streaming/reducing framework, but the prototype we're working on uses 'operator forms' like Select, Map, GroupBy and so on in the way you describe.

I don't think the exact details are the same, because our operators don't actually evaluate to transformers (they remain totally symbolic). Rather, the conversion of composed operators to an actual reducer pipeline happens lazily 'at the right time', which I think will make optimization a bit easier to express.

Re: Transducers are coming to Clojure

#38

Post by graycat »

ww520 wrote: post #18
graycat wrote: post #15

I'm sorry, but from the OP I can't be at all sure I can understand notation such as: ;;reducing function signature whatever, input -> whatever or ;;transducer signature (whatever, input -> whatever) -> (whatever, input -> whatever) Or, in mathematics there is some notation f: A --> B where A and B are sets and f is a function. This notation means that for each element x in set A, function f returns value f(x) in set…

It's not a formal notation. It's talking about a pattern in function signature. The function takes in some parameters (whatever, input) and spits out an output ( -> whatever ). The "reducing function signature" basically is just the function signature of a "reducer" (or "fold") function in the map/reduce (or map/fold) pattern. The "whatever" is kind of sloppy and confusing. It's the accumulating memo parameter of a r…

Thanks. I just looked up "map/reduce" on Wikipedia. Gee, I've been speaking 'prose' (an old joke) all along!

So, I was procrastinating from working on my code, and there I have some data base data split, for some positive integer n, into n 'partitions'. The intention, later, is to use n servers, one server for one partition.

Then I have some data X to be 'applied' to all the data in all the partitions, and from each partition I get back some data, say, for partition i = 1, 2, ..., n, from partition i I get back data Y(i). Then I combine all the data Y(i) to get my final results Z that I really want.

I've programmed the communications, etc., but it looks like I've just reinvented the wheel, i.e., map/reduce. Looks like a library of good map/reduce software could save me from programming the low level details (serialize to an array of byte an instance of a class and send the array via TCP/IP sockets) and also get some fault tolerance. Sounds good. So, I reinvented the 'pattern'.

For the OP, I'm not so clear on how in most compiled languages the 'transducer' could work; that is, it sounds like the programming language would need some means of 'reflection', 'entry variables', 'delegates', dynamically written, compiled, and linked code, interpretative code, or some such. There, 'static analysis' of 'dynamic code' seems a bit clumsy!

Re: Transducers are coming to Clojure

#39

Post by nohat00 »

prospero wrote: post #36
nohat00 wrote: post #34

> "these transformers were never exposed a la carte, instead being encapsulated by the macrology of reducers." What does 'macrology' mean in this context? Is this a common usage? Or a novel application of a word that ordinarily means "long and tedious talk without much substance"

It means that reducers were some macro sugar atop the underlying mechanism described in the post. See https://github.com/clojure/clojure/blob/master/src/clj/cloju...

... so 'macrology' means "use of macros" rather than "long and tedious talk without much substance"? Is this usage specific to Clojure, or to all languages that have macros? It seems like a pretty bizarre repurposing of a word that already has a very different meaning, and I wonder how widespread it is. Are we too late to stop it?

Re: Transducers are coming to Clojure

#40

Post by dragonwriter »

richhickey wrote: post #9
dustingetz wrote: post #7

Earlier quoted context omitted.

> This is a way to unify all these abstractions so that you can write a single map/filter/concat transform once, and use it in many different ways. I don't understand why these things aren't all unified in the first place, it's just function composition we're talking about here right? Edit: I mean it's clearly not just simple function composition, but I don't understand why not (def xform (comp (map inc) (filter even…

Your typical definition of map, filter etc includes concrete usage of e.g. lists. These don't. Transducers are not just currying or partial application of the map function over lists, they isolate the logic of map, filter etc from lists or any particular context, allowing them to be used in very different (e.g. non-collection) contexts.

> they isolate the logic of map, filter etc from lists or any particular context

Is it correct to say that the relationship between the new forms of map/filter/etc, reduction functions, and transducers is something like this:

"traditional" (map f l) is equivalent to (foldl (mapR f) l []), where (mapR f) is the "reduction function" corresponding to map. (mapR would still be list specific)

the new (map f) is a transducer that takes a reduction function and returns another reduction function; given idR, the "identity reduction function" for foldl such that (foldl idR l []) = l, ((map f) idR) = mapR.

Furthermore, given reduction functions mapRR such that (foldr (mapRR f) l []) == (map f l) and idRR such that (foldr idRR l []) = l, then ((map f) idRR) = mapRR. (Because all the list-specific things in the output reduction function come from the input reduction function, the transducer (map f) doesn't need to know anything about lists, so can be used in other contexts as well -- one minor-but-perhaps-easier-to-illustrate aspect of that is, even when used with lists, (map f) is independent of the folding direction, unlike the reduction functions mapR and mapRR.)

(I know this is barely even scratching the surface of the applications, but I'm trying to confirm that I've got the concept right.)

Post reply on HN