6 ms·

Clojure's Transducers are as fundamental as function composition

92 points by ithayer 12y ago

moomin 12y ago
If you ignore the arities, ignore the internal state, and correctly observe the unwritten rules, yes transducers act like function composition. I looked into this here: http://www.colourcoding.net/blog/archive/2014/08/16/lets-write-a-transducer.aspx http://www.colourcoding.net/blog/archive/2014/08/16/lets-wri... I think Rich's innovation here is extremely clever and quite subtle, but it's pretty Clojure-specific, both in terms of the problem it solves and the way it solves it.
- lkrubner 12y ago
  The overall pattern of map-reduce is possible in most languages, certainly any language that has closures. And the idea of composing multiple reducing functions together is something that comes up in many languages. If a language does not have closures, you could do something similar in any language by walking an accumulating object through multiple loops, but that is awkward and ugly. But you could certainly do something like this in Javascript, through the clever use of multiple closures, composing the closures together. But transducers formalize this as an idiomatic part of Clojure.
  - Tuna-Fish 12y ago
    In languages with more leeway on execution order, this problem can be made to go away. For example, Haskell's stream fusion combines back-to-back calls to list processing functions into a single iteration over the list.
    - seanmcdirmid 12y ago
      Lazy evaluation can also be encoded fairly easily in strict languages using constructs like lazy stream abstractions.
      - jeremyjh 12y ago
        Uh, sure but does any other language have a compiler that actually implements stream fusion?
        DanWaterworth 12y ago
        I don't believe GHC actually does implement stream fusion. I think stream fusion happens with rewrite rules.
        riffraff 12y ago
        pardon my ignorance, but what would be the difference between the two? Don't rewrite rules happen in GCH anyway?
        DanWaterworth 12y ago
        Sorry, I should have been clearer. The rewriting happens in GHC, but it's the application programmer who creates the rules. So, stream fusion isn't implemented by the compiler AFAIK.
        riffraff 12y ago
        ah that makes sense, thanks.
        gazarsgo 12y ago
        Not in the compiler, but enjoy a Microsoft Research paper about Steno, a C# library that claims to be superior to stream fusion (section 8.2): http://research.microsoft.com/pubs/173946/paper-pldi.pdf http://research.microsoft.com/pubs/173946/paper-pldi.pdf In case anyone is unaware, LINQ lets you represent queries as a series of function calls which it represents as a series of Expression objects and an in-memory AST.
        seanmcdirmid 12y ago
  - moomin 12y ago
    The thing is, it's something of a redefinition of what idiomatic clojure is. Overloading arity to do radically different things isn't idiomatic Clojure, but transducers do it at two levels. Equally, functions are expected to do explicit state passing e.g. old school drop, rather than implicit state e.g transducer drop.
- kazinator 12y ago
  What's clever is recognizing the "kernel" of a function like map. Hickey answers the question: if we take this list-processing/decimating function like "count-if" or "map" or whatever, and express it with reduce, what is that reducer function which we will need? And how is that reducer derived from or related to the function that goes into the list processing function, like the mapping function in map? He then makes those functions behave as methods (when called with one less argument) which give you that reducer. Now what if this is done to reduce itself? What should a reduced arity (reduce fun) return? I think that is a noop: nothing needs to be done to fun to make it reduce under reduce, so (reduce fun) -> fun. I.e. to transduce the reducer "fun", an arbitrary function, into a function X such that (reduce X list) will do the job of (reduce fun list), we simply equate X with fun.
tel 12y ago
What does "as fundamental as function composition" mean here? The article just appears to describe transducers. Transducers compose via ("reverse") function composition, sure, but that just means that they are functions of a type... and considerably less fundamental than functions since they're a specialization of that class of things. They're cool and all—I've characterized them (partially, perhaps) as CPS encoded flatmaps over lists and also as stateful left fold transformers, the latter of which being much more general—but they're more like a rich ecosystem for list transformations than any kind of fundamental abstraction.
- kazinator 12y ago
  I think "as fundamental as function composition" means that the relationship between a function like map and a transducer (map f) is fundamental in some sense that resembles function composition. But it isn't composition: it's something that "wrangles" the "reduce kernel" out of the combination of map and f: when we map something using f, what function instead of f will do the same mapping under reduce? That function inherits logic from map, and from f, but it's not a composition of the two.
  - moomin 12y ago
    I think what the author ultimately means is "well behaved transducers are equivalent to functions of the form a->[b] (modulo state) and therefore form a category". True story: the transducer announcement has mostly made me read up on the Haskell fold and lens libraries...
    - tel 12y ago
      If you think of Transducers as type Transducer a b = forall r . (b -> r -> r) -> (a -> r -> r) (And I'm not claiming this is correct) then you can reasonably easily show that this is isomorphic to (a -> [b]) forall r . (b -> r -> r) -> (a -> r -> r) forall r . (r -> b -> r) -> (r -> a -> r) a -> (forall r . (r -> b -> r) -> r -> r) [non-obvious, but true] a -> [b] This is "obviously" the Kleisli category for [] so you get rich, rich structure here. If you want to include local state such as what's needed to implement `take` then you can do something like data Fold i o where Fold :: (i -> x -> x) -> x -> (x -> o) -> Fold i o type Transducer a b = forall r . Fold b r -> Fold a r If you're familiar with pure profunctor lenses then I can tell you that Fold is a Profunctor and thus these can be acted on by a lot of generalized lens combinators. This explains a lot of the richness.
dschiptsov 12y ago
Subset of high-order functions are more fundamental than operations defined for a whole set?) Clojure's are more fundamental than other languages?
dons 12y ago
Title shows author doesn't understand programming language design. No, a small set of higher-order functions[1] is not as fundamental as the concept of higher-order functions in the first place. [1]: http://www.reddit.com/r/haskell/comments/2cv6l4/clojures_transducers_are_perverse_lenses/cjjgbbs?context=3 http://www.reddit.com/r/haskell/comments/2cv6l4/clojures_tra...
- ithayer 12y ago
  Author here, thanks for the comment -- since that seemed to have been lost, I'm using "fundamental" because transducers let you describe your logic so that it that can be applied over sequences and non-sequences in a way that you cannot by just applying composed logic functions through existing clojure machinery. EDIT: s/composed functions/composed logic functions/
