In C and C++, the "inert" pointer type void * can be used to
create collection data structures that can collect any
pointer type.  I propose an extension to C++ to create
corresponding "inert" types for all types in C++.

C++ already has "pseudo function templates"
(static_cast<X>(), for example).  I propose the "pseudo
class template" inert<X>.  For every type X, there is a
corresponding type inert<X>. inert<> has the following
properties for any type X:

o  static_cast<X>(inert<X>) is valid.
   static_cast<inert<X> >(X) is valid as well.  Furthermore,
   static_cast<X>(static_cast<inert<X> >(x)) does not change
   the value of x.

o  If X(const X &) exists, inert<X>(const inert<X> &) exists.
   Otherwise, if X(X &) exists, inert<X>(inert<X> &) exists.
   X(x) and
   static_cast<X>(inert<X>(static_cast<inert<X> >(x))) must
   produce the same result for all valid x.  Therefore, for
   each value of X, there is a single corresponding value of
   inert<X> given by static_cast<inert<X> >().

o  For each = and == operator valid for two operands of
   type X, there must be a corresponding operator valid for
   two operands of type inert<X>.  If static_cast<inert<X> >
   is applied to two X operands, the corresponding operator
   is applied to the two operands, then static_cast<X> is
   applied to the two operands, the resulting pair will be
   the same as if the X operator were applied to the
   original operand pair.  Furthermore, in the case of
   corresponding == operators, the operator result must be
   the same in the given scenario.

o  If X(void) exists, then inert<X>(void) exists.  If
   inert<X>(void) is substituted for any invocation of
   X(void) the result must be the value of inert<X> that
   corresponds to the value that would have resulted from
   calling X(void).

The simplest implementation for all this is to have inert<X>
simply be X.  Minimally, inert<X> should be the same type
for all types X that are built-in or pointer types and of a
particular size.  For example, on a typical 32-byte
architecture inert<long>, inert<unsigned long> and inert<T
*> (T being any type) should all be the same type. The next
step up would be for all types that assign, copy or compare
byte-by-byte and are of a particular size (perhaps with
padding to some word size) to map to the same inert type.
(If inert<X> has an == operator, static_cast<inert<X> >
would have to zero out "pad" bytes in X.)

So, what is the point of all this?  Consider the following
definitions for a stack container:

template<typename X> class Stack_
  {
  // ...
  public:
    void push(X);
    X pop(void);
  };

template<typename X> class Stack
  : public Stack_<inert<X> >
  {
  public:
    void push(X x)
      { Stack_::push(static_cast<inert<X> >(x)); }
    X pop(void)
      { return(static_cast<X>(Stack_::pop())); }
  };

The use of inert<> reduces the number of instantiations of
Stack_<>.  The wrapper template Stack<> would, with inlining,
generate little or no code.

The existence of inert<> would eliminate the need for partial
template instantiation for pointer types.  I find this feature
to be very unintuitive and difficult to describe formally.
inert<> is also difficult to describe formally, but I would
argue that it is very intuitive.

It might be useful to have a second pseudo template
packed_inert<>.  packed_inert<X> would store instances of
X with all "pad" bytes and vptrs "squeezed out".
packed_inert<> would otherwise work the same as inert<>.
inert-based collection (e.g. Stack) could have a packed
equivalent (e.g. PackedStack) to be used when memory is
dear.



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Walter W. Karas wrote:
>
> template<typename X> class Stack_
>   {
>   // ...
>   public:
>     void push(X);
>     X pop(void);
>   };
>
> template<typename X> class Stack
>   : public Stack_<inert<X> >
>   {
>   public:
>     void push(X x)
>       { Stack_::push(static_cast<inert<X> >(x)); }
>     X pop(void)
>       { return(static_cast<X>(Stack_::pop())); }
>   };
>

Why not just write it in C++?

template <int N> class Stack_
{
public:
 void push(void *x); // push N bytes located
    // at x onto the stack
 void *pop();  // pop N bytes off the stack,
    // returning their address
};

template <class X> class Stack
 : public Stack_<sizeof(X)>
{
typedef Stack_<sizeof(X)> Base;
public:
 void push(X x) { Base::push(&x); }
 X pop() { return *static_cast<X*>(Base::pop()); }
};

This has exactly the same drawback as the proposed language extension:
it copies bytes rather than objects; both will fail in cases where that
distinction matters.
 -- Pete
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Walter W. Karas <wkaras@ibm.net> writes:

