Re: [boost] Formal Review for Interval Library (was:IntervalLibraryreminder)

From: Joerg Walter (jhr.walter_at_[hidden])
Date: 2002-09-08 06:47:12

Hi Guillaume,

you wrote:

> > > IMHO, the issue is more about the usefulness of the implicit type
> > > conversion in the scope of interval arithmetic, compared to the
> > > interface complication.
> >
> > Are you talking about a possible interface complication when using
> > promote_traits? If yes, then I'm not sure how such an interface change
would
> > be visible for a user (apart from the fact, that he could use mixed
> > precision operations then ;-).
>
> When we designed the library, we didn't even think about mixed operations.
> Indeed, we didn't find a nice way of doing interval conversions, so we
> didn't get any further in the handling of intervals with different base
> types.

I appreciate your honesty.

> So, here is the problem: we need to convert 'interval<T1, P1>' to
> 'interval<T2, P2>'.

The first case I'm interested in is interval<T1, interval_traits<T1> > and
interval<T2, interval_traits<T2> > (because that's what I tested ;-).

> If all elements of T1 are exactly representable by
> elements of T2, there is no problem: a cast is enough.

Correct, so we should be able to get

    interval<double> ris1 = 0;
    interval<float> ris2 = 0;
    // Doesn't work.
    // std::cout << ris1 + ris2 << std::endl;
    std::cout << ris1 + interval<double> (ris2) << std::endl;

without risk, at least? This would be very helpful, because we then could
use

    vector<interval<double> > riv1 (1);
    vector<interval<float> > riv2 (1);
    riv1.clear ();
    riv2.clear ();
    // Doesn't work.
    // std::cout << riv1 + riv2 << std::endl;
    std::cout << riv1 + vector<interval<double> > (riv2) << std::endl;

immediately, i.e. std::complex and boost::interval would behave similar
w.r.t. basic linear algebra.

> But what if an
> element of T1 can't be represented? We need to convert it

This isn't a new problem, the same can happen, when converting a double to a
float.

> and respect the
> inclusion property of interval arithmetic.

Maybe this is a new problem. What do other interval libraries do here?

> Somebody could probably object that with 'promote_traits', we always are
> in the first case if 'promote_traits' is correctly built. But, in my
> opinion, if an interval can never get back to a less precise type, all the
> mixed operations stuff is useless.

Generally agreed. But if you build your promote_traits correctly, the user
of the interval library only needs to consider the cases where going back to
a less precise type, at least.

> I'm not sure to clearly explain what I
> mean; I will say it another way: if all the operations (being mixed or
> not) produce 'interval<double>' thanks to 'promote_traits', what's the
> point of having mixed operations able to handle 'interval<float>' since,
> after a few operations, only 'interval<double>' will remain.
>
> I hope I was able to explain we wanted to do conversions in the two
> directions. And here come the interface complications. Where can we put
> these conversions?
>
> First idea, to define them globally by something like:
>
>   template<class Src, class Dest>
>   struct conversion {
>     Dest convert_up  (const Src&);
>     Dest convert_down(const Src&);
>   };
>
> But now, it will conflict with the 'Rounding' policy of the interval class
> which is supposed to handle all the dirty work (aka handling the
> computation on the base type). So this is clearly not a solution.
>
> So, since 'Rounding' is here to handle this kind of stuff, why doesn't
> this policy do it? We could just add:
>
>   struct my_rounding {
>     ... // all the previous stuff
>     template<class Dest> Dest convert_up  (const T&);
>     template<class Dest> Dest convert_down(const T&);
>   };
>
> That's a solution. Another solution would be to have the conversion the
> other way around: 'template<class Src> T convert_...(const Src&);'. But
> these solutions suffer from the same drawback: when an user wants to add a
> new conversion to an existing policy, it's suddenly become less trivial
> (in my opinion).
>
> If the library was only meant to be used with float, double and long
> double (following the example of std::complex), we would have added such
> conversions. But because we wanted to be able to use it with a lot more
> type (rational, multi-precision numbers, etc), we didn't do it.
>
> Maybe there is a nice way to handle all of this, but unfortunately, it
> didn't occur to us.

Ok. First of all, I'm neither too familiar with your current implementation
nor with the pitfalls of policy based design in general. As far as I see,
the following transformation of ublas experiences restricted to the
simplified case might help:

- adding a templated constructor

  template<class T, class Traits = interval_traits<T> >
  class interval {
    // Need some magic to allow only types U, which are representable by T
    template<class U>
    interval (interval<U, interval_traits<U> >);
  }

- writing some type promotion traits

  template<>
  struct promote_traits<interval<double>, interval<float> > {
    typedef  interval<double> result_type;
  }

- implementing some binary operators

template<class T1, class T2> inline
typename promote_traits<interval<T1>, interval<T2> >::result_type operator+(
         const interval<T1>& x,
         const interval<T2>& y)
{
  typedef typename promote_traits<interval<T1>, interval<T2> >::result_type;
  if (interval_lib::detail::test_input(x, y))
    return result_type::result_type::empty();
  typename result_type::rounding rnd;
  return result_type(rnd.add_down(x.lower(), y.lower()),
       rnd.add_up  (x.upper(), y.upper()), true);
}

Best regards

Joerg

> PS: I'm not doing a kind of systematic opposition on this subject. It's
> true that we didn't think about mixed operations; but we really wanted to
> be able to do safe conversions from one interval type to another, and we
> unfortunately didn't find a way to do it.