Re: [boost] Re: [ANN] type_switch with pattern matching in sandbox

From: Douglas Gregor (gregod_at_[hidden])
Date: 2003-10-21 14:56:26

On Tuesday 21 October 2003 02:34 am, Brian McNamara wrote:
> In functional languages, algebraic data types require "tags"; we'd say
> something like
>
>    struct PII;  // ... and all the other tag names.  Ugh.
>    ...
>    variant< tag< PII, pair<int,int> >,
>             tag< PIB, pair<int,bool> >,
>             tag< PDF, pair<double,float> >,
>             tag< I,   int >
>
>           > var;
>
> and then the switch would look like
>
>    switch_<R>(var)
>
>      |= case_< tag< PII, pair<_1,_2> > >(f1)   // R f1(int,int);
>      |= case_< tag< PIB, pair<_1,_2> > >(f2)   // R f2(int,bool);
>      |= case_< tag< PDF, pair<_1,_> >(f3)      // R f3(double);
>      |= case_< tag< I, _1 > >(f4)              // R f4(int);
>
> This gives you pattern matching on the values, using the tags to
> discriminate the types.  I think that using lambda variables (like _1)
> is more important to pattern matching on _values_ than on types.
>
> It is unclear to me what the best design for C++ is.  Adding "tags" and
> using them to discriminate among the case arms is the essence of
> programming with algebraic data types, but it's very "heavy" to add name
> tags in C++.  Instead, perhaps ordinal values could be used: you could
> force people to have one case arm for every type in the variant, and
> force them to appear in the same order as they do in the type definition
> of the variant.  This seems error-prone, though.  Hmm.
>
>
> Can we create a lightweight tag mechanism?

Why not derive the tags from the representation, e.g.,

struct TagName : public Representation 
{ /* sure, constructors are annoying here */ };

> Then Doug's example could be realized as

typedef int Literal;
template<typename V> struct Add : public tuple<V, V> {};
template<typename V> struct Sub : public tuple<V, V> {};
template<typename V> struct Mul : public tuple<V, V> {};
template<typename V> struct Div : public tuple<V, V> {};

typedef recursive_variant< 
  Literal,
  Add<recursive_variant_>,
  Sub<recursive_variant_>,
  Mul<recursive_variant_>,
  Div<recursive_variant_>
  >::type Expr;

int eval( Expr e ) {
    return switch_<int>( e )
         |= case<Add>( _1+_2 )
         |= case<Sub>( _1-_2 )
         |= case<Mul>( _1*_2 )
         |= case<Div>(
              if_then_else_return(_2==0,throw_exception("div by 0"),_1-_2) )
         |= case<Literal>( _1 )
         ;
}

Those extra V's are particularly annoying, aren't they? However, I will note 
that we can tell between the "match a type like pair<_1, _2>" and the "match 
a tag" cases because types will be types (potentially including _1, _2, _, 
etc.) and tags will be templates.

> It is not clear to me how the pattern matching becomes "extensible", so
> that, e.g., we know that
>    Add<_1>     --> binds _1 to thing.get()
>    pair<_1,_2> --> binds _1 and _2 to thing.first and thing.second
>    etc.

This can be solved with product_traits (at least, I'd done it this way once), 
with the grand view that some day we'll have compile-time type traits so that 
product_traits can automagically work on the data members of a class :)

> It is also not clear to me that this will ever be lightweight enough to
> be useful.

I'm not sure. It would take me a lot more code to write the same expression 
tree for my example as simple classes, and I wouldn't get the benefits of a 
smart typeswitch. Well, okay, we'd need some constructor functions like this 
to make the above useful:

Add<Expr> add(const Expr& x, const Expr& y) 
{ return Add<Expr>(make_tuple(x, y));

Still, I'm betting we could whip up a macro that would take most of the 
drudgery out of this, and I think it'll come out shorter than the equivalent 
code without all of the help.

> To sum up:
>  - I like your original idea
>  - In theory, I like pattern matching on values even more than I like
>    pattern matching on types

I'm not sure if I care all that much about matching on values. I do, however, 
think that using tags can shorten code a bit.

>  - In practice, I dunno that there is a "good" way to do pattern
>    matching on values in C++
> but I am open to more ideas.

I can't think of a good way to match values, either. It would probably require 
the type/value switch to have three parts: a type matching part, a value 
matching part, and a function object. That just sounds too complicated to me 
:(. 

Besides, if we have tags, isn't that "close enough" to cover the common cases 
for value matching? I'm thinking of lists in Ocaml, for instance, or 
expression trees like in the example above.

        Doug