On 9/6/06, Sebastian Sylvan <[EMAIL PROTECTED]> wrote:
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])
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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
