memoize

[Jonathan M Davis]

On Monday 03 January 2011 22:17:52 Guilherme Vieira wrote:
> On Tue, Jan 4, 2011 at 4:05 AM, Andrew Wiley <debio264 at gmail.com> wrote:
> > On Mon, Jan 3, 2011 at 10:15 PM, Andrei Alexandrescu <
> > 
> > SeeWebsiteForEmail at erdani.org> wrote:
> >> I just added a higher-order function memoize to std.functional which I
> >> think is pretty cool. See the docs here:
> >> 
> >> 
> >> http://d-programming-language.org/cutting-edge/phobos/std_functional.htm
> >> l#memoize
> >> 
> >> I'm also thinking of adding that cutting-edge directory as a place for
> >> storing documentation for commits that are in flux but not officially
> >> released yet.
> > 
> > Pretty sweet, but if I'm understanding this correctly, the memoized
> > version of a pure function isn't pure, is it? Is there any way to get
> > that to happen?
> 
> memoize uses a static variable. Are static variables considered "global" as
> far as pure functions are concerned? If not, then I see no reason for it
> not to be pure, or am I missing something?
 
pure functions cannot access mutable globals or static variables. If they could, 
they could end up returning a different result with the same parameters because 
the global or static variable changed.
 
> Additionally, I don't understand this:
> 
> "Technically the memoized function should be pure because memoize assumes
> it
> 
> > will always return the same result for a given tuple of arguments.
> > However, memoize does not enforce that because sometimes it is useful to
> > memoize an impure function, too."
> 
> Wouldn't memoizing an impure function be a.. bug? It would return the same
> cached value when in fact it should have returned something else based on
> external factors. When can that be desirable?

It's quite easy to have a function which you cannot actually make pure but which 
you know to be logically pure. For instance, if a function called a C function, 
it can't be pure unless you play some games with function pointers and casting 
and the like. So, really, any function which calls a C function can't be pure. 
However, it's pretty easy to have a C function which is logically pure. So, your 
D function is then logically pure, but it's not actually pure, so pure functions 
can't call it. But it would work just fine with memoize. Sure, it's definitely 
less safe to use impure functions with memoize, and it could cause bugs, but 
that doesn't mean that it shouldn't necessarily be disallowed. It just means 
that if the programmer wants to use memoize, they're going to have to be aware 
that it could cause bugs if the function in question should actually be 
returning a different value on future callls.

- Jonathan M Davis