Clojure's Transducers are as fundamental as function composition | Hacker News Reader

Clojure's Transducers are as fundamental as function composition

thecomputersarewinning.com

92 pointsithayer47 comments

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.

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.

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...

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.

Here's proof that the last two parts are isomorphic:

    to :: (a -> [b]) -> (a -> (forall r . (b -> r -> r) -> r -> r))
    to f a =
      h (f a)
     where
      h :: [b] -> (forall r . (b -> r -> r) -> r -> r)
      h b cons nil =
        case b of
          (x:xs) -> cons x (h xs cons nil)
          [] -> nil

    from :: (a -> (forall r . (b -> r -> r) -> r -> r)) -> (a -> [b])
    from f a = f a (:) []

Thank you.

That step had me really confused.

The fast way is to say that [b] is the initial algebra of the functor (Maybe . (b,)) and then note that initial algebras are representable as

    newtype Mu f = Mu (forall r . (f r -> r) -> r)

Interesting. I'm not well versed in these things yet, but I've seen:

    forall r . (f r -> r) -> r

before. Am I right in saying it's the type of a catamorphism? In which case, yes, it makes total sense that your `Mu` type is equivalent to the (possibly) more usual:

    newtype Mu f = Mu (f (Mu f))

Yep! You can think of it as a "frozen catamorphism" or the "right half" of foldr when you specialize `f`.

The really fascinating part is that my Mu is equivalent to your Mu in Haskell... because it's Turing complete. In a world where least and greatest fixed points differ, in a world where data and codata differ, then Mu has a cousin Nu

    data Mu f = Mu (forall r . (f r -> r) -> r)
    data Nu f = forall r . Nu (r -> f r) r

where Mu generates the data and Nu generates the codata. You'll recognize Nu as a frozen anamorpism, of course.

If you want a total language, replace generalized fixed points with these two pairs of fixed points. Mu only lets you construct things finitely and tear them down with catamorphisms and Nu only lets you destruct things finitely which you've built with anamorphisms.

Even in Haskell you can treat certain uses of types as being data-like or codata-like by viewing them more preferentially through Mu or Nu---though you can always convert both to Fix

    newtype Fix f = Fix (f (Fix f))

I'd be grateful for a pointer to some fundamental background reading; I can only follow enough of your reasoning to be intrigued and committed to learning more :)

I'm trying to write up a blog post about this now. A really good presentation focused on types and programming languages is available in the middle chapters of Practical Foundations for Programming Languages. I originally learned about it from studying Aczel's Antifoundation Axiom from Barwise and Moss' Vicious Circles[0]---in there you can get a much more mathematical foundationalist POV---but Harper's book is more direct.

[0]http://www.amazon.com/Vicious-Circles-Center-Language-Inform...

Is this quite right? Sorry this is a bit vague/unclear, but what happens if you, say, call the reduction function, throw the result away and then call it again?

I ran this example through Clojure in let's write a transducer, and it plain doesn't work; I think the mapping given above works for all transducers that are actually valid, but I think the type definition allows for broken ones.

Again, I'm not sure & still learning, so please explain if I've gone wrong here.

If you throw the result away in pure code then you may as well have never computed it: the second result holds only.

In an impure setting none of the math above holds.

Edit: note that this doesn't mean you have to throw away local or global state. You can recapture that by using state machine transformers or even Kleisli state machine transformers (although that gets pretty heavy!)

Aaah. Makes sense. I couldn't figure out why the reasoning seemed sound, but I had something that didn't match. It's because in Clojure, r has state itself.

This is typical of Closure, as a sort of anti-Haskell. It starts with empirical structures invented by folks without PL theory training, and then wriggles to find an explanation in terms of standard theory. You can see this here on HN when Rich talks to Haskell folks and people translate his writing into standard language.

I would love a comparison in the form of Haskell, converted to Lisp syntax, and wired up to JVM.

*Clojure

You relate Haskell to standard theory and Clojure to non-PL-theory structures. I think the real issue is that strongly-typed lazy functional code (Haskell) and dynamically-typed isomorphic code (Clojure, and Lisp) have an "impedance mismatch" such that they don't inter-translate very well. I think that's based on the different foundation of each language.

