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

From: Brian McNamara (lorgon_at_[hidden])
Date: 2003-10-22 11:37:19

On Tue, Oct 21, 2003 at 03:56:26PM -0400, Douglas Gregor wrote:
> On Tuesday 21 October 2003 02:34 am, Brian McNamara wrote:
> > 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> {};

You need to redefine constructors for those 4 types (as you know).

> 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 )
>          ;
> }

There are a number of other minor problems which have accumulated.
Here's a new version which is hopefully bug-free:

----------------------------------------------------------------------
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;
typedef Add_<Expr> Add;
typedef Sub_<Expr> Sub;
typedef Mul_<Expr> Mul;
typedef Div_<Expr> Div;

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

That almost works "out of the box"; the only thing else is that stuff
like

   |= case<Add>( eval(_1)+eval(_2) )

isn't right, because the proposed switch_ construct would want it to be

   // pseudocode for clairty
   |= case<Add>( lambda(a){ eval( get<1>(a) )+eval( get<2>(a) ) } )

Right?

Wow, and it just occurred to me that there is a general and powerful
abstraction lurking here, namely:

   f( taf ) = lambda( tuple<X,Y> t ){ taf( get<1>(t), get<2>(t) ) }

Here "taf" means "two argument function".  I am not sure what to name
"f".  Clearly this generalizes to n-ary tuples.

Oh, duh.  This is what Haskell calls "uncurry".  Wow!  Ok, so the long
and the short of it is that I should be writing

   |= case<Add>( uncurry( eval(_1)+eval(_2) ) )

and now things totally work, right out of the box.  Cooooooool.

> Those extra V's are particularly annoying, aren't they? However, I will note 

Annoying, but clever.  :)

> > 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));

Actually, the "redefined constructors" I mentioned at the top of this
messages suffice for this job:

   Expr x, y;
   ...
   Add( x, y )   // voila!

> > 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.

I just realized I didn't communicate what I meant here.  By "matching
on values", I meant being able to use, e.g., "_1" inside the "Add" case
to mean the left-hand expression tree.  I did _not_ intend to imply
that I wanted to be able to have "case 0", "case 1", and "case n" arms,
for example.

So I think we're mostly on the same page.

This is great stuff!

-- 
-Brian McNamara (lorgon_at_[hidden])