Daniel Fischer
Am Montag 04 Januar 2010 16:30:18 schrieb Will Ness:
For me, a real smart compiler is one that would take in e.g. (sum $ take n $ cycle $ [1..m]) and spill out a straight up math formula, inside a few ifs maybe (just an aside).
Such things just aren't common enough. If you start letting the compiler look for patterns such as this which can be transformed into a simple formula, compile times would explode.
I was thinking more along the lines of inferencing compiler, proving new theorems about the types and applying that knowledge in simplifying the expressions. This would take time, so it should be a part of some interactive system, maybe kind of like Lisp has. In such a setting, the underlying compiler could first produce quick-n-dirty version, and would continue working in the background whenever the system is not busy, trying to improve the executable. Such a system would probably have to distinguish, at the type level, between [1..m] ; cycle [1..m] ; take n [1..m] ; etc. These would all be not just fuctions, but parts of a type's (here list) behaviour with automatically deduced semantics. What would such a type system be called?
The -fno-cse turns off Common Subexpression Elimination (rather sharing than elimination).
That is, if you have
f x = g (expensive x) y z (h (expensive x))
the compiler can see the common subexpression (expensive x) on the RHS and decide to share it, i.e. calculate it only once:
f x = let e = expensive x in g e y z (h e)
........
thanks for the in-depth explanation! :)
Now if you have a list producer and a consumer, without fusion, it goes like Consumer: Gimme Producer: creates cons cell, puts value, next cons cell (how to produce more) Consumer: takes value, does something with it, gimme more.
Stream fusion is about eliminating the cons cell creating and value passing, to fuse production and consumption into a nice loop. That is of course impossible if the produced list is shared between two (or more) consumers.
I would imagine so. Do I get this fusion on lists for free from the compiler, or do I have to recode for that? (haven't yet time to look into the article mentioned).
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe <at> haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe