Re: Memoization of pure-functional procedures

"Joachim Durchholz" <>
2 Jun 2002 01:40:32 -0400

          From comp.compilers

Related articles
Memoization of pure-functional procedures (Ray Dillinger) (2002-05-23)
Re: Memoization of pure-functional procedures (Bart Demoen) (2002-05-27)
Re: Memoization of pure-functional procedures (Robert A Duff) (2002-05-31)
Re: Memoization of pure-functional procedures (Joachim Durchholz) (2002-06-02)
| List of all articles for this month |

From: "Joachim Durchholz" <>
Newsgroups: comp.compilers
Date: 2 Jun 2002 01:40:32 -0400
Organization: Compilers Central
References: 02-05-115 02-05-160
Keywords: optimize
Posted-Date: 02 Jun 2002 01:40:32 EDT

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

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

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


Post a followup to this message

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