I have been reading through the reddit posts about the const faq, and also some posts here by guslay, and I believe Walter needs to re-think his beliefs about how transitive const is necessary for the future.

First, I think transitive const should be the default.  I am not a fan of C++'s head-const, where only the head is const, and all data referenced through the head is mutable.  I think this promotes "shoot yourself in the foot" code.  It is a valuable tool to have the compiler tell you "hey, you wanted this to be const, remember?"  At the same time it is also useful to tell the compiler "hey, I want this to not be affected by const, because it's not logically part of the state of the object."

Second, I'll show how logical const is ALREADY available with D's const, just in a less convenient form.  Let's look at an invariant property that is not invariant:

class X
{
   private static int _x;
   invariant int x()
   {
       return _x++;
   }
}

Notice that despite all efforts of the compiler to make sure invariant is transitive, it still cannot do any parallelizations or optimizations on the call to x.  If it does not have the source code for x, it cannot be sure that x isn't doing something like the above.

We can translate this into a form where we keep an associative array that maps each instance to a mutable struct that can be the non-const portion of the instance, so each instance can be separate:

class X
{
    private static int[X] _x;
    this()
    {
        _x[this] = 0;
    }

    ~this()
    {
         _x.remove(this);
    }

    invariant int x()
    {
       int *myx = this in _x;
       return (*myx)++;
    }
}

The problem is, you can think of each function not only passing the arguments, and possibly a this pointer, but passing a context pointer to the global namespace, which is never const.  As long as that remains mutable, we can store mutable data associated with a class in that space.  In order to allow multiprogramming, you need to ensure that the function does not access that space, unless the data is invariant.  But this is called a 'pure' function, and can exist WITH logical const and invariant.  If it couldn't, then it couldn't exist with today's version of const, which allows logical const and invariant as I have demonstrated.

Here is my interpretation of all this:

const is a tool for developers, not for the compiler.  Since const data can change at any time, it cannot be used for multithreaded or other optimizations.

invariant allows for some optimization on the compiler.  Invariant optimization is limited to POD values, because invariant functions can always be logically invariant, and there is no way to detect it.

pure is a tool for multiprogramming.  This allows all the fun stuff that Walter is always talking about.  pure can co-exist with logical const and logical invariant, because if it couldn't, then pure couldn't exist in today's version of const.

