5 ms·

Clojure transducers from the ground up: using them in practice

79 points by ghosthamlet 9y ago

ssttoo 9y ago
Reducing the font size (CMD -, CMD -) helps immensely :)
ulber 9y ago
Transducers are also familiar from automata theory. There’s a recent line of research into automata and transducers with symbolic representations for transitions. I’ve studied using them to apply fusion to pipelines of stream transformations [1]. Here’s talk I have for a related paper [2] and this talk by Loris d’Antoni gives a general overview of symbolic automata and transducers [3]. In a few weeks I’ll have a talk up that summarizes the last three papers I have on the subject. [1] http://dx.doi.org/10.1145/3062341.3062362 http://dx.doi.org/10.1145/3062341.3062362 [2] https://youtu.be/0IL60qJEKLU https://youtu.be/0IL60qJEKLU [3] https://youtu.be/ca9IF-7nSOA https://youtu.be/ca9IF-7nSOA
deleted 9y ago
[deleted]
exikyut 9y ago
This is not related to electrical transducers, which (without any additional scoping context) was what I thought this article was about. Relabeling it "Clojure transducers" would help the title in every way. But it's been up for 7 hours now, so we'll see if it changes.
- ulber 9y ago
  Transducer is the standard term inside CS for this model of computation [1]. Often there are some disambiguating terms, such as finite-state transducer, but this article does not limit itself to any particular kind. Of course Hacker News has content from both fields so the overloading of the term is unfortunate. [1] https://en.m.wikipedia.org/wiki/Finite-state_transducer https://en.m.wikipedia.org/wiki/Finite-state_transducer
  - moomin 9y ago
    Transducers don’t really directly map to any existing CS construct. In fact, Clojure transducers occupy a strange twilight world between “fold endomorphism” and “stream transformer”. Most transducers are both. Some are just one or the other.
    - deleted 9y ago
      [deleted]
todd8 9y ago
The domain (uswitch.com) along with the word "Transducers" really threw me off. It's about clojure not electricity!
- reborg 9y ago
  Ops, didn't think about that! Added Clojure to the title. Thanks for raising. (author here).
BoiledCabbage 9y ago
From reading this it seems like clojure transducers are the same thing as linq expressions over IEnumerable. Is there any additional functionality they provide?
- weavejester 9y ago
  Transducers aren't coupled to a particular output type, so they can be used in things like asynchronous streams. IEnumerable is more analogous to Clojure's seq abstraction. Transducers have less overhead and are more flexible.
- LambdaWizard 9y ago
  I don't know much about linq expressions, but I can offer you some properties of transducers and you can decide for yourself. When you initialize any transducer it works on all transducer accepting data types. Making a new data type accept transducers is trivially easy and once you do it once, your data type has access to all transducers. Transducers are orthogonally composable to all other transducers so stringing several up and taking them apart is also trivially easy. Transducers do not create intermediate collections during the process. I believe none of these are particularly anything new. Possibly the orthogonality is something new as you don't find composability quite like Clojure in many other languages as it's at the heart of the language design philosophy.
- arijun 9y ago
  One thing I believe is not possible with linq is you can pass a transducer to a function (since a transducer is just another function), which can then insert it into a pre-existing chain of transductions.
  - Veedrac 9y ago
    The analogue of a transducer is an iterator transformation, aka. something like `IEnumerator → IEnumerator`, which is also just a function.
