[boost] Proposal: type-promoting arithmetics for derivative types

From: Max Motovilov (max_at_[hidden])
Date: 2004-02-25 17:41:42

This is a long post, so please let me know if making it into a Web page and
posting the URL is a better idea.

=======================

[Terminology]

Since I am not sure whether there is an accepted term for this kind of
types, let me introduce one - "derivative arithmetic type":

- D.A.T. is a templatized ADT with at least some arithmetic operations
defined
- D.A.T. is parameterized with a single type-parameter which has at least
some arithmetic operations defined (usually it is a built-in numeric type,
but not necessarily)
- Arithmetic operations on D.A.T. are defined in terms of arithmetic
operations on the base type
- There is a conversion available between differently parameterized
instances of D.A.T.

The above certainly isn't a good "standardese" concept definition but it
should be enough to illustrate the proposal.

Examples of D.A.T.s are std::complex<>, boost::rational<>,
boost::math::quaternion<> etc. However, the motivation for this proposal
came from my experience with implementing geometric types such as point,
rectangle etc. along with operations on them.

[Proposal, Part I]

Providing a facility that simplifies arithmetic type promotions for D.A.T.s.
None of the examples above currently provide it, which means that you cannot
expect

std::complex<float>( 1, 0 ) + std::complex<double>( 0, 1 )

to yield std::complex<double>( 1, 1 ). So, expressions on D.A.T.s with mixed
base types do not really behave the way the built-in numeric types do, even
though the individual values can be converted from one instance of the same
D.A.T. to another.

In the ideal world, one should be able to write:

template< typename T1, typename T2 >
foo< typeof( T1() + T2() ) >
    operator+( const foo<T1>&, const foo<T2>& );

and then implement operator+ the way it is normally implemented for foo<T>,
first converting foo<T1> and foo<T2> to foo< typeof< T1() + T2() >. I
intentionally leave out the optimization issues such as defining operator+
in terms of operator+= etc. However, without typeof(), it would be nice to
have a library solution yielding similar result, for example:

template< typename T1, typename T2 >
foo< promoted_type< T1, T2, std::plus > >
    operator+( const foo<T1>&, const foo<T2>& );

The third argument of promoted_type<> could be any kind of tag value or type
associated with the type of arithmetic operation. Templates std::plus,
std::minus, std::multiplies, std::divides and std::modulus do not cover the
entire range of C++ arithmetic operations so some other tags may work
better. The implementation of promoted_type will obviously be based on
partial specializations along with a limited typeof() facility with the
assumption that T1 op T2 always yields either T1 or T2 (which is the case
for built-in base types). Here is a quick and dirty implementation for only
one operation, operator+:

template< typename T1, typename T2 > struct typeof_one_of_two
{
    template<int N> struct select_type;
    template<> struct select_type<1> { typedef T1 type; };
    template<> struct select_type<2> { typedef T2 type; };
    static char (&typeof_fun( const T1& ))[1];
    static char (&typeof_fun( const T2& ))[2];
};

template< typename T > struct typeof_one_of_two<T,T>
{
    template<int N> struct select_type { typedef T type; };
    static char typeof_fun( const T& );
};

template<
    typename T1, typename T2,
    template< typename _ > class Tag
> struct promoted_type;

template< typename T1, typename T2 > struct promoted_type< T1, T2, std::plus
>
{
    enum { tag = sizeof( typeof_one_of_two<T1,T2>::typeof_fun( T1() +
T2() ) ) };
    typedef typename typeof_one_of_two<T1,T2>::select_type< tag >::type
type;
};

(I tried it on MSVC++ 7.1 and it works, though for some reason it doesn't
compile if I drag the expression for promoted_type<>::tag into the
declaration for promoted_type<>::type. With the intermediate enum value it
works fine - a compiler bug?)

Note that promoted_type<> may be used not just in binary operators but in
any external function or a D.A.T. method, possibly with different D.A.T.
parameters, as long as one can make a reasonable deduction of the result
type based on certain arithmetic operation over base type values. Also note
that all built-in binary operators defined for a pair of built-in numeric
types produce results of the same type. This means we wouldn't really need
3rd parameter for promoted_type<> if the base types were always built-in
numerics, but user-defined base types may break this assumption.

