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

[Sebastian Sylvan]

On 9/6/06, Stephane Bortzmeyer <bortzmeyer at nic.fr> wrote:
> On Wed, Sep 06, 2006 at 02:12:28PM +0100,
>  Sebastian Sylvan <sylvan at student.chalmers.se> 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