Re: [boost] Formal Review for Interval Library

From: Fernando Cacciola (fcacciola_at_[hidden])
Date: 2002-09-10 13:32:39

Hello,

Here is my full review of the boost interval library (half a day later...
sorry)

First of all, all the authors have understood the comparison issues that had
been raised and had explicitly mentioned that they are willing to seriously
consider the scheme proposed by Douglas Gregor. Therefore, under the
assumption that this issue will be resolved, I vote to accept the library.

- What is your evaluation of the design?

The overall design is very good.
The different policies and the different helper classes used to build them
do cover IMO most practical cases.
The library is clearly targeted to some particular usages of IA, and I find
this appropriate. Others had argued that the library could provide a wider
abstraction, but I can't see very clearly how exactly such an abstraction
would be like, so I think that it is a more feasible goal to focus on
specific needs since otherwise we might risk overgenericity.

There is only one issue (besides comparisons) that I found quite odd:

I really don't understand the idea behind rounded_transc_dummy.
The rationale says that it is intended to output results which are valid
w.r.t the inclusion property, but why would it be useful to have a result
with such a property when it is invalid w.r.t the matemathically expected
value?
IMHO, this default policy should leave those functions undefined so that it
fails to compile, requiring the user to provide the appropriate functions.
As
it is right now, it looks to me as if log(-1) returned 6.02e28 just because
that result happens to be valid as a real number.

And a comment:

I could think of writing something like this:

interval<double> my_interval ;

interval_traits<my_interval>::rounding rnd ;

Because I might need to write my interval-based code (not generic numeric
code) with a minimum of coupling with this specific library.
However, there is already a class named 'interval_traits' which is not a
traits of an interval type, as its name might suggest, but a policy package.
And even worst, the code above will actually compile even though
"::rounding" is not the rounding policy used by my_interval.
I suggest to change the name of interval_traits to something like
'interval_policies and to add a new 'interval_traits' template class which
takes an interval type and exposes its inner types (base number, policies,
etc...)

- What is your evaluation of the implementation?

I was unable to compile the library with BCB5.0 Update 1 (bcc5.5.1);
and I had no time yet to see why; but I might in the future.
(and I better do it because I really need to use this library!)

Anyway, I looked closely at the code and here's what I found:

general:
~~~~~~~~

1) Numeric literals:

In my experience, numeric literals should be used with caution in generic
numeric code.
First of all, no literals should appear without the appropriate cast
expression, and new style cast (static_cast<T>(lit)) should be preferred
over
a converting-constructor cast ( T(lit) ).

Additionally, as a rule of thumb, those literals should be either integer or
floating point depending on the likelihood of the generic type to represent
integers or real numbers.
For example, if T is likely to be integer, then literals like 0,1,2 are OK.
But if T is likely to be real (floating-point), then literals like
0.0,1.0,2.0 are preferred.
There are two reasons for this rule:
(a) Numeric UDTs are likely to produce better code in the constructors from
the built-in types they are intended to replace.
(b) Numeric UDTs intended to replace, say, reals, might have more than one
constructor from FP types (float and double, for instance), but no
constructor from integers. In this case, an integer literal will produce an
ambiguity. The same could occur the other way around.

interval.hpp
~~~~~~~~~~~~

1) Should this constructor be explicit?

interval(const T& v = T());

I think it should because it is a converting constructor, and although the
class doesn't have a conversion to T (of course), it has mixed binary
operators.

2) The header declares this function:

template<class T, class Traits>
    bool in(const interval<T,Traits>& x);

which is not defined. The actual function takes a 'T' first.

3) The numeric_limits<> specialization contains the unqualified typedef:

typedef numeric_limits<T> bl;

I think that requires qualification (std::)

4) There is this function which is internally used to create interval
objects
directly:

interval(const T& l, const T& u, bool): low(l), up(u) {}

when this function is used, it looks like:

return interval(x,y,true);

