Fully transitive const is not necessary

[Bill Baxter]

Walter Bright wrote:
> Bill Baxter wrote:

>> If so, that seems unnecessarily restrictive to me.  Any side effect or 
>> indeterminacy of f() in that case is not because of f()'s doing.  So 
>> f()'s behavior *is* pure even if it takes a const argument.  It's not 
>> f's fault if the environment it's living in is unstable.
> 
> A function is pure or it isn't, there really isn't any room for 
> "unstable" purity, or the point of purity is lost.
> 
> Look at it another way. You can take the value of the bits pushed on the 
> stack as arguments to a pure function, and compare that with previous 
> bits passed to the same function, and if there's a binary bit match, you 
> can skip calling the function and return a previously cached result.
> 
> If that cannot be done, then the function is NOT pure.

If you want to define it that way then ok.  So lets say the kind of 
function I'm talking about would be labeled "nosfx".

>> Maybe there need to be two levels of pure?  One says this function by 
>> itself has no side effects, the other says additionally that the 
>> function is invariant with respect to the environment.  The former 
>> category of functions can all be run in parallel safely provided there 
>> are no other threads modifying the environment simultaneously.
> 
> No, you cannot run them simultaneously. The problem with const (instead 
> of invariant) is that the transitive state of the passed object is NOT 
> guaranteed to be the same:
> 
> pure int foo(const C c) { return c.p[0]; }
> class C { int* p; }
> C c;
> c.p = q;
> int i = foo(c);
> q[0] = 3;
> int j = foo(c);
> 
> Note that these foo's cannot be run in parallel, despite c never having 
> been changed. I think that notion of purity is not useful.

They can be run in parallel, as long as you don't stick non-pure 
mutating operations in between them.

That's quite useful for automatically parallelizing tight loops like this:

nosfx int foo(const C c) { return c.p[0]; }
...

C[] array;
...// put bunch of C's in array
int sum = 0;
foreach(c; array) {
    sum += foo(c);
}

Those foreach bodies could be run in parallel (with appropriate reduce 
logic added to handling of 'sum' by compiler) since we know each call to 
foo() in that loop has no external side effects.

This is the kind of thing OpenMP lets you do with directives like 
"#pragma pfor reduce".  Except I don't believe OpenMP has any way to 
verify that foo() is really side-effect free.

--bb