Walter Bright wrote:
> Bill Baxter wrote:
>> If the ultimate goal is support for multiprogramming, then shouldn't the detailed design work should start *there*, with how to do great multiprogramming?  Rather than with const.
>>
>> Not saying that you guys have done this, but I know from my own experience doing research that it's easy to get hung up trying to solve a tough but solvable problem that seems relevant for getting from A to B, only to realize in the end that it was not as relevant as I thought.
> 
> I think it is fairly obvious that transitive invariant (and const) is key to multiprogramming. The transitive closure of the state of everything reachable through an object is part of the state of that object, and all the troubles with multiprogramming stem from the state of an object changing asynchronously.

There are two very different aspects to the multiprogramming problem though:
* make it correct
* make it fast.

As far as I can tell, it's like any optimisation problem -- it's only 5-10% of the code that matters: it's only necessary to use multiple cores efficiently in a small fraction of the code (obviously the entire code needs to be correct). So I'm a little uneasy about arguments for const based on efficiency concerns -- there are many opportunities to worry about stuff which is ultimately irrelevant. I hope that's not happening here.

Janice Caron wrote:
> On 01/04/2008, Craig Black <craigblack2@cox.net> wrote:
>> Walter/Andrei are under the impression that transitive const is necessary
>>  for multiprogramming, but they have not presented a detailed explanation
>>  about why it is necessary.
> 
> It hardly needs a detailed explanation. In fact it's trivial to
> understand. Watch:
> 
>     // in C++
>     void f(const C &c)
>     {
>         c.some.deeply.nested.but.reachable.var++;
>     }
> 
> In a multithreaded program, a thread switch may occur between the read
> and the write of the read/write cycle that is ++. If that happens,
> you're screwed.
> 
>     // in D
>     void f(const C c)
>     {
>         c.some.deeply.nested.but.reachable.var++; /*ERROR*/
>     }
> 
> In D, such dodgy code just won't compile.

But this dodgy code will

void f(const C c) {
    some_global++;
}

So const isn't a guarantee of thread safety.

And watch this:

void f(const C c) {
    assert(
	c.we_like_const == c.we_like_const,
        "Oops!  "
	"Some other thread must have changed c "
	"while we weren't looking!");
}

Might just assert. Const gives no guarantee that values won't change out from under you when used in a multithreaded environment.

And watch this:
void f(C c) {
    int x = c.get_some_value();
}

Hey! That probably *is* thread safe, and it didn't even use const at all.

So it seems "const is necessary for multiprogramming" is not quite the whole truth, which was all the original poster was talking about. 'Course that may be a strawman.  I don't know that Walter has ever said precisely that.  He's usually phrases it more like "it will be important for what's coming".

I can see invariant having some value in conjunction with pure, but I also suspect that invariant, being so strict, is also something that will not get used a lot outside of simple constants and code carefully designed for running in parallel.  Like what Don's said.

--bb

On 01/04/2008, guslay <guslay@gmail.com> wrote:
>  -= A const method may exhibit side effects =-

There is really no such thing as a const method. What we /call/ a const method is just a function, like any other. In any function, some parameters may be const, others not. In what you call a "const method", the hidden variable "this" is typed const - but that has no impact on any other function parameter, nor on any other variable in scope. In fact, I could even do

    class C
    {
        int x;

        void f(C c) const
        {
            ++c.x;
        }

        void g()
        {
            f(this);
        }
    }

and have f() modify a member variable, despite being declared const, simply by doing it through another pointer.

So, while what you say is true, it's nothing but a statement of the obvious. It's /how things are supposed to work/. If you have any expectation that things are supposed to behave differently, then you just haven't understood what a const member function is.



>  The transitivity of const does not extends beyond the scope of the class.

It would be more accurate to say that the transitivity of const(T) does not extend beyond that which is reachable through T. But T doesn't have to be a class.


> You may call static/global functions and modify static/global data, modify mutable objects accessible through static/global pointers, perform I/O, etc.

Of course. Again, you're stating the obvious.


>  -= Const != thread-safe =-
>
>  A method with potential side effects is not implicitly thread-safe.

Again with the obvious. Is there any point to this? Are you somehow suggesting that anyone on this newsgroup believes otherwise?


>  -= Const is not the key to functional programming =-

Yes it is. But const is /part/ of the solution, not the /whole/ of the solution. Saying "const is not the key to functional programming" is a bit like saying "wheels are not the key to making cars". Well, it's true that wheels aren't /enough/ to make a car - an engine would help, for as start - but they do matter. It would be a tough job making a car without wheels. And likewise it would be a tough job making functional programming work without (transitive) const.