[Proposal, Part II]

Going further, we might want to add type-promoting arithmetics to existing
DATs that do not provide it. The best I could think of so far is introducing
overly generic template operators into global namespace, along with a
mechanism based on boost::enable_if to restrict their use to specific
parameter templates. The model implementation follows. I find it ugly, but
perhaps a better one may be immediately obvious to somebody else.

template< template< typename _ > class DAT > struct promote_sum
{
    typedef void tag;
};

template< typename P, typename E=void > struct do_not
{
    enum { value = false };
};

template< typename P > struct do_not< P, typename P::tag >
{
    enum { value = true };
};

template< typename T1, typename T2, template< typename _ > class DAT >
inline typename boost::disable_if_c<
    do_not< promote_sum< DAT > >::value,
    DAT< typename promoted_type<T1,T2,std::plus>::type >
>::type
    operator+( const DAT<T1>& a, const DAT<T2>& b )
{
    typedef typename DAT< promoted_type<T1,T2,std::plus>::type > T;
    return T( a ) + T( b );
}

To enable promoted-type operator+ for a specific DAT (that already has some
flavor of operator+ though without mixing base types), write:

template<> struct promote_sum< MyDAT > {};

The use, but not implementation, is similar to the technique suggested by
David Abrahams in boost::operators. This one is uglier but, I believe,
standard-compliant. Template do_not<> does a SFINAE trick of its own because
I couldn't figure out how to do the same thing with enable_if. And again,
MSVC++ 7.1 swallows it whole. Here's what I used to test it:

template<typename T> struct MyDAT_1
{
    friend MyDAT_1<T> operator+ ( const MyDAT_1<T>&, const MyDAT_1<T>& );
    MyDAT_1( T );
    template<typename T1> explicit MyDAT_1( const MyDAT_1<T1>& );
};

template<typename T> struct MyDAT_2
{
    friend MyDAT_2<T> operator+ ( const MyDAT_2<T>&, const MyDAT_2<T>& );
    MyDAT_2( T );
    template<typename T1> explicit MyDAT_2( const MyDAT_2<T1>& );
};

template<> struct promote_sum<MyDAT_1> {};

Here MyDAT_1 and MyDAT_2 are identical types; both define an operator+ for
uniform arguments. Promoted operator+ is only enabled for MyDAT_1. Now,

MyDAT_1<double> a(( MyDAT_1<int>( 1 ) + MyDAT_1<float>( 2.0 ) ));

compiles, while

MyDAT_2<double> b(( MyDAT_2<int>( 1 ) + MyDAT_2<float>( 2.0 ) ));

produces the following error:

e:\tmp\t.cpp(77): error C2678: binary '+' : no operator found which takes a
left-hand operand of type 'MyDAT_2<T>' (or there is no acceptable
conversion)
        with
        [
            T=int
        ]

which looks rather on-the-money to me.

The example implementation above only covers operator+( Foo<T1>, Foo<T2> ).
It has an obvious extension to all operator@( Foo<T1>, Foo<T2> ) as well as
to other things, for example:

template<> struct promote_product2< Matrix, Vector > {};

which can be implemented in the same way. An important special case is
support for things like operator*( Matrix<T1>, T2 ) where T2 is presumed to
be a scalar type and Matrix<T1>*T2 is expected to yield a Matrix<
promoted_type< T1, T2, std::multiplies > >. A generic operator* can be
provided for this case but it will only discriminate based on its first
argument, which may be dangerously generic for a general-purpose facility...

=================================

Well, if anybody got this far, I have to confess that I'm not sure what to
do with all this. The first part looks so trivial I may have well overlooked
an equivalent facility in one of the existing Boost libraries. If I haven't,
it hardly deserves a separate library, but I'm not sure which existing one
would be a good place for it. The second part looks like it belongs in
boost::operators, assuming that its benefits outweigh the dangers of
introducing very generic operators into global namespace (or is there a way
to do it otherwise and still get C++ to find the operator definitions?). Let
me know whether it will be worthwhile to develop proposed facilities for
subsequent Boostification.

Regards,
...Max...