www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - logical const is a subset of transitive const

reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
I had this idea last night.  Not sure if it is valid, my computational proof 
skills suck :)

If you define logical const as:

I can define an object that has members that will be permanently mutable. 
If this object is declared const, those members are still mutable, and I can 
call functions which only modify those members.  These members are said to 
not hold the state of the object, and so the object is still const, but 
logically const.

And you define transitive const as:

An object that is defined as const means that all members of the object are 
const, and all data that the object references through member pointers and 
references are const.

Now, I can implement an object in transitive-const-land that implements the 
same features as logically const.

Lets say the 'mutable' keyword indicates that a member of an object is 
permanently mutable.  For simplicity's sake, I'll define an object A which 
has two data members m_mutable, and m_normal.  m_mutable is declared 
'mutable', m_normal is not.  I can redefine this as a transitive-const 
object A' which has a sub-object B.  Object B contains m_normal, and A' 
contains m_mutable.

In addition to data members, A has member functions.  Some of these 
functions are declared 'const', meaning they do not modify any member 
variables that are not declared 'mutable'.  The other functions are not 
declared const.  Let's say I have 3 functions.  One function f_const() is 
declared 'const' and does NOT modify m_mutable.  Another function 
f_mutable() is declared 'const' and modifies m_mutable.  A third function 
f_nonconst() is not declared 'const' and modifies both m_mutable and 
m_normal.  In my new representation, f_const and f_nonconst go into B, and 
f_mutable goes in A', and is no longer declared 'const'.

If I say that the logically const version of A' is such that A' is not 
const, but B IS const, then I have the equivalent interface as I did when I 
was using object A, but in a transitive-const world.

Here is the code:

logically const world:
class A
{
   int m_normal;
   mutable int m_mutable;
   int f_const() const
   {
      return m_normal + m_mutable;
   }

   int f_mutable() const
   {
      return m_mutable += m_normal;
   }

   void f_nonconst()
   {
      m_mutable++;
      m_normal++;
   }
}

And in transitive-const land:

class Aprime
{
  int m_mutable;

  class B
  {
     int m_normal;
     int f_const() const
     {
        return m_normal + m_mutable;
     }

     void f_nonconst()
     {
        m_mutable++;
        m_normal++;
     }
  }

   int f_mutable() const
   {
      return m_mutable += m_normal;
   }

   // syntactic sugar
   alias m_b.m_normal m_normal;
   alias m_b.f_nonconst f_nonconst;
   alias m_b.f_const f_const;

   // const B m_b; // logically const version
   B m_b;  // non-const version
}

So,

Here is the kicker.  I can ALMOST implement exactly what I want using 
transitive const using templates, by defining the type of m_b in my template 
declaration.  However, I can't simply create a new logically const reference 
to an existing Aprime (even though they only differ by const-ness).  So this 
is where I would need help from the language developer (i.e. Walter).

All this could be implemented easily enough by the compiler, by allowing the 
keyword mutable, and having the compiler assume a similar structure (the 
structure doesn't have to be exactly implemented this way, it's just a 
proof).  Then, it could allow me to declare an object logically const by 
defining a new keyword.  I propose the keyword lconst.  Then, I would have 
to implement my A class as such:

class A
{
   int m_normal;
   mutable int m_mutable;
   int f_const() const
   {
      return m_normal + m_mutable;
   }

   int f_mutable() lconst // lconst needed or m_mutable can't be changed
   {
      return m_mutable += m_normal;
   }

   void f_nonconst()
   {
      m_mutable++;
      m_normal++;
   }
}

And then I can do things like:

A x = new A;
lconst(A) y = cast(lconst)x;
y.f_normal(); // error, y is lconst
y.f_mutable(); // ok
y.f_const(); // ok

and I can still define transitive const as:

const(A) z = cast(const)z;
z.f_normal(); // error, z is const
z.f_mutable(); // error, z is const
z.f_const(); // ok

OK, so does this all sound like a pipe dream?  I have no idea if this is 
valid, but it sounds right to me.  I think I covered all the bases...

