maxtal@physics.su.OZ.AU (John Max Skaller) writes:

>In article <1993Apr27.064232.25307@cdf.toronto.edu> g2devi@cdf.toronto.edu (Deviasse Robert N.) writes:
>>I've been thinking over the concept of logical constness lately.
>>
>>The basic idea of my (informal) proposal is to allow the programmer
>>to precisely specify what exactly is meant by the constness or volatileness
>>of a class.

> Sure: here's a general way to do it. Define a function

> X::operator==(const X&)

>That defines logical constness: if an object X x is accessed by
>some function, then the function has violated the logical constness
>if, and only if, the comparison of the object with itself before
>and after the operation is equal.

> Because such a function could be quite complex, there
>is no reason to expect a compiler could calculate which
>functions would always preserve logical constness.
>(Halting problem).

> In other words, there is no way to enable compiler
>checking of logical constness for arbitrary classes. The present
>scheme .. assuming physical const == logical const is wrong,
>but the main problem with it is not that you have to cast away
>const sometimes, but the opposite: you can modify the
>public state of an object without changing the object
>(via a pointer).

I have wrestled with this issue of what const means.  (Perhaps I'm still
a newbie.)  I very much like defining logical constness using operator==.
I'll use that conceptually.  Whether something happens in the compiler
I don't think I'll worry about it for a while.  As long as it lets me
insist that I know what I'm doing, I'll be happy for a while.
--
Kevin J. Hopps   e-mail: kjhopps@mmm.com
3M Company   phone: (612) 737-3300
3M Center, Bldg. 235-3B-16 fax: (612) 737-2700
St. Paul, MN 55144-1000      ** USE kjhopps@mmm.com FOR E-MAIL REPLIES **

Sorry for the lateness of the reply, real life had to take priority.


In article <1993Apr29.170005.5828@ucc.su.OZ.AU> maxtal@physics.su.OZ.AU (John Max Skaller) writes:
>In article <1993Apr27.064232.25307@cdf.toronto.edu> g2devi@cdf.toronto.edu (Deviasse Robert N.) writes:
>>I've been thinking over the concept of logical constness lately.
>>
>>The basic idea of my (informal) proposal is to allow the programmer
>>to precisely specify what exactly is meant by the constness or volatileness
>>of a class.
>
> Sure: here's a general way to do it. Define a function
>
> X::operator==(const X&)
>
>That defines logical constness: if an object X x is accessed by
>some function, then the function has violated the logical constness
>if, and only if, the comparison of the object with itself before
>and after the operation is equal.
>
> Because such a function could be quite complex, there
>is no reason to expect a compiler could calculate which
>functions would always preserve logical constness.
>(Halting problem).

The problem is that this function can also be extremely costly, for
example, in the case of a binary seach tree. Also, for a very big
data structure, keeping both a version of the "before" and "after"
images of the object might be very expensive in terms of both time
and space. That's why I proposed the qualifier keyword, to allow the
programmer to more precisely specify what logical constness means.
True, it can't do a complete job of it, but it should do a "good
enough" job in most cases. For cases where the qualifier keyword
is not good enough, class invariants and assertation statements
usually do the trick.

>
> In other words, there is no way to enable compiler
>checking of logical constness for arbitrary classes. The present
>scheme .. assuming physical const == logical const is wrong,
>but the main problem with it is not that you have to cast away
>const sometimes, but the opposite: you can modify the
>public state of an object without changing the object
>(via a pointer).

Agreed, and that's what the qualifier keyword seeks to avoid. There
are 2 problems to deal with:
   * Once you remove the constness of a class (through casting away
     the const or whatever method) the object loses all knowledge of
     it's prior constness and one has to (currently at least).
   * The logical constness (or volatileness) of a class might be
     extended into the values pointer members, but there is currently
     no way to transfer this constness. Thus the state of the class
     might be changed inadvertantly without changing the object.

