Re: Memoization of pure-functional procedures

Robert A Duff wrote:
> Automatic memoization seems like a cool thing to do, but I would think
> the programmer should have some control over which procedures this is
> applied to.


Actually you wouldn't want automatic memoization, since you lose
control over the memory footprint of your software. In particular if
the function has multiple parameters, you'll get a combinatorial
explosion in the table size. Automatic memoization would also have to
take into account that some functions are faster than the table looup
involved.


Most functional languages seem to memoize only where the programmer
requests it. And what's memoized is usually not a function but a
specific result.
Functional languages tend to allow expressions like
      let foo = some complicated expression
      in blah (foo, foo + 2, foo / 5)
or, the other while round,
      blah (foo, foo + 2, foo / 5)
      where foo = some complicated expression
with the understanding that foo is evaluated just once. (Which is
allowed if the complicated expression that makes up "foo" is pure.)


IOW memoization is more common and more useful on expressions, and
there's no need to make it automatic because programmers want to write
the "let" or "where" expression anyway, to avoid redundancy in their
software.


Some languages also offer a "memoize" function which takes a function
and returns the function with a memoization machinery wrapped around
the function. But this is more an afterthought than a regularly used
feature.


Regards,
Joachim

Return to the comp.compilers page.
Search the comp.compilers archives again.