Since const is a tool for developers, and CANNOT BE USED for optimization, let's please have logical const in a form that performs better and is easier to implement than the above example.  Something like C++'s mutable (but not exactly that, I'll explain below).

Since invariant functions cannot be guaranteed as pure functions, let's have logical invariance in a form that performs better and is easier to implement than the above example.  Optimizations based on POD types can still be had even with logical invariance.

Head const by default sucks, and still does, because const is less useful as a tool in that state.  However, as I have shown, head const cannot be avoided, and so why not support it as the exception to the transitive const rule?

mutable is used as the keyword in C++ to describe this type.  However, I do not like this word.  For example, whatever keyword is used, it should be usable just like const or invariant:

mutable(X)* refToX;

This would describe a reference to a mutable X.  adding const to this would then make the reference const, but the thing it points to mutable, giving us a head-const variable.

But what if X is an alias to const(Y)?  The statement implies that mutable(X) makes X mutable, even if it is was previously const or invariant, but this would be no good.  We need a word that says "this isn't affected by const or invariant, but it could already be const or invariant".  Something that is short and not heavily used in code.  Mabye even some form of punctuation.

Walter, I think you need to look at this, because not doing this is going to keep D out of the mainstream, as most developers will (and already do) complain about the lack of logical const.  I was one of those, but I gave up, because I convinced myself that logical const wasn't that important, and was a design flaw.  But since fully transitive const does not give us the benefits that you have been saying it will, why not allow it?

At the very least, this proof shows that you need a better reason to require fully transitive const/invariant than "I need it for the future."

-Steve

On 01/04/2008, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>  Second, I'll show how logical const is ALREADY available with D's const,
>  just in a less convenient form.  Let's look at an invariant property that is
>  not invariant:
>
>  class X
>  {
>    private static int _x;
>    invariant int x()
>    {
>        return _x++;
>    }
>  }

That does not break transitivity. You have misunderstood.

"invariant int x()" declares x() to be a function, within whose body
the variable "this" is invariant. X._x is a global variable, unrelated
to "this". Transitivity is not compromised.


>  Notice that despite all efforts of the compiler to make sure invariant is
>  transitive, it still cannot do any parallelizations or optimizations on the
>  call to x.  If it does not have the source code for x, it cannot be sure
>  that x isn't doing something like the above.

However, in the future, you will be able to declare

    class X
    {
        private static int _x;
        invariant int x()
        {
            return _x++; /*ERROR*/
       }
   }

and suddenly - bingo - the offending line will not compile.

You gotta think ahead.

On 01/04/2008, Janice Caron <caron800@googlemail.com> wrote:
> However, in the future, you will be able to declare
>
>     class X
>     {
>         private static int _x;
>         invariant int x()
>         {
>
>             return _x++; /*ERROR*/
>        }
>    }
>
>  and suddenly - bingo - the offending line will not compile.

Well, not exactly. I made a fatal typo in that code, and consequently completely screwed it up! So much for forward planning! Let's try again. What I meant was:

       class X
       {
           private static int _x;
           pure int x()
           {
               return _x++; /*ERROR*/
          }
      }

and suddenly - bingo - the offending line will not compile.

"Janice Caron" wrote
> On 01/04/2008, Steven Schveighoffer wrote:
>>  Second, I'll show how logical const is ALREADY available with D's const,
>>  just in a less convenient form.  Let's look at an invariant property
>> that is
>>  not invariant:
>>
>>  class X
>>  {
>>    private static int _x;
>>    invariant int x()
>>    {
>>        return _x++;
>>    }
>>  }
>
> That does not break transitivity. You have misunderstood.
>
> "invariant int x()" declares x() to be a function, within whose body
> the variable "this" is invariant. X._x is a global variable, unrelated
> to "this". Transitivity is not compromised.

No you have missed my point :)  Yes, transitivity is still intact, but Walter is always saying that fully transitive const is necessary for compiler optimizations, and so there is no place for logical const.  My point is, even with fully transitive const, the compiler cannot do optimizations based on the fact that a function is invariant, as it cannot guarantee that the function has no side effects.  And in fact, this IS logically const.  Logical const does not break transitive const, and despite all efforts to make logical const invalid, it is still present.

>
>
>>  Notice that despite all efforts of the compiler to make sure invariant
>> is
>>  transitive, it still cannot do any parallelizations or optimizations on
>> the
>>  call to x.  If it does not have the source code for x, it cannot be sure
>>  that x isn't doing something like the above.
>
> However, in the future, you will be able to declare
>
>    class X
>    {
>        private static int _x;
>        invariant int x()
>        {
>            return _x++; /*ERROR*/
>       }
>   }
>
> and suddenly - bingo - the offending line will not compile.
>
> You gotta think ahead.

I should hope this is not the case.  My understanding is that invariant and const will remain intact, and pure functions will be introduced to allow this kind of behavior.  What new rule are you thinking of that will apply to an invariant function that forces this?  Remember than an invariant function just means the instance is invariant, not the static or global data.

My entire point is that pure functions can exist with logical const, so there is no reason (that I know of) we need fully transitive const.  When pure functions are introduced, they simply will not be allowed to use the mutable members of a logically const class/struct.

-Steve

"Janice Caron" wrote
> On 01/04/2008, Janice Caron wrote:
>> However, in the future, you will be able to declare
>>
>>     class X
>>     {
>>         private static int _x;
>>         invariant int x()
>>         {
>>
>>             return _x++; /*ERROR*/
>>        }
>>    }
>>
>>  and suddenly - bingo - the offending line will not compile.
>
> Well, not exactly. I made a fatal typo in that code, and consequently completely screwed it up! So much for forward planning! Let's try again. What I meant was:
>
>       class X
>       {
>           private static int _x;
>           pure int x()
>           {
>               return _x++; /*ERROR*/
>          }
>      }
>
> and suddenly - bingo - the offending line will not compile.

OK, now you're making a little more sense :)

This still does not require fully transitive const, and so there is no reason to force people who wish to develop with logical const to do so in the hack-ish manner that my example does...

-Steve

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 sounds like a more detailed explanation of the merits of transitive const from Walter/Andrei would help here.

One idea that I had recently was that the const keyword could provide logical const (for developers) and the invariant keyword could provide transitive const (for the compiler).  I agree with you that for logical const, it is practical to have something like C++ mutable for class/struct fields.  I use C++ const, and it is practical to be able to subvert it.

-Craig 

== Quote from Janice Caron (caron800@googlemail.com)'s article
> On 01/04/2008, Janice Caron <caron800@googlemail.com> wrote:
> > However, in the future, you will be able to declare
> >
> >     class X
> >     {
> >         private static int _x;
> >         invariant int x()
> >         {
> >
> >             return _x++; /*ERROR*/
> >        }
> >    }
> >
> >  and suddenly - bingo - the offending line will not compile.
> Well, not exactly. I made a fatal typo in that code, and consequently
> completely screwed it up! So much for forward planning! Let's try
> again. What I meant was:
>        class X
>        {
>            private static int _x;
>            pure int x()
>            {
>                return _x++; /*ERROR*/
>           }
>       }
> and suddenly - bingo - the offending line will not compile.

You know, I'm a huge fan of D, but now we have const, invariant,
and pure, all ostensibly for making it possible for D to act more
like a functional language when functional languages don't need
all this mess to be parallelizable.  Perhaps it's because of the C++
0x post from yesterday, but the above is beginning to give me
flashbacks to C++ in that I'm starting to feel like D is trying to
be the universal solution to all problems, and thereby not an
ideal solution for any problem at all.  One thing D has really had
going for it thus far is conceptual and semantic simplicity, but
I'm starting the feel that the const features are causing that
simplicity to be lost.

Here's the thing: if I want to write heavily concurrent code I'm
not going to use D because imperative languages, D included,
are not structured in a way that inherently lend themselves to
parallelization.  It's certainly possible to write code that could
come close to matching a functional language--use 'pure' and
'invariant' everywhere, forego loops in favor of tail recursion
(which is hopefully optimized by the compiler to avoid stack
issues), etc.  But why mimic a functional programming structure
in an imperative language when I can simply use a functional
language in the first place?  I can only think of one reason:
in a large company it is often more difficult to choose one's
language than to choose one's programming style.  That's it.
But if that's the case then I probably won't be able to use D
anyway--I'll be using C++.

I can truly appreciate the desire to have D scale effectively
as programming becomes more concurrent.  At the same
time, I am beginning to worry that the struggle to achieve
this will end up destroying D's primary selling point (in my
view)--its simplicity.  I know this is all new ground for an
imperative language so there's nothing to do but wait and
see... I just wanted to get this out so I could move on with
my day :-)  Here's to hoping that D doesn't follow in the
way of C++.


Sean

"Sean Kelly" <sean@invisibleduck.org> wrote in message news:fstoa0$14ss$1@digitalmars.com...
> == Quote from Janice Caron (caron800@googlemail.com)'s article
>> On 01/04/2008, Janice Caron <caron800@googlemail.com> wrote:
>> > However, in the future, you will be able to declare
>> >
>> >     class X
>> >     {
>> >         private static int _x;
>> >         invariant int x()
>> >         {
>> >
>> >             return _x++; /*ERROR*/
>> >        }
>> >    }
>> >
>> >  and suddenly - bingo - the offending line will not compile.
>> Well, not exactly. I made a fatal typo in that code, and consequently
>> completely screwed it up! So much for forward planning! Let's try
>> again. What I meant was:
>>        class X
>>        {
>>            private static int _x;
>>            pure int x()
>>            {
>>                return _x++; /*ERROR*/
>>           }
>>       }
>> and suddenly - bingo - the offending line will not compile.
>
> You know, I'm a huge fan of D, but now we have const, invariant,
> and pure, all ostensibly for making it possible for D to act more
> like a functional language when functional languages don't need
> all this mess to be parallelizable.  Perhaps it's because of the C++
> 0x post from yesterday, but the above is beginning to give me
> flashbacks to C++ in that I'm starting to feel like D is trying to
> be the universal solution to all problems, and thereby not an
> ideal solution for any problem at all.  One thing D has really had
> going for it thus far is conceptual and semantic simplicity, but
> I'm starting the feel that the const features are causing that
> simplicity to be lost.

Agreed, but this one's tough.  I've thought it through a million times, and the arguments for const (of some sort) are very compelling.

> Here's the thing: if I want to write heavily concurrent code I'm
> not going to use D because imperative languages, D included,
> are not structured in a way that inherently lend themselves to
> parallelization.  It's certainly possible to write code that could
> come close to matching a functional language--use 'pure' and
> 'invariant' everywhere, forego loops in favor of tail recursion
> (which is hopefully optimized by the compiler to avoid stack
> issues), etc.  But why mimic a functional programming structure
> in an imperative language when I can simply use a functional
> language in the first place?  I can only think of one reason:
> in a large company it is often more difficult to choose one's
> language than to choose one's programming style.  That's it.
> But if that's the case then I probably won't be able to use D
> anyway--I'll be using C++.

As you well know imperative/OOP languagaes are much more popular than functional languages.  Functional features in D will ease the transition into a more functional style.  From what I have read, pure functional languages suffer from severe limitations, just as pure OOP languages do, so a good mix is probably a better solution.  And while we are comparing functional languages to D, I'm not so sure that functional languages will be any better at being simple, since non-pure functional languages (Haskell in particular) seem to suffer from feature drift and language complexity just as much as D does.

The growing push toward concurrency is still sketchy.  Although it will probably help, I'm not so sure the functional paradigm alone will be "the solution" to the problem.  I find it hard to believe that any paradigm will magically make parallelism automatic.  I think it will always require some knowledge of the underlying hardware, and how things work at the low level to glean optimum performance.  Language features such as pure functions may help some with this, but I still think it's going to be increasingly hard to write software that scales well.  It is difficult to forsee the scalability issues that will arise the number of processors per die increases at an exponential rate, and as streaming processors like those found in the Cell, AMD's FireGL, and NVidia's Tesla become mainstream.

> I can truly appreciate the desire to have D scale effectively
> as programming becomes more concurrent.  At the same
> time, I am beginning to worry that the struggle to achieve
> this will end up destroying D's primary selling point (in my
> view)--its simplicity.  I know this is all new ground for an
> imperative language so there's nothing to do but wait and
> see... I just wanted to get this out so I could move on with
> my day :-)  Here's to hoping that D doesn't follow in the
> way of C++.

Time will tell.  A reassuring observation about Walter is that he has been known to change directions if something doesn't pan out (although it may take an act of God for this to happen with the const stuff).

-Craig

Sean Kelly wrote:
> You know, I'm a huge fan of D, but now we have const, invariant,
> and pure, all ostensibly for making it possible for D to act more
> like a functional language when functional languages don't need
> all this mess to be parallelizable.  Perhaps it's because of the C++
> 0x post from yesterday, but the above is beginning to give me
> flashbacks to C++ in that I'm starting to feel like D is trying to
> be the universal solution to all problems, and thereby not an
> ideal solution for any problem at all.  One thing D has really had
> going for it thus far is conceptual and semantic simplicity, but
> I'm starting the feel that the const features are causing that
> simplicity to be lost.

Agreed!

> I can truly appreciate the desire to have D scale effectively
> as programming becomes more concurrent.  At the same
> time, I am beginning to worry that the struggle to achieve
> this will end up destroying D's primary selling point (in my
> view)--its simplicity.  I know this is all new ground for an
> imperative language so there's nothing to do but wait and
> see... I just wanted to get this out so I could move on with
> my day :-)  Here's to hoping that D doesn't follow in the
> way of C++.

If D did move the way of C++ it would be a lot better off than it is now.  But, that being said, I agree with you... there's such a huge opportunity here!  Instead of going the way C++ did, or the way D is going now (which is even worse), why not take the time to find a really good, simple and effective solution?

For large parallel projects, I have seen some successful uses of Erlang, but most of the parallel development these days is done in Fortran and C++ because of OpenMP (even some big distributed apps are moving to OpenMP via Intel's clustering OpenMP compiler).  C++ also has a nice join calculus module available in Boost, not to mention Boost's [new] MPI support.

People aren't using C++ and Fortan because they're the best suited languages... and parallel people are always looking for something better because, like you said, in theory there should be a lot better choices available to us.  Functional languages promise neat and tidy parallelization with no side affects, etc, but in reality they're too slow and don't produce optimized code on the machines that parallel developers need to write code for.

What we want is a fast, system level language, that can be targeted by an optimizing compiler, but that is also quick and enjoyable to write code in.

If D did have some support for parallel programming I think it would be a major selling point, and I don't think it would need to complicate the language at all.  The whole problem here isn't that adding parallel support automatically makes a language ridiculously complex.

The real issue is Walter's wacky and complex const system.  Somehow he thinks it's going to help with parallel development, so the issues are getting mixed, but in reality they're completely unrelated.

Good arguments, Steven.
The hand-waving over future benefits enabled by transitive const also has me feeling uneasy.  If the benefits are known then it should be possible to show some examples.  Clearly, though, as you say the benefit is not (at least directly) related to parallel optimizations.  So what optimizations does it allow?

So probably to use "pure" is going to require that a function A)
touches only const/invariant data and B) does not reference any globals.

So it seems logical, then, that there would need to be a const system in place to specify what things are ok for a pure function to use and do. Imagine a pure function that manipulates an array of external class objects.  The array will need to be of type const(Klass)[] to denote that the Klass objects won't be touched.  Or if the pure function wants to call a Klass method, it better be a pure method.

But as I think Sean mentioned before, the constness in that case could conceivably be checked by the compiler without requiring user annotations.  Consider this case though:

  // Hypothetical pure function with implicit/deduced constness
  pure int foo(Klass a) {
     scope b = new Klass;
     Klass[] x;
     x ~= a;
     x ~= b;
     random_shuffle(x);
     x[0].prop = 10;  // is this ok or not?
  }

The trouble is that it's difficult for the compiler to guess whether to treat x as const(Klass)[] or mutable Klass[].   It is possible in this case though.  Basically it can infer from the x[0].prop=10 line that the container must be mutable, and thus the line  x ~= a is invalid because the parameters to a pure function are assumed const.

So hmm, it does seem conceivable to me that the compiler could enforce "pure" without needing any explicit const notation.


I also agree with Sean that D is great, and that the simplicity of D is one of it's biggest selling points.  And also that const currently doesn't seem to be helping much in that department.


--bb