-Steve
Sep 14 2007
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Steven Schveighoffer" wrote

 And in transitive-const land:

 class Aprime
 {
  int m_mutable;

  class B
  {
     int m_normal;
     int f_const() const
     {
        return m_normal + m_mutable;
     }

     void f_nonconst()
     {
        m_mutable++;
        m_normal++;
     }
  }

   int f_mutable() const
   {
      return m_mutable += m_normal;
   }


Oops, this should have been:

int f_mutable() // no const

-Steve
Sep 14 2007
parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 9/14/07, Steven Schveighoffer <schveiguy yahoo.com> wrote:
I can't argue with your reasoning.

...but...

It's a paradigm thing. Logical const is all about *interface*;
physical const is all about *implementation*.

If keywords existed for both paradigms, I think there would only be
more confusion. Writers of classes would have to choose between
viewpoints, and there would be no consistency.

For example, suppose I have a Date class, with a function
getMonthLong. Should it be declared as:
const string getMonthLong()

or as
lconst string getMonthLong()
?

For sake of argument, let's say my first implementation is physically
const. Should I declare it const to reflect that? Or should I declare
it logically const so that I can change the implementation at a later
date?

If I choose "const", then I am implicitly saying "it is safe for
multiple threads simultaneously to reference the same instance of
const(Date) without mutex locking". So programmers would be free to
use the class in just that way. If I choose "lconst" then I am
implicitly saying "it is /not/ safe".

Why would I want to declare it not threadsafe, when it in fact, is?
Because of the possibility that I might change the implementation
later? What if I don't plan to. Am I allowed to change my mind.

It turns out, the answer is no. Suppose I chose to go with const,
reflecting the current, physically const, implementation, and people
start writing code with it. Suppose then that at a later date I change
the implementation so it's now no longer physically const. Then I'd
need to change the declaration to lconst or it wouldn't compile. But
that wouldn't help all the people who are already using my class in
multithreaded applications - particularly becase, as Walter is fond of
pointing out, this circumstance is not compiler checkable. All the
hapless programmer would know that, at some time after upgrading to
the latest version of Date, their program randomly crashes in an
almost-impossible-to-diagnose way.

In summary - we've already got two keywords for constness (const and
invariant), and that's already one too many from the point of view of
seeming confusing. I'd rather not see another one.
Sep 14 2007
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Janice Caron" wrote

 On 9/14/07, Steven Schveighoffer <schveiguy yahoo.com> wrote:
 I can't argue with your reasoning.


Thanks, that helps my self confidence :) Seriously!  (sometimes electronic 
communication seems sarcastic, but I assure you this is genuine)  I respect 
your opinion greatly.


 ...but...

 It's a paradigm thing. Logical const is all about *interface*;
 physical const is all about *implementation*.


Then declare everything lconst.  You will not get compiler optimizations.  I 
have no problem with that.


 If keywords existed for both paradigms, I think there would only be
 more confusion. Writers of classes would have to choose between
 viewpoints, and there would be no consistency.


I think the alternative is too restrictive.  Only using transitive const 
restricts those who wish to have the benefits of the compiler helping them 
prevent mistakes in logical-const type situations.  Only using logical const 
prevents the compiler from making assumptions about const, and could hamper 
D in the future of multi-core systems (Walter's suggestion, not mine).

I think this medium allows both to co-exist.  There is only one viewpoint. 
Use logical const if you need it, otherwise, use const to get compiler 
optimizations.  If you are unsure whether you are going to need logical 
const, make it logical const.


 If I choose "const", then I am implicitly saying "it is safe for
 multiple threads simultaneously to reference the same instance of
 const(Date) without mutex locking".


I disagree.  Declaring it const means that calling that function will not 
change any members of the date object.

Declaring it pure means that it will always return the same value, which 
means it would be safe for multiple threads to access without locking (I am 
very new to this concept, but I got all my knowledge from wikipedia: 
http://en.wikipedia.org/wiki/Functional_programming)

If the class is non-mutable after creation, then declare the methods to be 
pure.  Otherwise declare it const.  const does NOT mean thread safe.


 So programmers would be free to
 use the class in just that way. If I choose "lconst" then I am
 implicitly saying "it is /not/ safe".


No, const/lconst has nothing to do with thread safety.  It only has to do 
with whether the method changes anything local to the object or objects it 
contains or associates with.  Even with only transitive const, you cannot 
ensure thread safety just becase a method is const.

e.g.

const void method()
{
   globalVariable++;
}


 Why would I want to declare it not threadsafe, when it in fact, is?
 Because of the possibility that I might change the implementation
 later? What if I don't plan to. Am I allowed to change my mind.

 It turns out, the answer is no. Suppose I chose to go with const,
 reflecting the current, physically const, implementation, and people
 start writing code with it. Suppose then that at a later date I change
 the implementation so it's now no longer physically const. Then I'd
 need to change the declaration to lconst or it wouldn't compile. But
 that wouldn't help all the people who are already using my class in
 multithreaded applications - particularly becase, as Walter is fond of
 pointing out, this circumstance is not compiler checkable. All the
 hapless programmer would know that, at some time after upgrading to
 the latest version of Date, their program randomly crashes in an
 almost-impossible-to-diagnose way.


I think this is incorrect.  It would not randomly crash, it would not 
compile.  They would not be able to call the now lconst method through a 
const reference.

If you were using the method previously assuming it was thread safe because 
it was const, then you were not understanding const properly.

I think your argument stems from the incorrect assumption that const == 
thread safe, which I think I've argued against above.


 In summary - we've already got two keywords for constness (const and
 invariant), and that's already one too many from the point of view of
 seeming confusing. I'd rather not see another one.


I think invariant, const, and lconst all have clear meanings, are clearly 
separated.  Since lconst/invariant would be new to D, a new programmer would 
need to know about them to use them, so they would need to read 
documentation and descriptions of the keywords to understand them.  I agree 
that in learning a new language, it would be a slightly larger learning 
curve, but with simple examples (please note, examples are key, I love 
examples) and a concise explanation would make learning const take at most 1 
hour.  At least for me :)

