Re: [boost] Formal Review for Interval Library beginning

From: Douglas Gregor (gregod_at_[hidden])
Date: 2002-09-03 12:10:11

Here is my review of the interval library. Thus far I've read through the 
documentation, skimmed the source code, and tried a few examples with an eye 
toward using the library for static analysis (involving intervals over 
integers and symbolic expressions). The sticking point for me with this 
library is the handling of interval comparisons. I'll start with those:

[Comparisons]
* The 'bool' return value from comparisons doesn't give enough information, 
because 3 states {false, indeterminate, true} are mapped to 2 states {false, 
true} before the comparison returns. Thus to see if a comparison is 
indetermine one needs (based on compare_certainly):

  interval<T> i, j; // get i, j from somewhere
  if (!(i < j) && !(i >= j)) {
    // ...
  }

  My opinion is that mapping to bool from any larger state-space should be 
done as late as possible, so that information isn't lost prematurely.

* I'm not a big fan of the comparison policy. Policies are great for code 
reuse, but when they are used to decide between different syntactic forms for 
equivalent semantics things can get _very_ confusing. This code is quite 
ambiguous:

  template<typename T, typename Traits>
  void foo(interval<T, Traits> x, interval<T, Traits> y)
  {
    if (x < y) {
      // ...
    }
  }
  
  Checking 'x < y' has no well-defined semantics, because 'foo' has no way to 
know what the comparison policy is. This forces all generic code to use 
'cerlt' or 'poslt' instead to give reasonable semantics. Essentially, any 
benefit of the '<' syntax is lost because one needs full contextual 
information to determine the semantics of the operation.

* I don't understand the reasoning behind the definition of <=. The 
documentation says "...another misleading interpretation of the comparison 
is: (still with the example of compare_certainly) [a, b] < [c, d] is true if 
and only if it is true for each pair of element in [a, b] and [c, d]. But 
[a, b] <=[c, d] is true if and only if it is true for at least one pair." 
  Why choose this (to me, non-obvious) semantics? Given a comparison such as 
[3,5] <= [4,6], why would we consider this true? I view an interval 
comparison [3,5] <= [4,6] as the comparison x <= y where x is in [3,5] and y 
is in [4,6], so the result is indeterminate (x could be 5 when y is 4, but x 
could also be 3 when y is 6, so either true or false is possible). What 
interpretation of [3,5] <= [4,6] leads to a value of (certainly) true?

* The <= semantics from above don't hold for cerle. Consider this fragment:

  interval<int> i(3, 5);
  interval<int> j(4, 6);
  assert(i <= j); // okay, based on above semantics
  assert(cerle(i, j)); // fails! the cerle semantics are different from <=?

  I would expect the semantics of <= with compare_certainly to coincide with 
the semantics of cerle, but they don't. (I prefer the cerle semantics)

* Comparisons require the underlying type 'T'  to be a total order, but I 
don't see the logical basis for this requirement because a partial order will 
suffice (intervals are a partial order regardless). I realize I'm pushing the 
interval library out of its intended domain, but the library is very close to 
usable more abstract domains (e.g., intervals bounded by symbolic 
expressions). 

[Comparisons - potential solution]
My proposed solution is:
  * Use a 3-state boolean type for the result of comparisons between 
intervals. The 'tribool' type I posted a few weeks ago is one such type that 
I believe would give a reasonable semantics.
  * Remove comparison policies entirely. With an accepted 3-state boolean 
type, there will be one semantics for 3-state boolean values that users will 
need to learn, so an interval comparison 'i < j' has a single, well-defined 
semantics in terms of 3-state boolean values and its narrowing to a standard 
'bool' will be consistent.
  * Remove cer?? and pos?? functions. 3-state boolean values can be queried 
directly to determine if they are false, indeterminate, or true. Without 
comparison policies, conversions to 'bool' are predictable.
  * Reformulate comparisons & routines that use comparisons to allow the 
underyling type 'T' to model only a partial order. For instance, the 
'intersect' routine requires a total order:

template<class T, class Traits> inline
interval<T, Traits> intersect(const interval<T, Traits>& x,
                              const interval<T, Traits>& y)
{
  using std::min;
  using std::max;
  if (interval_lib::detail::test_input(x, y))
    return interval<T, Traits>::empty();
  const T& l = max(x.lower(), y.lower());
  const T& u = min(x.upper(), y.upper());
  if (l <= u) return interval<T, Traits>(l, u, true);
  else        return interval<T, Traits>::empty();
}

If 'T' is only a partial order, the last two lines need to change to take into 
account the possibility that 'l <= u' cannot be determined. So, for instance, 
if the 3-state boolean type evaluates true only when its value is true (like 
compare_certainly - tribool acts this way), the last two lines would become:

  if (l > u) return interval<T, Traits>::empty();
  else return interval<T, Traits>(l, u, true);

The difference is that we return an empty interval only when we are _sure_ 
that the interval is empty. 

Now onto other things...

[General comments]
* I would prefer concept documentation as in SGI's STL documentation (or the 
Boost Graph library, MPL) instead of the use of C++ structs with exact 
operations listed. For instance, the documentation of compare_full states 
that the function object type "must have an operator of signature bool 
Function::operator()()", whereas concept documentation would require only 
that the expression 'static_cast<bool>(f())' be valid for a function object 
'f'. 

* I feel that I'm missing reference documentation for this library, and in 
particular the exact semantics of operations on intervals.

* Is there any relationship between the constants in interval/constants and 
the proposed mathematical constants library?

* Should the interval library go in boost/math/interval (and 
boost::math::interval_lib)?

* rounded_transc_dummy seems very dangerous, because it will allow meaningless 
code to compile. I think Jeff Garland already brought this up, but a call to 
sin(interval<T>) should not compile if it isn't going to do anything useful. 

* A typo in the "Interval Support Library" section: "...combined to fabricate 
almost various commonly-related..."

[Code comments]
* interval.hpp: Should the compare, checking, and rounding typedefs be 
exported as part of the public interface (probably with the names 
compare_type, checking_type, and rounding_type, respectively)?

* interval.hpp: pred/succ are #if 0'd out and should probably be removed (also 
log10, atan2, std::less specialization)

* io.hpp: some dead code #if 0'd out

* rounded_arith.hpp, rounding.hpp, utility.hpp, rounded_transc.hpp: should be 
moved into 'detail'  subdirectory

* rounded_arith.hpp: Macro ROUND_NR should have BOOST_ prefix

* checking.hpp: change assert() into BOOST_STATIC_ASSERT()

* rounding.hpp: should the architecture checks be moved into the config 
library?

[Conclusion]
Overall, I feel that the interval library is on the verge of becoming a great 
library for handling intervals of all kinds, but that it is not yet there. 
Dates/times (brought up by Jeff Garland) and symbolic expressions are 
examples of other types that nearly (and, IMHO, should) work with the 
interval library, but don't yet.

The handling of comparisons is, IMHO, the weakest point of the interface. 
There are some surprising inconsistencies with the use of comparisons, and 
overall I feel that this part of the interface could have been much 
(c)leaner.

Based on these two comments, (1) that the library is _almost_ a full generic 
interval library (and should be!), but there may be some challenges in 
achieving the next level of genericity that we can't foresee, and (2) that 
the handling of comparisons requires extensive changes in the interface that 
may ripple through the library, I vote to reject the interval library at this 
time. 

        Doug