Steven Schveighoffer wrote:
> I have been reading through the reddit posts about the const faq, and also some posts here by guslay, and I believe Walter needs to re-think his beliefs about how transitive const is necessary for the future.
> 
> First, I think transitive const should be the default.  I am not a fan of C++'s head-const, where only the head is const, and all data referenced through the head is mutable.  I think this promotes "shoot yourself in the foot" code.  It is a valuable tool to have the compiler tell you "hey, you wanted this to be const, remember?"  At the same time it is also useful to tell the compiler "hey, I want this to not be affected by const, because it's not logically part of the state of the object."
> 
> Second, I'll show how logical const is ALREADY available with D's const, just in a less convenient form.  Let's look at an invariant property that is not invariant:
> 
> class X
> {
>    private static int _x;
>    invariant int x()
>    {
>        return _x++;
>    }
> }
> 
> Notice that despite all efforts of the compiler to make sure invariant is transitive, it still cannot do any parallelizations or optimizations on the call to x.  If it does not have the source code for x, it cannot be sure that x isn't doing something like the above.
> 
> We can translate this into a form where we keep an associative array that maps each instance to a mutable struct that can be the non-const portion of the instance, so each instance can be separate:
> 
> class X
> {
>     private static int[X] _x;
>     this()
>     {
>         _x[this] = 0;
>     }
> 
>     ~this()
>     {
>          _x.remove(this);
>     }
> 
>     invariant int x()
>     {
>        int *myx = this in _x;
>        return (*myx)++;
>     }
> }
> 
> The problem is, you can think of each function not only passing the arguments, and possibly a this pointer, but passing a context pointer to the global namespace, which is never const.  As long as that remains mutable, we can store mutable data associated with a class in that space.  In order to allow multiprogramming, you need to ensure that the function does not access that space, unless the data is invariant.  But this is called a 'pure' function, and can exist WITH logical const and invariant.  If it couldn't, then it couldn't exist with today's version of const, which allows logical const and invariant as I have demonstrated.
> 
> Here is my interpretation of all this:
> 
> const is a tool for developers, not for the compiler.  Since const data can change at any time, it cannot be used for multithreaded or other optimizations.
> 
> invariant allows for some optimization on the compiler.  Invariant optimization is limited to POD values, because invariant functions can always be logically invariant, and there is no way to detect it.
> 
> pure is a tool for multiprogramming.  This allows all the fun stuff that Walter is always talking about.  pure can co-exist with logical const and logical invariant, because if it couldn't, then pure couldn't exist in today's version of const.
> 
> Since const is a tool for developers, and CANNOT BE USED for optimization, let's please have logical const in a form that performs better and is easier to implement than the above example.  Something like C++'s mutable (but not exactly that, I'll explain below).
> 
> Since invariant functions cannot be guaranteed as pure functions, let's have logical invariance in a form that performs better and is easier to implement than the above example.  Optimizations based on POD types can still be had even with logical invariance.
> 
> Head const by default sucks, and still does, because const is less useful as a tool in that state.  However, as I have shown, head const cannot be avoided, and so why not support it as the exception to the transitive const rule?
> 
> mutable is used as the keyword in C++ to describe this type.  However, I do not like this word.  For example, whatever keyword is used, it should be usable just like const or invariant:
> 
> mutable(X)* refToX;
> 
> This would describe a reference to a mutable X.  adding const to this would then make the reference const, but the thing it points to mutable, giving us a head-const variable.
> 
> But what if X is an alias to const(Y)?  The statement implies that mutable(X) makes X mutable, even if it is was previously const or invariant, but this would be no good.  We need a word that says "this isn't affected by const or invariant, but it could already be const or invariant".  Something that is short and not heavily used in code.  Mabye even some form of punctuation.
> 
> Walter, I think you need to look at this, because not doing this is going to keep D out of the mainstream, as most developers will (and already do) complain about the lack of logical const.  I was one of those, but I gave up, because I convinced myself that logical const wasn't that important, and was a design flaw.  But since fully transitive const does not give us the benefits that you have been saying it will, why not allow it?
> 
> At the very least, this proof shows that you need a better reason to require fully transitive const/invariant than "I need it for the future."
> 
> -Steve 
> 
>