Haskell is strongly typed and lazily evaluated, which easily enables functions to take only one argument at a time. Although a function could take a tuple parameter, it can be, and usually is, rewritten to take each component of the tuple as a separate parameter, which makes the strong typing and builtin currying simple, higher structures like monads possible, and the syntax can designed to suit this style.

Lisp functions, on the other hand, must take many arguments at a time to cater to the isomorphicity of the language. It's therefore much more difficult for parameters to be typed, or to curry them. The syntax requires explicit visual nesting. Inter-translating between this style and the Haskell style therefore is difficult.

I'd even suggest the Haskell and Lisp styles are two different peaks on the ladders of programming language abstraction, and the poster child of each, monads and macros, just don't interoperate very well, simply because of the different required foundations of each language.

I don't find it difficult to intertranslate at all. Trivial actually: the currying is a complete non-issue. For pure, terminating code laziness/strictness hardly matters.

And dear god do I wish people would stop abusing "isomorphic".

I'm guessing that "homoiconicity" was intended, not "isomorphic". The former makes sense in context.

I did mean "homoiconic". It was 5am when I wrote it.

> I don't find it difficult to intertranslate at all.

I should have also mentioned "variadic" with regards to lists and macros. Although it's possible to inter-translate, the required add-ons such as Template Haskell macros and Typed Clojure make each language more clunky. The pure form of each language is based on two mutually exclusive foundations, i.e. strongly typed auto-curried parameters and variadic untyped macro parameters.

Many macros can be translated to Haskell due to laziness. It's true that these can be difficult to translate or end up requiring TH. That's a downside, but it's rare.

And variadic functions are easily translated as well. They're much more syntactic convenience than true semantic variation. Typically, variadic functions encode defaulting which, in Haskell style, is just ignored. Otherwise, you just encode them as separate functions with different names. That can be annoying, but in my experience it rarely is. Worst case, you can often abstract over most of the polymorphism using a typeclass.

I'm sure you could manufacture some Clojure code which takes advantage of non-obvious macros, bizarre variadicity, and massive dynamic typing... but it'd be really hard to understand as a human.

Human intelligibility tends to drive Clojure code to be easily translatable.

Haskell beginner here:

Re: the characterisation, the only thing I'd add is that they have explicit start and end calls. Start resets the state, end can clean up resources if necessary.

I tried thinking about what output structure a generalised transducer would form, and came to the conclusion it was a foldable monoid i.e. pretty list-like.

From what I've seen Transducers tend to use Clojure's ambient state mechanics to get local state to each "transduction step". If you want to do away with that then you can embed the state in a Fold (which is basically a Moore FSA) and then think of transducers as Fold transformers which aren't allowed to touch their output.

"fundamental as function composition" is obviously subjective, but I think the point is that it seems you can make a fairly strong argument that in lisps, there is a question of what does the form (map f) eval to, and transducers put forth an answer that seems to be logically correct and superior to any alternatives. Hence, it seems fundamental.

I would suggest that there's a good chance that lenses (in particular, one subset of the general theory called Folds) are vastly more general.

I think the meaning is the following:

Function composition usually operates at non-collection type inputs. If you compose f and g, that usually means f takes some input and then g takes as input the output of g.

Transducers are a generalization of composition in the sense that it takes a collection of those inputs f would accepts.

So, in that sense, function composition could be a specific instance of transducers with number of inputs = 1.

It's much, much more of the opposite situation. Function composition can easily operate at collection type inputs---indeed, that is exactly how transducers operate.

Transducers are a subset of functions. They cannot be generalizing them.

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_tra...

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/

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-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.

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.

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.

Lazy evaluation can also be encoded fairly easily in strict languages using constructs like lazy stream abstractions.

Uh, sure but does any other language have a compiler that actually implements stream fusion?

I don't believe GHC actually does implement stream fusion. I think stream fusion happens with rewrite rules.

pardon my ignorance, but what would be the difference between the two? Don't rewrite rules happen in GCH anyway?

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.

ah that makes sense, thanks.

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

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.

There is also the dynamic language run-time (DLR), which as a generalization of LINQ (to support statements) is pretty powerful when writing up these tools on .NET. I use it often in my work.

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.

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.

Subset of high-order functions are more fundamental than operations defined for a whole set?)

Clojure's are more fundamental than other languages?

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?

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.

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.

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

Reply on news.ycombinator.com