rebcabin 12y ago
In addition to map transducers (which are 1-to-1) and filter transducers (which are many-to-1), flatMap transducers (which are 1-to-many) should be fundamental.
- tel 12y ago
  flatMap is the fundamental transducer (of a particular model). To be clear, the function a -> [b] subsumes mapping and filtering---if [b] is always a single element then a -> [b] is a map, if [b] is always either 0-or-1 elements then a -> [b] is a filter (possibly adjoined to a map).
anon4 12y ago
What is the difference (or what is gained) from transducing a reducer over mapping (filtering, etc) a list and reducing it? Is it a clojure-specific optimisation?
- tel 12y ago
  It avoids intermediate structure and enables more sources and sinks to work. For instance, if you build a reducer, you're basically adjoining a "reducible" and a "reduction function" and then transforming the reducer by transforming that reduction function. This already avoids the creation of intermediate structure since you just keep transforming the reduction function, but you have this sort of useless "reducible" thing attached. Mostly, the trouble is that you were afflicted by the kingdom of nouns---you don't really need a structure to think of first class objects. Instead, you can just consider the various ways of transforming reduction functions. They all compose as (reverse) functions (you can see them as a category) and you can take your resultant "transducer" and apply it to a source and sink structure to map out of the source and into the sink.
deleted 12y ago
[deleted]

92 points by ithayer 12y ago

If you ignore the arities, ignore the internal state, and correctly observe the unwritten rules, yes transducers act like function composition. I looked into this here: http://www.colourcoding.net/blog/archive/2014/08/16/lets-write-a-transducer.aspx http://www.colourcoding.net/blog/archive/2014/08/16/lets-wri... I think Rich's innovation here is extremely clever and quite subtle, but it's pretty Clojure-specific, both in terms of the problem it solves and the way it solves it.

lkrubner 12y ago
The overall pattern of map-reduce is possible in most languages, certainly any language that has closures. And the idea of composing multiple reducing functions together is something that comes up in many languages. If a language does not have closures, you could do something similar in any language by walking an accumulating object through multiple loops, but that is awkward and ugly. But you could certainly do something like this in Javascript, through the clever use of multiple closures, composing the closures together. But transducers formalize this as an idiomatic part of Clojure.
- Tuna-Fish 12y ago
  In languages with more leeway on execution order, this problem can be made to go away. For example, Haskell's stream fusion combines back-to-back calls to list processing functions into a single iteration over the list.
  - seanmcdirmid 12y ago
    Lazy evaluation can also be encoded fairly easily in strict languages using constructs like lazy stream abstractions.
    - jeremyjh 12y ago
      Uh, sure but does any other language have a compiler that actually implements stream fusion?
      - DanWaterworth 12y ago
        I don't believe GHC actually does implement stream fusion. I think stream fusion happens with rewrite rules.
        riffraff 12y ago
        pardon my ignorance, but what would be the difference between the two? Don't rewrite rules happen in GCH anyway?
        DanWaterworth 12y ago
        Sorry, I should have been clearer. The rewriting happens in GHC, but it's the application programmer who creates the rules. So, stream fusion isn't implemented by the compiler AFAIK.
        riffraff 12y ago
        ah that makes sense, thanks.
      - gazarsgo 12y ago
        Not in the compiler, but enjoy a Microsoft Research paper about Steno, a C# library that claims to be superior to stream fusion (section 8.2): http://research.microsoft.com/pubs/173946/paper-pldi.pdf http://research.microsoft.com/pubs/173946/paper-pldi.pdf In case anyone is unaware, LINQ lets you represent queries as a series of function calls which it represents as a series of Expression objects and an in-memory AST.
        seanmcdirmid 12y ago