I think that the qualifier keyword takes care of these concerns.
As a side benefit, the qualifier keyword also allows the volatileness
of a class to be defined.

One thing to note, Mark Jefferys pointed out that there is a problem
with my current proposal. The problem is that taking over the complete
meaning of the qualified type is a very error prone process. Since the
class members that violate the qualifier specification are exceptions to
the expected qualification of members and since these exceptions are usually
few in number, one should specify these members as breaking the rule.

Thus:
   class qualifier Foo{
        qualifier int bar;             // has same qualification as Foo
        int do;                        // always unqualified
   };

would become:
   class Foo{
        int bar;                       // has same default qualification as Foo
        ~qualifier int do;             // always unqualified -- unaffected by
                                       // qualification of Foo
   };

Mark also suggests that ~const and ~volatile be allowed. I'm a little skeptical
that they could have any use, but I don't how also allowing these would hurt.

All right Mr Skaller or anyone else that wishes to jump in, I'll present 3
examples that the qualifier keyword can deal with and if you have any better
way of implementing these in current C++, or have a kludge that works cheaply,
or have some other extension proposal that will handle these cases please
share them.


EXAMPLE 1
=========
   class Envelope{
     private:
       qualifier Envelope * ~qualifier letter;
     // ...
       qualifier Envelope* operator->() const volatile { return letter; }

       virtual void modifyObject();
       int foo;
   };

   Envelope e(/*initialization*/);
   const Envelope ce(/*initialization*/);

In this case, the state of the Envelope includes the state of the letter
object and thus has the same qualification as the Envelope. Thus we want:
   e->foo=42;          // this must be legal
   ce->foo=42;         // this must be illegal

   e->modifyObject();  // this must be legal
   ce->modifyObject(); // this must be illegal


EXAMPLE 2
=========
   class BinaryTree{
      private:
         struct Node{
            qualifier Node * ~qualifier right;
            qualifier Node * ~qualifier left;
            qualifier int key;
            qualifier Foo * ~qualifier data;
         };

         qualifier Node * ~qualifier head;
      public:
         // ...

         const Foo* find(int key) const volatile;  // Find node and reorder
                                                   // tree for efficiency

         void insert(Foo* node,int key) volatile; // Insert unqualified data into tree.
         Foo* remove(int key) volatile;   // Simply destroy node and return
                                          // data value. (note the downcast
   };                                     // to unqualified data)


   // The following 2 constraints are guarenteed to hold:
   // * When qualifier==const in the above, the pointers to the right
   //   and left node may be changed but the data and key must remain constant.
   // * Const member functions may not violate these constraints.

   BinaryTree t;
   const BinaryTree *ct=&t;
   Foo* fp;
   Foo* cfp;
   // ...
   cfp=t.find(1969);              // this should be legal
   cfp=ct->find(25);              // this should be legal

   fp=t.remove();                 // this should be legal
   fp=ct->remove();               // this should be illegal, deleting from
                                  // a constant tree



EXAMPLE 3
=========
   class X{
     public:
       // ...
       qualifier X& do_f() const { /*...*/ return *this; }
       X& alter_X()              { /*...*/ return *this; }
   };


In this case, the function do_f()'s return value is asserted to have
the same as the type qualifier as the *this type, but the function
alter_X() is assumed to have the unqualified X type. Thus we want:

   X x;
   const X cx;

   x.do_f().alter_X().do_f().do_f();      // this must be legal
   cx.do_f().do_f();                      // this must be legal
   cx.alter_X();                          // this must be illegal


==========================================================================

The above examples illustrate some of the problems with the current C++
definition of const and volatile classes and how the qualifier keyword
can deal with them. As mentioned above, alternate type-safe implementations
of the above examples are welcomed.



