On 9/6/06, Stephane Bortzmeyer <[EMAIL PROTECTED]> wrote:
On Wed, Sep 06, 2006 at 02:12:28PM +0100,
Sebastian Sylvan <[EMAIL PROTECTED]> 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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
