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

41–50 of 103 posts

Re: Transducers are coming to Clojure

#41

Post by scythe »

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)?

It appears that the operator forms he's talking about are things like Select[EvenQ], which would become "transducers" if I could do something like:

even_selector = Select[EvenQ]

incrementor = Map[Inc]

decrementor = Map[Dec]

even_incremented_selector = incrementor * even_selector (????)

odd_selector = even_incremented_selector * decrementor

even_selector[{1,2,3,4,5,6,7}] => {2,4,6}

even_incremented_selector[{1,2,3,4,5,6,7}] => {2,4,6,8}

odd_selector[{1,2,3,4,5,6,7}] => {1,3,5,7}

However I'm not entirely sure I've understood things correctly, I just stared at it for a while and need to get back to work...

(edit: HN does _not_ like formatting)

Re: Transducers are coming to Clojure

#42

Post by jamii »

swannodette wrote: post #25
berdario wrote: post #21

Earlier quoted context omitted.

I'm not sure I grok this, but I think that the main points are: - reducers can work on tree structures, and thus can exploit parallelism. This would be like using a map that requires only the Foldable typeclass - In Haskell you have stream/vector fusion, but it's not obvious to know when ghc will actually exploit it, you might want to use something like Control.Monad.Stream or Data.Vector. In theory it might be gener…

Comparing transducers to stream fusion is far narrower than the scope of their applicability.

They are more comparable to Oleg's Enumerators (http://okmij.org/ftp/Haskell/Iteratee/describe.pdf), in that you compose a series of computations and then push data through them. The type signature is similar:

    type Iteratee el m a -- a processor of 'els' in the monad 'm' returning a type 'a'

    type Enumerator el m a = Iteratee el m a -> m (Iteratee el m a)
The Enumerators library is complicated by the presence of monads and by trying to automatically close handles when the stream is processed. In some ways it seems that the goal of solving the lazy IO problem led to missing a much simpler abstraction. Transducers seem to be simpler and more focused on just abstracting stream/map-reduce computation.

Re: Transducers are coming to Clojure

#43

Post by jamii »

taliesinb wrote: post #37
richhickey wrote: post #33

Earlier quoted context omitted.

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 rig…

So if I understand correctly, you would arrive at a symbolic expression like (->> (map f) (map g) x) and directly rewrite it to (->> (map (f . g)) x), rather than having to manipulate the resulting data-structures?

Re: Transducers are coming to Clojure

#44

Post by malisper »

swannodette wrote: post #32
unlogic wrote: post #29

Earlier quoted context omitted.

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.

You could just make them transducer-map, transducer-filter, etc.

There is no reason the exact same name should be used for two different things. It is a lot harder to tell the difference between (map inc) and (map inc xs) then it is to tell the difference between (transducer-map inc) and (map inc xs).

Re: Transducers are coming to Clojure

#45

Post by vbit »

I'm not quite sure what this means, so here's my attempt to translate this into Python. A reducer is a function such as `add`:

    def add(sum, num):
      return sum + num
Of course you can plug `add` directly in `reduce(add, [1, 2, 3], 0)` which gives `6`.

A transducer is an object returned by a call such as `map(lambda x: x + 1)`.

You can now apply the transducer to a reducer and get another reducer.

    map_inc = map(lambda x: x + 1)
    add_inc = map_inc(add)
Our first reducer simply added, but the next one increments and then adds. We can use it as `reduce(add_inc, [1, 2, 3], 0)` which gives, I'm guessing, `9`.

Since the transducer returns a reducer as well, we can compose transducers:

     r1 = filter(is_even)(map(increment)(add))
     # use r1 in reduce()
It seems in clojure, reduce() isn't the only useful function that works with reducers, there are others which makes this all worthwhile.

Is my translation accurate?

Re: Transducers are coming to Clojure

#46

Post by kenko »

swannodette wrote: post #27
unlogic wrote: post #20

This looks exciting, but I'm confused about the decision to add extra arity to collection-manipulating functions. "filter" that returns a collection or a transducer depending only on arity seems a little counter-intuitive.

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.

It seems very weird to me; it looks like currying (or partial application) but actually you're getting two fundamentally different things. Partially applying `map` to one argument with `partial` (or just doing `#(map f %)`) gets you one thing; non-partially applying map to one argument gets you something totally different.

Re: Transducers are coming to Clojure

#47

Post by [deleted] »

jamii wrote: post #43
taliesinb wrote: post #37

Earlier quoted context omitted.

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 rig…

So if I understand correctly, you would arrive at a symbolic expression like (->> (map f) (map g) x) and directly rewrite it to (->> (map (f . g)) x), rather than having to manipulate the resulting data-structures?

[deleted]

Re: Transducers are coming to Clojure

#48

Post by taliesinb »

jamii wrote: post #43
taliesinb wrote: post #37

Earlier quoted context omitted.

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 rig…

So if I understand correctly, you would arrive at a symbolic expression like (->> (map f) (map g) x) and directly rewrite it to (->> (map (f . g)) x), rather than having to manipulate the resulting data-structures?

Yeah, it's pretty easy to turn

    Map[#^2&] /* Select[PrimeQ] /* Select[OddQ]
into

    Select[OddQ[#] && PrimeQ[#]&] /* Map[#^2&]
and so on via rules that look like:

    Select[s1_] /* Select[s2_] :> Select[s1[#] && s2[#]&] 
    Map[f_ ? SideEffectFreeQ] /* s_Select :> s /* Map[f]
    Map[Extract[p_Integer | p_Key]] :> Extract[{All, p}]
I'm already doing a bunch of that for Dataset.

But in reality you need to move to a DSL for complex enough rules, and then Clojure and WL will be on the same footing (Clojure even a bit stronger, maybe, WL doesn't really have a proper macro system).

Does Clojure core do or allow for any of that kind of optimization already?

Re: Transducers are coming to Clojure

#49

Post by tel »

lmm wrote: post #35
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?

No, it's kind of a universal construction though, but not in any way more special than regular lists are.

Re: Transducers are coming to Clojure

#50

Post by taliesinb »

scythe wrote: post #41
richhickey wrote: post #33

Earlier quoted context omitted.

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)?

It appears that the operator forms he's talking about are things like Select[EvenQ], which would become "transducers" if I could do something like: even_selector = Select[EvenQ] incrementor = Map[Inc] decrementor = Map[Dec] even_incremented_selector = incrementor * even_selector (????) odd_selector = even_incremented_selector * decrementor even_selector[{1,2,3,4,5,6,7}] => {2,4,6} even_incremented_selector[{1,2,3,4,5…

No, because all that is required for operator forms to do what you write is just ordinary function application. Which they already do just fine.

Rich is talking about something deeper, in which operators like filter become transformers that themselves operate on stateful processors (reducers) to produce new stateful processors that have incorporated the action described by the original operator.

Post reply on HN