Re: [boost] Domain library

From: Brook Milligan (brook_at_[hidden])
Date: 2008-08-06 11:58:40

John Bytheway writes:
 > A good point, but the implementation I was looking at (from the gcc 
 > 4.3.1 header ext/numeric) doesn't, because it actually supports 
 > arbitrary MonoidOperations, not just multiply (and that in turn makes me 
 > think that there's something missing in that implementation, but that's 
 > another issue).

The basic implementation you speak of has a more general form that
takes a monoid as an argument.  Thus, it is possible to make this same
algorithm work for a variety of tasks.  Nevertheless, you are correct
that the algorithm itself does not handle the conversions that could
make it more general.  Thus, it could impose unnecessary
interconversions for Domain-aware types.

 > Could you easily write it such a way as to work well for both 
 > Domain-based types and other types?  (Clearly this is possible with 
 > sufficient metaprogramming, but is it easy?)

Yes, but I believe it requires a slight restriction on the monoid type
to do so.  Specifically, an adaptable monoid concept would be needed
that would include at least a result_type typedef.

Suppose such a monoid existed.  Then the following is a potential
defintion of a power() function.  (Note that this is solely for
illustration as it is not optimized to use squares, etc. as the
ext/numeric one is.)

     template < typename T, typename Integer, typename Monoid >
     typename Monoid::result_type
     power (const T& t, Integer n, Monoid monoid_op)
     {
       typename Monoid::result_type t_(t);
       for (Integer i = 0; i < n; ++i)
         t_ = monoid_op(t_,t_);
       return t_;
     }

This will perform the conversion internally and at most once.  Thus,
the problem of lots of conversions can be avoided for types that
interconvert correctly.

Of course, this transfers a bit of the complexity to the design of the
monoid type, as it needs to deduce things like the result type.  For
general types that do not have interconversions, monoids can be
written as the obvious extension to existing ones: just add the
following typedef (where T is the primary value type used by the
monoid):

          typedef T result_type;

For types created by the Domain library, which would have
interconversions and would have to do type deduction for the result
type, something like the following is possible:

       template <
         typename DomainFamily
         , typename DomainClass
           = typename boost::domains::extensions::domains::tag::multiplicative
         , typename Domain
           = typename boost::domains::mpl::default_domain<
             DomainClass
             , DomainFamily
	     >::type
         , typename Value
           = typename boost::domains::mpl::default_value<
             DomainFamily
             , Domain
	     >::type
         , typename Result
           = boost::domains::domain<Domain,Value>
         , typename Monoid = std::multiplies<Value>
	 >
       struct monoid
       {
         typedef Result result_type;

         template < typename D1, typename V1, typename D2, typename V2 >
         result_type operator () (const boost::domains::domain<D1,V1>& d1,
                                  const boost::domains::domain<D2,V2>& d2)
         {
           typedef typename result_type::domain_type domain_type;
           typedef typename result_type::value_type value_type;
           return result_type(Monoid()(value_type(d1.value_cast(result_type())),
                                       value_type(d2.value_cast(result_type()))));
         }
       };

I'm not at all certain that this is the best design.  However, it does
illustrate the point that a completely flexible monoid is possible and
that lots of the type deduction can be encapsulated within
library-provided MPL code.  Thus, users of the Domain library can
construct types such as this monoid that provide lots of flexibility
without having to worry about the details of type deduction.

By the way, the monoid above will work with the generic ext/numeric
algorithm as well as with the more general one above.  Likewise, the
algorithm above works with other types that are not part of the Domain
library so long as the monoid provides the result_type typedef.

Thus, I think the answer is that, yes, it is easy to provide these
algorithms that are very flexible, work with "normal" types, maintain
type safety, but will also support automatic domain interconversions
for types that are Domain-aware.  All this can be accomplished without
placing a great burden on the user of the Domain library to master the
arcane details of MPL.

Cheers,
Brook