>  Immutability is required for FP, but const "mathematical" guarantees are too weak to provide that ability.

I don't understand that sentence. Why is the word mathematical in quotes? I hope you're not suggesting that mathematics is a dodgy discipline, because it's probably the /only/ discipline in the universe which offers solid proofs for its theorems. Even ignoring that, I have no idea what you're trying to say here.


>  -= Pure function + invariant data is required for FP =-

That sounds reasonable, though it should really say /transitive/ invariant data.


>  As many have pointed out, the expected pure function will enable FP.

OK.


>  This concept is not yet into place, but I will define it has a method that only call other pure functions, and performs read-only operation on its class members and static/global data.

INCORRECT. A pure function cannot read static or global data, period.



>  -= Const is part of the interface, not part of the implementation =-
>
>  Const part of the interface: you need to have a const method to call on a const object.
>
>  It is also an abstraction. In some sense, D const is already logical const.

No it isn't.


>  Sure, the bits of the object cannot change, but since /everything else/ can change,
 the "purity" of constness

Const doesn't claim to be pure.


>  It does not mean that it is useless or without teeth, because D const is enforceable (but only on a member-by member basis).

On a variable by variable basis, yes. /That's what const means/.


> Allowing this would be desirable.
>
>    class MyMutableClass
>    {
>       private         int normal_part;
>       private mutable int mutable_part;
>
>       public int const lazyGetter();
>    }
>
>    const MyMutableClass obj = new MyMutableClass;

The bottom line is that any class which is not /truly/ const, (as in physically, not merely logically), cannot be passed to any function which modifies the mutable parts, and simultaneously stay thread-safe.


>  If not, people will find a way to hack around it with ugly tricks.

And their code won't be thread-safe.


>  -= Allowing mutable members does not break or weaken the const model =-

I'm afraid it does. A type with mutable members can never be cast - either implicitly or explicitly - to fully const. That breaks everything.


>  What mutable does is allowing finer-grained control over the powerful const system. It does not weaken it, it controls its scope. Those are orthogonal issues (as far as I have yet to see an instance where having half the fields of an object const, instead of all the fields of the object, limits anything in any way).

Really?

    class C
    {
        int x;
        mutable int y; // just pretend this is legal
    }

    void f(const(C) c)
    {
        int temp = y;
        y = temp + 1;
    }

Now imagine two threads calling f simultaneously with the same c. Imagine a thread switch occurs between the two statements.



>  -= Mutability is required =-

Mutability, you have. It happens when you don't declare a thing const.


>  An object is fully initialized, but some parts are lazyly evaluated and require mutable members.

Then it isn't const.


>  a) Mutable members are not allowed. The object cannot be passed as const. The non-const object is passed to the external function, renouncing to any control at all on the immutability of the object.

There are trivial workarounds. Instead of

    class C
    {
        int x;
        mutable int y;
    }

    void f(const(C) c);

just do this:

    class C
    {
        int x;
    }

    class D
    {
        int y;
    }

    void f(const(C) c, D d);

This is just a simple matter of saying what you really mean.


>  b) Mutable members are allowed. The object is passed as const. The caller can be confident that the internal state of the object will not be modified beyond the intention of the class designer.

...or it might be screwed up entirely as a result of a threading conflict.

On 02/04/2008, Bill Baxter <dnewsgroup@billbaxter.com> wrote:
>  But this dodgy code will
>
>  void f(const C c) {
>     some_global++;
>  }
>
>  So const isn't a guarantee of thread safety.

Correct. And nobody's saying it is. You, me, Walter, Andrei - we all agree on this point, so it needs no further discussion.

This is simple logic. A => B isn't the same thing as B => A. Unless of course you would argue that everything with four legs is a dog.

(1) const does not guarantee thread safety
(2) thread safety requires const guarantees

Both of these statements are simultaneous true.



>  So it seems "const is necessary for multiprogramming" is not quite the
> whole truth, which was all the original poster was talking about. 'Course
> that may be a strawman.  I don't know that Walter has ever said precisely
> that.

And that's the nub of the matter. Folk that have thought the whole pure/multiprocessor thing through are saying "A => B", and detractors are saying "Wait a minute, B !=> A". It's sort-of a strawman, but only in the sense of misunderstanding.

Janice Caron wrote:
> On 01/04/2008, guslay <guslay@gmail.com> wrote:

>>  -= Const != thread-safe =-
>>
>>  A method with potential side effects is not implicitly thread-safe.
> 
> Again with the obvious. Is there any point to this? Are you somehow
> suggesting that anyone on this newsgroup believes otherwise?
> 
> 
>>  -= Const is not the key to functional programming =-
> 
> Yes it is. But const is /part/ of the solution, not the /whole/ of the
> solution. Saying "const is not the key to functional programming" is a
> bit like saying "wheels are not the key to making cars". Well, it's
> true that wheels aren't /enough/ to make a car - an engine would help,
> for as start - but they do matter. It would be a tough job making a
> car without wheels. And likewise it would be a tough job making
> functional programming work without (transitive) const.

Analogies can be use to prove a lot of untrue things.  Legs are used by pretty much all creatures on the planet to get from point A to point B, so it is obvious that a man-made vehicle will also certainly require legs.  Maybe const is like legs.

>>  This concept is not yet into place, but I will define it has a method that only call other pure functions, and performs read-only operation on its class members and static/global data.
> 
> INCORRECT. A pure function cannot read static or global data, period.

Unless the data is invariant.  Shouldn't be a problem then.


>> Allowing this would be desirable.
>>
>>    class MyMutableClass
>>    {
>>       private         int normal_part;
>>       private mutable int mutable_part;
>>
>>       public int const lazyGetter();
>>    }
>>
>>    const MyMutableClass obj = new MyMutableClass;
> 
> The bottom line is that any class which is not /truly/ const, (as in
> physically, not merely logically), cannot be passed to any function
> which modifies the mutable parts, and simultaneously stay thread-safe.


>>  If not, people will find a way to hack around it with ugly tricks.
> 
> And their code won't be thread-safe.

And const will not have prevented it.  So what use was its transitivity?

>>  -= Allowing mutable members does not break or weaken the const model =-
> 
> I'm afraid it does. A type with mutable members can never be cast -
> either implicitly or explicitly - to fully const. That breaks
> everything.

But a type that depends on globals *can* be made fully const.  So why doesn't that break everything?

>>  What mutable does is allowing finer-grained control over the powerful const system. It does not weaken it, it controls its scope. Those are orthogonal issues (as far as I have yet to see an instance where having half the fields of an object const, instead of all the fields of the object, limits anything in any way).
> 
> Really?
> 
>     class C
>     {
>         int x;
>         mutable int y; // just pretend this is legal
>     }
> 
>     void f(const(C) c)
>     {
>         int temp = y;
>         y = temp + 1;
>     }
> 
> Now imagine two threads calling f simultaneously with the same c.
> Imagine a thread switch occurs between the two statements.

Now imagine instead of mutable int it's static int[C].  It's the same loophole.


>>  b) Mutable members are allowed. The object is passed as const. The caller can be confident that the internal state of the object will not be modified beyond the intention of the class designer.
> 
> ...or it might be screwed up entirely as a result of a threading conflict.

As would also be the case with the globals loophole.

Would think and write more, but gotta go now.

--bb

On 02/04/2008, Bill Baxter <dnewsgroup@billbaxter.com> wrote:
> > INCORRECT. A pure function cannot read static or global data, period.
>
>  Unless the data is invariant.  Shouldn't be a problem then.

Maybe. I don't know the details. My guess would be that only manifest constants will be allowed. Invariant data can be created with idup, and might not be considered sufficiently pure. We shall have to wait and see.


>  And const will not have prevented it.  So what use was its transitivity?

pure would have prevented it, and pure requires transitive const.


>  But a type that depends on globals *can* be made fully const.  So why
> doesn't that break everything?

I don't understand the question. What is a "type that depends on globals"? Do you mean something like this:

    string g = "hello";

    class C
    {
        string s;
        this() { s = g; }
    }

I don't think that passing a const(C) to a pure function would break anything. The essential point is not that g's character data can be reached, it's that it can be reached /through a pointer passed to the function/, and that's what purity requires.


> Now imagine instead of mutable int it's static int[C].  It's the same loophole.

It is. But again, static data will not be accessible in pure functions, so the loophole is closed there.


> > ...or it might be screwed up entirely as a result of a threading conflict.
>
>  As would also be the case with the globals loophole.

which pure closes.

