 # Boost :

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

[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...

* 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..."

* 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