Steven Schveighoffer Wrote:

> "guslay" wrote
> > Janice Caron Wrote:
> >
> >> On 09/04/2008, Georg Wrede wrote:
> >>
> >>     int f(invariant D d) invariant pure { ... }
> >
> > Shouldn't it be
> >
> > int f(invariant D d) pure { ... }
> >
> > Pure functions are a subset of invariant functions, no?
> 
> No.
> 
> A function does not necessarily need to take an invariant 'this' pointer to be pure.
> 
> For example:
> 
> class C
> {
>    invariant int x;
>    pure int getX() { return x;}
> }
> 
> void foo()
> {
> C c = new C;
> c.getX(); // ok
> }
> 
> -Steve

c.getX() is equivalent to " int getX( ref C this ) ", so its not pure.

I will restate: Pure member functions are a subset of invariant member functions.

Steven Schveighoffer wrote:
> "Georg Wrede" wrote
> 
>>Janice Caron wrote:
>>
>>>On 09/04/2008, Denton Cockburn wrote:
>>>
>>>
>>>>>Of course, the explicit cast necessary to
>>>>>create an invariant C in the first place is a bit ugly. Maybe we need
>>>>>"inew" to make new invariant objects?
>>>>
>>>>Couldn't the compiler insert the cast based on the declaration?
>>>
>>>
>>>No, because objects created by new are not necessarily transitively
>>>unique. For example
>>>
>>>    class C
>>>    {
>>>        int * p;
>>>
>>>        this()
>>>        {
>>>            p = &someGlobalVariable;
>>>        }
>>>    }
>>>
>>>    invariant C c = cast(invariant) new C;
>>>    someGlobalVariable = 1;
>>>
>>>Whoops! c just changed!
>>>
>>>The explicit cast makes it the programmer's fault, not the compiler's!
>>>
>>>Come to think of it, "inew" would suffer the exact same problem, so it
>>>doesn't solve anything. Looks like there's no easy way to make an
>>>invariant class instance.
>>
>>It should be illegal to cast objects invariant unless the compiler can guarantee the invariantness. So the cast here should produce an error.
> 
> This cannot be guaranteed by the compiler.  It is depending on you to ensure that the object stays invariant. From http://www.digitalmars.com/d/2.0/const3.html
> 
> "The second way (to create invariant data) is to cast data to invariant. When doing so, it is up to the programmer to ensure that no other mutable references to the same data exist."

My mistake.

"guslay" wrote
> Steven Schveighoffer Wrote:
>
>> "guslay" wrote
>> > Janice Caron Wrote:
>> >
>> >> On 09/04/2008, Georg Wrede wrote:
>> >>
>> >>     int f(invariant D d) invariant pure { ... }
>> >
>> > Shouldn't it be
>> >
>> > int f(invariant D d) pure { ... }
>> >
>> > Pure functions are a subset of invariant functions, no?
>>
>> No.
>>
>> A function does not necessarily need to take an invariant 'this' pointer
>> to
>> be pure.
>>
>> For example:
>>
>> class C
>> {
>>    invariant int x;
>>    pure int getX() { return x;}
>> }
>>
>> void foo()
>> {
>> C c = new C;
>> c.getX(); // ok
>> }
>>
>> -Steve
>
> c.getX() is equivalent to " int getX( ref C this ) ", so its not pure.

AFAIK, C.getX() is equivalent to int getX(C this).

i.e. you can't change the this pointer to point to something else during the function.

I don't see why it's not pure.  I'm questioning the assertion that pure functions MUST take invariant reference types.  They can take mutable ones as long as they do not reference mutable data within the type.  It's the same reason you will be able to pass strings to a pure function.  A string is mutable, but the data it points to is not.

-Steve

"Georg Wrede" wrote
> Steven Schveighoffer wrote:
>>
>> 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?
>
> Before commenting on the rest,
>
> to me it is obvious that c is solely owned by f (because no references to c can exist outside of f), and therefore c is considered internal to f, so it's legal.

