I just got it! (invariant/const)

[Steven Schveighoffer]

"Georg Wrede" wrote
> Jason House wrote:
>> Consider this example:
>>
>> class D{
>>   void invMemberFunc() invariant; // not pure
>> }
>>
>> class C{
>>   int f(invariant D) invariant pure{
>>     D.invMemberFunc(); // illegal
>>   }
>> }
>
> ((Upon proofreading it dawned to me that the example above may contain 
> errors, but for the sake of clarity, somebody still explain.))
>
> Not being an expert on this stuff, I have to ask:
>
>   void invMemberFunc() invariant; // not pure
>
> What does it actually mean? A function taking no arguments, returning 
> nothing? If it has no side effect, then it has no bearing on the program, 
> therefore, it essentially is a null function, doing nothing. Or, if it has 
> side effects, then the whole question is about: Do we allow or disallow 
> pure functions calling member functions with intra-object side-effects. 
> (And as far as I understand it, currently this is considered illegal, but 
> just may become legal in D3 -- if it /really/ then seems like a warranted 
> idea.) (1)
>
> And then it is /invariant/. What exactly does the word invariant mean in a 
> function definition when it's after the function name? That it requires 
> the argument to be an invariant? (I sure hope it's not some property 
> "invariant" of the function, meaning somehow that it doesn't change 
> (whatever)).

It means that the 'this' pointer is invariant.  We don't see the body of the 
function, so we don't know if it's pure or not.

However, the point is, since it is not *declared* pure (we don't know the 
correct syntax for this by the way because it doesn't exist yet!), the 
compiler doesn't know whether it has side effects or not.  Remember, Walter 
and Andrei are trying to create a statically verifyable functional 
programming construct.  This means that the compiler doesn't just *assume* 
that a pure function has no side effects, it *guarantees* that the function 
has no side effects.

> Along the same lines (please anybody explain),
>
>   int f(invariant D) invariant { ... } //omitting pure here for now
>
> What does that mean? Like, one would understand the latter invariant on 
> the line to mean that you only can pass invariant data to the function, 
> but then the former invariant on the line would be superfluous, right?

Not exactly, it is another way of saying that the 'this' pointer is 
invariant.

>
> And then,
>
>    int f(invariant D) invariant pure{ ... }
>
> If the function is pure, then should that now implicitly demand an 
> invariant argument? (At least as far as I've understood anything about 
> this D version.) And therefore actually /both/ invariants are superfluous 
> in the definition.

Not necessarily :)  A pure function can take non-invariant arguments, it 
just can't use the non-invariant pieces of that.  Yeah, I know you just did 
a double take :)  But think about this:

f(int x)

Does x need to be invariant for f to be pure?  No, because every time we 
call x, we create a COPY of x on the stack, which means f has it's own 
private copy that isn't invariant, but f is guaranteed that nothing else 
will change it.  Now if we have:

f(int *x)

Does x need to be invariant for f to be pure?  Actually, no :)  Because f is 
STILL given a stack variable, which happens to be a pointer to mutable data. 
If f dereferences x, then it cannot be pure unless x is invariant.  See the 
difference?  Now the real crux of the issue:

class C
{
   invariant int x;
   int y;
}

f(C c)

Does c need to be invariant for f to be pure?  No.  Because c is still a 
stack variable, which is a reference to an instance of C.  However, in order 
for f to be declared pure, it can only access c.x, it cannot access c.y, 
because c.y might change.

What about structs?

struct S
{
   int x;
}

f(S s)

Again, s does not need to be invariant, because the entire struct is copied 
onto the stack.  This is similar to the f(int) case.

f(S *s)

Now, f can still be pure, but it is not allowed to dereference s.

The rules for pure are:

can only access:
- local variables (mutable, invariant or const)
- invariant data that is referenced by local variables (a class is 
intrinsically a reference, so class instances fall under this category)
- pure functions

There are interesting puzzles that I'm not sure how they will be solved. 
For example:

pure int f()
{
   char[] c = new char[15];
   c[0] = 'h'; // does this compile?
}

Does c need to be invariant to access members of the array?  Clearly from 
this code, you can see that c is private to f.  But under the rules, the 
data c references is not invariant, and so should be inaccessible.  How will 
the compiler make this distinction?

>
> Finally,
>
>> class D{
>>   void invMemberFunc() invariant; // not pure
>> }
>>
>> class C{
>>   int f(invariant D) invariant pure{
>>     D.invMemberFunc(); // illegal
>>   }
>> }
>
> Since invMemberFunc is not pure, then using it in f should really be 
> illegal. Syntactically, that is, per definition. This because other 
> alternatives would be too complicated for the compiler (and the 
> programmer) to be practical.
>
> The above example might be clearer (at least to me :-), and depending of 
> course on what exactly you are asking... ) if it said
>
> class D {
>   int invMemberFunc(int i) invariant; // not pure
> }
>
> class C {
>   int e;
>   invariant int g;
>   int f(invariant D d) invariant pure{
>     e = d.invMemberFunc(g); // illegal
>   }
> }

Whether invMemberFunc takes or returns an int or not is irrelevant :)  The 
fact that it is invariant means it can still might change global data, and 
so it might not be pure.  It could be pure in the sense that it does not 
change global data, but because we didn't declare it pure, the compiler 
cannot know whether it is pure or not, and so it errs on the side of 
caution.

Note that passing in an int and returning an int does not mean it can't be 
pure.  I know you didn't get that when you wrote the post, but I want to 
emphasize it for other readers...

> (1) Which leads to the tought: since a pure function can't call other 
> functions to use their side effects, the only reason left to call a 
> function is to get it's value. From which follows that calling void 
> functions should be made illegal! On the grounds that there is no point in 
> calling such a function in the first place. (This as part of the 
> "barriers" mentioned in the post 69190 "What is pure and what is not 
> pure".)

This is true, calling a pure function which returns nothing makes no sense, 
but clearly this function can be pure:

void f() {return;}

as it has no side effects :) Should it be illegal?  I'd say no.  Useless, 
but not illegal.

-Steve