[Haskell-cafe] Re: does the compiler optimize repeated calls?

On 9/6/06, Stephane Bortzmeyer wrote:

On Wed, Sep 06, 2006 at 02:12:28PM +0100, Sebastian Sylvan wrote a message of 36 lines which said:

...

I think most compilers actually do CSE

And automatic memoization? Because common subexpressions can be difficult to recognize but, at run-time, it is much easier to recognize a function call that has already been done. Any common compiler / interpreter which automatically memoizes? In theory, it is also a huge advantage of "pure" functional programming languages.

Not that I'm aware of. I don't think it's very easy to do well. The compiler would have to keep a buffer of input/output pairs for each function (even ones which never gets called with the same input twice) which eats up memory - it's probably very difficult to statically say anything about the frequency of certain inputs to functions so you'd have to store caches for every function in the program. If you have a function with a certain range which is used often, it's very easy to do memoization yourself in Haskell (untested!): import Data.Array fac n | n <= 100 = facArr ! n | otherwise = fac' n where fac' x = product [1..x] facArr = listArray (1,100) (map fac' [1..100]) Basically this stores the first 100 fac numbers in an array (note that the contents of the array is lazily evaluated, each entry gets evaluated the first time it is required), and checks against that first, reverting to the regular fac function for all other inputs. /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862