3 ms·

I never understood what was so special about Clojure's Transducers. Isn't it essentially just applying a transformation on the lambda applied to a fold?

waffletower 6mo ago
That is a bit reductive. You can consider these implementations in other languages: https://github.com/hypirion/haskell-transducers https://github.com/hypirion/haskell-transducers -- https://github.com/ruuda/transducers https://github.com/ruuda/transducers
- solomonb 6mo ago
  It seems like a messy abstraction whose results could be achieved through a variety of other tools. :/
  - waffletower 6mo ago
    It isn't messy in Clojure
  - mhitza 6mo ago
    Free Monads are a very nice (though not performant) way of creating an embedded domain specific language interpreter. Once I was building a declarative components library in PHP, using the ideas I've learned from free monads. I'm sure you can't imagine what an attrocity I've built. It did the job, but I had to mentally check out and throw in a couple of goto's in my main evalution loop. All that to say that elegance of expressivity is tied to the syntax and semantics of languages.
    - solomonb 6mo ago
      Free Monads are also built on a tower of mathematical structures that come with laws and invariants. I have yet to see such formalization for transducers.
Veedrac 6mo ago
Fundamentally, there are two ways of representing iteration pipelines: source driven, and drain driven. This almost always maps to the idea of _internal_ iteration and _external_ iteration, because the source is wrapped inside the transforms. Transducers are unusual in being source driven but also external iterators. Most imperative languages choose one of two things, internal iteration that doesn't support composable flow control, and external iteration that does. This is why you see pause/resume style iteration in Python, Rust, Java, and even Javascript. If that's your experience, transducers are a pretty novel place in the trade-off space: you keep most of the composability, but you get to drive it from things like event sources. But the gap is a bit smaller than it might appear. Rust's iterators are conceptually external iterators, but they actually do support internal iteration through `try_fold`, and even in languages that don't, you can 'just' convert external to internal iterators. Then all you have to do to recover what transducers give you is pass the object to the source, let it run `try_fold` whenever it has data, and check for early termination via `size_hint`. There's one more trick for the rare case of iterators with buffering, but you don't have to change the Iterator interface for that, you just need to pass one bit of shared state to the objects on construction. Not all Iterators are strictly valid to be source-driven, and while most do, not everything works nicely when iterated this way (eg. Skip could but doesn't handle this case correctly, because it's not required to), but I don't think transducers can actually do anything this setup can't. It's just an API difference after that point.
- solomonb 6mo ago
  > If that's your experience, transducers are a pretty novel place in the trade-off space That is not my experience and TBH I don't know what a lot of your terminology specifically means.
  - Veedrac 6mo ago
    I wasn't saying you would have that experience, I was saying that the reason people act like transducers are unique is that transducers are an unconventional place on well worn ground. Ultimately, yes, everything bottoms out, most special tricks seem less special the more you understand about them, because it's programming and Turing Equivalence is the bedrock the whole field rests on. But the average person learning about transducers is not going to spot how closely related it is to other things that already exist. I'm happy to elaborate on any part of the terminology if you're curious, but tbh I mostly wrote it for myself because I thought the framing was novel and wanted it noted down somewhere.

waffletower 6mo ago

That is a bit reductive. You can consider these implementations in other languages: https://github.com/hypirion/haskell-transducers https://github.com/hypirion/haskell-transducers -- https://github.com/ruuda/transducers https://github.com/ruuda/transducers

solomonb 6mo ago
It seems like a messy abstraction whose results could be achieved through a variety of other tools. :/
- waffletower 6mo ago
  It isn't messy in Clojure
- mhitza 6mo ago
  Free Monads are a very nice (though not performant) way of creating an embedded domain specific language interpreter. Once I was building a declarative components library in PHP, using the ideas I've learned from free monads. I'm sure you can't imagine what an attrocity I've built. It did the job, but I had to mentally check out and throw in a couple of goto's in my main evalution loop. All that to say that elegance of expressivity is tied to the syntax and semantics of languages.
  - solomonb 6mo ago
    Free Monads are also built on a tower of mathematical structures that come with laws and invariants. I have yet to see such formalization for transducers.

Veedrac 6mo ago

Fundamentally, there are two ways of representing iteration pipelines: source driven, and drain driven. This almost always maps to the idea of _internal_ iteration and _external_ iteration, because the source is wrapped inside the transforms. Transducers are unusual in being source driven but also external iterators. Most imperative languages choose one of two things, internal iteration that doesn't support composable flow control, and external iteration that does. This is why you see pause/resume style iteration in Python, Rust, Java, and even Javascript. If that's your experience, transducers are a pretty novel place in the trade-off space: you keep most of the composability, but you get to drive it from things like event sources. But the gap is a bit smaller than it might appear. Rust's iterators are conceptually external iterators, but they actually do support internal iteration through `try_fold`, and even in languages that don't, you can 'just' convert external to internal iterators. Then all you have to do to recover what transducers give you is pass the object to the source, let it run `try_fold` whenever it has data, and check for early termination via `size_hint`. There's one more trick for the rare case of iterators with buffering, but you don't have to change the Iterator interface for that, you just need to pass one bit of shared state to the objects on construction. Not all Iterators are strictly valid to be source-driven, and while most do, not everything works nicely when iterated this way (eg. Skip could but doesn't handle this case correctly, because it's not required to), but I don't think transducers can actually do anything this setup can't. It's just an API difference after that point.

solomonb 6mo ago
> If that's your experience, transducers are a pretty novel place in the trade-off space That is not my experience and TBH I don't know what a lot of your terminology specifically means.
- Veedrac 6mo ago
  I wasn't saying you would have that experience, I was saying that the reason people act like transducers are unique is that transducers are an unconventional place on well worn ground. Ultimately, yes, everything bottoms out, most special tricks seem less special the more you understand about them, because it's programming and Turing Equivalence is the bedrock the whole field rests on. But the average person learning about transducers is not going to spot how closely related it is to other things that already exist. I'm happy to elaborate on any part of the terminology if you're curious, but tbh I mostly wrote it for myself because I thought the framing was novel and wanted it noted down somewhere.