Purity (D2 standard libraries / object.d)

Michel Fortin michel.fortin at michelf.com
Fri Jan 9 18:27:21 PST 2009


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.

-- 
Michel Fortin
michel.fortin at michelf.com
http://michelf.com/




More information about the Digitalmars-d mailing list