The whole problem comes from the parsing.  I'm not a guru when it comes to how D's grammar is structured, but I think it's supposed to be 'context free'?

So in the single statement:

c[0] = 'h';

and c's type is char[], how can the compiler be sure it's pointing to local data without context/analysis?

In my mind, I think that it should be allowed, but I'm just not sure how that can be implemented in a guaranteed fashion, and still keep the grammar context-free.  If c has it's own special 'pure' type, that's one thing, but I'm not sure how that works.  Maybe it just tags c as being local internally, just to check for purity...

-Steve

Steven Schveighoffer Wrote:

> AFAIK, C.getX() is equivalent to int getX(C this).
> 
> i.e. you can't change the this pointer to point to something else during the function.
> 
> I don't see why it's not pure.  I'm questioning the assertion that pure functions MUST take invariant reference types.  They can take mutable ones as long as they do not reference mutable data within the type.  It's the same reason you will be able to pass strings to a pure function.  A string is mutable, but the data it points to is not.
> 
> -Steve
> 

I can't think of a counter-example, you might be correct.

On 09/04/2008, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>  It's the
>  same reason you will be able to pass strings to a pure function.  A string
>  is mutable, but the data it points to is not.

No, that's because of Andrei's

    RULE 3:
    T implicitly converts to and from invariant(T) iff T refers to no
mutable memory

(from accu-functional.pdf)
Therefore, string implicitly casts to invariant(string).

Perhaps then, we may say that the parameters of a pure function should be invariant, or implicitly castable to invariant?

Of course, it's /possible/ to write a pure function that takes mutable pointers, e.g.

    int f(char[] s) pure?
    {
        return 42;
    }

but do we care? Wouldn't it just be easier to make that illegal and insist that the programmer rewrite the function more sensibly?

Steven Schveighoffer wrote:
> "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.

Ok. But I strongly resent being able to put the invariant either before or after the function name. It really gives the impression that it means something else.

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

>> And then,
>>
>>   int f(invariant D) invariant pure{ ... }
>>
> 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:

In A/W pure, where the reason for all this invariantness is optimization, it would seem hard to enforce, so it would be easier to simply forbid non-invariant arguments.

> f(int x)
> 
> Does x need to be invariant for f to be pure? 

Well, excluding A/W, the pureness of a function is within itself, and not in whether the arguments can change. But here it's different.

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

Generalising this, the point is to be able to make a local copy from data that potentially can change? Thus, the compiler can optimize relying on the now acquired invariantness.

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

Which would mean that if f initially makes a local copy of c.y, then everyting would be ok?

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

Ok. And the point being here is that a private copy is made. (Just making sure that _stack_ is not the keyword here. It might as well be on the heap (for example), /as long as/ f has the only reference to it. Of course normally it would be stack, of course.)

> f(S *s)
> 
> Now, f can still be pure, but it is not allowed to dereference s.

Which is useless, right? :-) But still "correct".

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

Agreed.

>>(1) Which leads to the thought: 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.

If there wasn't for the risk that this needs to be allowed as a potential product of some template stuff, I'd say this should have been made illegal, in the same sense as unreachable code: it makes no sense.

Steven Schveighoffer wrote:
> "Georg Wrede" wrote
>>Steven Schveighoffer wrote:
>>
>>>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?
>>
>>Before commenting on the rest,
>>
>>to me it is obvious that c is solely owned by f (because no references to c can exist outside of f), and therefore c is considered internal to f, so it's legal.
> 
> The whole problem comes from the parsing.  I'm not a guru when it comes to how D's grammar is structured, but I think it's supposed to be 'context free'?
> 
> So in the single statement:
> 
> c[0] = 'h';
> 
> and c's type is char[], how can the compiler be sure it's pointing to local data without context/analysis?

