memoize

[Guilherme Vieira]

On Tue, Jan 4, 2011 at 4:48 AM, Jonathan M Davis <jmdavisProg at gmx.com>wrote:

> 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
>

Ah, I was under the impression that @trusted was used to force purity.
Shame.. Sorry I mixed things up.

In any case, aren't those rules a bit too rigid? No matter how you look at
memoize, it should generate pure functions (since it exhibits pure nature,
are logically pure or whatever you call it). Would it be tough on the
compiler for it to actually find if a function is pure or not by a more
detailed analysis of its behavior?

-- 
Atenciosamente / Sincerely,
Guilherme ("n2liquid") Vieira
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20110104/71aaaa1d/attachment.html>