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

41–49 of 49 posts

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

#41

Post by seanmcdirmid »

gazarsgo wrote: post #31
jeremyjh wrote: post #13

Earlier quoted context omitted.

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.

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.

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

#42

Post by metasoarous »

tel wrote: post #40
vorg wrote: post #39

Earlier quoted context omitted.

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

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

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

#43

Post by moomin »

DanWaterworth wrote: post #16
tel wrote: post #14

Earlier quoted context omitted.

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

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 (:) []

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.

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

#44

Post by riffraff »

DanWaterworth wrote: post #26
riffraff wrote: post #20

Earlier quoted context omitted.

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.

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

#45

Post by vorg »

metasoarous wrote: post #42
tel wrote: post #40

Earlier quoted context omitted.

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.

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

#46

Post by tel »

vorg wrote: post #45
metasoarous wrote: post #42

Earlier quoted context omitted.

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…

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.

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

#47

Post by tel »

moomin wrote: post #43
DanWaterworth wrote: post #16

Earlier quoted context omitted.

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 (:) []

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

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

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

#49

Post by moomin »

tel wrote: post #47
moomin wrote: post #43

Earlier quoted context omitted.

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

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.
Post reply on HN