Boost logo

Boost :

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 {
  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()
  return 0;


Boost list run by bdawes at, gregod at, cpdaniel at, john at