Don Clugston wrote:
> As far as I can tell, it's like any optimisation problem -- it's only 5-10% of the code that matters: it's only necessary to use multiple cores efficiently in a small fraction of the code (obviously the entire code needs to be correct). So I'm a little uneasy about arguments for const based on efficiency concerns -- there are many opportunities to worry about stuff which is ultimately irrelevant. I hope that's not happening here.

Although better code generation is a positive consequence of const, and is worth mentioning, it isn't the motivation for it.

What const and transitive const achieves is more reliable and more demonstrably correct code, which will indirectly improve productivity.

My point is that global variables violate the guarantee transitive const provides... My question is how having them as an exception does not invalidate the whole argument that transitive const is needed for multithreading. I view global variables the same as head const.

Walter Bright Wrote:

> Jason House wrote:
> > Walter Bright wrote:
> > And how do global variables fit into that?  Technically, they're always
> > reachable and never inherit const.
> 
> If the global variables are not invariant, then you're going to have synchronization problems when accessing them from multiple threads. If they are invariant, you cannot have sync problems.

On 2008-04-02 04:14:28 -0400, "Janice Caron" <caron800@googlemail.com> said:

>> -= Pure function + invariant data is required for FP =-
> 
> That sounds reasonable, though it should really say /transitive/ invariant data.

Hum, I'm wondering if an invariant class couldn't have a mutable member, but access to the mutable member from a const or invariant reference would require synchronized access to keep thread safety guaranties.

In other words:

	class X {
		mutable int a;
		
		const void foo() {
			writefln(a); // illegal, const this doesn't give access to mutable member.
			synchronized (this) {
				writefln(a); // legal, synchronization gives access to mutable member.
				++a;         // legal since a is mutable.
			}
		}
	}

-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/

On Wed, 02 Apr 2008 12:14:28 +0400, Janice Caron <caron800@googlemail.com> wrote:

> On 01/04/2008, guslay <guslay@gmail.com> wrote:
>> What mutable does is allowing finer-grained control over the powerful const system. It does not weaken it, it controls its scope. Those are orthogonal issues (as far as I have yet to see an instance where having half the fields of an object const, instead of all the fields of the object, limits anything in any way).
>
> Really?
>
>     class C
>     {
>         int x;
>         mutable int y; // just pretend this is legal
>     }
>
>     void f(const(C) c)
>     {
>         int temp = y;
>         y = temp + 1;
>     }
>
> Now imagine two threads calling f simultaneously with the same c.
> Imagine a thread switch occurs between the two statements.
>

I like current const system, and I understand that it would help to do multiprogramming in D.

But maybe we sould look to the problem from different point.
The problem you have just shown doesn't correlate with const correctness.

Maybe we should introduce some other data status like 'concurrent' or 'thread-safe' to determine that data can be accessed or method can be called with no side effects. It is _great_ contract which not only gives programmer additional guaranties, but it also helps compiler to make optimizations.

class C
{
   // Call this method as you wish, it's safe!
   // Author takes all the responsibility for its safety
   concurrent void f()
   {
       // ... some data manipulation, guarded by mutexes
   }

   // This method is concurrent, too
   // Compiler makes guaranty it's safe
   synchornized void g()
   {
   }
}


Neither programmer nor compiler can rely on method if it behaves like this:

class C
{
   int refCount = 0;

   void addRef()
   {
       ++refCount;  // not safe
   }
}

And we cannot mark the method 'pure'. Instead, we could mark it 'concurrent':

class C
{
   int refCount = 0;

   // via 'synchronized' modifier
   synchronized void addRef()
   {
      ++refCount;
   }

   // or by hand
   concurrent void addRef_2()
   {
       while (true) {
          int refs = refCount;
          if (thread.atomic.cas(&refCount, refs, refs+1)) {
             break;
          }
       }
   }
}

Note that ALL pure methods are concurrent.

This way, we could allow mutable data, but only if _all_ access to it is passes through concurrent methods:

class Square
{
    private mutable int area;
    private int width;

    this(int width)
    {
       this.width = width;
       this.area = -1;      // ok, safe
    }

    invariant int getArea()
    {
       if (area == -1) {
          area = width*width;	// BAD
          // method cannot be marked as invariant, if it modifies mutable variables
       }
       return area;
    }

    invariant int getArea()
    {
       if (area == -1) {
          synchronized(this) {
             if (area == -1) {
                area = width*width;	// OK now, no sife effects.
             }
          }
       }
       return area;
    }
}

Logical const _can_ be used with no sife effects, but programmer should pay attention to this kind of data.

Waht do you think?