[Boost-users] Re: mpl rational_c and fixed_c

From: Aleksey Gurtovoy (agurtovoy_at_[hidden])
Date: 2004-03-15 03:13:29

Matt Calabrese wrote:
> Okay, I decided before I continue with my other library, I'll fully
> implement rational_c properly (and possibly fixed_c), however, doing 
> so without making the code horribly complex would require changes to
> the current definitions of pretty much all of the operations (plus, 
> multiplies, etc. as well as the conditional operators).
                                  ^^^^^^^^^^^
I suppose you meant "comparison", here and below.

> 
> The problem is that those current functions take 5 parameters, making
> specialization nearly impossible for the rational and fixed templates 
> as you'd have to account for when the 3rd, 4th, 5th, etc parameters 
> are not passed (and so the default integral 0 is used). That can't be 
> easily done (at least I don't see how) without having to specialize 
> each condition separately (one for 3 rational types, one for 4 
> rational types, etc ). Moreso, this applies to the conditional 
> operators as well, there is no easy way to account for using different
> types in multiplies IE multiplying a rational and integral together, 
> or a fixed and rational, etc. Again, to account for these 
> possibilities you'd have to make an incredibly large amount of 
> specializations. Of course, you could always just limit them to only 
> work when all the parameters are the same kind of compile-time value
> template, but that would be somewhat limitting,especially with other
> solutions available.

I pretty much agree with the analysis.

> 
> What I propose is a way around this situation, but still have the
> metafunctions declared the same way, therefore not breaking old code 
> and not limiting functionality. To do so, the following adjustments 
> would have to be made (and I have already begun to make them for my 
> own use):
> 
> 1) Additional versions of all of the arithmetic operators which take 2
> parameters, each need to be defined and work like binary operators. 
> They should be specialized for when both the left and right operands 
> are of the same type. How to account for when they are different types
> will be covered in the future points.

Sounds good so far.

> 2) A value_cast metafunction which can cast between all different
> compile-time constant types. The way it is implemented is by requiring
> all types to have specialized metafunctions for converting to and from
> the fixed point type. When value_cast is used, it, by default, 
> converts the right hand operand to fixed_c, then converts that fixed_c 
> to the target type. Since a fixed_c can hold pretty much any real 
> value to a certain precision, you can be certain, to an extent, that 
> little, if any precision will be lost through conversion. So, with 
> that proposed addition, you'd be able to convert between all different 
> types and only require people developing new types to have to 
> specialize conversion to and from fixed_c. The only problem is that in
> order for the value_cast to exist, it obviously needs to have a 
> parameter which specifies a type to convert to. The only way I can 
> currently see that would allow that would be to have the value_cast 
> take a type parameter which would be a template instantiation with a 
> dummy value, which would, in a way, be very similar to rebinding 
> allocators.

The idea of avoiding a combinatorial explosion through a single 
user-defined conversion metafunction which will be used to even the 
argument types is definitely solid; however, I am afraid we cannot 
escape with something as simplistic as conversion to a default 
predefined "contains-it-all" numeric type -- simply because there is no
such type (for instance, 'fixed_c' is not capable of holding 
compile-time complex numbers, and so on). Moreover, specializing of 
arithmetic metafunctions is not necessary a prerogative of numeric types
-- consider, for example, random-access iterators.

To summarize, IMO the idea is excellent, but it needs to be carried a 
little bit further -- please see below.

> 3) The conditional operations and 2 operand arithmetic operations 
> should be redefined in the base template definition to convert both 
> types to fixed_c and then make a comaprison, therefore allowing 
> programmers to use the operations on two different types of 
> compile-time constants without having to manually convert them to 
> similar types before-hand (as I alluded in first point). The 
> conditional operations can then be specialized for when the types 
> are the same on each side to avoid the cost of a cast on each of the
> operands to fixed_c.

Yep to everything except the 'fixed_c' part.