- phaedrus 9y ago
  I believe there are two fundamental differences between transducers and LINQ/IEnumerable. First, IEnumerable only abstracts "where" input is demanded from, but it doesn't abstract "when" or "who" initiates it. For example, consider the difficulty of producing one LINQ expression which can be used either in "pull mode" (ask the expression as a whole for items) or "push mode" (tell the expression to react to an item of a specific input stream). Or consider the difficulty of writing a LINQ primitive "Zip(a,b)" that is flexible with respect to the details of its usage may actually require all of "a" be read+cached before combining with "b", or perhaps where "a" and "b" are actually the same stream, or else they're independent and you really can just read each one alternating. Now imagine doing so without knowing in advance which case it will be and without using if-statements or some other kind of dispatching based on situation. If I understand transducers right (which I may not) I believe that they allow writing code that is agnostic of such details, in a way which LINQ/IEnumerable do not. The second difference is that transducers make the concept of a fold (collapsing many values into one value) an inherent part of the design, as opposed to LINQ which treats such operations as extension methods built on top of IEnumerable, i.e. as things you do to an IEnumerable rather than being a feature of IEnumerable. E.g. .Aggregate(), .First(), etc. IMO that's an area LINQ gets wrong, as it makes it awkward to deal with single-item cases; you have to choose between enumerations with one item, or extracting the item. Besides the fact that that could fail if the sequence is empty, it also means that LINQ is not algebraically closed under all of it operations. The two issues combined lead to certain ways that LINQ, much as I like it, is not always as good as it could be. For instance recently I had a problem of matching controls on a windows dialog up to a list of expected controls from a database, with a fuzzy match of +/- 2 pixels on each rectangle side, and produce four lists: 1-1 matches, ambiguous matches, missing left, missing right. I can express very clearly what I want, declaratively (in fact, I just did - in an ideal object query language that sentence would have almost a direct translation). However as a LINQ query it gets very messy. Since it's a fuzzy match, I can't simply equi-join the two lists. (Note that the match predicate is not transitive; |A-B|<=2 and |B-C|<=2 does not imply |A-C|<=2.) Since there's 4 dimensions being compared, I can't use just a single sort. On the other hand if the distance in any one dimension is greater than 2, there's no point in comparing the other 3. But I don't want to do N^2 comparisons, either. So I go with a solution which produces candidate matches on each dimension and joins the two lists. Since LINQ only supports equijoin, and I don't feel like writing an sort-intersect primitive, I just lazily generate all five integers +/-2 of the real value. At least it is 5+5+5+5 rather than 5 * 5 * 5 * 5, because the dimensions are joined on separately not as a tuple. Then I do a group-by using the object itself as the group key, and discard groups which don't match at least once in all four dimensions. I have to do extra work after that to discover ambiguous and missing matches. Maybe not the best way, but the best compromise I could come up with between optimality, readability, and development time. But notice how many non-essential details I had to think about! The core task that my LINQ expression is doing is only a small part of all the expanding, joining, grouping, and extracting that I had to do. Even if I couldn't just hand the problem off and let the computer figure out to do all this (which I would like to be able to do), just being able to separate the essential and accidental parts of this query would be helpful. True, I got in the situation because I didn't want to accept the O(N^2) brute force option doing a filter on the cross product. However note that LINQ also didn't do anything for insulating my essential query code from the strategy used to collate the data; instead it mixes them together. I'm still learning about transducers, but my hope is that they will someday allow better separation of concerns than LINQ/IEnumerable by itself.
yomly 9y ago
This is a small point, but to the author: in your first part of the article[0], binding the function argument to f in map, and then binding the head of the collection in filter was a bit confusing when scanning through...
- reborg 9y ago
  Happy to review the code, but I'm having trouble understand which snippet you're referring to.
twic 9y ago
So are transducers basically this Java, but in Clojure: https://gist.github.com/tomwhoiscontrary/e41d52e9c98a706552be66f8a5f2fc17 https://gist.github.com/tomwhoiscontrary/e41d52e9c98a706552b... ? I've done that in terms of Consumer, but it might also be possible, and perhaps more elegant, in terms of flat-mapping functions (Function<T, Stream<T>>). If i've understood right, then from a Java point of view, transducers are an attempt to reify the various operations on streams - mapping, filtering, etc. To do that, you have to figure out a type which is general enough to model all those operations. The need for a general type is where you get the perilously-close-to-general-abstract-nonsense "a transducer is a transformation from one reducing function to another". Here, "a reducing function" is what stands in, in a very oblique way, for the stream - it's ultimately a conduit for values, and transducers take some existing conduit, wrap another layer of processing round it, and give you the resulting conduit. So they're a bit like backward streams, i suppose. If anything, it's like how you go around wrapping up layers of OutputStreams when doing IO: new PrintStream(new BufferedOutputStream(new GZIPOutputStream(new CipherOutputStream(new FileOutputStream("file.dat"), cipher)))); Except instead of explicitly constructing wrappers, transducers know how to do the wrapping.
- phaedrus 9y ago
  I thought that transducers also abstracted away the difference between an input stream and an output stream? (Or the difference between pulling values on demand versus pushing values.)

