Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Clojure's Transducers are as fundamental as function composition

thecomputersarewinning.com

Post reply on HN
Print view View original

31–40 of 49 posts

Re: Clojure's Transducers are as fundamental as function composition

#31

Post by gazarsgo »

jeremyjh wrote: post #13
seanmcdirmid wrote: post #6

Earlier quoted context omitted.

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?

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.

Re: Clojure's Transducers are as fundamental as function composition

#33

Post by rebcabin »

tel wrote: post #30
DanWaterworth wrote: post #27

Earlier quoted context omitted.

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

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

Re: Clojure's Transducers are as fundamental as function composition

#35

Post by tel »

rebcabin wrote: post #33
tel wrote: post #30

Earlier quoted context omitted.

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

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

Re: Clojure's Transducers are as fundamental as function composition

#36

Post by tel »

anon4 wrote: post #34

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.

Re: Clojure's Transducers are as fundamental as function composition

#37

Post by tel »

rebcabin wrote: post #32

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

Re: Clojure's Transducers are as fundamental as function composition

#38

Post by tel »

gfodor wrote: post #21
tel wrote: post #5

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 f…

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

Re: Clojure's Transducers are as fundamental as function composition

#39

Post by vorg »

judk wrote: post #9
tel wrote: post #5

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 f…

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…

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.

Re: Clojure's Transducers are as fundamental as function composition

#40

Post by tel »

vorg wrote: post #39
judk wrote: post #9

Earlier quoted context omitted.

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…

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 e…

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

Post reply on HN