> 4) The current "varying length" operations which cause problems 
> (multiplies, plus, minus, etc) should be redefined to just call the 2
> operand version of the corresponding operation on each of the 
> parameters passed to the operation. This way, programmers can still 
> pass multiple parameters to these functions, with each parameter being
> a different type, without the developer having to make an extremely 
> large amount of specializations for each type (including those which 
> have yet to be developed).

Yep! Something like

    template< 
          typename N1
        , typename N2
        , typename N3 = int_<0>
        , typename N4 = int_<0>
        , typename N5 = int_<0>
        >
    struct plus
        : plus2< plus2< plus2< plus2<N1,N2>,N3 >,N4 >,N5 >
    {
    };

    // ...

    template< 
          typename N1
        , typename N2
        >
    struct plus<N1,N2,int_<0>,int_<0>,int_<0> >
        : plus2<N1,N2>
    {
    };

> 
> I have already begun implementing all of the points I have suggested,
> though with my rational_c as a the basis for conversion rather than 
> fixed_c (as I haven't yet developed fixed_c). Also, converting to and 
> from rational_c is considerably simpler than converting to and from 
> fixed_c. For this reason, I may end up leaving the basis for 
> conversion as rational_c instead of fixed_c.
> 
> If anyone sees any other, more elegant solutions for the problems I
> mentioned, please post them and I may change my approach. Additional
> suggestions are also greatly appreciated.

You are going in the right direction. Here are some suggestions of how
to generalize the scheme to get what I would consider an ideal solution:

1) Make specializable binary templates for each arithmetic/comparison
metafunctions to be tag-dispatched metafunction classes, e.g.

    template< 
          typename N1
        , typename N2
        >
    struct plus2
        : plus_impl< // 'plus_impl' is a point of customization
              typename plus_tag<N1>::type
            , typename plus_tag<N2>::type
            >::template apply<N1,N2>::type
    {
    };

    // 'plus_impl' implemenation for plain integral constants
    template<> 
    struct plus_impl<integral_c_tag,integral_c_tag>
    {
        template< typename N1, typename N2 > struct apply
            : integral_c<
                  BOOST_MPL_AUX_TYPEOF(N1,N1::value + N2::value)
                , (N1::value + N2::value)
                >
        {
        };
    };

where 'plus_tag' is something as simple as

    template< typename T > struct plus_tag
    {
        typedef typename T::tag type;
    };

2) Provide a rank mechanism so that we know in which direction to cast
in case of mixed operations; can be as simple as an integral-constant 
'rank' member of the corresponding tag:

    plus_tag< int_<5> >::type::rank == 0

3) Provide default implementations of '*_impl' binary templates which
would use ranks, tags, and 'numeric_cast' to implement a general scheme
for mixed arithmetics/comparison, something along these lines:

    template< 
          bool c_
        , typename Tag1
        , typename Tag2
        >
    struct plus_impl_
    {
        template< typename N1, typename N2 > struct apply
            : plus_impl<Tag2,Tag2>::template apply<
                  typename apply< numeric_cast<Tag2,Tag1>, N2>::type
                , N2
                >
        {
        };
    };

    template< 
          typename Tag1
        , typename Tag2
        >
    struct plus_impl_<false,Tag1,Tag2>
    {
        template< typename N1, typename N2 > struct apply
            : plus_impl<Tag1,Tag1>::template apply<
                  N1
                , typename apply< numeric_cast<Tag1,Tag2>, N2>::type
                >
        {
        };
    };

    template< 
          typename Tag1
        , typename Tag2
        >
    struct plus_impl
        : plus_impl_< ( Tag1::rank < Tag2::rank ),Tag1,Tag2 >
    {
    };

Does it make any sense to you? 

P.S. I suggest we move the discussion to the developers list (I'm going
to cross-post this one).

--
Aleksey Gurtovoy
MetaCommunications Engineering