What I think WOULD be confusing and ambiguous is to allow logical const, but 
to use const to refer to both logically const and transitive const 
references.

What I think would be error prone is to not allow logical const, or only 
allow it through complicated template wrappers.  This would dissuade people 
from using logical const as a tool to help them design better software.

And I'm not dead-set on lconst.  I actually don't like it.  But it seemed 
logical (no pun intended).  If someone has a better idea for a keyword, then 
I'm all for it.  But I do think another keyword is required to clarify what 
the author of the code wants.

Janice, thanks for your views, I don't think I would have understood this 
whole const battle enough if it weren't for your persistance :)

-Steve
Sep 14 2007
parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 9/14/07, Steven Schveighoffer <schveiguy yahoo.com> wrote:

 I disagree.  Declaring it const means that calling that function will not
 change any members of the date object.

 Declaring it pure means that it will always return the same value, which
 means it would be safe for multiple threads to access without locking (I am
 very new to this concept, but I got all my knowledge from wikipedia:
 http://en.wikipedia.org/wiki/Functional_programming)


I stand corrected. Yes, you are right. A function can be declared
const and still read and write global variables, and hence not be
threadsafe.

In that case, I don't understand why Walter wants to outlaw intransitive const!



 I think this is incorrect.  It would not randomly crash, it would not
 compile.  They would not be able to call the now lconst method through a
 const reference.


I stand corrected again. Well argued.



 I think your argument stems from the incorrect assumption that const ==
 thread safe, which I think I've argued against above.


It did. Because that was the only only argument that Walter managed to
get through into my brain when he was justifying that there would be
no way to specify e.g. pointer to const pointer to int.



 I think invariant, const, and lconst all have clear meanings, are clearly
 separated.  Since lconst/invariant would be new to D, a new programmer would
 need to know about them to use them, so they would need to read
 documentation and descriptions of the keywords to understand them.  I agree
 that in learning a new language, it would be a slightly larger learning
 curve, but with simple examples (please note, examples are key, I love
 examples) and a concise explanation would make learning const take at most 1
 hour.  At least for me :)


Of course, there would be /four/ keywords, if you count "pure". And
five if you count "mutable".
:-)
Sep 14 2007
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Janice Caron wrote:

 On 9/14/07, Steven Schveighoffer <schveiguy yahoo.com> wrote:

 I disagree.  Declaring it const means that calling that function will not
 change any members of the date object.

 Declaring it pure means that it will always return the same value, which
 means it would be safe for multiple threads to access without locking (I am
 very new to this concept, but I got all my knowledge from wikipedia:
 http://en.wikipedia.org/wiki/Functional_programming)


 
 I stand corrected. Yes, you are right. A function can be declared
 const and still read and write global variables, and hence not be
 threadsafe.


Whoa.  Excuse me while I get up off the floor after having the rug 
pulled out from under me.

Was the point of const then perhaps more micro-level optimizations? 
Things like if "X is const then I can assume the value in this register 
is still valid without having to re-fetch from main memory".  For instance
     X* foo;
     foo.bar = 10;
     func(foo);  // takes fully_const X*

     // In C++ const the next line requires re-fetching foo.bar
     // from memory,
     // because func might actually change fully_const X*.
     // In D it could reuse the value in register, or even assume it's
     // still the constant 10.

     Y biff = foo.bar;

Just a guess.  IANACW (compiler writer).

--bb
Sep 14 2007
next sibling parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 9/14/07, Bill Baxter <dnewsgroup billbaxter.com> wrote:

 Was the point of const


Dunno about the "point".

A const /function/ (as opposed to a const /object/) is a member
function of some class T which can see a hidden variable called "this"
of type const(T).

...or put another way, it can't modify any member variables of the class.

There's no such thing as a const function which is not a member
function. That would make no sense.

A non-const member function can also see a variable called "this", but
this time it's of type T, not const(T).

So yes, a const function can still read and write global variables.

For that matter, it can even legitimately modify it's own class member
variables - but only through another pointer! For example:

class A
{
    int x;
    const void f(A a)
    {
        a.x = 3;
    }
}

A a = new A();
a.f(a);

I guess the "point" of a const function is exactly the same as the
"point" of a static or global function which takes a const parameter.
Same difference. In either case, there's an object which is physically
const. The compiler can make presumably make some assumptions and/or
optimisations concerning that variable.

What I /don't/ understand is why D lets you declare a member function
(as opposed to an object) as being invariant. To my brain, that ought
to mean the function sees "this" as having the type invariant(T) - but
that's clearly an invalid assumption, because "this" /can/ be
modified. You have a read-only view, that's all.

"Pure" on the other hand, only makes sense for functions. So far as I
know, there's no such thing as a pure object.
Sep 14 2007
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Janice Caron" wrote

 What I /don't/ understand is why D lets you declare a member function
 (as opposed to an object) as being invariant. To my brain, that ought
 to mean the function sees "this" as having the type invariant(T) - but
 that's clearly an invalid assumption, because "this" /can/ be
 modified. You have a read-only view, that's all.


Yeah, I totally agree that invariant declared on a function doesn't seem to 
be right.  I'm guessing the only reason they did that is because it makes no 
sense to return an invariant type, so you could put invariant before the 
function name and not be ambiguous.

i.e.

const int* f(); // is f const, or is it returning a const int*?
invariant int* f(); // can't have a pointer to invariant (at least in 
current spec), so invariant must refer to f

