== Quote from Sean Reque (seanthenewt@yahoo.com)'s article
> Steven Schveighoffer Wrote:
> > "Sean Kelly" wrote
> > > == Quote from Janice Caron article
> > >> ...which raises an interesting point. Can "synchronized" be used on a const object? What about an invariant object?
> > >
> > > They'll work just fine with const objects in D.  Object monitors in D
> > > currently
> > > live outside the const checking scheme.
> >
> > Oh so you mean Walter couldn't implement mutexes without logical const huh? I think this part of the system should be ripped out and you should have to pass mutexes along with objects everywhere you want to ensure thread safety and const is transitive.  That's easier and less obfuscated, right?
> >
> > -Steve
> >
> >
> The whole point of invariant objects and pure functions in terms of thread safety is that you don't
need any form of synchronized data access. If, for instance a piece of data is guaranteed not to change, then two cores can hold two separate copies of the same data in each of their local caches instead of having to fetch the same data from an external source. Requiring synchronization on all const objects would entirely defeat optimizations like these.


As I've illustrated previously, invariance doesn't eliminate the need for synchronization.
It's true that if two threads have existing reference to a shared piece of invariant data
then further accesses of that data do not need to be synchronized, but unless the data
exists in ROM or was created at application start time there must be a synchronization
point involved when each new thread obtains a reference to this data.  If this were not
the case, lock-free programming would be largely unnecessary or at least painfully
simple.  The problem with shared-memory multiprogramming is the fact that memory
is shared.  Functional languages are good for multiprogramming because they don't
have any shared data, not because their data is all invariant (though I believe the latter
should help for additional automatic parallelization of loops and such even though
that's not commonly done today AFAIK).


Sean

Walter Bright wrote:
> Bill Baxter wrote:
> 
>> So does that mean
>>
>>   pure int f(const Class c)
>>   { ...
>>   }
>>
>> will *not* be allowed?  Because some part of c *could* change, even if it's not f() doing the changing.  I.e. another thread could be changing c concurrently.
> 
> Right. That declaration of f is erroneous.

I'd disagree.

Whether a function is pure or not, has nothing to do with whether c could change or not.

Take, for example sin(x). We all know that it's pure, period. Now, whether x changes between two consecutive invocations or not, is irrelevant. Of course you get a different result. And you should.

But pure, IMHO, means (1) the function is guaranteed to give the same result every time /if/ the input is the same (like sin(x) does), (2) it does not change anything at all anywhere, it's only way of affecting life is by its return value, (3) it doesn't access info from non-constants anywhere.

Now, to the issue between

    (1)pure int f(const Class c)
    (2)pure int f(Class c)

I'd say that, since a Pure function promises not to change /anything/ (other than its return value, of course) anywhere, this means a pure function /simply has to implicitly treat its arguments as unchangeable/!

Therefore, depending on what A/W want, either:

 - a pure function has to have const decorated parameters only (1)
 - and (2) would be a syntax error

or

 - a pure function's parameters are implicitly const, and (1) is then a syntax error

(Not making the latter a syntax error isn't technically impossible, but for those learning the language and the casual readers of ex. magazine articles, this would wreak havoc with their understanding D.)


*Back to concurrency*, if someone changes c in mid-run, then it's the programmer's fault. It's his headache. The function f only guarantees not to change c /by itself/.

If the programmer wants to guarantee that c doesn't change during f's invocation, then the invocation of f should be put in a synchronized block. This might be the case if c has a complicated state (with several fields).

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

I wonder if that's so simple when we allow non-POD type arguments?

Of course, if you're speaking metaphorically here, then that's another thing. But the same literal bit pattern of course could mean the same object referred to, only that now it suddenly contains other data.

To further clarify,

If a pure function gets a tree t passed to it, and makes a (potentially very complicated and) deep search into it, then the only thing the function's pureness guarantees is that if the particular nodes and leaves it's looked at stay the same, then it should return the same result the next time.

The rest of the tree could undergo severe changes in between, or even during an invocation of the pure function, for all it knows. (Of course this is academic, but tries to illustrate the issue literally.)

In practice we wouldn't want that, but that's not relevant to the Pureness Issue.

Sean Kelly wrote:
>> If C.name were invariant, there would be no need for any locks. I don't
>> think this is a good example, because with D's invariant strings there
>> is no need for such locking.
> Also, I believe my example demonstrated that memory fences and order
> of evaluation issues are still a concern with invariants.  They aren't a
> magical safe ticket to lock-free programming land.

While creating an invariant is something that should be done with care, once it is created, locks are no longer needed on it. After all, since it cannot change, where is the need to sync it?

> Let me re-iterate my point by saying that the /only/ feature provided by
> invariants is that once invariant data is shared through a properly
> synchronized method, the invariant is guaranteed not to change out from
> under the viewer.  This is identical to the guarantee provided by returning
> a copy of the same data when it is requested.  Invariant references simply
> guarantee that any copying will be done up front, automatically, so it does
> not have to occur manually later on.

You're right that invariants can give equivalent semantics to always getting a local copy.

> In general, I feel that the amount of copying caused by invariants is greater
> than without them in a typical program,

I'm not convince of that. Invariants make sharing much more possible and practical, because one doesn't have to worry about making a local copy to protect it from some other alias.

Steven Schveighoffer wrote:
> "Walter Bright" wrote
>> Sure, but static class members are *not* part of the transitive closure state of the object. They're just global variables.
> 
> Neither are mutable member variables.

How can a member not be a member of the state of an object?

== Quote from Walter Bright (newshound1@digitalmars.com)'s article
> Sean Kelly wrote:
> >> If C.name were invariant, there would be no need for any locks. I don't think this is a good example, because with D's invariant strings there is no need for such locking.
> > Also, I believe my example demonstrated that memory fences and order
> > of evaluation issues are still a concern with invariants.  They aren't a
> > magical safe ticket to lock-free programming land.
> While creating an invariant is something that should be done with care, once it is created, locks are no longer needed on it. After all, since it cannot change, where is the need to sync it?

The issue is largely with being sure that the creation process is complete
and the changes made appropriately visible by the time other threads
attempt to view the data.  Strings also impose an additional requirement
that any shared referencemust be set carefully because the references
are the size of two pointers and thus are not set in an atomic manner
even on x86.  My sample program illustrated both problems.  Sadly,
not even D's 'volatile' statement can do anything about safe setting of
string references, since the single instruction will still involve at least
two separate stores.


Sean

Lars Ivar Igesund wrote:
> Walter Bright wrote:
>> Invariant strings have turned out to be a resounding success (and I was
>> very, very skeptical of that initially). I suspect that more and more
>> programs will gravitate towards using invariant as people get more used
>> to the idea. I know my programs will.
> Do you have any references to this resounding success?

It's success in other languages for one, and not finding any problems with it when using it in D for two.

Don Clugston wrote:
> Walter Bright wrote:
>> A function is pure or it isn't, there really isn't any room for "unstable" purity, or the point of purity is lost.
> 
> I think there is. A function which accesses a global is inherently impure. But, a function which takes a non-invariant argument, can in theory safely be called from inside a pure function, provided any non-invariant arguments are local variables, or invariant.
> 
> eg.
> 
> class C
> {
>   int numcalls;
>   this() { numcalls=0; }
>   void foo() { ++numcalls; } // Not pure - but no global side effects.
> }
> 
> pure int bar(int x)
> {
>     C c = new C;
>     for (int i=0; i<x; ++i) c.foo();
>     return c.numcalls;
> }
> 
> Is bar() pure or not?

I think it is pure, although it might be difficult for the compiler to detect it. Like for CTFE, I think the compiler should start out rather restrictive about what it regards as pure, and over time expand it as it gets more capable.

Walter Bright wrote:
> Don Clugston wrote:
>> Walter Bright wrote:
>>
>>> A function is pure or it isn't, there really isn't any room for "unstable" purity, or the point of purity is lost.
>>
>> I think there is. A function which accesses a global is inherently impure. But, a function which takes a non-invariant argument, can in theory safely be called from inside a pure function, provided any non-invariant arguments are local variables, or invariant.
>>
>> eg.
>>
>> class C
>> {
>>   int numcalls;
>>   this() { numcalls=0; }
>>   void foo() { ++numcalls; } // Not pure - but no global side effects.
>> }
>>
>> pure int bar(int x)
>> {
>>     C c = new C;
>>     for (int i=0; i<x; ++i) c.foo();
>>     return c.numcalls;
>> }
>>
>> Is bar() pure or not?
> 
> I think it is pure, although it might be difficult for the compiler to detect it. Like for CTFE, I think the compiler should start out rather restrictive about what it regards as pure, and over time expand it as it gets more capable.

No.

The result of having run the function changes something outside the function, and that makes it impure.

It does not matter that what's being changed is hidde behind the bushes in a small tin box.

On 04/04/2008, Walter Bright <newshound1@digitalmars.com> wrote:
>  I think it is pure, although it might be difficult for the compiler to
> detect it. Like for CTFE, I think the compiler should start out rather
> restrictive about what it regards as pure, and over time expand it as it
> gets more capable.

What about this one. Is f pure?

    import std.date;

    void main()
    {
        invariant s = toString(getUTCtime());

        pure string f()
        {
            return s;
        }

        writefln(s);
    }

The function f relies only on the string s. which is fully invariant and in scope. Yet f will give a different return value for the same input (void), each time the program is run.

I assume the answer is no, but this one seems a bit grey to me. Is it impure because s is not global?

On 04/04/2008, Janice Caron <caron800@googlemail.com> wrote:
>         writefln(s);

That would have been a more effective question if I'd written

        writefln(f);

:-)