- moomin 12y ago
  The thing is, it's something of a redefinition of what idiomatic clojure is. Overloading arity to do radically different things isn't idiomatic Clojure, but transducers do it at two levels. Equally, functions are expected to do explicit state passing e.g. old school drop, rather than implicit state e.g transducer drop.
kazinator 12y ago
What's clever is recognizing the "kernel" of a function like map. Hickey answers the question: if we take this list-processing/decimating function like "count-if" or "map" or whatever, and express it with reduce, what is that reducer function which we will need? And how is that reducer derived from or related to the function that goes into the list processing function, like the mapping function in map? He then makes those functions behave as methods (when called with one less argument) which give you that reducer. Now what if this is done to reduce itself? What should a reduced arity (reduce fun) return? I think that is a noop: nothing needs to be done to fun to make it reduce under reduce, so (reduce fun) -> fun. I.e. to transduce the reducer "fun", an arbitrary function, into a function X such that (reduce X list) will do the job of (reduce fun list), we simply equate X with fun.

tel 12y ago

What does "as fundamental as function composition" mean here? The article just appears to describe transducers. Transducers compose via ("reverse") function composition, sure, but that just means that they are functions of a type... and considerably less fundamental than functions since they're a specialization of that class of things. They're cool and all—I've characterized them (partially, perhaps) as CPS encoded flatmaps over lists and also as stateful left fold transformers, the latter of which being much more general—but they're more like a rich ecosystem for list transformations than any kind of fundamental abstraction.

kazinator 12y ago
I think "as fundamental as function composition" means that the relationship between a function like map and a transducer (map f) is fundamental in some sense that resembles function composition. But it isn't composition: it's something that "wrangles" the "reduce kernel" out of the combination of map and f: when we map something using f, what function instead of f will do the same mapping under reduce? That function inherits logic from map, and from f, but it's not a composition of the two.
- moomin 12y ago
  I think what the author ultimately means is "well behaved transducers are equivalent to functions of the form a->[b] (modulo state) and therefore form a category". True story: the transducer announcement has mostly made me read up on the Haskell fold and lens libraries...
  - tel 12y ago
    If you think of Transducers as type Transducer a b = forall r . (b -> r -> r) -> (a -> r -> r) (And I'm not claiming this is correct) then you can reasonably easily show that this is isomorphic to (a -> [b]) forall r . (b -> r -> r) -> (a -> r -> r) forall r . (r -> b -> r) -> (r -> a -> r) a -> (forall r . (r -> b -> r) -> r -> r) [non-obvious, but true] a -> [b] This is "obviously" the Kleisli category for [] so you get rich, rich structure here. If you want to include local state such as what's needed to implement `take` then you can do something like data Fold i o where Fold :: (i -> x -> x) -> x -> (x -> o) -> Fold i o type Transducer a b = forall r . Fold b r -> Fold a r If you're familiar with pure profunctor lenses then I can tell you that Fold is a Profunctor and thus these can be acted on by a lot of generalized lens combinators. This explains a lot of the richness.

dschiptsov 12y ago

Subset of high-order functions are more fundamental than operations defined for a whole set?) Clojure's are more fundamental than other languages?

dons 12y ago

Title shows author doesn't understand programming language design. No, a small set of higher-order functions[1] is not as fundamental as the concept of higher-order functions in the first place. [1]: http://www.reddit.com/r/haskell/comments/2cv6l4/clojures_transducers_are_perverse_lenses/cjjgbbs?context=3 http://www.reddit.com/r/haskell/comments/2cv6l4/clojures_tra...

ithayer 12y ago
Author here, thanks for the comment -- since that seemed to have been lost, I'm using "fundamental" because transducers let you describe your logic so that it that can be applied over sequences and non-sequences in a way that you cannot by just applying composed logic functions through existing clojure machinery. EDIT: s/composed functions/composed logic functions/

rebcabin 12y ago

In addition to map transducers (which are 1-to-1) and filter transducers (which are many-to-1), flatMap transducers (which are 1-to-many) should be fundamental.

tel 12y ago
flatMap is the fundamental transducer (of a particular model). To be clear, the function a -> [b] subsumes mapping and filtering---if [b] is always a single element then a -> [b] is a map, if [b] is always either 0-or-1 elements then a -> [b] is a filter (possibly adjoined to a map).

anon4 12y ago

What is the difference (or what is gained) from transducing a reducer over mapping (filtering, etc) a list and reducing it? Is it a clojure-specific optimisation?

tel 12y ago
It avoids intermediate structure and enables more sources and sinks to work. For instance, if you build a reducer, you're basically adjoining a "reducible" and a "reduction function" and then transforming the reducer by transforming that reduction function. This already avoids the creation of intermediate structure since you just keep transforming the reduction function, but you have this sort of useless "reducible" thing attached. Mostly, the trouble is that you were afflicted by the kingdom of nouns---you don't really need a structure to think of first class objects. Instead, you can just consider the various ways of transforming reduction functions. They all compose as (reverse) functions (you can see them as a category) and you can take your resultant "transducer" and apply it to a source and sink structure to map out of the source and into the sink.

deleted 12y ago

[deleted]