If that is the reason, then I say use const, and put it after the func 
declaration, like in C++.  May look weird, but it's unambiguous.


 "Pure" on the other hand, only makes sense for functions. So far as I
 know, there's no such thing as a pure object.


pure implies that:
1. you can only call pure functions
2. you can only access invariant data (data that cannot be changed anywhere 
else).

so I think you are right, pure is more for functions.

BTW, if we get rid of invariant for functions meaning the same thing as 
const functions, I think pure should be replaced with invariant.  It makes 
more sense to me as an intuitive keyword.  An invariant function cannot 
change anything and can only access invariant data, and call other invariant 
functions.  Makes a lot of sense to me...

-Steve
Sep 14 2007
next sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 9/14/07, Steven Schveighoffer <schveiguy yahoo.com> wrote:

 const int* f(); // is f const, or is it returning a const int*?


I tried playing around with compiling things like this. In D2.0, it
definitely looks like the compiler interprets this as meaning that f
is const.

Maybe it also means the return value is /also/ const? As in, it
returns const(int *). I haven't checked. Either way, weird.



 If that is the reason, then I say use const, and put it after the func
 declaration, like in C++.  May look weird, but it's unambiguous.


There's also the possibilities of:
int * const f()
int * const(f())

These would be more in line with D's "functional notation" for const,
as opposed to C's postfix notation.
Sep 14 2007
prev sibling parent reply Bruce Adams <tortoise_74 yeah.who.co.uk> writes:
Steven Schveighoffer Wrote:


 "Janice Caron" wrote

 What I /don't/ understand is why D lets you declare a member function
 (as opposed to an object) as being invariant. To my brain, that ought
 to mean the function sees "this" as having the type invariant(T) - but
 that's clearly an invalid assumption, because "this" /can/ be
 modified. You have a read-only view, that's all.


 
 Yeah, I totally agree that invariant declared on a function doesn't seem to 
 be right.  I'm guessing the only reason they did that is because it makes no 
 sense to return an invariant type, so you could put invariant before the 
 function name and not be ambiguous.
 
 i.e.
 
 const int* f(); // is f const, or is it returning a const int*?
 invariant int* f(); // can't have a pointer to invariant (at least in 
 current spec), so invariant must refer to f
 
 If that is the reason, then I say use const, and put it after the func 
 declaration, like in C++.  May look weird, but it's unambiguous.
 

 "Pure" on the other hand, only makes sense for functions. So far as I
 know, there's no such thing as a pure object.


 
 pure implies that:
 1. you can only call pure functions
 2. you can only access invariant data (data that cannot be changed anywhere 
 else).
 
 so I think you are right, pure is more for functions.
 
 BTW, if we get rid of invariant for functions meaning the same thing as 
 const functions, I think pure should be replaced with invariant.  It makes 
 more sense to me as an intuitive keyword.  An invariant function cannot 
 change anything and can only access invariant data, and call other invariant 
 functions.  Makes a lot of sense to me...
 
 -Steve 
 


