Purity (D2 standard libraries / object.d)

[Andrei Alexandrescu]

Michel Fortin wrote:
> On 2009-01-09 20:45:57 -0500, Jason House <jason.james.house at gmail.com> 
> said:
> 
>>> For each function, you'll have to pick
>>> which way you want to go. I don't see what that has to do with D's
>>> future, though, the language allows either.
>>
>> Somehow, I had the impression that D might use memoization as some 
>> kind of optimization once pure functions are embraced.  That was 
>> probably a misunderstanding on my part.
> 
> Hum, could the compiler be trusted to add the memoization code to pure 
> functions so they can stay pure? Something like this:
> 
>     pure memoize int costlyCalculus(int i, int j)
>     {
>         return i + j;
>     }
> 
> being transformed into this by the compiler?
> 
>     int[TypeTuple!(i, j)] _costlyCalculus_cache;
>     pure int costlyCalculus(int i, int j)
>     {
>         {
>             int* _found_result = Tuple!(i, j) in _costlyCalculus_cache;
>             if (_found_result)
>                 return _found_result;
>         }
>         {
>             int _calculated_result = i + j;
>             _costlyCalculus_cache[Tuple!(i, j)] = _calculated_result;
>             return _calculated_result;
>         }
>     }
> 
> Surely this way the compiler would be able to bypass purity checks for 
> accessing the cache while still ensuring that the function has no side 
> effect and always return the same result for the same arguments. The 
> downside being that a hash table may not always be the best memoization 
> technique.
> 
> Perhaps then it belongs more in the standard library.
> 
>     pure int costlyCalculus(int i, int j);
>     Memoizer!(costlyCalculus) memoizedCostlyCalculus;
> 
> where Memoizer is a struct template defining a pure opCall and 
> containing the cache it can access by casting away purity in a few 
> places. But it makes it more difficult to add memoization while 
> overriding a function.
> 

Yes!

Memoization is One Great Litmus Test of compile-time reflection. I 
implemented a couple of simple memoizers along the lines you mention, 
and I plan to make memoization examples part of TDPL.

The Even Greater Litmus Test would be to expose the memoizer itself as a 
pure function (which it essentially is).


Andrei