Re: [boost] Proposal --- A type-safe union

From: Douglas Gregor (gregod_at_[hidden])
Date: 2002-06-12 13:25:08

On Wednesday 12 June 2002 01:18 pm, Fernando Cacciola wrote:
> Aha, I see. I though he referred to exactly the opposite.  :-)

I'm hoping he'll chime in at some point to disambiguate, but I think by now we 
agree on resolutions for both possibilities anyway :)

> I normally consider implicit conversion very dangerous and I usually avoid
> them.
> It appears that I've considered this variant type to be modeling a
> different thing:
>
> I thought of variant<T,U,V> as a type whose value is *equally* any of T, U
> or V.

Oh, I see what you meant. This isn't the type of variant I was talking about.

> But this variant seems to be a type whose value is *only one of* T,U, V
> (but not all at the same time).
> (Now that I think of it, 'discriminated' would mean just that, wouldn't
> it?)

Yes, this is what I was thinking of. 

[big snip]
> OK, I see it.
> I notice that there is a lot complexity just to support incomplete types
> and full-featured recursion.
>
> Incomplete types "could" be detached from the variant itself by an
> appropiate handle-body scheme.
> It does involve more work for the user, but it also unbound all the
> possible decisions (allocation,ownership, etc...).
>
> I think that a variant type supporting incomplete types *might* be useful.
> Though, I still need to see a complete example were a handle-body pattern
> is not better from an engineering perspective.
> But OTOH, I think it will introduce significant complexity. It might be a
> good idea to at least have a light-weight variant too.

There's a lot of complexity in supporting direct, full-featured recursion 
(e.g., std::vector<rec>). However, supporting just incomplete types should be 
quite easy. 

If your only objection to supporting incomplete types is the implementation 
complexity, then I still think that we should support incomplete types. The 
handle-body scheme is indeed more flexible, but it is a maintenance nightmare 
without an automated scheme for creating the handle classes. 

Direct recursive types (e.g., using 'rec'), however, might be too complex to 
justify. I pursued them under the somewhat misguided notion that they were 
needed to easily support a pattern-matching typeswitch statement. However, it 
appears that recursive types aren't at all necessary for that, and that I've 
already written a typeswitch that does essentially what I wanted:

  http://groups.yahoo.com/group/boost/files/typeswitch-20020413.tgz

The implementation uses some traits on sum types (boost::any was used for the 
experiment) and product types (boost::tuples::tuple was used for the 
experiment) to implement a generic typeswitch statement. The example from the 
tarball is the following:

---------------------------------------------------------------------------
using namespace boost::tuples;

typedef any Expr;
typedef tuple<int> Literal;
class Add : public boost tuple<Expr, Expr> {};
class Sub : public boost tuple<Expr, Expr> {};
class Mul : public boost tuple<Expr, Expr> {};
class Div : public boost tuple<Expr, Expr> {};
// some simple trait specializations

int compute(Expr expr)
{
  using namespace boost::lambda;

  return switch_<int>(expr)[
           case_<Literal>((_1, _1))
           | case_<Add>(bind(&compute, _1) + bind(&compute, _2))
           | case_<Sub>(bind(&compute, _1) - bind(&compute, _2))
           | case_<Mul>(bind(&compute, _1) * bind(&compute, _2))
           | case_<Div>(bind(&compute, _1) / bind(&compute, _2))
  ];
}
---------------------------------------------------------------------------

We could take a similar approach by allowing only incomplete types, and not 
use the 'rec' trickery at all. The same code above could be used with a 
hypothetical variant type like this:

---------------------------------------------------------------------------
typedef tuple<int> Literal;
class Add;
class Sub;
class Mul;
class Div;

typedef boost::variant<incomplete<Add>, incomplete<Sub>, 
                       incomplete<Mul>, incomplete<Div>,
                       Literal> Expr;

// same definitions for Add, Sub, Mul, and Div

// compute function doesn't change, but now we get static 
// completeness-of-decoding checks
---------------------------------------------------------------------------

I still don't know how to do more complex pattern matching that can check 
substructures, e.g., match a tree like:

  Add
  / \
 X  Sub
    / \
   Y   X

where X and Y are expressions, and the two X's are equal by the '==' operator. 
But this can be solved separately from the implementation of the variant, we 
just need a good way to represent the trees. But I digress...

> It seems to me that the choice of extensive-list vs dot-list is driven by
> an implementation concern.
> So, from the user perspective, is there any significant difference? Would
> it be better for the user to use a dot-list?
> I think not, but still this desicion should not be so much affected by the
> choice of matching mechanism; it should be based primary on the effect on
> the interface.

I'd prefer 
  variant<int, float, double, std::string> 
to the typelist equivalent 
  variant<TYPELIST_4(int, float, double, std::string)> 
or
  variant<boost::mpl::list<int, float, double, std::string> >

because I can't see any interface-driven motivation to use typelists, so long 
as the maximum number of types can be changed if necessary. Also, both Tuples 
and Function use separate arguments instead of dot/type-lists. 

I think the error messages might be more readable because the typelist 
implementation I have in mind introduces a LOT of extra template levels to 
muddy up the terminal window. (It's shown below, but not by me)

Oh, and the implementation is easier :)

> > If you are really interested, there is a way to make the compiler perform
> > overload resolution for an arbitrary-length typelist, but I'm not going
> > to type out an explanation unless someone asks specifically :)
>
> Well... You bet I'm curious... but I wouldn't ask you to explain it just to
> satisfy my curiousity :-)
> If you ever do explain it, just let me know.

Brad King apparently took my laziness as a challenge and sent a solution :)

----------------------------------------------------------------------------
#include <iostream>
#include <typeinfo>

struct nil {};

template <typename Car, typename Cdr=nil>
struct list
{
  typedef Car car;
  typedef Cdr cdr;
};

template <typename List>
struct checker: public checker<typename List::cdr>
{
  typedef checker<typename List::cdr> derived;
  using derived::check;
  static void check(typename List::car)
    {
    std::cout << "check(" << typeid(typename List::car).name() << ")\n";
    }
};

template <>
struct checker<nil>
{
  static void check() {}
};

int main()
{
  typedef list<int, list<char> > my_list;
  typedef checker<my_list> my_checker;
  my_checker::check(1);
  my_checker::check('c');
  return 0;
}
-----------------------------------------------------------------------------

The important part is the 'using derived::check', which ties together all of 
the overloads. I don't know how (practically) portable this is: GCC 3.x 
handles it fine, but GCC 2.95.x does not.

> > It's accessible via 'variant_cast', which I had previously defined as:
>
> So.. If I got it right, this variant has -at a given time- a value of 'one'
> of Tn, correct?

Yes.

        Doug