Well, the localness of c is established with char[] c on the preceding line. And since D relies on bounds checking (not in release code, but in its Philosophy), c[0] is "local" too, for the purposes of this discussion.

> In my mind, I think that it should be allowed, but I'm just not sure how that can be implemented in a guaranteed fashion, and still keep the grammar context-free.  If c has it's own special 'pure' type, that's one thing, but I'm not sure how that works.  Maybe it just tags c as being local internally, just to check for purity...

The compiler has to keep track of local variables anyhow.

"Janice Caron" wrote
> On 09/04/2008, Steven Schveighoffer wrote:
>>  It's the
>>  same reason you will be able to pass strings to a pure function.  A
>> string
>>  is mutable, but the data it points to is not.
>
> No, that's because of Andrei's
>
>    RULE 3:
>    T implicitly converts to and from invariant(T) iff T refers to no
> mutable memory

Hm.. I glossed over that rule :)  But by the same rule, my example class C should be implicitly castable to invariant, but in the case where C has invariant and mutable parts, then this is not the case...  I was thinking a different rule (for pure functions) would be more appropriate:

Disallow access to non-invariant data

Should be changed to:

Only allow access to invariant and local data.

>
> (from accu-functional.pdf)
> Therefore, string implicitly casts to invariant(string).
>
> Perhaps then, we may say that the parameters of a pure function should be invariant, or implicitly castable to invariant?

Hopefully not the former, as working with invariant data when one doesn't have to makes things really cumbersome.  If it's implicitly castable to invariant, then it's implicitly castable from invariant, I'd rather have the mutable version :)

>
> Of course, it's /possible/ to write a pure function that takes mutable pointers, e.g.
>
>    int f(char[] s) pure?
>    {
>        return 42;
>    }
>
> but do we care? Wouldn't it just be easier to make that illegal and insist that the programmer rewrite the function more sensibly?

I'm thinking more of the case where an argument is a mutable stack pointer (meaning it is a pointer, but only exists in the pure function's stack) to a chunk of data that has both mutable and invariant pieces.  i.e.:

class C
{
    int *m;
    invariant(int *) i;
}

pure int getI(C c)
{
    return *i;
}

There may be a reason to use i, but not m in a pure function.  Why should pure restrict this?  It's technically correct and statically verifiable.

-Steve

On 09/04/2008, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>  A function does not necessarily need to take an invariant 'this' pointer to
>  be pure.
>
>  For example:
>
>
>  class C
>  {
>    invariant int x;
>
>    pure int getX() { return x;}
>  }
>
>  void foo()
>  {
>  C c = new C;
>  c.getX(); // ok
>  }

OK, I'm gonna risk it. :-)

Andrei proposes a new feature, *invariant constructors*, which are constructors with special rules to ensure that pointers to mutable memory, however, my interpretation of accu-functional.pdf is that invariant constructors will cause the /entire class/ to be created invariant. Thus, one would write

    class C
    {
        int x;

        this(int n) invariant
        {
            x = n;
        }

       int getX() invariant pure
       {
           return x;
       }
    }

    invariant c = new C(4);
    int n = c.getX;

My interpretation is that the invariant constructor will construct a /completely invariant/ object. In that case, there can never be any such thing as a non-invariant C.

What you're describing is something different - a non-invariant class with invariant members. Well, the only time you can assign an invariant member is at compile-time. That means they have to be assigned with compile-time constants. That, in turn, means they might as well be static, because they are not going to differ from instance to instance. And /that/ means you can rewrite your counterexample as

    class C
    {
        static invariant int x = 4;

        static int getX() pure
        {
            return x;
        }
    }

    auto c = new C(4);
    int n = c.getX;

Now getX() is pure because it's static, and therefore /has/ no this pointer.

In conclusion, it may well be that D will insist that all parameters of pure functions be completely invariant. I don't know that for /sure/, but that would be my guess.