Conceptually, one may think of the const/volatile/unqualified class hierarchy
as having the following inheritance structure:

                         const volatile CLASS
                             /        \
                            /          \             <- virtual inheritance
                           /            \
                    const CLASS      volatile CLASS
                           \            /
                            \          /
                             \        /
                               CLASS

Upcasting is safe, while downcasting should only be done if there is so
guarantee that there is no effective violation of the type safety. Any scheme
that tries to implement logical constness/volatility should preserve this
hierarchy, at in the semantic sense. One can simulate the above hierarchy
by defining the classes const_volatile_CLASS, const_CLASS, volatile_CLASS, and
CLASS, but this makes the inheritance tree rather messy and we get into
trouble since "const CLASS", etc, all exist and any template will preferably
use it to const_CLASS, etc. The qualifier scheme appears to preserve this
type safe behaviour with a nice clean syntax. Admittedly one cannot perfectly
define logical constness/volatility exactly in all cases, but the scheme
presented  does seem to be "good enough" for most cases and appears to go a
long way to solving the logical qualifier problem.


>
>--
>        JOHN (MAX) SKALLER,         INTERNET:maxtal@suphys.physics.su.oz.au
> Maxtal Pty Ltd,      CSERVE:10236.1703
>        6 MacKay St ASHFIELD,     Mem: SA IT/9/22,SC22/WG21
>        NSW 2131, AUSTRALIA


Take care
    Robert



--
/----------------------------------+------------------------------------------\
| Robert N. Deviasse               |"If we have to re-invent the wheel,       |
| EMAIL: g2devi@cdf.utoronto.ca    |  can we at least make it round this time"|
+----------------------------------+------------------------------------------/

I've been thinking over the concept of logical constness lately.
There are several approaches to get around the problem but all
have one weakness or another. From what I understand about the
~const proposal, this proposal goes a long way towards addressing
the problems of allowing logical constness. Still, from what I
understand of it, I feel a little uneasy about it. My main objection
to what I understand to be the ~const proposal is that it doesn't
tell the compiler what a const class *should* be. Rather, it specifies
what which member functions are allowed to cheat on the definition
of const.

The problem with this approach is that the constness of the class is
completely enforced by the programmer with little language support.
True, it's better to declare that a member function is cheating than
allow free casting away from const, but that's missing the point. The
problem is that (again from what I understand of the ~const proposal)
the ~const allows arbitrary modification of const members. Thus a subclass
may accidently make non-const a member in it's parent that was meant to
be const. Yes I know that through the use of conventions such as only
modifying ~const members through accessors, and only defining accessors
in the base class where the members are declared, this problem will be
avoided. Still, it seems less than satisfactory.


I have an idea that seems not only deal with logical constness,
but will also deal with logical volatileness and logical const
volatileness and a few other qualifier related issues.

The basic idea of my (informal) proposal is to allow the programmer
to precisely specify what exactly is meant by the constness or volatileness
of a class. The basic principle I'm assuming is that the class qualifier
qualifies certain of the members of the class -- but not the member functions.

Suppose we want to declare a dynamic array class. Under my proposal, the
dynamic array class could be declared as:

   class qualifier DynamicArrayOfChar{
     private:
       qualifier char *data;
       int size;
     public:
       DynamicArrayOfChar() : data(0), size(0) {}

       void resetSize(int n);

       qualifier char &operator[](int n) const volatile;   // automagically allocate space as needed

       int length() const volatile { return size; }
       // ...
   };

   DynamicArrayOfChar a;
   const DynamicArrayOfChar ca;
   volatile DynamicArrayOfChar va;
   const volatile DynamicArrayOfChar cva;