Pure is a good intuitive name to use for several reasons.
For a start it has exactly the same meaning as its counterpart in Fortran-90.
If it exists in any functional languages out there most likely they use the
same terminology.
Sep 16 2007
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Bruce Adams" wrote

 Steven Schveighoffer Wrote:

 BTW, if we get rid of invariant for functions meaning the same thing as
 const functions, I think pure should be replaced with invariant.  It 
 makes
 more sense to me as an intuitive keyword.  An invariant function cannot
 change anything and can only access invariant data, and call other 
 invariant
 functions.  Makes a lot of sense to me...

 -Steve


 Pure is a good intuitive name to use for several reasons.
 For a start it has exactly the same meaning as its counterpart in 
 Fortran-90. If it exists in any functional languages out there most likely 
 they use the same terminology.


I agree, using the same terminology is a good thing.  I personally don't use 
functional programming, so I could care less what the keyword is as I 
probably will not use it.  I was just pointing out that 'invariant' to me 
means 'cannot change anything whatsoever' *intuitively* more than pure does. 
I understand the reasoning behind using pure as a keyword, but for someone 
who doesn't use FP, it is not as intuitive.  For example, it could be taken 
to mean 'free from defects', which would be a very arrogant declaration 
indeed :)

In any case, I've re-examined what invariant functions mean, and now I 
understand that there are *both* const and invariant functions, and they 
mean two separate things.  Since my argument to change 'pure' to 'invariant' 
was based on the belief that const functions were described with the 
'invariant' keyword to get around syntax requirements, my argument is no 
longer valid.

So I take it back, you can have pure :)

-Steve
Sep 17 2007
prev sibling parent reply Daniel Keep <daniel.keep.lists gmail.com> writes:
Janice Caron wrote:

 [...]
 What I /don't/ understand is why D lets you declare a member function
 (as opposed to an object) as being invariant. To my brain, that ought
 to mean the function sees "this" as having the type invariant(T) - but
 that's clearly an invalid assumption, because "this" /can/ be
 modified. You have a read-only view, that's all.


I'd always assumed it was so you could do this:

class A
{
    int foo() { ... }
    invariant int foo() { ... }
}

{
    invariant(A) a = cast(invariant) new A;
    a.foo();
}

I realise that I could have accomplished the same thing by making the
second foo a const method, but the question is, is that always the same?
 I can't think of a case, but it's possible that sometimes the
implementation might change or be more efficient if you've got
invariant(this) instead of const(this).

	-- Daniel
Sep 14 2007
parent reply "news.digitalmars.com" <schveiguy yahoo.com> writes:
"Daniel Keep" wrote

 I'd always assumed it was so you could do this:

 class A
 {
    int foo() { ... }
    invariant int foo() { ... }
 }

 {
    invariant(A) a = cast(invariant) new A;
    a.foo();
 }

 I realise that I could have accomplished the same thing by making the
 second foo a const method, but the question is, is that always the same?
 I can't think of a case, but it's possible that sometimes the
 implementation might change or be more efficient if you've got
 invariant(this) instead of const(this).


Here is the spec:

" Invariant member functions are guaranteed that the object and anything 
referred to by the this reference is invariant."

" Const member functions are functions that are not allowed to change any 
part of the object through the member function's this reference."

A const function guarantees not to change the object.

An invariant function can only be called on objects that are declared 
invariant.  This should mean that at least the object is not going to 
change.  This also implies that the function is const.

This suggests that the compiler can make more optimizations in invariant 
functions because an invariant object is not supposed to change.  In a const 
function, there could be a mutable pointer to the same data, so the compiler 
can't make those same assumptions.

So I think this is how it works:

A
{
  invariant void ifunc();
  const void cfunc();
}

const(A) a1 = new A;
invariant(A) a2 = cast(invariant) new A;

a1.ifunc(); // error, a1 is not invariant
a1.cfunc(); // ok
a2.ifunc(); // ok
a2.cfunc(); // ok

One thing that is notably missing from the spec is how to declare a const 
member function.  As it has been stated in other threads, it is ambiguous to 
do:

const int *f();

As you don't know if f is const, or if the return value is a const pointer.

-Steve
Sep 14 2007
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"news.digitalmars.com" wrote

Hm... this should have been "Steve Schveighoffer"

Sorry, I setup my news reader at home, and put news.digitalmars.com in too 
many places lol :)

