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

From: Brian McNamara (lorgon_at_[hidden])
Date: 2003-10-21 01:34:23

On Mon, Oct 20, 2003 at 05:43:03PM -0700, Eric Friedman wrote:
> The decomposition of product types seems trickiest to me. First, I don't 
> see a good way of allowing the user to specify the pattern for 
> unpacking. Second, without such user-specified unpacking patterns, it 
> seems somewhat dangerous to allow the set of "unpackable" types to be 
> extensible.
>
> Perhaps I could abandon my current idea of using the pattern to match 
> the contained *type* and rather use the pattern (a la ML) to indicate 
> how to unpack contained product *values*. Do you see a better solution, 
> ideally one that allows both kinds of matching?

Yes and no.  :)

Here was one of your earlier examples:

>> switch_(var)
>>   |= case_< pair<_1,_1> >(...) // matches pair<int,int>
>>   |= case_< pair<int,_> >(...) // matches pair<int,*>
>>   |= case_< pair<_,_> >(...)   // matches pair<*,*>
>>   |= case_< int >(...)

You kind of "need" to match based on "type" owing to the lack of 
"tag names" in the variant.  Obviously this causes a problem in that
cases like

   case_< pair<_1,_1> >(...) 

can't be used both to match the type (pair<T,T>) and the values (_1,_2)
simultaneously.

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?

I suppose if

   MAKE_TAG( name );

were a macro that expanded into

   template <class T>
   class name {
      T x;
   public:
      name( const T& xx ) : x(xx) {}
      T get() const { return x; }
   };

Then Doug's example could be realized as

   MAKE_TAG( Literal );
   MAKE_TAG( Add );
   MAKE_TAG( Sub );
   MAKE_TAG( Mul );
   MAKE_TAG( Div );

   typedef recursive_variant< 
      Literal<int>, 
      Add< pair< recursive_variant_, recursive_variant_ > >,
      Sub< pair< recursive_variant_, recursive_variant_ > >,
      Mul< pair< recursive_variant_, recursive_variant_ > >,
      Div< pair< recursive_variant_, recursive_variant_ > > 
      > Expr;

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

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.

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

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

-- 
-Brian McNamara (lorgon_at_[hidden])