I found the last parameter (true) confusing, it appears as a real
(meaningful) argument.
I suggest that the type of this third parameter is replaced by a tag struct
(such as
interval_impl)

rounded_arith.hpp
~~~~~~~~~~~~~~~~

1) The function 'sign':

template <class T> inline bool sign(const T& x) { return x < 0; }

returns 'true' if the value is 'negative'.
I personally have always seen such functions returning 'true' for the
positive case (or better -1,0,.+1).
I suggest its name is changed to 'is_negative()'

2) T median (const T& x, const T& y) { return (x + y) / 2; }

Change '2' to static_cast<T>(2.0), as explained above.

rounded_transc.hpp
~~~~~~~~~~~~~~~~

1) Why are these hyperbolic functions over T unqualified?

#ifdef BOOST_HAVE_INV_HYPERBOLIC
    T asinh_down(const T& x) { return ::asinh(x); }
    T asinh_up  (const T& x) { return ::asinh(x); }
    T acosh_down(const T& x) { return ::acosh(x); }
    T acosh_up  (const T& x) { return ::acosh(x); }
    T atanh_down(const T& x) { return ::atanh(x); }
    T atanh_up  (const T& x) { return ::atanh(x); }
#endif

utility.hpp
~~~~~~~~~~~

1) Just remember to double-check the commented code.
You've probably left it to make sure it can be really removed.

template<class T, class Traits> inline
const T& interval<T, Traits>::lower() const
{
  /*if (checking::is_empty(low, up))
  return checking::nan();*/
  return low;
}

- What is your evaluation of the documentation?

I have some comments about the docs:

1) "... Unlike std::complex, however, we don't want to limit T to these
types."

I think this should be rephrased so not to give the impression that
std::complex is purposely limited to FP types. It is just undefined for
other types.

2) "... Some of the following functions expect min and max to be defined for
the base type".

It should say: std::min and std::max

3) {immediately after the above} "... Those are the only requirements for
the interval class"

I think this should be  "requirements for the base number type"

4) "... The operators / and /= will try to produce an empty interval if the
denominator is exactly zero and a whole interval if it only contains zero"

I think that the docs should make an introduction about the roles of 'empty'
and "whole" intervals. Otherwise, the user will stop at the sentence above
and wander why a division by zero does return something instead of being
treated as an error. (as I did :-)

5) I strongly recommend that the rationale for the functions by separated in
paragraphs, reference-like, function per function. It is hard to look-up for
a specific function the way it is.

6) "...intersect computes the set intersection of two closed sets"

Should it be "the intersection of two intervals"?
"Closed Sets" are never formally defined nor related to an interval.

7) "...Interval values and references
This problem is a corollary of the previous problem with x != x. All the
functions of the library only consider the value of an interval and not the
reference of an interval. In particular, you should not expect (unless x is
a singleton) the following values to be equal: x/x and 1, x*x and square(x),
x-x and 0, etc."

I really don't understand any of the above

What is "the reference of an interval"? An "interval<T> const&"?
Why does it -whatever it means- prevents me from expecting "x/x==1"?
If it isn't just me, please provide a more elaborate explanation.

8) ..."Hence, use the policy compare_data to insert intervals in std::map."

I would add: "or provide your own custom comparator to the std container"
(which I think is the preferred way for non-totally ordered types).

9) The function reference needs a note explaining that the ranges shown on
the right of each function are the function domain.

10) The docs for sqrt() says that it can't take the argument 0. Why is it?

11) ... "the function will try to produce an invalid value or an input
interval"
It should read: "or an empty interval"

- How much effort did you put into your evaluation? A glance? A quick
reading? In-depth study?

I've done a deep study of the library, but I was not able to compile and use
it.

- Are you knowledgeable about the problem domain?

Yes. I've used other interval classes before in the domain of generic exact
or robust numerical applications.

- Do you think the library should be accepted as a Boost library?

Yes, as I said, assuming the comparison issue will be taken care of.

Fernando Cacciola
Sierra s.r.l.
fcacciola_at_[hidden]
www.gosierra.com