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

On 9/6/06, Sebastian Sylvan wrote:

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

Sorry, the facArr needs to be toplevel otherwise it probably won't retain it's values. So something like: module Fac (fac) where -- we don't export fac' only fac import Data.Array fac n | n <= 100 = facArr ! n | otherwise = fac' n fac' x = product [1..x] facArr = listArray (1,100) (map fac' [1..100]) -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862