[boost] [Interval Comparisons] Proposed resolution

From: Douglas Gregor (gregod_at_[hidden])
Date: 2002-09-06 16:34:06

I propose that we:
  1) Remove comparison policies _in their current form_
  2) Create a default comparison semantics that makes interval<T> a numeric 
type that will work well in generic functions (it should throw if rounding 
errors cause a comparison to be indeterminate)
  3) Allow other comparison semantics to override the default semantics within 
a particular scope

I'll give the approach semantics first, then a justification of those 
semantics, then finally the actual implementation.

[Behavior of Interval Comparisons]
Under this proposal, intervals will act like their underlying data types 
except that rounding issues will be taken into account. Generic code that 
operates on a numeric type 'T' will compile and work with 'interval<T>'. When 
comparisons on interval<T> objects become indeterminate (i.e., rounding 
errors have significantly affected the computation), an exception is thrown 
to report the problem.

The semantics therefore corresponds to the way the library works now with 
compare_full and a function object that throws; however, the Comparison 
policy has been removed.

Other semantics can be introduced within a given scope using rel_ops-style 
trickery (thanks to David Abrahams for suggesting this). A new semantics is 
introduced by creating a new namespace:

namespace my_interval_semantics {
  template<typename T>
  bool operator<(const interval<T>& x, const interval<T>& y)
  {
    // ...
  }
  
  // other comparison operators
}

When we want to use this semantics, we bring it into scope:

void foo()
{
  using namespace my_interval_semantics;

  interval<int> x, y;
  if (x < y) { // uses my_interval_semantics::operator<
    // ...
  }
}

[Justification of this Behavior]
There are a few things to justify here, of course. I'll try, Q&A-style :)

Q: Why choose the arithmetic semantics as the default semantics?
A: There is a lot of generic code for performing numerical algorithms that 
predates the interval library. However, the primary reason the authors 
developed the interval library was to be able to leverage this existing code 
but with the safety guarantees of interval arithmetic. Domains relying on 
other semantics aren't as deeply entrenched, and I know of no generic 
libraries that operate on intervals. Therefore, the default fits existing 
practice; other libraries built on top of the interval arithmetic library 
will be able to set a particular semantics for intervals that they need.

Q: Why is this rel_ops-style better than comparison policies?
A: Comparison policies can be dangerous because of the coupling between the 
comparison semantics and the type. Some specific reasons:
  1) Comparison policies interact poorly with generic functions. If a generic 
function 'foo' expects one comparison semantics, but is instantiated with a 
type 'interval<T, OtherComparisonSemantics>', it will still compile but will 
operate strangely. Generic functions need to be able to choose their 
semantics and be sure that those semantics are used; the rel_ops approach 
allows a generic function to write 'using namespace my_desired_semantics' and 
be sure that intervals will use the appropriate semantics. 

  2) It is unnatural to tie the comparison semantics to the type being 
compared. The same type interval<T> might be useful under two different 
semantics at different parts in the program. Those different program parts 
can differ lexically (e.g., be in different scopes) but cannot operate on the 
same interval type with the policies approach. With the rel_ops approach, one 
part of the program can use one semantics with 'using namespace semantics_a' 
and the other part of the program can use a different semantics with 'using 
namespace semantics_b', and they can still share the underlying interval<T> 
type that is orthogonal to the way it is compared.

  The difference between the approach I'm proposing and the comparison 
policies approach is this: I'm proposing an approach that ties the comparison 
semantics to the current scope, whereas the comparison policies tie the 
comparison semantics to the interval type. I believe that scopes more 
naturally represent the logical blocks in which a particular comparison 
semantics is more desireable than any other comparison semantics.

Q: Why throw when an indeterminate result is found in the arithmetic 
comparison semantics?
A: The arithmetic comparison semantics is useful when performing computations 
where one needs to know how rounding affects the results. In these semantics, 
interval<T> _must_ act just like T. When an indeterminate result is found in 
comparing intervals, it means that roundoff errors have gotten so bad as to 
have an effect on the computation itself, and an exception is a reasonably 
way to indicate failure that generally should not occur.

Q: Aren't we pushing the interval _arithmetic_ library out of its bounds? It's 
only meant to handle the behavior that is the default in this proposal.
A: I think we may have pushed the library beyond its intended bounds, but I 
don't believe that we've pushed it beyond it's natural level of abstraction. 
With the exclusion of comparison semantics, we all seem to agree on the 
semantics of interval computations for at least two very different domains 
(interval computation to keep roundoff in check and static analysis), and it 
would be unfortunate to have to duplicate 95% of the library to create an 
library for that other kind of interval arithmetic. With a little bit of 
pickiness about the definitions of operators, and a way to safely introduce 
different comparison semantics, this interval arithmetic library can subsume 
several types of static analysis on integer variables. The proof of a generic 
interface is when it can be naturally applied to problems in domains not 
considered when the interface was designed; IMHO, the library interface is 
95% of the way to a natural application in a very different domain. 

[Implementation Details]
Here's a short sample program that describes the implementation scheme that 
can be used. The crucial point is that the definition of operator< inside the 
interval class is the default operator<. However, the second argument (not 
'this') requires a (no-op) implicit conversion via the interval_holder class 
template. Thus, if any operator<(const interval<T>&, const interval<T>&) is 
available (e.g., introduced via a 'using namespace ...'), that operator< will 
be a better choice than the operator< inside the interval class, because the 
second argument will only require cv-qualifier adjustments instead of a 
user-defined conversion by constructor. The result is that 'using namespace 
my_interval_semantics' brings in a set of operators whose semantics are 
always better than the default semantics.

template<typename T> struct interval_holder;

template<typename T>
class interval {
public:
  bool operator<(const interval_holder<T>& other) const
  {
    std::cout << "Default implementation\n";
    return true;
  }
};

template<typename T>
struct interval_holder
{
  interval_holder(const interval<T>& in_interval) : interval_(in_interval) {}

  const interval<T>& interval_;
};

namespace my_interval_semantics {
  template<typename T>
  bool operator<(const interval<T>& x, const interval<T>& y)
  {
    std::cout << "my_interval_semantics implementation\n";
    return false;
  }
};

void foo()
{
  interval<int> x, y;
  assert(x < y);
}

void bar()
{
  using namespace my_interval_semantics;

  interval<int> x, y;
  assert(!(x < y));
}

int main()
{
  foo();
  bar();
  return 0;
}

        Doug