> In C and C++, the "inert" pointer type void * can be used to
> create collection data structures that can collect any
> pointer type.  I propose an extension to C++ to create
> corresponding "inert" types for all types in C++.
>
> C++ already has "pseudo function templates"
> (static_cast<X>(), for example).  I propose the "pseudo
> class template" inert<X>.  For every type X, there is a
> corresponding type inert<X>. inert<> has the following
> properties for any type X:

[ if something is true for T, it's also true for inert<T> ]

> The simplest implementation for all this is to have inert<X>
> simply be X.

[...]

> So, what is the point of all this?  Consider the following
> definitions for a stack container:

[...]

> The use of inert<> reduces the number of instantiations of
> Stack_<>.

> The existence of inert<> would eliminate the need for partial
> template instantiation for pointer types.  I find this feature
> to be very unintuitive and difficult to describe formally.
> inert<> is also difficult to describe formally, but I would
> argue that it is very intuitive.

I don't think so. I don't _really_ understand it (inert<T> is T
without being T), and I don't want to have to teach that to a
friend.

I think this is a case of false optimisation, when someone wants
to change the language in order to do an optimisation, but only
prevents optimisations by complicating compilers. (Each time you
make the standard more complex, you take some of the implementor's
time, and remove oportunity for optimisations.)

The compiler can and should do that if memory usage is important
(say for embeded systems):
- automatically, without programmer help
- in a transparent way, without language support

There is nothing difficult with such code sharing, just that you
need to rewrite the linker (ie you need access to the linker).

Anyway every C++ compiler writter should rewrite the linker (not
only on embeded systems).

In short: I am strongly opposed to this proposal.

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://www.pratique.fr/~bonnardv/
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pete Becker wrote:
...
>
> Why not just write it in C++?
>
> template <int N> class Stack_
> {
> public:
>         void push(void *x);     // push N bytes located
>                                 // at x onto the stack
>         void *pop();            // pop N bytes off the stack,
>                                 // returning their address
> };
>
> template <class X> class Stack
>         : public Stack_<sizeof(X)>
> {
> typedef Stack_<sizeof(X)> Base;
> public:
>         void push(X x) { Base::push(&x); }
>         X pop() { return *static_cast<X*>(Base::pop()); }
> };
>
> This has exactly the same drawback as the proposed language extension:
> it copies bytes rather than objects; both will fail in cases where that
> distinction matters.
>         -- Pete

This is incorrect.  I admit my description is difficult to understand.
inert<X> only copies bytes when that is what X does (e.g. when X is
a built-in type).  inert<X> must reproduce the effects of the X's
copy constructor and assignment operator (or lack thereof).  Wouldn't
you agree that most types who's instances are directly collected (that
is, not via pointers) use the default copy ctor and assignment operator?

A similar argument was made when void * was introduced into C, since
using char * for void * almost always works fine.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Valentin Bonnard wrote:
...
>
> I think this is a case of false optimisation, when someone wants
> to change the language in order to do an optimisation, but only
> prevents optimisations by complicating compilers. (Each time you
> make the standard more complex, you take some of the implementor's
> time, and remove oportunity for optimisations.)
>
> The compiler can and should do that if memory usage is important
> (say for embeded systems):
> - automatically, without programmer help
> - in a transparent way, without language support
>
> There is nothing difficult with such code sharing, just that you
> need to rewrite the linker (ie you need access to the linker).
>
> Anyway every C++ compiler writter should rewrite the linker (not
> only on embeded systems).
>
> In short: I am strongly opposed to this proposal.

The large-scale optimization you describe is obviously desirable.
But generic programming has been around since at least the
early '80s, and this level of optimization is not available.  So
I think it's valid to suggest changes to the language that
allow the programmer to help the compiler optimize code sharing
by instantiations of templates.

A compiler could make inert<X> be the same as X, just as a
compiler can ignore the "register" storage class modifier.  A
smart compiler could recognize that:

class A { public: char a, b, c, d; };

class B { private: char a, b; public: char c, d; };

class C { public: char x[4] };

etc.

can all correspond to the same inert type, since their
parameterless constructer, copy constructor, and assignment
operator are _exactly_ the same when translated to
machine code.

As I mentioned, adding this feature eliminates the need
to allow partial template specialization for pointer types.
So I would argue its effect on the complexity of the
language is at least neutral.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]