79 points by ghosthamlet 9y ago

Reducing the font size (CMD -, CMD -) helps immensely :)

Transducers are also familiar from automata theory. There’s a recent line of research into automata and transducers with symbolic representations for transitions. I’ve studied using them to apply fusion to pipelines of stream transformations [1]. Here’s talk I have for a related paper [2] and this talk by Loris d’Antoni gives a general overview of symbolic automata and transducers [3]. In a few weeks I’ll have a talk up that summarizes the last three papers I have on the subject. [1] http://dx.doi.org/10.1145/3062341.3062362 http://dx.doi.org/10.1145/3062341.3062362 [2] https://youtu.be/0IL60qJEKLU https://youtu.be/0IL60qJEKLU [3] https://youtu.be/ca9IF-7nSOA https://youtu.be/ca9IF-7nSOA

deleted 9y ago

[deleted]

exikyut 9y ago

This is not related to electrical transducers, which (without any additional scoping context) was what I thought this article was about. Relabeling it "Clojure transducers" would help the title in every way. But it's been up for 7 hours now, so we'll see if it changes.

ulber 9y ago
Transducer is the standard term inside CS for this model of computation [1]. Often there are some disambiguating terms, such as finite-state transducer, but this article does not limit itself to any particular kind. Of course Hacker News has content from both fields so the overloading of the term is unfortunate. [1] https://en.m.wikipedia.org/wiki/Finite-state_transducer https://en.m.wikipedia.org/wiki/Finite-state_transducer
- moomin 9y ago
  Transducers don’t really directly map to any existing CS construct. In fact, Clojure transducers occupy a strange twilight world between “fold endomorphism” and “stream transformer”. Most transducers are both. Some are just one or the other.
  - deleted 9y ago
    [deleted]

todd8 9y ago

The domain (uswitch.com) along with the word "Transducers" really threw me off. It's about clojure not electricity!

reborg 9y ago
Ops, didn't think about that! Added Clojure to the title. Thanks for raising. (author here).

BoiledCabbage 9y ago

From reading this it seems like clojure transducers are the same thing as linq expressions over IEnumerable. Is there any additional functionality they provide?

weavejester 9y ago
Transducers aren't coupled to a particular output type, so they can be used in things like asynchronous streams. IEnumerable is more analogous to Clojure's seq abstraction. Transducers have less overhead and are more flexible.
LambdaWizard 9y ago
I don't know much about linq expressions, but I can offer you some properties of transducers and you can decide for yourself. When you initialize any transducer it works on all transducer accepting data types. Making a new data type accept transducers is trivially easy and once you do it once, your data type has access to all transducers. Transducers are orthogonally composable to all other transducers so stringing several up and taking them apart is also trivially easy. Transducers do not create intermediate collections during the process. I believe none of these are particularly anything new. Possibly the orthogonality is something new as you don't find composability quite like Clojure in many other languages as it's at the heart of the language design philosophy.
arijun 9y ago
One thing I believe is not possible with linq is you can pass a transducer to a function (since a transducer is just another function), which can then insert it into a pre-existing chain of transductions.
- Veedrac 9y ago
  The analogue of a transducer is an iterator transformation, aka. something like `IEnumerator → IEnumerator`, which is also just a function.
