Re: [boost] Formal Review for Interval Library

From: Guillaume.Melquiond (gmelquio_at_[hidden])
Date: 2002-09-10 15:27:48

On Tue, 10 Sep 2002, Fernando Cacciola wrote:

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

Thank you for your review.

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

Yes, comparisons will probably be rewritten with the scheme Douglas Gregor
proposed. I say "probably" because future is something I'm unfortunately
unable to predict :-). But what I'm sure is that the two other authors and
I did agree this scheme is better.

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

Okay. I seem to remember you weren't the only to prefer undefined
functions. And since it's something we aren't particularly fond of,
'rounded_transc_dummy' may be suppressed.

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

All 'traits' in the code will be replaced by 'policies' since it's what it
really is (and some people complained). So the term 'interval_traits' will
be freed and it could be replaced by your definition. However, it's
already possible to do 'my_interval::traits_type::rounding'. What is the
prefered style:  'interval_traits<my_interval>' or
'my_interval::traits_type'?

> - 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!)

I did try to compile it with BCC 5.5.1. There was a little problem with
some code in the constructors (you should have the same errors than me)
and when this code was commented out, there was no more compilation
problem.  So I think it can be easily fixed (I hope so).

There was also a little problem at runtime. But I already know how to fix
it (and it will be done as soon as I get a Windows computer back).

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

Yes, you're right. And integer values were finally chosen because we
thought they were more generic. Indeed it's easier to build a constructor
from 'int' to 'T' when you already have a constructor from 'float' to 'T'
than the contrary.

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

Yes, it's something some of us wanted. But unfortunately, declaring it
'explicit' disallow this statement:

  interval<T> my_variable = some_expression_of_type_T;

So we finally decided to let the constructor be 'implicit'.

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

Oops. Thanks for spotting it.

> 3) The numeric_limits<> specialization contains the unqualified typedef:
>
> typedef numeric_limits<T> bl;
>
> I think that requires qualification (std::)

I may be wrong: since the 'numeric_limits' specialization belongs to
'std', the qualification in the 'typedef' isn't really required, is it?

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

I hope you're the only one to suggest this modification; or there will be
a lot of changes in the implementation :-).

More seriously, it can easily be done.

> 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 disagree with "-1,0,+1". It would change a lot of the algorithms and I
don't want to go through a thorough verification of the new functions.

> I suggest its name is changed to 'is_negative()'

Yes, it's probably more adapted than 'sign'. Now that you mention it, I
remember a 'sign' function usually returns "-1,0,+1" rather than a
boolean.

> 2) T median (const T& x, const T& y) { return (x + y) / 2; }
>
> Change '2' to static_cast<T>(2.0), as explained above.

Right.

> 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

Somebody else will probably answer. But I seem to remember the Standard
doesn't require these functions of <cmath> to be defined in the namespace
'std'. It was also discussed on gcc mailing-list (I hope my memory
doesn't fail me).

> 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;
> }

No, we are sure it can be removed. But we left it because we intended to
define two functions 'checked_lower' and 'checked_upper'. And these
functions would have use the commented code.

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

Okay.

> 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

No, we can't really be sure that 'min' and 'max' are defined in 'std'
(they may be in the same namespace than the definition of 'T' for
example), so we only expect 'min' and 'max' to be defined. If they aren't,
the code will automatically fallback on '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"

No, it wasn't meant to be "for the base number type". But now that you
mention it, I understand the sentence may be confusing and should be
rephrased.

> 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 :-)

Okay.

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

Right.

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

I will try to explain it.

Let's suppose you have:

  double x, y, z;
  ...
  z = x - x + y;

You probably would expect this code to be equivalent to 'z = y;'.

Now, let's suppose you replace 'double' by 'interval<double>'.
Mathematically, you would also expect the code to be equivalent to 'z =
y;'. But the library doesn't look at the address of the objects and
doesn't know they represent the same object. So it will answer that 'x -
x' is '[-width(x), width(x)]' rather than '[0,0]'.

Is it clearer explained like that?

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

It won't be a problem anymore if we choose the scheme Douglas Gregor
proposed.

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

It's written: "The domains are written next to their respective
functions". Or are you speaking about something else?

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

No, you get it wrong. It only means that the functions of the policy don't
have to handle the argument 0. The domains are what the library expects
from the functions.

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

Right.

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

Thank you,

Guillaume