12 ms·

“Transducers” by Rich Hickey at Strange Loop [video]

203 points by sgrove 12y ago

hawkice 12y ago
I enjoyed the discussion of the types. I dig haskell (and clojure), and I think this is perhaps the perfect lens with which to view how to make choices between them. You can have an insanely complex typesafe haskell transducer, a still very complex but unsafe haskell transducer, a weaker and less flexible version of transducers with a simpler type encoding in haskell, some combination of those ideas, OR... you just test your code out in the repl while developing in clojure and just kinda rely on the fact that core infrastructure or popular libraries will generally work.
- lomnakkus 12y ago
  Personally, I don't think the gist posted by tel qualifies as "insanely complex" by any stretch. But a more serious question is: how do you know if "will generally work" applies to your particular case? The short answer is that you don't and you end up having to test library-provided functionality as part of your own test suite. You can argue that you'd have to do the same in e.g. Haskell, but really the surface area of potential failures is hugely reduced by the fact that you know whether a function "f: a -> b" can have side effects and that given something shaped "a" it will give you something shaped "b" (modulo termination, but that applies in any non-total language). This is not merely a theoretical issue: Compare the amount of documentation you need when using some random library in Haskell vs. e.g. JavaScript. The types act as compiler-checked documentation. In JavaScript it's really a crapshoot if the library has sufficient documentation and it's always specified in an ad-hoc manner (which naturally differs from library to library).
  - hawkice 12y ago
    I think if you sit down with the code clojure uses to implement transducers and compare it directly against the haskell code and _don't_ come to the conclusion that the clojure code is simpler, there might be some motivated cognition at work. I don't think it's trivial for someone with Haskell experience to even verify that code implements the same (or a similar) thing. I also believe it lacks sufficient polymorphism, for instance surrounding the output of the step function, and lacks safety around (notably, but not exclusively) the application of the step function (i.e. to only the last value of the transducer, not just something of that type). So this would be squarely in the tries-to-be-simple category, despite it's use of profunctors (don't know why that was used here, it's not a super-standard abstraction). But this is all beside the larger point. Things generally working is learned through philosophical induction in the case of clojure -- just seeing something work a bunch of times and understanding the mechanisms in some level of detail. That's not the same as having a machine-verified proof, but it's also not the same as not knowing at all.
    - lomnakkus 12y ago
      It depends on what you mean by "simpler", I suppose. > there might be some motivated cognition at work. Did you really just say that? > I don't think it's trivial for someone with Haskell experience to even verify that code implements the same (or a similar) thing. No, not to verify that it does the same thing. For that you'd have to understand exactly what the Clojure version does too. I'm a quite rusty on Clojure, so I can't make a fair comparison on how easy it is to understand vs. the Haskell version. However, you'll note that I didn't actually say anything about the Clojure version being harder to understand. In fact, my point is that I don't even have to understand the implementation of the Haskell version: I just have to understand its interface (i.e. the types) and have a general idea of what it's supposed to do (in fuzzy terms).
    - tel 12y ago
      Outside of the opinions being expressed, some technical comments. 1. I'd like to learn more specifically what kind of output polymorphism you would like. Right now the outputs are universally quantified, but linked. I've written it in other ways as well, but I could not find any reason in practice to use that added complexity. In particular, the universal quantification does force you to use the output of the step since there is no other way (in scope) to produce values of the needed type. For that use case at least the RankNType is exactly what you want. 2. Profunctors are not really needed at all. It was more to demonstrate that Moore and T have nice structure. The same holds for Category (and my note about Arrow). In all cases, this is just giving nice organization to regular properties of T and Moore.
  - skybrian 12y ago
    However, it only helps if you thoroughly understand the type system. Since Haskell has a rather complex type system, the relative lack of documentation in English is a barrier to entry for the uninitiated. (Also, aren't the types often omitted due to type inference?)
    - hawkice 12y ago
      It's actually considered bad practice to omit types in Haskell for top level declarations. Unless needed, it's typically best to omit them _within_ declarations, though. I am not entirely sure why this is where the community landed, but you could get away with e.g. only providing types explicitly for exported functions, and no one would really care, I think. You can always use your IDE/repl to just tell you the types whether they are explicit or not. [EDIT: This didn't really address your core point. I'm not sure how to do that, precisely, but here is a shot. I think the ideal Haskell use case is active collaboration between the programmer and the compiler. The lack of English language docs is seen as less important than clear contracts within that interaction. I think the descriptive statement of "If you try to operate without the compiler and reason using English language understandings, Haskell will be more frustrating for you than it is for people in the Haskell community" seems both true and fair. Suffice it to say, most understanding of actual things is most easily expressed in natural language, because most communication happens in natural languages, so that's just how we hear about those ideas.]
      - ufo 12y ago
        Another way to say this is that Haskell encourages what Rich Hickey would call "guardrail programming". The types give you hints as to how the different pieces of the program piece together. When you finally get everything to compile it should hopefully work straight away.
      - skybrian 12y ago
        Yes, I agree. This dialog with the compiler may help library authors and library callers, but it doesn't help readers. A beginner is likely to be reading code on the Internet, in tutorials, blog posts, on stack overflow, or in papers. Perhaps a particularly active, determined reader might also try out the code they read. It's common to automatically syntax-highlight online code but not to type-annotate or cross-reference it (adding links between declarations and usages). But perhaps the tools will get better.
- imanaccount247 12y ago
  >You can have an insanely complex typesafe haskell transducer How do you come to this conclusion? I can't even see how that is possible other than outright ignoring reality and just making up something you like the sound of. It isn't even complex, much less insanely complex. >you just test your code out in the repl while developing in clojure and just kinda rely on the fact that core infrastructure or popular libraries will generally work. And then get bitten by the fact that "generally work" isn't adequate.
  - hawkice 12y ago
    There is no way in Haskell 2010 to express a function who can take as an argument more than one shape of thing and then give compiler assurances that the value, not just the shape, given to it is precisely that of the result of calling it last (not to mention unless you fold this into a strict monad to hide the type changes of the state function, 'called last' may not be very well defined). This is simply not how Haskell works. You can drop polymorphism or you can drop safety, but I am not pretending to describe a potential tradeoff, I am describing a tradeoff the designers of Haskell already made when they decided (rightly, perhaps) that even if you had dependent types, encoding a fully polymorphic (map map) doesn't help as much as it hurts.
    - tel 12y ago
      Sure there is. You just take a generic function f :: r -> r and you keep specializing it with whatever input you like. f (x :: Int) :: Int f (y :: Char) :: Char which is essentially the RankNType trick. You could express something fancier with dependent types, but I've yet to see a real need for it. You could also do this with a "Resumption Type": data Resumption a where Resume :: x -> (x -> (a, Resumption a)) -> Resumption a In this case, each time you receive a Resumption you can open it up to receive a totally unique `x` which you have zero knowledge of except in that you are able to give it back to the "resumption function" you also unpacked in order to receive a token. A little variation on this is exactly the Moore machine encoding I used in the Gist.
      - 12y ago
raspasov 12y ago
Great talk by Rich on transducers, instrumental in understanding the "hows" and "whys" behind the concept.
tel 12y ago
First, to be clear, I really liked this presentation. The criticism below is both technical and small---all in all I greatly enjoy Rich Hickey's work and generally admire his ability to talk compellingly about complex technical topics. That said. I somewhat disliked Hickey's presentation of typing transducers here. I feel as though he builds a number of strawmen toward typing and then tries to knock them down and suggest that either Clojure has some kind of mystical mechanism that is ineffable to types or that the exercise of typing transducers is wasteful. I disagree on both accounts, I suppose. I think types are useful for analysis and teaching. The two major points he seems to make is that in order to "properly type" transducers you must 1. Index the type of the "accumulation so far" so that it cannot be transformed out-of-order 2. Implement early stopping "without wrapping anything except for the reduced value" There may be other critiques as well, but I want to examine these two in the context of Haskell. With respect to the first point, the major concern appears to be prohibiting behavior loosely described as "applying the reducing function, say, 3 times and then returning the first resulting accumulation". In some sense, the idea is to force us to be faithful in passing on the accumulating parameter. In code, a pathological setting is the following: transduce :: (r -> a -> r) -> (r -> a -> r) transduce reduce accu0 a = let acc1 = reduce acc0 a acc2 = reduce acc1 a acc3 = reduce acc2 a in acc1 The concern is unfounded in a pure language, however, since calling `reduce` can have no side effects. This entails that all possible effects on the world of calling `reduce` are encapsulated in the return and, therefore, we can completely eliminate the steps producing `acc2` and `acc3` without worry. transduce :: (r -> a -> r) -> (r -> a -> r) transduce reduce accu0 a = let acc1 = reduce acc0 a in acc1 Now, there may be concern here that we still want to index the `r` type somehow to allow for changes of accumulation to occur. This is not the case (in this simple model!) as in order to achieve the "baggage carrier independence" property the `r` type must be left unspecified until the transducer is actually applied. The cleanest way to do that is to use a higher-rank type (Hickey mentions these briefly and offhandedly toward the end of his talk) type Transducer a b = forall r . (r -> b -> r) -> (r -> a -> r) which thus prohibits the implementer of a Transducer from affecting the values of `r` in any way whatsoever---they must be left anonymous until someone decides to use the Tranducer on a particular collection of values `a`. (It must be noted that the model given above is isomorphic to a "Kleisli arrow on the list monad" which I described a little bit here http://jspha.com/posts/typing-transducers/ http://jspha.com/posts/typing-transducers/. It should also be noted that this model includes neither (a) the ability to use local state to capture time-varying transductions or (b) the ability to terminate early) With respect to the second point, I'd like to suggest that there is a difference between the semantic weight of wrapping the result types in an Either in order to indicate early termination and the implementation weight. I completely agree that using an Either to implement early stopping (as it's easy, if finicky for the library implementor, to do) will involve wrapping and unwrapping the "state" of the transduction continuously. I also would like to suggest that it's a very natural way of representing the "accumulation | reduction" notion Hickey uses in his own "Omnigraffle 8000 type system". We really would like to capture the idea of the transducer state as being "either" in-progress or fully-reduced and act accordingly. If Clojure's implementation of that requires fewer runtime tags than an Either, so be it, but I personally fail to see a semantic difference except in the way one can play fast-and-loose with dynamic types over static types to begin with. --- So, I gave above an implementation of Transducers in types which has some of their properties, but certainly not all. In fact, I abused the fact that there is no ambient state in Haskell in order to ensure that a certain property would hold (notably this doesn't require a type system at all, just purity). I also argued that using Either is a perfectly natural way to implement early termination in such a transduction pipeline. I've also made an extension to the `(r->b->r) -> (r->a->r)` mechanism which enables local state to be enabled for various components of the transduction pipeline. A version without early termination is available here: https://gist.github.com/tel/714a5ea2e015d918f135 https://gist.github.com/tel/714a5ea2e015d918f135 Notably, this uses most of the same typing tricks as `(r->b->r) -> (r->a->r)` but adds a "reduction local hidden state" variable which lets us implement `take` and `partition`. This takes Hickey's notion of needing to be explicit about the state being used to a whole new level. --- So what is the point of all this? I'd like to argue that Transducers do not present such a mysterious mechanism that they cannot be sanely typed in a reasonably rich language. I believe that I can capture most of their salient features in types without using the dependent indexing Hickey suggested was necessary. More than this, the compartmentalized, hidden reducer-local state in the Gist implementation allows for each reduction step to include fairly exotic local states in their state machine. You could implement a kind of type indexing here if desired and no end-user would ever know of its existence. I also absolutely concede that many type systems people regularly use could not achieve this kind of encoding. Finally, what I really want to say is that type systems are not something to be denigrated. I believe some of the earliest "transducers v. types" argumentation took a nasty turn as amateur type theorists (myself included) rushed to write things like "Transducers are just X". I want to apologize for any kind of bad feelings my own writing in that thread may have stirred up. I try not to be haughty or dismissive with this kind of writing, but I also make mistakes. So what I'd really like to suggest is that types should not be taken as reductivist on interesting techniques like Transducers but instead as a tool for analyzing their construction and either improving it or better teaching it. Hickey himself often turns to some kind of "pseudotyping" to talk about how Transducers work---formalizing those notions should only lead to greater clarity. Of course, implementations will differ in small ways. As I've noted abundantly here, a major difference between the Haskell and Clojure implementations is driven more by Haskell's purity than its typing. Hopefully, however, exploration of alternative implementations and the rich analysis produced by their typing can help to introduce new ideas. For instance, the Gist implementation, if you strip the types away, is an interesting divergence in raw functionality from Clojure Transducers---if Clojure Transducers are "reduction function transformers" than the Gisted Transducers are "Moore-style (Infinite) State Machine transformers" and that difference allows the implementer to be extra explicit about the use of local state. I'd rather see discussion about whether such InFSM transformation techniques have a place in Transducers literature than a fight over whether or not its possible or reasonable to "type transducers".
atratus 12y ago
Removing conj is what finally made it click
kazagistar 12y ago
I'm still a little confused and will have to go over some code or something to really understand the limitations of what transducers can do... can any transducer be used in a "parallel" context (like map and filter) or are they limited to a linear context (like the fold makes me suspect)?
- mistaken 12y ago
  I think it could be parallelized by chunking up the input, however the transducer doesn't know how to do that by itself, so the step function would have to be modified somehow.
  - jjcomer 12y ago
    Exactly! core.async had the pipeline mechanism added which allows for the parallel application of a transducer to a channel. https://github.com/clojure/core.async/blob/17112aca9b07ebba6ce760ca01d117c24c80cc9a/src/main/clojure/clojure/core/async.clj#L500 https://github.com/clojure/core.async/blob/17112aca9b07ebba6...
- nickik 12y ago
  Check out clojure reducers (http://clojure.org/reducers http://clojure.org/reducers) they are earlier work in the same line of thinking. The where used to do pmap style things. The same tricks can be used with trnasducers, but I dont think its implmented yet.
Animats 12y ago
I think somebody just reinvented data flow programming.
- blackkettle 12y ago
  yeah, is this going to become a 'thing'? i'm finding it really kind of annoying that terms from the fundamentals of theoretical & applied compsci ([weighted] finite-state transducers WFSTs) are being appropriated like this.
iamwil 12y ago
Transducers really sound like monads. Are they the same thing?
- lgas 12y ago
  No.
- tel 12y ago
  In almost every meaning of that sentence—no. One simplified model of transducer happens to be similar to half of a particular monad. It's very disingenuous to say that "transducers are monads" or even "transducers are a particular form of monad", however.
  - iamwil 12y ago
    :( it was an honest question. I really didn't know. I watched the talk. I didn't get everything that was said, so I came here to ask a question. Man, HN is use to too much snark.
    - tel 12y ago
      Oh! Sorry, I may have written that poorly. I meant that technically: "in almost every sense, no". There is one sense in which "yes" they kind of are: a simplified model can be seen as Transducer a b ~ (a -> [b]) where the right side is a pretty fundamental type when talking about the list monad. In fact, composition of transducers is exactly "monad-arrow composition" or "composition in the list monad Kleisli category". So in that sense, they are a particular form of monad. But it's a bit of a stretch. Thus, I really meant it in "almost every way", not every way entirely.
      - iamwil 12y ago
        So by what you wrote, it sounds like they're related, but a completely separate concept. Where can I find an intro to transducers that's readable for beginners? I don't know what "list monad Kleisli category" means. Searching for "transducers" came up with a physical transducer.
scythe 12y ago
I threw together a toy implementation in Lua: https://gist.github.com/scythe/d28c3f4933ff2f1e5c47 https://gist.github.com/scythe/d28c3f4933ff2f1e5c47 Granted, none of the cool out-of-order-iteration is there, but the reverse composition looks natural to me now, so I can sleep at night.
- GordonFreeman 12y ago
  Took me a while to understand the reverse composition too so I hacked on it in Python https://gist.github.com/colinsmith/3140e7cb57c4095ed83f https://gist.github.com/colinsmith/3140e7cb57c4095ed83f
rovjuvano 12y ago
Correcting two flaws with this leads to an interesting result: 1) no error handling, at all, anywhere, not just missing from the presentation, but not in the code. transduce just wraps reduce. FAIL!!! 2) the 'result' parameter unnecessarily pollutes the interface. reduce can be reduced to foreach (doseq) with state and be implemented like other tranducers that require state. Correcting for these two errors: a) the 0-arity init function is removed b) the 1-arity completed function becomes 0-arity c) the 2-arity reducing function becomes 1-arity d) a 1-arity error function is added. Since these functions cannot be distinguished by arity alone, we give them names: call the reducing function 'onNext', the error function 'onError', and the completed function 'onCompleted', and optionally, group the three functions into an object and voila, we have Rx Observers. Hickey's twist here is composing Observers instead of Observables. Whether this buys you anything worthwhile is debatable. Two derivations of Rx often accompany it's introduction: 1) Observable being the dual of Iterable 2) Observables being Promises with multiple return values. Thanks to Hickey, we can add Observers being an abstraction from reduce/fold (along with it's many other names).

203 points by sgrove 12y ago

I enjoyed the discussion of the types. I dig haskell (and clojure), and I think this is perhaps the perfect lens with which to view how to make choices between them. You can have an insanely complex typesafe haskell transducer, a still very complex but unsafe haskell transducer, a weaker and less flexible version of transducers with a simpler type encoding in haskell, some combination of those ideas, OR... you just test your code out in the repl while developing in clojure and just kinda rely on the fact that core infrastructure or popular libraries will generally work.

lomnakkus 12y ago
Personally, I don't think the gist posted by tel qualifies as "insanely complex" by any stretch. But a more serious question is: how do you know if "will generally work" applies to your particular case? The short answer is that you don't and you end up having to test library-provided functionality as part of your own test suite. You can argue that you'd have to do the same in e.g. Haskell, but really the surface area of potential failures is hugely reduced by the fact that you know whether a function "f: a -> b" can have side effects and that given something shaped "a" it will give you something shaped "b" (modulo termination, but that applies in any non-total language). This is not merely a theoretical issue: Compare the amount of documentation you need when using some random library in Haskell vs. e.g. JavaScript. The types act as compiler-checked documentation. In JavaScript it's really a crapshoot if the library has sufficient documentation and it's always specified in an ad-hoc manner (which naturally differs from library to library).
- hawkice 12y ago
  I think if you sit down with the code clojure uses to implement transducers and compare it directly against the haskell code and _don't_ come to the conclusion that the clojure code is simpler, there might be some motivated cognition at work. I don't think it's trivial for someone with Haskell experience to even verify that code implements the same (or a similar) thing. I also believe it lacks sufficient polymorphism, for instance surrounding the output of the step function, and lacks safety around (notably, but not exclusively) the application of the step function (i.e. to only the last value of the transducer, not just something of that type). So this would be squarely in the tries-to-be-simple category, despite it's use of profunctors (don't know why that was used here, it's not a super-standard abstraction). But this is all beside the larger point. Things generally working is learned through philosophical induction in the case of clojure -- just seeing something work a bunch of times and understanding the mechanisms in some level of detail. That's not the same as having a machine-verified proof, but it's also not the same as not knowing at all.
  - lomnakkus 12y ago
    It depends on what you mean by "simpler", I suppose. > there might be some motivated cognition at work. Did you really just say that? > I don't think it's trivial for someone with Haskell experience to even verify that code implements the same (or a similar) thing. No, not to verify that it does the same thing. For that you'd have to understand exactly what the Clojure version does too. I'm a quite rusty on Clojure, so I can't make a fair comparison on how easy it is to understand vs. the Haskell version. However, you'll note that I didn't actually say anything about the Clojure version being harder to understand. In fact, my point is that I don't even have to understand the implementation of the Haskell version: I just have to understand its interface (i.e. the types) and have a general idea of what it's supposed to do (in fuzzy terms).
  - tel 12y ago
    Outside of the opinions being expressed, some technical comments. 1. I'd like to learn more specifically what kind of output polymorphism you would like. Right now the outputs are universally quantified, but linked. I've written it in other ways as well, but I could not find any reason in practice to use that added complexity. In particular, the universal quantification does force you to use the output of the step since there is no other way (in scope) to produce values of the needed type. For that use case at least the RankNType is exactly what you want. 2. Profunctors are not really needed at all. It was more to demonstrate that Moore and T have nice structure. The same holds for Category (and my note about Arrow). In all cases, this is just giving nice organization to regular properties of T and Moore.
- skybrian 12y ago
  However, it only helps if you thoroughly understand the type system. Since Haskell has a rather complex type system, the relative lack of documentation in English is a barrier to entry for the uninitiated. (Also, aren't the types often omitted due to type inference?)
  - hawkice 12y ago
    It's actually considered bad practice to omit types in Haskell for top level declarations. Unless needed, it's typically best to omit them _within_ declarations, though. I am not entirely sure why this is where the community landed, but you could get away with e.g. only providing types explicitly for exported functions, and no one would really care, I think. You can always use your IDE/repl to just tell you the types whether they are explicit or not. [EDIT: This didn't really address your core point. I'm not sure how to do that, precisely, but here is a shot. I think the ideal Haskell use case is active collaboration between the programmer and the compiler. The lack of English language docs is seen as less important than clear contracts within that interaction. I think the descriptive statement of "If you try to operate without the compiler and reason using English language understandings, Haskell will be more frustrating for you than it is for people in the Haskell community" seems both true and fair. Suffice it to say, most understanding of actual things is most easily expressed in natural language, because most communication happens in natural languages, so that's just how we hear about those ideas.]
    - ufo 12y ago
      Another way to say this is that Haskell encourages what Rich Hickey would call "guardrail programming". The types give you hints as to how the different pieces of the program piece together. When you finally get everything to compile it should hopefully work straight away.
    - skybrian 12y ago
      Yes, I agree. This dialog with the compiler may help library authors and library callers, but it doesn't help readers. A beginner is likely to be reading code on the Internet, in tutorials, blog posts, on stack overflow, or in papers. Perhaps a particularly active, determined reader might also try out the code they read. It's common to automatically syntax-highlight online code but not to type-annotate or cross-reference it (adding links between declarations and usages). But perhaps the tools will get better.
imanaccount247 12y ago
>You can have an insanely complex typesafe haskell transducer How do you come to this conclusion? I can't even see how that is possible other than outright ignoring reality and just making up something you like the sound of. It isn't even complex, much less insanely complex. >you just test your code out in the repl while developing in clojure and just kinda rely on the fact that core infrastructure or popular libraries will generally work. And then get bitten by the fact that "generally work" isn't adequate.
- hawkice 12y ago
  There is no way in Haskell 2010 to express a function who can take as an argument more than one shape of thing and then give compiler assurances that the value, not just the shape, given to it is precisely that of the result of calling it last (not to mention unless you fold this into a strict monad to hide the type changes of the state function, 'called last' may not be very well defined). This is simply not how Haskell works. You can drop polymorphism or you can drop safety, but I am not pretending to describe a potential tradeoff, I am describing a tradeoff the designers of Haskell already made when they decided (rightly, perhaps) that even if you had dependent types, encoding a fully polymorphic (map map) doesn't help as much as it hurts.
  - tel 12y ago
    Sure there is. You just take a generic function f :: r -> r and you keep specializing it with whatever input you like. f (x :: Int) :: Int f (y :: Char) :: Char which is essentially the RankNType trick. You could express something fancier with dependent types, but I've yet to see a real need for it. You could also do this with a "Resumption Type": data Resumption a where Resume :: x -> (x -> (a, Resumption a)) -> Resumption a In this case, each time you receive a Resumption you can open it up to receive a totally unique `x` which you have zero knowledge of except in that you are able to give it back to the "resumption function" you also unpacked in order to receive a token. A little variation on this is exactly the Moore machine encoding I used in the Gist.
    - 12y ago

raspasov 12y ago

Great talk by Rich on transducers, instrumental in understanding the "hows" and "whys" behind the concept.

tel 12y ago

First, to be clear, I really liked this presentation. The criticism below is both technical and small---all in all I greatly enjoy Rich Hickey's work and generally admire his ability to talk compellingly about complex technical topics. That said. I somewhat disliked Hickey's presentation of typing transducers here. I feel as though he builds a number of strawmen toward typing and then tries to knock them down and suggest that either Clojure has some kind of mystical mechanism that is ineffable to types or that the exercise of typing transducers is wasteful. I disagree on both accounts, I suppose. I think types are useful for analysis and teaching. The two major points he seems to make is that in order to "properly type" transducers you must 1. Index the type of the "accumulation so far" so that it cannot be transformed out-of-order 2. Implement early stopping "without wrapping anything except for the reduced value" There may be other critiques as well, but I want to examine these two in the context of Haskell. With respect to the first point, the major concern appears to be prohibiting behavior loosely described as "applying the reducing function, say, 3 times and then returning the first resulting accumulation". In some sense, the idea is to force us to be faithful in passing on the accumulating parameter. In code, a pathological setting is the following: transduce :: (r -> a -> r) -> (r -> a -> r) transduce reduce accu0 a = let acc1 = reduce acc0 a acc2 = reduce acc1 a acc3 = reduce acc2 a in acc1 The concern is unfounded in a pure language, however, since calling `reduce` can have no side effects. This entails that all possible effects on the world of calling `reduce` are encapsulated in the return and, therefore, we can completely eliminate the steps producing `acc2` and `acc3` without worry. transduce :: (r -> a -> r) -> (r -> a -> r) transduce reduce accu0 a = let acc1 = reduce acc0 a in acc1 Now, there may be concern here that we still want to index the `r` type somehow to allow for changes of accumulation to occur. This is not the case (in this simple model!) as in order to achieve the "baggage carrier independence" property the `r` type must be left unspecified until the transducer is actually applied. The cleanest way to do that is to use a higher-rank type (Hickey mentions these briefly and offhandedly toward the end of his talk) type Transducer a b = forall r . (r -> b -> r) -> (r -> a -> r) which thus prohibits the implementer of a Transducer from affecting the values of `r` in any way whatsoever---they must be left anonymous until someone decides to use the Tranducer on a particular collection of values `a`. (It must be noted that the model given above is isomorphic to a "Kleisli arrow on the list monad" which I described a little bit here http://jspha.com/posts/typing-transducers/ http://jspha.com/posts/typing-transducers/. It should also be noted that this model includes neither (a) the ability to use local state to capture time-varying transductions or (b) the ability to terminate early) With respect to the second point, I'd like to suggest that there is a difference between the semantic weight of wrapping the result types in an Either in order to indicate early termination and the implementation weight. I completely agree that using an Either to implement early stopping (as it's easy, if finicky for the library implementor, to do) will involve wrapping and unwrapping the "state" of the transduction continuously. I also would like to suggest that it's a very natural way of representing the "accumulation | reduction" notion Hickey uses in his own "Omnigraffle 8000 type system". We really would like to capture the idea of the transducer state as being "either" in-progress or fully-reduced and act accordingly. If Clojure's implementation of that requires fewer runtime tags than an Either, so be it, but I personally fail to see a semantic difference except in the way one can play fast-and-loose with dynamic types over static types to begin with. --- So, I gave above an implementation of Transducers in types which has some of their properties, but certainly not all. In fact, I abused the fact that there is no ambient state in Haskell in order to ensure that a certain property would hold (notably this doesn't require a type system at all, just purity). I also argued that using Either is a perfectly natural way to implement early termination in such a transduction pipeline. I've also made an extension to the `(r->b->r) -> (r->a->r)` mechanism which enables local state to be enabled for various components of the transduction pipeline. A version without early termination is available here: https://gist.github.com/tel/714a5ea2e015d918f135 https://gist.github.com/tel/714a5ea2e015d918f135 Notably, this uses most of the same typing tricks as `(r->b->r) -> (r->a->r)` but adds a "reduction local hidden state" variable which lets us implement `take` and `partition`. This takes Hickey's notion of needing to be explicit about the state being used to a whole new level. --- So what is the point of all this? I'd like to argue that Transducers do not present such a mysterious mechanism that they cannot be sanely typed in a reasonably rich language. I believe that I can capture most of their salient features in types without using the dependent indexing Hickey suggested was necessary. More than this, the compartmentalized, hidden reducer-local state in the Gist implementation allows for each reduction step to include fairly exotic local states in their state machine. You could implement a kind of type indexing here if desired and no end-user would ever know of its existence. I also absolutely concede that many type systems people regularly use could not achieve this kind of encoding. Finally, what I really want to say is that type systems are not something to be denigrated. I believe some of the earliest "transducers v. types" argumentation took a nasty turn as amateur type theorists (myself included) rushed to write things like "Transducers are just X". I want to apologize for any kind of bad feelings my own writing in that thread may have stirred up. I try not to be haughty or dismissive with this kind of writing, but I also make mistakes. So what I'd really like to suggest is that types should not be taken as reductivist on interesting techniques like Transducers but instead as a tool for analyzing their construction and either improving it or better teaching it. Hickey himself often turns to some kind of "pseudotyping" to talk about how Transducers work---formalizing those notions should only lead to greater clarity. Of course, implementations will differ in small ways. As I've noted abundantly here, a major difference between the Haskell and Clojure implementations is driven more by Haskell's purity than its typing. Hopefully, however, exploration of alternative implementations and the rich analysis produced by their typing can help to introduce new ideas. For instance, the Gist implementation, if you strip the types away, is an interesting divergence in raw functionality from Clojure Transducers---if Clojure Transducers are "reduction function transformers" than the Gisted Transducers are "Moore-style (Infinite) State Machine transformers" and that difference allows the implementer to be extra explicit about the use of local state. I'd rather see discussion about whether such InFSM transformation techniques have a place in Transducers literature than a fight over whether or not its possible or reasonable to "type transducers".

atratus 12y ago

Removing conj is what finally made it click

kazagistar 12y ago

I'm still a little confused and will have to go over some code or something to really understand the limitations of what transducers can do... can any transducer be used in a "parallel" context (like map and filter) or are they limited to a linear context (like the fold makes me suspect)?

mistaken 12y ago
I think it could be parallelized by chunking up the input, however the transducer doesn't know how to do that by itself, so the step function would have to be modified somehow.
- jjcomer 12y ago
  Exactly! core.async had the pipeline mechanism added which allows for the parallel application of a transducer to a channel. https://github.com/clojure/core.async/blob/17112aca9b07ebba6ce760ca01d117c24c80cc9a/src/main/clojure/clojure/core/async.clj#L500 https://github.com/clojure/core.async/blob/17112aca9b07ebba6...
nickik 12y ago
Check out clojure reducers (http://clojure.org/reducers http://clojure.org/reducers) they are earlier work in the same line of thinking. The where used to do pmap style things. The same tricks can be used with trnasducers, but I dont think its implmented yet.

Animats 12y ago

I think somebody just reinvented data flow programming.

blackkettle 12y ago
yeah, is this going to become a 'thing'? i'm finding it really kind of annoying that terms from the fundamentals of theoretical & applied compsci ([weighted] finite-state transducers WFSTs) are being appropriated like this.

iamwil 12y ago

Transducers really sound like monads. Are they the same thing?

lgas 12y ago
No.
tel 12y ago
In almost every meaning of that sentence—no. One simplified model of transducer happens to be similar to half of a particular monad. It's very disingenuous to say that "transducers are monads" or even "transducers are a particular form of monad", however.
- iamwil 12y ago
  :( it was an honest question. I really didn't know. I watched the talk. I didn't get everything that was said, so I came here to ask a question. Man, HN is use to too much snark.
  - tel 12y ago
    Oh! Sorry, I may have written that poorly. I meant that technically: "in almost every sense, no". There is one sense in which "yes" they kind of are: a simplified model can be seen as Transducer a b ~ (a -> [b]) where the right side is a pretty fundamental type when talking about the list monad. In fact, composition of transducers is exactly "monad-arrow composition" or "composition in the list monad Kleisli category". So in that sense, they are a particular form of monad. But it's a bit of a stretch. Thus, I really meant it in "almost every way", not every way entirely.
    - iamwil 12y ago
      So by what you wrote, it sounds like they're related, but a completely separate concept. Where can I find an intro to transducers that's readable for beginners? I don't know what "list monad Kleisli category" means. Searching for "transducers" came up with a physical transducer.

scythe 12y ago

I threw together a toy implementation in Lua: https://gist.github.com/scythe/d28c3f4933ff2f1e5c47 https://gist.github.com/scythe/d28c3f4933ff2f1e5c47 Granted, none of the cool out-of-order-iteration is there, but the reverse composition looks natural to me now, so I can sleep at night.

GordonFreeman 12y ago
Took me a while to understand the reverse composition too so I hacked on it in Python https://gist.github.com/colinsmith/3140e7cb57c4095ed83f https://gist.github.com/colinsmith/3140e7cb57c4095ed83f

rovjuvano 12y ago

Correcting two flaws with this leads to an interesting result: 1) no error handling, at all, anywhere, not just missing from the presentation, but not in the code. transduce just wraps reduce. FAIL!!! 2) the 'result' parameter unnecessarily pollutes the interface. reduce can be reduced to foreach (doseq) with state and be implemented like other tranducers that require state. Correcting for these two errors: a) the 0-arity init function is removed b) the 1-arity completed function becomes 0-arity c) the 2-arity reducing function becomes 1-arity d) a 1-arity error function is added. Since these functions cannot be distinguished by arity alone, we give them names: call the reducing function 'onNext', the error function 'onError', and the completed function 'onCompleted', and optionally, group the three functions into an object and voila, we have Rx Observers. Hickey's twist here is composing Observers instead of Observables. Whether this buys you anything worthwhile is debatable. Two derivations of Rx often accompany it's introduction: 1) Observable being the dual of Iterable 2) Observables being Promises with multiple return values. Thanks to Hickey, we can add Observers being an abstraction from reduce/fold (along with it's many other names).