RE: [boost] Submission: typelist

From: Aleksey Gurtovoy (alexy_at_[hidden])
Date: 2001-11-29 14:50:19

Mat Marcus wrote:
> I would also be interested in seeing some examples illustrating 
> any of the facilities that Dave mentioned in an earlier post:

I supplied some of those below, but basically most of the code just copied &
pasted from the test suite in "boost/libs/mpl/test" directory in CVS
("mpl_development" branch), and there are much more there. So if you are
interested - please, take a look!

> 
> At 7:59 PM -0500 11/27/01, David Abrahams wrote:
> >1. Algorithms can be used with different compile-time 
> > sequence structures and implementations

Right now boost::mpl provides 4 different types of sequences: 'type_list',
'type_vector', 'value_list', and 'value_range'. The sequences have different
functional and (compile-time) performance characteristics, which has a
direct effect on the applicability and efficiency of particular algorithms,
as well as expressiveness of user code. The only core operations that a
sequence is required to provide in order to be used with the library
algorithms are begin<>/end<> meta-functions, that can be specialized for a
particular type of sequence either by using C++ class template
specialization feature, or other implementation mechanisms provided by the
library. As one can guess, begin<>/end<> meta-functions provide an iterators
interface to the sequence, that is used to implement most of the other
general purpose sequence algorithms the library provides. Also, many of the
"basic" sequence operations (algorithms), - 'back', 'front', 'size', 'at',
etc., - can be and are specialized for the particular kinds of sequences in
order to provide a more efficient/simple implementation than default
iterators version. Speaking about implementation of the particular sequences
classes mpl currently provides - 'type_list' and 'value_list' share some
common implementation (and, therefore, most of compile-time
performance/functional characteristics), while 'type_list', 'type_vector'
and 'value_range' are completely different; 'type_list' is a forward-access
mutable sequence; 'type_vector' is a random-access mutable sequence with
fixed maximum number of elements, and 'value_range' is a sorted immutable
random-access sequence of int_t's. Below are requested examples of some of
mpl algorithms applied to these different kinds of sequences:

    using namespace boost::mpl;

    // 4 different types of sequences 
    typedef type_list<int,char,long,short,char,long,double,long> types;
    typedef type_vector<char,short,int,long> types_vec;
    typedef value_list<1,0,5,1,7,5,0,5> values;
    typedef value_range<0,10> range_0_9;

    // back
    BOOST_MPL_ASSERT_IS_SAME(back<types>::type, long);
    BOOST_MPL_ASSERT_IS_SAME(back<types_vec>::type, long);
    BOOST_STATIC_ASSERT(back<values>::value == 5);
    BOOST_STATIC_ASSERT(back<range_0_9>::value == 9);

    // front
    BOOST_MPL_ASSERT_IS_SAME(front<types>::type, int);
    BOOST_MPL_ASSERT_IS_SAME(front<types_vec>::type, char);
    BOOST_STATIC_ASSERT(front<values>::value == 1);
    BOOST_STATIC_ASSERT(front<range_0_9>::value == 0);

    // copy_if
    typedef copy_if<
          types
        , type_list<>
        , make_f_x<boost::is_float>
        >::sequence float_types;

    // count 
    BOOST_STATIC_ASSERT((count<types,int>::value == 1));
    BOOST_STATIC_ASSERT((count<types,char>::value == 2));
    BOOST_STATIC_ASSERT((count<types_vec,int>::value == 1));
    
    BOOST_STATIC_ASSERT((count< values, int_t<1> >::value == 2));
    BOOST_STATIC_ASSERT((count< values, int_t<5> >::value == 3));

    BOOST_STATIC_ASSERT((count< range_0_9, int_t<5> >::value == 1));
    BOOST_STATIC_ASSERT((count< range_0_9, int_t<10> >::value == 0));

    // count_if
    BOOST_STATIC_ASSERT((count_if< types, make_f_x<boost::is_float> >::value
== 1));
    BOOST_STATIC_ASSERT((count_if< types, same_as<char> >::value == 2));
    BOOST_STATIC_ASSERT((count_if< types_vec, make_f_x<boost::is_float>
>::value == 0));
    
    BOOST_STATIC_ASSERT((count_if< values, lt<5> >::value == 4));
    BOOST_STATIC_ASSERT((count_if< values, eq<0>  >::value == 2));

    BOOST_STATIC_ASSERT((count_if< range_0_9, lt<5> >::value == 5));
    BOOST_STATIC_ASSERT((count_if< range_0_9, eq<5> >::value == 1));

    // equal
    typedef value_list<0,1,2,3,4,5,6,7,8,9> values_0_9;

    BOOST_STATIC_ASSERT((equal<values_0_9,range_0_9>::value == true));
    BOOST_STATIC_ASSERT((equal<values,range_0_9>::value == false));
    BOOST_STATIC_ASSERT((equal<types,types_vec>::value == false));

    // find
    typedef find<types, short>::iterator types_itor;
    typedef find<types_vec, double>::iterator types_vec_itor;
    typedef find< values, int_t<7> >::iterator values_itor;
    typedef find< range_0_9, int_t<15> >::iterator range_itor;

    BOOST_MPL_ASSERT_IS_SAME(types_itor::type, short);
    BOOST_MPL_ASSERT_IS_SAME(types_vec_itor, end<types_vec>::iterator);
    BOOST_STATIC_ASSERT(values_itor::value == 7);
    BOOST_MPL_ASSERT_IS_SAME(range_itor, end<range_0_9>::iterator);

    // replace     
    typedef replace<types,char,short>::sequence new_types;
    typedef replace<types_vec,short,int>::sequence new_types_vec;
    typedef replace< values,int_t<0>,int_t<9> >::sequence new_values;

    // transform
    typedef type_list<int*,char*,long*,short*,char*,long*,double*,long*>
