pure functions cannot be removed, actually: pure vs. total

[Steven Schveighoffer]

On 6/7/18 5:04 PM, Jonathan M Davis wrote:
> On Thursday, June 07, 2018 20:14:19 Johan Engelen via Digitalmars-d wrote:
>> On Tuesday, 5 June 2018 at 14:48:23 UTC, FeepingCreature wrote:
>>> I'm just posting to clear up the misunderstanding that a call
>>> to a pure function can be removed. Actually, even calls to
>>> strongly pure functions cannot always be removed. This is
>>> because there is one thing that a pure function can do that
>>> will change program behavior if it is removed, even if it does
>>> not change any global state whatsoever: it can simply never
>>> return.
>>>
>>> void foo() pure { while (true) { } }
>>
>> This is not a valid program, in my opinion. (Still only my
>> opinion, because I have not found it in the D spec, so needs
>> adding.)
>> A valid C++ program must make progress in each thread. C++ spec
>> states:
>> "The implementation may assume that any thread will eventually do
>> one of the following:
>> - terminate,
>> - make a call to a library I/O function,
>> - access or modify a volatile object, or
>> - perform a synchronization operation or an atomic operation."
> 
> I would be _very_ surprised if the D spec said anything like this simply
> because it doesn't do a lot of talking about conceptual stuff like this and
> talks a lot more about what the compiler actually does (or is supposed to
> do) - though that certainly doesn't mean that the spec shouldn't say
> something like that, and Walter has previously stated that anything that
> needs to be in the spec but isn't should be reported in bugzilla. So, if you
> have anything like this that you really think should be in the spec, please
> report it in bugzilla.
> 
> Regardless, I see zero value in supporting something like
> 
> void foo() pure { while(true) {} }

OK, so FeepingCreature has come up with an interesting case that's 
*similar* to this, and I think it makes things a little less cut and dry.

Let's say you have an infinite range that returns a single value. But 
instead of that value being stored in the range itself, it's an enum.

Maybe something like this:

struct Range
{
    enum empty = false;
    enum front = true;
    void popFront() pure nothrow {}
}

Now, let's say you ran find on it:

auto result = Range.init.find(false);

This *should* do an infinite loop. If it returned, it means that find 
has found where `false` is!

But let's dissect the call to `find`:

* It's a template, and everything that it calls, given this range is 
pure nothrow, so it is inferred pure nothrow.
* It accepts a type that has no mutable data.
* It returns a type that has no mutable data.
* The return type can be proven to not depend on the input.
* Therefore, it is a strong-pure function.

So logically, the compiler could assume if it thinks infinite loops are 
invalid, that it must return. Since it doesn't really need to call the 
function to see what it returns, it can just replace the code with:

auto result = Range.init;

And here, we have found `false` in an infinite range that only contains 
`true`.

So the danger of assuming no infinite loops is that some convoluted case 
like true.repeat.find(false) might incorrectly return something. Note 
that the repeat call wouldn't cause this problem, since it stores a 
mutable element inside it.

I still think that for void-returning functions we can simply assume to 
not do anything. Literally, the only thing it can do is return or 
infinite loop.

But I'm definitely not as sure as I was when I first responded to this 
thread.

-Steve