Re: [boost] Formal Review for Interval Library beginning

From: Herve Bronnimann (hbr_at_[hidden])
Date: 2002-09-03 12:54:22

On Tue, Sep 03, 2002 at 01:10:11PM -0400, Douglas Gregor wrote:
> 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:

Doug: thanks for your review. I'll let my coauthors answer the question
on comparaisons. Your points are fair, subtle, and coherent. Let me just
say that we are aware of the problem behind operator< and this is why
Guillaume felt it necessary to introduce the cerlt, etc. functions.
There was no talk of 3-state booleans at the time we were working on it,
and thus it shaped our design. But we'll have to discuss yours and get
back to you.

> [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 like that documentation style, but it is not widely adopted in boost,
where the synopsis style (for short classes anyway) seems to prevail.
(And not so short either, if I can quote boost/quaternion).

Concept documentation is used to document requirements, mostly for
template parameters (e.g. ForwardIterator). It is appropriate for the
base number type, and the Function parameter of compare_full. But it is
not really appropriate for classes and functions.

I agree with you that the requirements could be phrased differently and
more carefully, for the Function operator. This will be corrected.

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

We use the `standard' semantics of operations on intervals, mainly
driven by the inclusion property. See also:
http://www.cs.utep.edu/interval-comp/main.html

As I agreed in a prior reply, the introduction could (and should) be
beefed up. We'll keep that in mind.

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

It would be nice if the math constants library provided some guaranteed
upper and lower bounds for various constants. Then we could provide the
matching interval constants. AFAIK, though, the proposed mathematical
constants proposes only nearest representable values. We should perhaps
coordinate here. But this proposed library is not yet part of Boost, if
I am following correctly, and we do not want an external dependence on a
moving target.

Could the proposer of the mathematical constants library please contact
us privately?

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

This makes the use a little more cumbersome, but would definitely be
warranted wrt the scope of the library.

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

This is the other route. Our choice is correct (i.e. returns a valid
interval) and but it is true that the danger is that the user is
unaware of why he/she is getting strange intervals.

> [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)?

I wouldn't mind but the traits_type provides those already (with one
more level of indirection).

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

Date/times have already been discussed.  As has been mentioned before,
though, this library is primarily intended as a numerical computation
library. As Jeff himself has pointed out, dates don't really provide a
number type. Durations do.

Symbolic expressions such as boost::rational and other types that
fundamentally represent numbers could be (and should probably have been)
tested, if we had had more time, but I do not see a major problem why
they shouldn't work. Indeed, they have worked in other (closely related)
interval libraries. Other than that, I am not sure what other symbolic
types you envision. Perhaps you can elaborate.

At any rate, obviously much quality thinking has gone into your review
and we appreciate the time you took to write it. We will definitely
review the merits of your comparison proposal. Thank you,
--
Hervé