Re: [boost] status of variant type implementations & recursive variant types

From: Douglas Gregor (gregod_at_[hidden])
Date: 2002-04-02 16:29:02

On Tuesday 02 April 2002 01:44 pm, you wrote:
> But let's turn to other issues.
>
> It seems that most variant type proposals seem to silently omit the variant
> type constructors (or tags) used in FP languages. Even the C++ union allows
> multiple fields with the same type:

I think variant type constructors are the easiest part of building a variant 
class template. I worked on a prototype implementation where the tags were 
optional, to support both uses of variants:

typedef variant<int, float, double> v1;

or

struct x {}; struct y {}; struct z {};
typedef variant<tagged<x, int>, tagged<y, int>, tagged<z, int> > v2;

This is basically the same as you have proposed. (with tagged == ctor). I 
also like the use of ctor<name> (or tagged<name>) for a tag/constructor 
without a value. An untagged type in the variant (e.g., in v1 above) has tag 
equal to the value type, so v1 is equivalent to:

typedef variant<tagged<int, int>, 
                tagged<float, float>, 
                tagged<double, double> > v1_equiv;

Aside: I think we should use the name 'tag' instead of 'constructor' in the 
context of C++.

> In FP languages, variants are constructed by using the constructors of the
> variant:
>
>     Mul_expr ( Int_expr 1, Int_expr 2 )
>
> In C++ we would also specify both the tag and the value. Something like
> this perhaps:
>
>     expr(mul_expr(),make_tuple(expr(int_expr(),1),expr(int_expr(),2)))
>
> In FP languages, variant types are usually immutable. In other words, you
> can not change the tag of a variant after it has been constructed. In C++,
> we would probably want to be able to do just that. In such an assignment,
> we would have to pass both the tag and the value:
>
>     e.assign<int_expr>(3);
>
> Copy assignment would look like an ordinary C++ assignment:
>
>     e = other_e;

... or just make the tags actual useful classes, and let the constructors 
take the appropriate arguments. Then the first assignment would be:

  e = int_expr(3);

This works nicely for variants with untagged types in them, e.g.,

  variant<int, double, float> e1 = 5;
  e1 = 5.5;
  e1 = 3.14159f;

> Variants would have value semantics.

Agreed.

> In FP languages, probably the most important operation on variant types is
> pattern matching. Consider the following Ocaml function:
>
>     let rec eval expr =
>       match expr with
>
>        | Add_expr (lhs,rhs) -> (eval lhs) + (eval rhs)
>        | Sub_expr (lhs,rhs) -> (eval lhs) - (eval rhs)
>        | Mul_expr (lhs,rhs) -> (eval lhs) * (eval rhs)
>        | Div_expr (lhs,rhs) -> (eval lhs) / (eval rhs)
>        | Neg_expr expr      -> - (eval expr)
>        | Int_expr value     -> value
>
> The above could be done in C++, using the lambda library, something like
> this:
>
>   int eval(expr& e)
>   { return
>       e.match
>         ( with<add_expr>(
>             bind(eval, bind( get_0, _1)) + bind(eval, bind(get_1, _1)) )
>
>         | with<sub_expr>(
>
>             bind(eval, bind( get_0, _1)) - bind(eval, bind(get_1, _1)) )
>
>         | with<mul_expr>(
>
>             bind(eval, bind( get_0, _1)) * bind(eval, bind(get_1, _1)) )
>
>         | with<div_expr>(
>
>             bind(eval, bind( get_0, _1)) / bind(eval, bind(get_1, _1)) )
>
>         | with<neg_expr>(
>
>             - bind(eval, _1) )
>
>         | with<int_expr>(
>
>             (0, _1) )
>         );
>   }
>
> Serious type deduction is needed for the above to compile. It would
> probably be a good idea to make it possible to explicitly specify the
> return type.

I agree completely. I'd really like to generalize this so that it can be used 
also with boost::any. Stealing a little Phoenix syntax, one could write the 
above as:
  
  switch_(e) [
      case_<add_expr>(...)
    | case_<sub_expr>(...)
    ...
  ];

> We would also want to be able to match any tag:
>
>     bool is_int(value& v)
>     { return
>         v.match
>           ( with<int_value>( constant(true)  ) // doesn't work currently
>
>           | with<>         ( constant(false) ) // nullary function
>
>           );
>     }

I'd prefer default_(...) with the above syntax, but this part of the syntax 
is trivial :)

> It would also be nice to be able to test for a specific constructor (this
> does not invalidate the usefulness of being able to match any tag):
>
>     if (v.is<int_value>()) {...} else {...}
>
> And to cast using a specific constructor:
>
>     int i = v.cast<int_value>()

Agreed. In my prototype I used "is" and "as" for your "is" and "cast". 
However, I think that it might be better to use free functions and avoid the 
member template ugliness:
  template<typename V>
  void foo(V& v) {
    int i = v.template cast<int_value>();
  }

> Are there any other operations that we should support or could we remove
> support for some operations?

I would _love_ support for decomposing product types within a variant switch 
statement, but I'm not yet sure how to implement it cleanly. For instance, 
let's look back at your example:

        | with<sub_expr>(
            bind(eval, bind( get_0, _1)) - bind(eval, bind(get_1, _1)) )

This really should be as simple as:
  | with<sub_expr>(bind(eval, _1) - bind(eval, _2))

This would be perfectly reasonable if we had a good tuple-like interface to 
product types, e.g.,

  template<typename T>
  struct product_type_traits {
    static const int length = /* the number of elements in the product */;

    template<int N> struct nth_type {
      typedef /* ... */ type; // Nth type in the product
      typedef type& reference; // for get()
      typedef const type& const_reference; // for const get()
    };

    // Get Nth element in the tuple
    template<int N> static typename nth_type<N>::reference get(T&);

    template<int N> 
    static typename nth_type<N>::const_reference get(const T&);
  };
  
Then we dispatch our call to the function object 'f' given to 'with' (or 
'case_' in Phoenix-like notation) based on the number of elements in the 
product. If there are zero elements, we call it as 'f()', with one element it 
is 'f(traits::get<1>(e1))', two elements is 'f(traits::get<1>(e1), 
traits::get<2>(e2))', and so on.

        Doug