[Haskell-cafe] Re: FASTER primes

Will Ness will_n48 at yahoo.com
Tue Jan 5 04:33:19 EST 2010

Daniel Fischer <daniel.is.fischer <at> web.de> writes:

> 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 

> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

More information about the Haskell-Cafe mailing list