memoize

[Guilherme Vieira]

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

> On Monday 03 January 2011 22:59:37 Guilherme Vieira wrote:
> > 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?
>
> @safe, @trusted, and @system have nothing to do with purity. If a function
> is
> marked as pure, then it's pure. If it's not, then it's not. End of story.
> Now,
> the concept of "weakly" pure functions was recently added, but all pure
> functions are still marked with pure. Strongly pure functions are pure
> functions
> where all of the parameters are immutable or implicitly convertible to
> immutable
> (so, immutable variables and value types). Weakly pure functions are pure
> functions whose parameters are not all immutable or implicitly convertible
> to
> immutable. Unlike strongly pure functions, they can alter their arguments.
> However, just like strongly pure functions, they cannot access globals or
> statics. Strongly pure functions can be optimized such that only one call
> to
> them is made in an expression because their return value will always be the
> same, and they cannot alter their parameters. Weakly pure functions cannot
> be
> optimized in that manner, but because they don't alter the global state,
> they
> can be safely called from strongly pure functions without violating the
> strongly
> pure function's purity.
>
> Pure is not logically pure for essentially the same reasons that const is
> not
> logically const. Making it logical instead of guaranteed eliminates the
> guarantees, and the compiler can no longer rely on those guarantees, making
> them
> _far_ less valuable.
>
> It is true that a memoized function must be logically pure, or you're going
> to
> get errors. However, if you were to force such functions to be pure, it
> would be
> highly limiting. And since memoize _can't_ be pure, it would make recursion
> with
> memoize impossible. True, allowing for memoized functions to be impure
> makes it
> so that the programmer must be more careful, but it's still quite useful -
> in
> fact more useful - that way. And since you _can't_ have memoize be pure
> anyway,
> it's not like you're losing any guarantees from the compiler like if you
> tried
> to make pure logically pure or const logically const.
>
> - Jonathan M Davis
>

Don't take me too seriously since I'm learning those things on-the-fly here
(I'm greedy). The const FAQ (
http://www.digitalmars.com/d/2.0/const-faq.html#logical-const) says D
doesn't support logical const because it would break transitivity, and they
deemed transitivity to be more important (Walter even thinks it's bad,
doesn't he?), so I understand why const in D is not logical const.

But in the case of memoize, aren't there things that can be done to the
language spec to allow it to be pure? Maybe by adding some language
construct, I dunno.

Or by analysis of behavior. Obviously, that wouldn't work for external C
functions, but at least memoize would be okay. Also, I'm to guess it would
be extremely hard to write a compiler that does this, but I'd just like to
confirm.

@Walter: would it be hard/impossible for the compiler to look at memoize and
tell it exhibits pure behavior and is, thus, pure?

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