Memory allocation purity

[Steven Schveighoffer via Digitalmars-d]

On Thu, 15 May 2014 18:30:55 -0400, David Nadlinger <code at klickverbot.at>  
wrote:

> On Thursday, 15 May 2014 at 15:09:32 UTC, Steven Schveighoffer wrote:
>> But in this case, you have ignored the rules, […]
>
> Which rules exactly? My point is mainly that this area of the language  
> is underspecified.

The rules that we have been discussing, you cannot make significant  
decisions based on the addresses of 2 unrelated pointers.

>> This means format("%x", ptr) isn't allowed to be pure?
>
> The short answer would be: Yes. The alternatives seem to be:
>   - Disallowing memory allocations in pure code (not workable)
>   - Bidding farewell to the idea that pure + no mutable indirections  
> means FP-sense purity.

There is a 3rd option:

- FP purity, working fine as long as you don't do stupid things based on  
addresses. And even possibly working fine if you do stupid things based on  
addresses.

In other words, still assume FP purity, and if you expect randomness based  
on heap addresses to work, it just won't. Keep in mind, nothing discussed  
so far can cause invalid results. It just will be less random than  
expected. I really don't see a problem with this.

You are changing non-deterministic behavior to different, but still  
non-deterministic behavior. How do you even measure the impact?

>> What about calculating index offsets? Note that pointer math between  
>> two pointers on the same block of memory is perfectly legitimate.
>
> Taking offsets within the same block are fine. Even in the light of GC  
> allocations being pure, this doesn't lead to any non-determinism, as  
> there isn't any mechanism for the relative offset between whatever you  
> are considering to change without any outside input.

I think it is impossible to statically prevent address comparison between  
2 unrelated pointers, but statically allow address comparison between 2  
related ones. The compiler does not have the information to determine  
whether 2 pointers are related at compile time.

In fact, it may do BOTH!

bool foo(int *x, int *y) pure
{
    return x < y;
}

bool bar() pure
{
    if(foo(new int, new int)) // bad
    {
       int[10] x;

       return foo(x.ptr, x.ptr + 5); // ok
    }
    return false;
}


In the interest of nailing down what the rules SHOULD be (and I agree they  
need to be in the spec), here is a strawman to discuss:

You cannot do comparisons between two unrelated heap pointers that were  
allocated from the heap inside the same pure call. This only applies to  
the pointer values themselves, not the data pointed at (as long as that  
data is not a similar pointer).

I will define the "same pure call" as the function call into a pure  
function from a non-pure function.

Note, this is not a rule to implement as a static enforcement, it's one  
the programmer must not do. Like 'undefined behavior'. I don't think we  
can enforce it, as I mentioned above.

A lint tool may be able to catch it, and we can also possibly catch it at  
runtime, as long as the allocator can determine whether you're inside a  
pure function.

-Steve