Re: [boost] Re: Re: Yet another Variant class

From: Douglas Gregor (gregod_at_[hidden])
Date: 2002-07-02 11:18:21

On Tuesday 02 July 2002 10:14 am, David Abrahams wrote:
> This is getting awfully tangled. We weren't discussing polymorphism in
> general, but is-a relationships. Where's the is-a reltionship here?

I'm going to start over and try to reclarify a bit. I shifted from the 'is-a' 
relationship (which has strong object-oriented connotations) to the more 
general notion of polymorphism because I had a premonition that the OO view 
wasn't going to work, as you illustrated here:

> > > Structurally speaking you've got it inside-out, in fact. Given an
> > > expression lvalue, we can get a double lvalue.
> >
> > Given a double, we can build an expression from it (derived-to-base
>
> cast).
>
> Bad analogy. Derived-to-base never requires the construction of a new
> object. That's like saying vector<double> is-a int because I can write
>
>     vector<double> x(300);

What I was really getting at (but didn't realize) was this basic question:

  If I have a variant type V that can hold a value of one of the types T1, T2,
  ..., TN, are T1, T2, ..., TN subtypes of the variant type V?

If T1, T2, ..., TN are subtypes of the variant type V, then:
  - we expect subtype polymorphism to work properly
  - 'cast' seems like a reasonable description for the type-to-subtype 
conversion (i.e., from V to one of the types Ti)

If T1, T2, ..., TN are _not_ subtypes of the variant type V, then:
  - subtype polymorphism doesn't exist (V is just a container of one element)
  - 'extract' seems like a reasonable description for accessing the value 
stored within the variant type

I thought about it for a while, and decided that T1, T2, ..., TN should be 
subtypes of the variant type because if I have a value of type T1, it is one 
of the legal forms of the type V. If I call a routine that expects a V, it is 
perfectly reasonably that I give it a T1 because T1 is a valid form for V. 

I dug around a little bit for variant subtyping rules, to see what others 
think. After a little looking I came across some notes/corrections from 
(apparently) a series of lectures on a typed lambda calculus 
(http://www.cs.pdx.edu/~apt/cs510cal_2000/typing_note.ps). It contained this 
rule for variant subtyping:

{l1', ..., lm'} \subseteq {l1, ..., ln}     lj' = li => Tj' <: Ti
-----------------------------------------------------------------
         <l1':T1', ..., lm':Tm'> <: <l1:T1, ..., ln:Tn>

Where:
  l1, l2, ..., ln and l1', ..., lm' are just labels (simple identifiers)

  T1, ..., TN and T1', ..., TM' are types

  <: is the subtyping relationship (i.e., Ti <: Tj means that Ti is a subtype 
of Tj)

In more C++-ish terms, it says that if we have two variant types V1 and V2, 
and the set of types that V1 can hold is a subset of the types that V2 can 
hold, then V1 is a subtype of V2. So if we have:

  typedef variant<int, double> V1;
  typedef variant<int, double, std::string> V2;

then V1 is a subtype of V2 (because you can use a V1 wherever a V2 is needed 
without breaking type safety). Then with:

  typedef variant<int> V3;

V3 is a subtype of V1 and V2. But 'variant<int>' is just syntactic desugaring 
for 'int' (they should be equivalent, if the C++ type system would allow such 
a thing).

The variant implementations given thus far have gotten about as close to 
allowing variant subtyping as we can in C++. A variant can be constructed 
from any subtype, and variants can be casted to any of the value types they 
may hold. We can't ask for much more from a subtyping relation.

> >  we can get to the double
> > (base-to-derived cast). What's inside-out?
>
> That's much more-analogous to derived-to-base than base-to-derived. The
> double storage exists within the Expression object, just as the Base
> storage exists within the Derived object. That's what's inside-out.

That's a _really_ low-level view of the semantics, where the storage 
determines the semantic view of a type. I don't think we should consider 
storage at all when looking at the semantics of a type. I can represent 
std::string's storage as a map of floating-point values if I want, but it 
doesn't change the semantics of std::string that are apparent to the user.

> >   type expression = Literal of float
> >
> >     | Plus of expression * expression
> >     | Minus of expression * expression
>
> I don't have enough of a feel for ML to comment, having never used it
> myself. Fortunately, we're discussing C++ <0.2 wink>
>
> > Does it hold that Plus(x, y) is-a expression?
>
> Which definition of Plus/expression are you using?
>
> -Dave

The ML definition.

        Doug