[boost] Interval Library review

From: Gennadiy Rozental (gennadiy_at_[hidden])
Date: 2002-09-07 18:35:13

This is my review for the Interval Library.

Based on several serious concerns I am having with current design, interface
and implementation I vote NO for inclusion this library in it's current
state into boost.

Here my comments (several of my original comments still apply; I did not
mentioned them here)

Design:

I believe that reviewed library design is too restrictive in several
directions.

1. The interval is defined as one whole.
Currently library only working for 'number' types that fit to very long list
of requirements. While in reality I may be interesting only in some of the
functionality without complying to the rest of requirements. So IMO library
need to be significantly refactored based on set of requirements:
Minimal interval - minimal set of requirements (probably only partial order)
Add some operation  - minimal set + total order
.....
Complete interval functionality - should comply to all current requirements

Rounding policy will need to be separated on several policies each
responsible for appropriate set of functionality.

2. Open/Close intervals
Library should explicitly support open and close intervals. For example it
could be 2 subclasses
open_interval<...> and close_interval
3. Library should support an ability to define operation over intervals with
different base types. It could be easily done with use of specific traits
class like this:
template<typename Arg1Type, typename Arg2Type>
struct binary_interval_operation
{
    typedef ... result_type;
};

Now you could introduce as many specialization as you want, like this

template<>
binary_interval_operation<double,float>
{
     typedef double result_type;
}

Now you could use this trait to implement any binary operation.
4. Multi-Interval support
Though I agree that this is complex task and need not to be in a first
release of the library, I still believe it should be considered as essential
part of generic interval library. In my experience static analysis task
required namely this type of abstraction. Also, result of operation 1/x for
x = [-1,1] should be (-inf,-1] && [1,+inf) not [-inf,+inf]. Even if it could
be ok in numeric computation domain (Unfortunately I did not get a response
on my request on usage examples for the library and I am not an expect in
this domain to judge) I could envision that it is not in some others. So IMO
library should state that this is among future directions.

5. Interval lacks notion of iterator
I believe it could be convenient in many context to consider interval as a
container and accordingly we need the iterators.

6. iostream operation should be more flexible.
 The best would be to have an ability to define input/output format
externally. At least open/close intervals should differ.

7. Checking policy is poorly designed
Checking policy should *check*. It should not provide any type traits. Every
time I see T int = checking ::inf() I

8. I agree with Doug that comparison policy is most probably is orthogonal
to the interval, IOW you could use the same interval with different
comparison policies. So design should be changed accordingly.

9.   Why pow function have second argument int. How could I calculate
interval ^ 5/3.
10. Why log presented only natural?
11. Why transcendental function presented only exp? What about 2 ^ interval
?

Interface:

1. Template parameters should be decoupled and specialized using named
template parameters (and named as a policy not a traits)
2. Nor checking policy nor compare policy should be parameterized with T,
since they are not depend on T. You should have used template member
function instead.
3. Why lower, upper free functions returns T instead of T const&? It could
be expensive when you work with types like bigint

Implementation:

1. set_empty and set_whole are excessive and should be removed.
2. namespace interval_lib is confusing.
   Everything that is in this library is interval lib. Better name may be
interval_policies.
3. Checking policy implementation could be made more concise and flexible
would it be implemented in a form:
template<typename isNanChecker, IsEmptyChecker,...>
struct check {...};
With use of named template parameters it will be even more convenient.
4. Why constant pi defined only as a double or float. What if I need pi as
miltiprecision_double class value? Maybe it should be computed at compile
time. You may provide precomputed specialization for intrinsic types.
5. What is to_int method and why is it defined sometimes only for double or
float?
6. All rounding_control, rounded_arith_..., rounded_trancs_...  and
rounded_math does not seems to depend on T. So they should not be a
parameterized with T at all. You should use template member functions
instead.
7. Why do you need 3 separate classes rounded_transc_... parameterized with
Rounding? Do expect that rounded_transc_opp could use rounded_arith_std?
8. It would be more clear and flexible if State Management logic would be
orthogonal to rounding and specified as a second argument of class rounded
math. Also every level of rounding logic could be passed as a parameter
also. In combination with 6 and 7 rounding policy could be implemented like
this:

