memoize

[Jonathan M Davis]

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