Re: [boost] Re: is_base_and_derived question

From: Terje Slettebø (tslettebo_at_[hidden])
Date: 2003-01-30 09:13:19

>From: "Gennaro Prota" <gennaro_prota_at_[hidden]>

> On Thu, 30 Jan 2003 11:13:23 +0100, Terje Slettebø
> <tslettebo_at_[hidden]> wrote:
>
> >>From: "Gennaro Prota" <gennaro_prota_at_[hidden]>
> >
> >> On Tue, 28 Jan 2003 10:47:52 -0800, "Andrei Alexandrescu"
> >> <andrewalex_at_[hidden]> wrote:
> >>
> >> >"Peter Dimov" <pdimov_at_[hidden]> wrote in message
> >> >> While we're at it, is the final verdict that
is_base_and_derived<void,
> >X>
> >> >> should be false? What about is_base_and_derived<void, void>?
> >> >
> >> >Well, clearly void is no base. Even if we also define
> >is_super_and_subtype,
> >> >void is hardly a supertype of everything.
> >>
> >> Could you please clarify this? You mean:
> >>
> >>   T is a subtype of U <=> ...?...
> >>
> >>   T is a supertype of U <=> ...?...
> >
> >Supertype/subtype is a more general notion than inheritance and
> >base/derived. The Liskov Substitution Principle states[...]
>
> Be careful though. If you bring in a "behavioral" principle like LSP
> than the issue becomes complicated.

The point is that if you define supertype = base class and subtype = derived
class, then what's the point in having an is_super_and_subtype? In this
case, they would be identical.

> The square/rectangle example is
> classic: if your square class throws e.g. when detecting that
> invariants are broken then it's trivial to construct an object of type
> square o1 and a program P defined in terms of rectangles which changes
> behavior if you replace an instance of rectangle with o1. Whether
> defining such a square class is good practice or not is another
> matter. The point is that is_base_of is just a mechanical relation
> that is difficult to define in terms of behavior.

Yes, as you say, the language doesn't enforce LSP for public inheritance, it
merely _assumes_ it, as I mentioned in the previous posting.

> Roughly speaking B is a base of D if and only if
> the base-specifier-list of D contains a class name for B or for a
> class of which B is a base. Of course you can see if that's the case
> by knowing the definition of D and examining an inheritance graph. And
> since that's what a compiler does all the time, is_base_and_derived is
> another thing that could be (ahehm) easily implemented as a built-in
> operator.

True. But it's also detectable using C++98, as shown by Rani's proposal.

> Not that I'm set for it, but please think about this: can
> you give off-hand a proof that Rani's implementation is equivalent to
> the mechanical definition I gave above?

A proof? Egads. :) I had a hard enough time figuring out how it works, in
the first place. :) It relies on some dusty corners of the language, such as
the order in which overload resolution is done. As has been shown with
tests, hardly any of the current compilers gets it right, only the EDG ones
have been reported as working with it.

I think it may be doable, though.

> If you are going to write the
> documentation for is_base_and_derived what do you write? The
> definition above? Or something else? If you write the definition above
> (as it is now, because the docs say more-or-less "if and only if B is
> a base of D") shouldn't you prove that it is implementable in C++? How
> much time will the committee spend to get agreement on the definition
> and seeing that it is implementable? How much time does it take to
> implement the built-in operator once you stick to the "mechanical"
> definition? Maybe the answer to the last question is much much smaller
> than the previous ones.

I haven't argued for or against having is_base_and_derived as a built-in
operator, or not. However, the fact is that having it as an operator
requires a language change, and that's likely several years away.

There are a few observations:

- is_base_and_derived (Rani's proposal) is usable here and now, so
regardless of any language/library change, it may be used now.
- If it turns out that is_base_and_derived doesn't completely detect base
and derived class, according to the definition in the standard, and a way is
not found to do so within the current definition of the language, one may
e.g.:
  - Change the part of the standard that the is_base_and_derived relies on
for its workings, so that it _does_ work correctly, if possible. Or,
  - Add is_base_and_derived as an operator in C++0x

There is a very important point: Adding is_base_and_derived as an
operator/keyword in C++ requires adding a keyword, and that's a _major_
change. It may break a lot of programs, if those programs uses an identifier
with this name, especially if it's not used in the way an operator would be
used. On the other hand, if you're able to implement it using the language
features, then it may e.g. be a standard library component, and that won't
break any existing programs.

> >>"What is wanted here is something like the following substitution
property:
> >If for each object o1 of type S there is an object o2 of type T such that
> >for all programs P defined in terms of T, the behavior of P is unchanged
> >when o1 is substituted for o2 then S is a subtype of T."
> >
> >Notice that it doesn't say anything about "class" or "inheritance",
> >anywhere. If S = T, LSP still holds. Therefore, as Andrei said it, in
> >language theory, such as this, a type may be considered its own
> >supertype/subtype.
>
> Actually the reason for my question is a little strange :-) I hope to
> explain it in understandable English: Andrej said
>
>     "void is hardly a supertype of everything"
>
> Rewording it, it is: "void is not a supertype of everything".
>
> This immediately made me think to why he didn't say: "not a supertype
> of anything". In other words I wondered: "is he implying that void is
> not a supertype of everything but *is* a supertype of something"? What
> it this "something"? :-) That's an example of my odd mental
> contortions.

<g> I don't think it is; it's just precision, which is good. Well, according
to LSP, void may be considered its own supertype. So it's at least the
supertype of _one_ type. :)

> >Supertype/subtype may also have other forms than inheritance. "short" may
be
> >considered a subtype of "int"
>
> I don't know. The LSP definition seems to elementary to me to map to
> C++. Think e.g. to binding an int to a reference to int&.
>
>   int main() {
>     int i;
>     int & r = i;
>   }
>
> Can you replace "int i;" with "short i;"?

No, so it doesn't map in all the cases that base and derived maps to LSP.
However, as has been noted, using derived and unambiguous public base
doesn't ensure LSP, either, although the program may compile in that case.

Regards,

Terje