phaedrus 9y ago
I believe there are two fundamental differences between transducers and LINQ/IEnumerable. First, IEnumerable only abstracts "where" input is demanded from, but it doesn't abstract "when" or "who" initiates it. For example, consider the difficulty of producing one LINQ expression which can be used either in "pull mode" (ask the expression as a whole for items) or "push mode" (tell the expression to react to an item of a specific input stream). Or consider the difficulty of writing a LINQ primitive "Zip(a,b)" that is flexible with respect to the details of its usage may actually require all of "a" be read+cached before combining with "b", or perhaps where "a" and "b" are actually the same stream, or else they're independent and you really can just read each one alternating. Now imagine doing so without knowing in advance which case it will be and without using if-statements or some other kind of dispatching based on situation. If I understand transducers right (which I may not) I believe that they allow writing code that is agnostic of such details, in a way which LINQ/IEnumerable do not. The second difference is that transducers make the concept of a fold (collapsing many values into one value) an inherent part of the design, as opposed to LINQ which treats such operations as extension methods built on top of IEnumerable, i.e. as things you do to an IEnumerable rather than being a feature of IEnumerable. E.g. .Aggregate(), .First(), etc. IMO that's an area LINQ gets wrong, as it makes it awkward to deal with single-item cases; you have to choose between enumerations with one item, or extracting the item. Besides the fact that that could fail if the sequence is empty, it also means that LINQ is not algebraically closed under all of it operations. The two issues combined lead to certain ways that LINQ, much as I like it, is not always as good as it could be. For instance recently I had a problem of matching controls on a windows dialog up to a list of expected controls from a database, with a fuzzy match of +/- 2 pixels on each rectangle side, and produce four lists: 1-1 matches, ambiguous matches, missing left, missing right. I can express very clearly what I want, declaratively (in fact, I just did - in an ideal object query language that sentence would have almost a direct translation). However as a LINQ query it gets very messy. Since it's a fuzzy match, I can't simply equi-join the two lists. (Note that the match predicate is not transitive; |A-B|<=2 and |B-C|<=2 does not imply |A-C|<=2.) Since there's 4 dimensions being compared, I can't use just a single sort. On the other hand if the distance in any one dimension is greater than 2, there's no point in comparing the other 3. But I don't want to do N^2 comparisons, either. So I go with a solution which produces candidate matches on each dimension and joins the two lists. Since LINQ only supports equijoin, and I don't feel like writing an sort-intersect primitive, I just lazily generate all five integers +/-2 of the real value. At least it is 5+5+5+5 rather than 5 * 5 * 5 * 5, because the dimensions are joined on separately not as a tuple. Then I do a group-by using the object itself as the group key, and discard groups which don't match at least once in all four dimensions. I have to do extra work after that to discover ambiguous and missing matches. Maybe not the best way, but the best compromise I could come up with between optimality, readability, and development time. But notice how many non-essential details I had to think about! The core task that my LINQ expression is doing is only a small part of all the expanding, joining, grouping, and extracting that I had to do. Even if I couldn't just hand the problem off and let the computer figure out to do all this (which I would like to be able to do), just being able to separate the essential and accidental parts of this query would be helpful. True, I got in the situation because I didn't want to accept the O(N^2) brute force option doing a filter on the cross product. However note that LINQ also didn't do anything for insulating my essential query code from the strategy used to collate the data; instead it mixes them together. I'm still learning about transducers, but my hope is that they will someday allow better separation of concerns than LINQ/IEnumerable by itself.

yomly 9y ago

This is a small point, but to the author: in your first part of the article[0], binding the function argument to f in map, and then binding the head of the collection in filter was a bit confusing when scanning through...

reborg 9y ago
Happy to review the code, but I'm having trouble understand which snippet you're referring to.

twic 9y ago

So are transducers basically this Java, but in Clojure: https://gist.github.com/tomwhoiscontrary/e41d52e9c98a706552be66f8a5f2fc17 https://gist.github.com/tomwhoiscontrary/e41d52e9c98a706552b... ? I've done that in terms of Consumer, but it might also be possible, and perhaps more elegant, in terms of flat-mapping functions (Function<T, Stream<T>>). If i've understood right, then from a Java point of view, transducers are an attempt to reify the various operations on streams - mapping, filtering, etc. To do that, you have to figure out a type which is general enough to model all those operations. The need for a general type is where you get the perilously-close-to-general-abstract-nonsense "a transducer is a transformation from one reducing function to another". Here, "a reducing function" is what stands in, in a very oblique way, for the stream - it's ultimately a conduit for values, and transducers take some existing conduit, wrap another layer of processing round it, and give you the resulting conduit. So they're a bit like backward streams, i suppose. If anything, it's like how you go around wrapping up layers of OutputStreams when doing IO: new PrintStream(new BufferedOutputStream(new GZIPOutputStream(new CipherOutputStream(new FileOutputStream("file.dat"), cipher)))); Except instead of explicitly constructing wrappers, transducers know how to do the wrapping.

phaedrus 9y ago
I thought that transducers also abstracted away the difference between an input stream and an output stream? (Or the difference between pulling values on demand versus pushing values.)