pointers;
    typedef transform<
          types
        , type_list<>
        , make_f_x<boost::add_pointer>
        >::sequence result;
    
    BOOST_STATIC_ASSERT((equal<result, pointers>::value == true));

> >2. Function composition
> >3. Argument binding

As with the standard library, many of the boost::mpl algorithms take either
predicates or transformation unary/binary functions as their parameters, and
as the experience shows that the ability to compose simple
predicates/functions into more complex ones is just as important in
compile-time world as it is in run-time one, the library provides
compile-time equivalent of boost::compose (boost/mpl/compose.hpp) and
std::bind (boost/mpl/bind.hpp) functionality (see also and "meta-lambda"
section below):

    // find either a 'void' or a type convertible to 'int'
    typedef find_if<
           types
         , compose_f_gx_hx<
               logical_or<_1,_2>
             , bind1st< make_f_xy<boost::is_same>, void >
             , bind2nd< make_f_xy<boost::is_convertible>, int >
             >
         >::iterator itor;

> >4. A far-thinking design for metafunctions which will 
> > probably allow a meta-lambda facility

It's possible to implement compile-time lambda mechanism, so instead the
above compose example one could write this:

    typedef find_if<
          types
        , logical_or<
              , boost::is_same<void, _1>
              , boost::is_convertible<_1, int>
              >
        >::iterator itor;

A limited form of it is already implemented.

> >5. Lifts the need for the user to deal explicitly with loopn 
> > termination in a separate piece of code (the specialization).

Basically, to iterate any compile-time sequence you just use the algorithms
(e.g. for_each), or loops - for_each, while_loop, etc. No need to use
"pattern matching", hacks around lack of partial specialization, and your
brand-new algorithm will work with any kind of sequence that satisfies the
algorithm iteration requirements.

> >6. A convenient way to specify type lists without macros

Well, I've already showed this in the above examples:

    typedef type_list<int,char,long,short,char,long,double,long> types;
    typedef type_vector<char,short,int,long> types_vec;
    typedef value_list<1,0,5,1,7,5,0,5> values;

HTH,
Aleksey