Purity of Memoized Functions in D

Question

Are there any clever ways of preserving purity when memoizing functions in D?

I want this when caching SHA1-calculations of large datasets kept in RAM.

Answer 1

Short answer: Pick memoization or purity. Don't try and have both.

Long answer: I don't see how it would be possible to preserve purity with memoization unless you used casts to lie to the compiler and claim that a function is pure when it isn't, because in order to memoize, you have to store the arguments and the result, which breaks purity, since the number one guarantee of pure functions is that they don't access mutable global or static variables (which is the only way that you'd be able to memoize anything).

So, if you did something like

alias pure nothrow Foo function() FuncType;
auto result = (cast(FuncType)&theFunc)();

then you can treat theFunc as if it were pure when it isn't, but then it's up to you to ensure that the function acts pure from the outside - including dealing with the fact that the compiler thinks that it can change the mutability of the return type of a strongly pure function which returns a mutable type. For instance, this code will compile just fine

char[] makeString(size_t len) pure
{
    return new char[](len);
}

void main()
{
    char[] a = makeString(5);
    const(char)[] b = makeString(5);
    const(char[]) c = makeString(5);
    immutable(char)[] d = makeString(5);
    immutable(char[]) e = makeString(5);
}

even though the return type is always mutable. And that's because the compiler knows that makeString is strongly pure and returns a value which could not have been passed to it - so, it's guaranteed to be a new value every time - and therefore changing changing the mutability of the return type to const or immutable doesn't violate the type system.

If you were to do something inside of makeString that involved casting a function to pure when it violated the guarantee that makeString always returned a new value, then you'd have broken the type system, and you'd be risking having very buggy code depending on what you did with the values returned from makeString.

The only way that I'm aware of getting purity when you don't have it is to cast a function pointer so that it's pure, but if you do that, then you must fully understand what guarantees a pure function makes and what the compiler thinks that it can do with it so that you fully mimic that behavior. That's easier if you're returning immutable data or a value type, because then you don't have the issue of the compiler changing the mutability of the return type, but it's still very tricky business.

So, if you're thinking about casting something to pure, think again. Yes, it's possible to do some stuff that way that you couldn't otherwise, but it's very risky. Personally, I'd advise that you decide whether purity matters more to you or memoization matters more to you and that you drop the other. Anything else is highly risky.