-Steve
Sep 14 2007
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Bill Baxter" wrote

 Janice Caron wrote:

 On 9/14/07, Steven Schveighoffer <schveiguy yahoo.com> wrote:

 I disagree.  Declaring it const means that calling that function will 
 not
 change any members of the date object.

 Declaring it pure means that it will always return the same value, which
 means it would be safe for multiple threads to access without locking (I 
 am
 very new to this concept, but I got all my knowledge from wikipedia:
 http://en.wikipedia.org/wiki/Functional_programming)


 I stand corrected. Yes, you are right. A function can be declared
 const and still read and write global variables, and hence not be
 threadsafe.


 Whoa.  Excuse me while I get up off the floor after having the rug pulled 
 out from under me.

 Was the point of const then perhaps more micro-level optimizations? Things 
 like if "X is const then I can assume the value in this register is still 
 valid without having to re-fetch from main memory".  For instance
     X* foo;
     foo.bar = 10;
     func(foo);  // takes fully_const X*

     // In C++ const the next line requires re-fetching foo.bar
     // from memory,
     // because func might actually change fully_const X*.
     // In D it could reuse the value in register, or even assume it's
     // still the constant 10.

     Y biff = foo.bar;

 Just a guess.  IANACW (compiler writer).


IAANACW (I am also not a compiler writer).

You are wrong in your assumption.  Even in a single thread, I can circumvent 
the constness by having a global non-const pointer to my object, and using 
that object.  Very bad implementation, but it would not break the rules. 
For example:

X mutableinstance;

class X
{
   int bar;
}

func(const X myref)
{
  mutableinstance.bar++; // I can do this because I'm not changing myref
}

myfoolishfunc()
{
  X foo = new X;
  mutableinstance = foo;
  foo.bar = 10;
  func(foo); // increments foo.bar because mutableinstance is foo

  int biff = foo.bar; // biff now should be 11.
}

The definition of a function that does not have ANY side effects is a pure 
function (see the functional programming reference).  That type of function 
would not be able to change anything, even global variables, and so the 
compiler could assume that bar still contained 10  (BTW you cannot assume 
the register is still valid after calling func because func is allowed to 
change registers, even if it is pure).

However, in multithreaded land, it is questionable whether you can assume 
that foo will not change even with pure functions because another thread 
could conceivably come along and wreck foo while you are calling your pure 
function.

Multithreaded programming is hard.  const sucks.  There are a lot of strange 
rules.  Not being a compiler writer, I have no idea what compiler advantages 
transitive const has over logical const, but I'm going to defer to Walter on 
that because he is the compiler writer, and he seems to be very hard-set on 
it.  However, being an OO programmer and designer, and having lots of 
experience with threading, I want to ensure that the compiler optimizations 
are not going to impede the language as a good OO-equiped language.  I hope 
with my proposal, that both sides are satisfied.

-Steve
Sep 14 2007
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Steven Schveighoffer wrote:

 "Bill Baxter" wrote

 Janice Caron wrote:

 On 9/14/07, Steven Schveighoffer <schveiguy yahoo.com> wrote:

 I disagree.  Declaring it const means that calling that function will 
 not
 change any members of the date object.

 Declaring it pure means that it will always return the same value, which
 means it would be safe for multiple threads to access without locking (I 
 am
 very new to this concept, but I got all my knowledge from wikipedia:
 http://en.wikipedia.org/wiki/Functional_programming)


 I stand corrected. Yes, you are right. A function can be declared
 const and still read and write global variables, and hence not be
 threadsafe.


 Whoa.  Excuse me while I get up off the floor after having the rug pulled 
 out from under me.

 Was the point of const then perhaps more micro-level optimizations? Things 
 like if "X is const then I can assume the value in this register is still 
 valid without having to re-fetch from main memory".  For instance
     X* foo;
     foo.bar = 10;
     func(foo);  // takes fully_const X*

     // In C++ const the next line requires re-fetching foo.bar
     // from memory,
     // because func might actually change fully_const X*.
     // In D it could reuse the value in register, or even assume it's
     // still the constant 10.

     Y biff = foo.bar;

 Just a guess.  IANACW (compiler writer).


 
 IAANACW (I am also not a compiler writer).
 
 You are wrong in your assumption.  Even in a single thread, I can circumvent 
 the constness by having a global non-const pointer to my object, and using 
 that object.  Very bad implementation, but it would not break the rules. 
 For example:
 
 X mutableinstance;
 
 class X
 {
    int bar;
 }
 
 func(const X myref)
 {
   mutableinstance.bar++; // I can do this because I'm not changing myref
 }
 
 myfoolishfunc()
 {
   X foo = new X;
   mutableinstance = foo;
   foo.bar = 10;
   func(foo); // increments foo.bar because mutableinstance is foo
 
   int biff = foo.bar; // biff now should be 11.
 }


Yeh, ok.  It's perverse, but it does show clearly that even transitive 
const is not enough to guarantee anything.   But that example is 
definitely teetering on the edge of undefined behavior.  It depends on 
whether you take "const X myref" to mean "this function will not modify 
the contents of myref" vs "this function will not modify myref via the 
myref handle".   It might be reasonable to say that if you alias a const 
argument then you're in undefined behavior territory.


 (BTW you cannot assume 
 the register is still valid after calling func because func is allowed to 
 change registers, even if it is pure).


Well, if so, that rather pokes a hole in my example.  So I have no clue 
what great optimizations Walter has in mind.  He should just tell us.


 However, in multithreaded land, it is questionable whether you can assume 
 that foo will not change even with pure functions because another thread 
 could conceivably come along and wreck foo while you are calling your pure 
 function.


Isn't that "you're on your own" territory there?  Sure some other thread 
could be changing foo, but if you're using that sort of threading then 
it was up to you to properly mutex protect foo.  I think the purpose of 
pure is more to support constructs with more limited scope, like 
parallel foreach loops.


 Multithreaded programming is hard.  const sucks.  There are a lot of strange 
 rules.  Not being a compiler writer, I have no idea what compiler advantages 
 transitive const has over logical const, but I'm going to defer to Walter on 
 that because he is the compiler writer, and he seems to be very hard-set on 
 it. 


If there is some clear advantage to transitive, then it shouldn't be too 
difficult for Walter to explain what it is.   It may even be beneficial. 
  Writing things down is a good way to discover flaws in one's own 
logic.  There's a reason journals actually require people to write the 
whole article rather than just allowing them to publish their 
conclusions.  :-)

--bb
Sep 14 2007
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Bill Baxter" wrote

 Steven Schveighoffer wrote:

 IAANACW (I am also not a compiler writer).

 You are wrong in your assumption.  Even in a single thread, I can 
 circumvent the constness by having a global non-const pointer to my 
 object, and using that object.  Very bad implementation, but it would not 
 break the rules. For example:

 X mutableinstance;

 class X
 {
    int bar;
 }

 func(const X myref)
 {
   mutableinstance.bar++; // I can do this because I'm not changing myref
 }

 myfoolishfunc()
 {
   X foo = new X;
   mutableinstance = foo;
   foo.bar = 10;
   func(foo); // increments foo.bar because mutableinstance is foo

   int biff = foo.bar; // biff now should be 11.
 }


 Yeh, ok.  It's perverse, but it does show clearly that even transitive 
 const is not enough to guarantee anything.   But that example is 
 definitely teetering on the edge of undefined behavior.  It depends on 
 whether you take "const X myref" to mean "this function will not modify 
 the contents of myref" vs "this function will not modify myref via the 
 myref handle".   It might be reasonable to say that if you alias a const 
 argument then you're in undefined behavior territory.


My example is perfectly defined and legal, and should behave the same way 
every time.  But it's not likely to be coded this way :)  This kind of thing 
CAN happen in real code, it's just usually that your function calls a global 
function, which calls another function, which adds an object to a queue, 
which uses some mutable reference to your object, and bingo (or even more 
crazy stuff).  The point is that you cannot guarantee thread safety in the 
language without proper thread tools such as mutexes.  Const/invariant is 
not thread safety.


 (BTW you cannot assume the register is still valid after calling func 
 because func is allowed to change registers, even if it is pure).


 Well, if so, that rather pokes a hole in my example.  So I have no clue 
 what great optimizations Walter has in mind.  He should just tell us.


This is just basic assembly.  Every function is free to use registers in the 
processor.  There are clearly defined rules as to what registers mean what 
when calling a function and when returning (this is why you have all those 
stupid modifiers for Microsoft Windows, like STDCALL, and CDECL, these are 
defining different ways functions are called).  All the other registers are 
fair game.  If the compiler wants to save those registers, it must push them 
on the stack, then pop them after the return (which it could do as an 
optimization, I suppose, it depends on what's faster, loading a constant 
into a register, or pushing/popping a value from the stack).

That doesn't mean that optimizations can't be made by the compiler.  In some 
cases you need to declare variables volatile (does D have this concept?) to 
prevent the compiler from optimizing out 2 different references to the 
variable, like so:

if(x == 5)
{
    y = 2;
    if(x == 5 && n == 3) // x == 5 could be optimized out by the compiler 
unless x is volatile.


 However, in multithreaded land, it is questionable whether you can assume 
 that foo will not change even with pure functions because another thread 
 could conceivably come along and wreck foo while you are calling your 
 pure function.


 Isn't that "you're on your own" territory there?  Sure some other thread 
 could be changing foo, but if you're using that sort of threading then it 
 was up to you to properly mutex protect foo.  I think the purpose of pure 
 is more to support constructs with more limited scope, like parallel 
 foreach loops.


The purpose of pure, if I understand it correctly is to save time calling 
functions that will return exactly the same value and have no impact on 
other data.  For example, if I have a function f() which is pure, it will 
return the same value each time, so a statement like f() * f() will only 
call f() once.  The compiler could also call execute two different pure 
functions at once through 2 cores without fear that one would interfere with 
the other.

But pure does not guarantee that another thread can't change any state in 
your program.  That is what mutex locks are for.

-Steve
Sep 14 2007
prev sibling next sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 9/15/07, Janice Caron <caron800 googlemail.com> wrote:

 The irony is that a C++ const std.string is only /logically/ const,
 not physically const, because it has a mutable reference counter in
 it.


(I don't think it actually uses the mutable keyword in its source
though. mutable members and intransitive const are to some extent
interchangeable).

So here's how it works. A C++ std.string is a reference object, like a
class in D. The class data (on the heap) contains a reference counter.
When you copy a string, you get one more pointer to the same
heap-data, but the reference counter is incremented. When you destroy
a string, the reference counter is decremented, and the heap data is
not freed unless the reference counter reaches zero.

So, consider the following C++ code:
const string s1 = "hello";
const string s2 = s1;

That's like, in D:
class String { /* whatever */ }
const String s1 = new String("hello");
const String s2 = s1.dup();
...where s1.dup() MODIFIES s1 (increments a reference counter) despite
s1 being const.

It is allowed to do this because const is not transitive in C++
Sep 14 2007
prev sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 9/14/07, Bill Baxter <dnewsgroup billbaxter.com> wrote:

 It depends on
 whether you take "const X myref" to mean "this function will not modify
 the contents of myref" vs "this function will not modify myref via the
 myref handle".


The latter, by definition. The former would be "invariant" in D-speak.



 It might be reasonable to say that if you alias a const
 argument then you're in undefined behavior territory.


I think I suggested that in another thread ("restrict sucks"), but the
idea changing the default behavior and breaking deployed code in
un-diagnosable ways didn't go down too well. :-)




 However, in multithreaded land, it is questionable whether you can assume
 that foo will not change even with pure functions because another thread
 could conceivably come along and wreck foo while you are calling your pure
 function.


 Isn't that "you're on your own" territory there?  Sure some other thread
 could be changing foo, but if you're using that sort of threading then
 it was up to you to properly mutex protect foo.  I think the purpose of
 pure is more to support constructs with more limited scope, like
 parallel foreach loops.


True. In a pure function, two threads may simultaneously call f(x)
without mutex locking and get the same result... but there have to be
restrictions on the type of x or it won't work. If x is a value type
with no references, like int, and it's passed by value, that's
obviously no problem. At the other extreme, if x were a non-const
reference type, it would totally screw things up and needs to be
forbidden. But in between, there's this grey area...

If x is of type const(X), where X is a reference type then we (that
is, Walter) would /like/ it to be true that f(x) can be safely called
by multiple threads without mutex locking. Unfortunately, because even
a const object have non-pure const functions (e.g. those that call
scanf(), or read and write global variables) this desire does not hold
true.

I guess it /would/ hold true if the class X had no const functions,
but only pure functions. That is compiler-checkable.

In C++, there is the notion of a "concrete" object. There's no keyword
for it, it's just a design idea. A concrete object is an object that
behaves like a value type. It might actually /be/ a value type (e.g. a
complex number), or it might be a reference type with some sort of
smart pointer and copy-on-write (e.g. an arbitrary size matrix, or a
C++ std.string). Does this help D? I have absolutely no idea. Walter
spoke of "reference types that behave like value types", and maybe
that's what he had in mind. Operator overloads make a lot of sense for
concrete objects.

The irony is that a C++ const std.string is only /logically/ const,
not physically const, because it has a mutable reference counter in
it. Without that, it wouldn't work. (It also wouldn't work without a
copy constructor and an assignment operator).

It is safe for multiple threads to share the same instance of a C++
const std.string, not because of inherent properties of constness, but
because the implementation of std.string contains proper mutex locking
where it's needed.

In other words, a C++ const std.string can be passed to a pure
function, despite not being physically const.

The ability to be able to create concrete objects such as arbitrarily
large matrices /requires/ mutable members and/or intransitive const
(unless every matrix were "final", which would be heavy on memory use
and allocations). This is a good use case for that which Walter wants
to outlaw. However, to use them in multi-threaded land would require
the programmer of such an object to mutex-lock as required. It seems
that Walter doesn't trust the programmer to get this right.

(That's why, in another thread, I proposed that mutable members be
allowed so long as they're mutex protected. It was subsequently
pointed out to me that so long as we're prepared to risk casting away
const, we don't need language support. But are we? That's officially
undefined behaviour.)

So, you should be able to pass a concrete object to a pure function.
Unfortunately, except for very simple cases, we're not allowed to
write them.
Sep 14 2007