struct rounding_control
{
    ...
    template<typename T>
    static T const& force_rounding(T const& x) { ... }
    ....
};

template<typename RoundingControl>
struct rounding_arith_exact : RoundingControl
{
    ...
    template<typename T>
    static T const& force_rounding(T const& x) { ... }
    ...
};

template<class RoundingControl>
struct rounded_transc_exact: rounding_arith_exact<RoundingControl>
{
    template<typename T>
    T exp_down  ( T const& x ) { ... }
};

template<typename StateManagement = save_state_nothing , typename
RoundingTransc = ..., RoundingControl = ... >
struct rounded_math
: save_state_nothing<RoundingTransc<RoundingControl> >
  {};
9. Function templates like: template<class T> inline T pi_lower() does not
work at least on MSVC. Use class specializations instead.

Code:

1. Why exception_create_empty::operator() returns T?
2. Should not ext de a subdirectory of details?
3. Should bcc_rounding_control.hpp be names x86bcc_rounding_control.hpp?
4. The fact that all template parameters are named Rounding is very
confusing. Instead it should be RoundingControl for rounded_arith_...
classes RoundedArith for rounded_transc_.. functions and Rounding policy for
interval class.
5. rounding_control needs to be in a separate headers also as you did with
rounded_arith and rounded_transc
6. Prefer typename to class to mark template parameter
7. It's a pity that you could not work in case if BOOST_NO_STDC_NAMESPACE is
defined. Why couldn't you do the same workaround as in all other places.
8. class interval implementation should be in interval.hpp or
interval_impl.hpp or interval/impl.hpp

Docs:

1. Fist line in comparison doc page is started:
"As was said before". Where?
2. intersection is named intersect in docs. Who is correct?
3. bisect is not mentioned in "Operations and Functions" section. width is
not marked bold
4. Comparison operators are not mentioned in "Operations and Functions"
section.
5. "singleton test if an interval is a singleton" is unclear.

Compilation
Its a pity that library does not compile with MSVC 6.5. It does not seem to
use any "advanced" features so should be pretty portable.

Testing.

Main and general comment: you should have used new Boost.Test.  For one do
not use deprecated tools like BOOST_TEST (use BOOST_CHECK instead). Second
you testing may become more expressive

add.cpp  fmod.cpp pi.cpp
I know that function templates like
template<typename T>
void foo() {
    ...
}
produces wrong specialization with MSVC. So you whole test module may not
work. Use class specialization instead.

Instead of BOOST_TEST( equal( expr1, expr2 ) ) better use:
BOOST_CHECK_PREDICATE( equal, 2, ( expr1, expr2 ) );
It will make your error notification much more expressive.

cmp.cpp
Did you consider using unit test framework? In this case following

int test_main(int, char *[])
{
  test_12_34();
  test_13_24();
  test_12_23();

  ...

could be rewritten more explicitly as a separate test cases.

det.cpp
The same issue as in add.cpp with function specializations.
Propagate test assertion to the lowers level possible. IOW do not test
result of complex function. Test exactly where error occurs.
In this case, instead of
      if (!(equal(d_op, d_sp) && equal(d_sp, d_ou) && equal(d_ou, d_su)))
        return false;
Write
BOOST_CHECK_PREDICATE( not1( equal ), 2, ( d_op, d_sp ) );
BOOST_CHECK_PREDICATE( equal, 2, ( d_sp, d_ou ) );
BOOST_CHECK_PREDICATE( equal, 2, ( d_ou, d_su ) );

interval_test.cpp
Why did not you use Boost.Test here?

io.cpp
The same issue as in add.cpp with function specializations.
use ostream_test_stream for testing output operation. In this case you would
not need this verbose ifdefs.

pow.cpp mul.cpp
Te same comments as with det.cpp, but you should have used BOOST_CHECK_EQUAL

overflow.cpp
The same comment as with add.cpp. You test should look like:
BOOST_CHECK_PREDICATE( in, 2, ( x, y ) );

Gennadiy.