In the latest D2, both the frontend and backend support use and optimization when user code declares pure code. This isn't particularly useful when pure functions can't call standard library code.

When considering the standard library changes, I realized that object.d could change. I believe a pure opCmp or toString could break user code with impure versions of those functions. Would that kind of a change to object.d cause any real problems for D2 users?

Are there other ambiguous purity options when converting the standard libraries? Which parts of Phobos/druntime would you expect to be pure/impure?

Jason House wrote:
> When considering the standard library changes, I realized that
> object.d could change. I believe a pure opCmp or toString could break
> user code with impure versions of those functions. Would that kind of
> a change to object.d cause any real problems for D2 users?

As Andrei pointed out, the trouble with making the Object functions pure is if you want to do an override that caches its value.

Walter Bright Wrote:

> Jason House wrote:
> > When considering the standard library changes, I realized that object.d could change. I believe a pure opCmp or toString could break user code with impure versions of those functions. Would that kind of a change to object.d cause any real problems for D2 users?
> 
> As Andrei pointed out, the trouble with making the Object functions pure is if you want to do an override that caches its value.

If you have:

class A {
    invariant final pure bool opEquals(invariant(Object) other) { ... }
}

int main() {
    auto a = cast(invariant) new A();
    auto b = cast(invariant) new A();
    if(a1 == a2) { return 0; } else { return 1; }
}

... will the compiler optimize it? Since A.opEquals() is final, there's no polymorphism, so it should be able to, but I don't know about the implementation.

Robert Fraser wrote:
> ... will the compiler optimize it? Since A.opEquals() is final,
> there's no polymorphism, so it should be able to, but I don't know
> about the implementation.

It should optimize it.

Walter Bright Wrote:

> Jason House wrote:
> > When considering the standard library changes, I realized that object.d could change. I believe a pure opCmp or toString could break user code with impure versions of those functions. Would that kind of a change to object.d cause any real problems for D2 users?
> 
> As Andrei pointed out, the trouble with making the Object functions pure is if you want to do an override that caches its value.

One could easily generalize that to mean non-final virtual functions should never be pure. Memoizaton is a pretty basic need. I thought that was in D's future. Is that not true?

Jason House wrote:
> Walter Bright Wrote:
> 
>> Jason House wrote:
>>> When considering the standard library changes, I realized that object.d could change. I believe a pure opCmp or toString could
>>> break user code with impure versions of those functions. Would
>>> that kind of a change to object.d cause any real problems for D2
>>> users?
>> As Andrei pointed out, the trouble with making the Object functions
>> pure is if you want to do an override that caches its value.
> 
> One could easily generalize that to mean non-final virtual functions
> should never be pure. Memoizaton is a pretty basic need. I thought
> that was in D's future. Is that not true?

Memoization and purity don't mix. 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.

Walter Bright wrote:

> Memoization and purity don't mix.

True, but...

All pure functions can be memoized.  They can be memoized by the caller of the pure function, or the pure function could be rewritten to automatically memoize.

When writing a pure but potentially costly function, the coder may consider memoization.  They must predict how frequently the function would get called with the same input.  They must also decide if the time/space trade-off is worth it for the program as a whole and how inconvenient it would be to call the function.  If it's called from another pure function, well... they don't mix.

All-in-all, memoization is a tough call to make.  For library writers, it's even tougher.  They may not know how their code would get used and may be unable to make the call about memoization.  It's possible to provide a pure function and a memoized alternative.  Of course, there are many memoization options available, especially when memory space is restricted or various thread safety/locking methods may be desired.  A library writer may just declare that if the user wants memoization that they should use a memoization library to do it.

Anyone who writes an inheritable classes also have to predict if the writers of classes that inherit from their class will want to memoize or not.  Some may forbid it because then they can declare the function pure.  Others will feel like they can't declare any virtual functions as pure (and therefore allow memoization).

> 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.

I do think that writers of generic/library/inheritable code will continuously revisit the question of memoization.  That may affect the future of D usage, but not the underlying language specification.

Jason House wrote:
> 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.

Another word for that is "common subexpressions". And yes, the compiler has the option to do that, and in fact does do that (in a small way) in the latest release. But what I was talking about is the user himself doing memoization.

On 2009-01-09 20:45:57 -0500, Jason House <jason.james.house@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@michelf.com
http://michelf.com/

Michel Fortin wrote:
> Hum, could the compiler be trusted to add the memoization code to pure functions so they can stay pure?

If the compiler does general memoization on pure functions, all it has to do is use the bits of the arguments passed on the stack to the function as an index into an associative array of the return values.

The problem is identifying if this would be faster than recomputing the return value.