So what does the above mean? First of all,the first line ("class qualifier
DynamicArrayOfChar") specifies that the programmer has overridden the meanings
of "DynamicArrayOfChar", "const DynamicArrayOfChar", "volatile DynamicArrayOfChar",
and "const volatile DynamicArrayOfChar". The "qualifier char *data" line
specifies that effectively, "data" has the same qualifier as "this".  That
means that in a, ca, va, and cva, the types of "data" are, unqualified class,
const, volatile, and const volatile respecitively. Also, when calling the
member functions length and operator[], the type of "data" is effectively
const volatile. However, when calling the member function resetSize(), the
"data" member function is effectively an unqualified type.

The "size" member has no qualification and so is unqualified for a, ca, va,
and cva. Finally, the "qualifier char&" return type of the operator[] member
function specifies that the return type qualifier of the operator[] is the
same as the qualifier for the class calling the member function.

Even though the class qualifier has been overloaded, the standard automatic
qualifier conversions still hold and affect the class members. So
((const DynamicArrayOfChar)a) is allowed and the resulting class has "data"
with the qualifier const.

The qualifier approach above seems to capture the meaning of what is meant
by the constness, volatileness, etc of the class without cluttering up the
syntax of class. The qualifier approach has the disadvantage of needing a
new keyword to be added to C++. However, when compared to the ~const proposal,
it seems more type-safe and can handle the volatile keyword.

The qualifier approach also deals very well with class member
function chaining. Consider the folowing situation:

   class X{
     public:
       // ...
       const X& do_f() const { /*...*/ return *this; }
       X& alter_X()          { /*...*/ return *this; }
   };

In the above class, the do_f() and alter_X member functions
were designed to be chained. However, there is one minor
problem. The fact that do_f() doesn't modify the class X
prevents alter_X() from appearing after it in the chain.
We could, of course, change the signature of do_f() to
"X& do_f() const" and cast away the const when we return
*this. This works alright until we declare a const object.
What we would like is for the constness (or like of thereof)
to be preserved along the chain. The qualifier keyword allows
this idea to expressed.

   class X{       // qualifier keyword is not really needed here
     public:
       // ...
       qualifier X& do_f() const { /*...*/ return *this; }
       X& alter_X()              { /*...*/ return *this; }
   };


In this case, the function do_f()'s return value is asserted to have
the same as the type qualifier as the *this type. Thus, the following
is legal:

   X x;
   const X cx;
   x.do_f().alter_X().do_f().do_f();
   cx.do_f().do_f();

//   cx.alter_X();          // ERROR

In this example, the only object that can have the "qualifier X&" type is
*this; but this need not be the case. Consider the following:

   class qualifier Envelope{
     private:
       qualifier Envelope* letter;
     // ...
       qualifier Envelope* operator->() const volatile { return letter; }
   };

Here, "letter" has the same qualifier as "this" and so it may be
returned by the delegation operator ->.


Any comments? I know that there are still a lot of other things to specify
like where exactly the qualifier keyword can appear, and I still have to
ensure that the qualifier keyword does not somehow break the type-safety
of C++, and what happens during inheritance.

If there's any interest, I'll write up a formal proposal.


Take care
    Robert
--
/----------------------------------+------------------------------------------\
| Robert N. Deviasse               |"If we have to re-invent the wheel,       |
| EMAIL: g2devi@cdf.utoronto.ca    |  can we at least make it round this time"|
+----------------------------------+------------------------------------------/

In article <1993Apr27.064232.25307@cdf.toronto.edu> g2devi@cdf.toronto.edu (Deviasse Robert N.) writes:
>
>       qualifier char &operator[](int n) const volatile;   // automagically allocate space as needed
>
You cannot write an array class in which [] grows the array and returns
a reference to its internal storage.

I presume that [] returns a reference to enable usage as an lvalue. Other-
wise, returning a char would be easier. But the code like
 void swap( char&, char& );

 swap( a[i], a[i+1] )
will break if the call to i+1 happened to trigger reallocation. (I know,
many compilers evaluate function calls right to left, and everything
will go well...)

I used to write code like this, until Tom Cargill enlightened me.

Cay

In <1993Apr27.142608.25703@sjsumcs.sjsu.edu> horstman@sjsumcs.sjsu.edu (Cay Horstmann) writes:

>In article <1993Apr27.064232.25307@cdf.toronto.edu> g2devi@cdf.toronto.edu (Deviasse Robert N.) writes:
>>
>>       qualifier char &operator[](int n) const volatile;   // automagically allocate space as needed
>>
>You cannot write an array class in which [] grows the array and returns
>a reference to its internal storage.

>I presume that [] returns a reference to enable usage as an lvalue. Other-
>wise, returning a char would be easier. But the code like
> void swap( char&, char& );

> swap( a[i], a[i+1] )
>will break if the call to i+1 happened to trigger reallocation. (I know,
>many compilers evaluate function calls right to left, and everything
>will go well...)

>I used to write code like this, until Tom Cargill enlightened me.

>Cay

Well perhaps my example was written a little too quickly, but I was trying
to show the essence of the qualifier word without dwelling on a needlessly
complicated example. I wanted to make the "size" attribute nonconst for the
purpose of the example, and it wouldn't make sense to leave it const unless
the size of the array changed. This was the first example that popped into
my mind.

Agreed. The code ideally should have either required explicit memory expansion,
or used threaded arrays, or returned a smart pointer/reference (which holds
both the "this" pointer and the offset) which overloads the operator=.

Anyway, that's besides the point -- what do you think of the "qualifier"
approach?

Take care
    Robert


--
/----------------------------------+------------------------------------------\
| Robert N. Deviasse               |"If we have to re-invent the wheel,       |
| EMAIL: g2devi@cdf.utoronto.ca    |  can we at least make it round this time"|
+----------------------------------+------------------------------------------/

In article <1993Apr27.064232.25307@cdf.toronto.edu> g2devi@cdf.toronto.edu (Deviasse Robert N.) writes:
>I've been thinking over the concept of logical constness lately.
>
>The basic idea of my (informal) proposal is to allow the programmer
>to precisely specify what exactly is meant by the constness or volatileness
>of a class.

 Sure: here's a general way to do it. Define a function

 X::operator==(const X&)

That defines logical constness: if an object X x is accessed by
some function, then the function has violated the logical constness
if, and only if, the comparison of the object with itself before
and after the operation is equal.

 Because such a function could be quite complex, there
is no reason to expect a compiler could calculate which
functions would always preserve logical constness.
(Halting problem).

 In other words, there is no way to enable compiler
checking of logical constness for arbitrary classes. The present
scheme .. assuming physical const == logical const is wrong,
but the main problem with it is not that you have to cast away
const sometimes, but the opposite: you can modify the
public state of an object without changing the object
(via a pointer).

--
        JOHN (MAX) SKALLER,         INTERNET:maxtal@suphys.physics.su.oz.au
 Maxtal Pty Ltd,      CSERVE:10236.1703
        6 MacKay St ASHFIELD,     Mem: SA IT/9/22,SC22/WG21
        NSW 2131, AUSTRALIA

In article <1993Apr27.142608.25703@sjsumcs.sjsu.edu> horstman@sjsumcs.sjsu.edu (Cay Horstmann) writes:
>In article <1993Apr27.064232.25307@cdf.toronto.edu> g2devi@cdf.toronto.edu (Deviasse Robert N.) writes:
>>
>>       qualifier char &operator[](int n) const volatile;   // automagically allocate space as needed
>>
>You cannot write an array class in which [] grows the array and returns
>a reference to its internal storage.

 Why not? If the language required this, it could be done.

 Besides, my array class does exactly that.

 And at least on the 386 you can physically do exactly that.

--
        JOHN (MAX) SKALLER,         INTERNET:maxtal@suphys.physics.su.oz.au
 Maxtal Pty Ltd,      CSERVE:10236.1703
        6 MacKay St ASHFIELD,     Mem: SA IT/9/22,SC22/WG21
        NSW 2131, AUSTRALIA