[boost] [XInt] Review

Subject: [boost] [XInt] Review
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2011-03-09 13:11:31

Dear Chad, Volodya, list,

This is my review on the XInt library. On the outset I'd like to thank
Chad for his work and stamina in providing the XInt library. It is not
only a big effort to provide a portable, functional and well
documented library like this, but it also takes a great deal of
courage to undergo a review process on the boost list.

As far as I can see from some tests and use cases the library is
useful, functional, correct and portable. The library implements the
interface that is about to be part of the new standard. So many things
are looking good and independent of the final result of the review,
XInt is already a valuable tool and a great contribution.

While this is more than is needed for many purposes, I come to the
conclusion that it is not enough for boost. Integer is a very central
prototypical data structure that should be and will be expected to be
a model for the design of other libraries. I expected its design to be
very clear and simple and very flexible and generic at the same time.

While I was looking more deeply into the code and structures of XInt I
came more and more to the conclusion that the current design is
insufficient for a boost library in general even more so for an
Infinite Precision Integer Library.

So my vote is NO for acceptance of XInt with its current design.

Even though, I'd like to encourage Chad to solve the questions around
concept based generic design for XInt and to resubmit his project,
when design and other issues raised in this review are solved. Maybe a
deal of patience and reflection and openness to the information
provided by others was helpful. Maybe the person with the most
unpleasant critique has the most valuable insights for you.

At the same time I'd like to call on the boost community to support
Chad and to see an Integer library as an opportunity to develop more
common understanding how a state of the art generic design looks like
in this specific case.

Best regards,
Joachim

==============
Review Details
==============

1.1 Naming: Library
===================

An unlimited integer is an int that is not limited to a size
restriction. So it conforms the mathematical notion of an integer
better than built in ints. My favorite name for such a library was

Boost.Integer

Where would a (new) user expect such a library, exactly there. IMO
Boost.Integer is much better than Boost.Xint. Boost.Integer already
exists. So why not integrate new (unlimited) integer types into
Boost.Integer? For simple concise naming and intuitive structuring
according to user expectations, that would be the best choice.

1.2 Naming: Namespace
=====================

Components of Boost.Integer are relatively old and located directly
within namespace boost. So for the new Integer library we can choose

namespace integers

completely consistent to the official boost naming conventions:

http://www.boost.org/development/requirements.html#Naming_consistency
which says:
The library's primary namespace (in parent ::boost) is given that same
name [as the library], except when there's a component with that name
(e.g., boost::tuple), in which case the namespace name is
*pluralized*.

which is specifically consistent since we know that Chads Integer
library offers *different* integer types such that declarations

integers::pure<>     i; // limitless "pure" integers
integers::fixed<512> j; // limited to fixed size

are pretty intuitve.

1.3 Naming: Types
=================

What I like about boost, compared to many other libraries, is the
culture of short and concise naming. This includes the absence of
cryptic pre and suffixes. But there are exceptions. One of those is
the _t suffix used for a variety of types, namely int<n>_t types from
Boost.Integer.

I am opposed to any pre or suffixing, since it is not inline with
general boost naming conventions, that discourages cryptic names or
name components. My guess is that the _t suffix has been chosen as an
emergency measure once: The name of choice had been used already and
overloading was not possible.

Where no such conflict is present, I propose to use concise and simple
names without pre or suffixes.

One of the reasons why I dislike pre/suffixes is that they are cryptic
abbreviations most of the time. The second reason is that they, even
if non cryptic, introduce useless redundancy:

// "type" is used 5 times as pre or suffix
typedef typename foo_type::key_type mykey_type;

// instead of
def foo::key mykey;

// or
type mykey = foo::key

2. Design
=========

As other reviewers have pointed out before the design does not allow
for decoupled integer types that can be models of integer concepts,
such that appropriate sets of free standing functions will serve to
operate on those types and the library can be extended for any other
type that will be implemented as model of the integer concepts that
the library defines.

I think such a design would implement the ideas that can be found in
[Järvi et.al. 2003, Concept Controlled Polymorphism]
http://parasol.tamu.edu/~jarvi/papers/concept-controlled.pdf
and that is implemented in modern boost libraries like e.g.
Boost.Polygon. (Boost.Geometry is also a good example, but not so
close to the Järvi paper)

Because of its fundamental character, a general Boost.Integer should
serve as a model, a prototype for other libraries and it should
represent the current state of the art in this field. Because everyone
understands integers, people will probably look at Boost's Integer
design to understand modern design from a concise example. This is an
opportunity and a challenge for the author but more so for the boost
community.

It could also be an opportunity to converge and synthesize different
points of view in a prototypical design.

The current design does not meet my requirements here. This is not a
shortcoming of the author alone. In the discussions that have taken
place around xint's design, the concept based paradigm and techniques
obviously were not communicated in such a way that they found their
way into a state of the art design.

2.2 Boost.Parameter considered unfavorable
==========================================

Although flexible, the options feature based on Boost.Parameter comes
with an unnecessary and undesired level of abstraction and
indirection. It obfuscates the different kinds of parameters and makes
the implementation much more difficult to read. Moreover the meta code
involved with Boost.Parameter imposes a compile time penalty.

IIUC all of the option parameters are compile time constants designed
to steer implementation variants. There are much simpler and clearer
ways to do that.

Also

integers::fixed<512> myVar; //is very intuitive, while

xint::integer_t<xint::options::fixedlength<512> > myVar;
  // can't probably be done without consulting the docs
  // and it is more verbose

2.3 Policy based design
=======================

I think policy based design is a very good and powerful technique that
is specifically useful to separate implementation variants of class
templates in clear and flexible ways. Unfortunately I can not see that
you are actually using policy based design here. Because your design
lacks typical policy classes that encapsulate implementation variants
in a way that reduces codereplication and enhances flexibility.

What your intended policy classes say, nan_functions<..>, only do is
to encapsulate the functions that other implementation variants do not
need. But this can be done by simple object inheritence alone.

2.4 Do we really want to be nanied
==================================

Recently I met a guy named Larry from Huston Texas who introduced me
to the notion of a nanny state. Germany, for example is a nanny state,
because it imposes coercive health inshurance on its citizens. This
may be totally unnecessary for some, who are always able to perform
surgery on themselves.

In a similar sense we could introduce the notion of a nany class, for
thouse of us, who are not able to control their program logic ;-)

To come to the point. I still don't really see the the indispensable
benefits of nan and an exception free bigint class. We happiely work
with ints for decades, that throw interrupts for division by zero. So
why do we need a protection against that case that can be easily
controlled through program logic?

If we let go of the nan idea, everything is a great deal simpler and
less ugly. The rationale given by the docs does not convince me
either.

3. Implementation
=================

3.1. Codestyle
==============
3.1.1 Codestyle: Layout
=======================

The library aheres to a restricion of a line length of 80 characters,
which is still official boost policy. In many instances the lines are
just broken before length 81 regardless of syntactical structure and
readability.

I dislike this coding style since it obscures structure and easy
readability for no obvious reason. At some points the reader needs
extra efforts to scan the text. E.g. the inheritence list of class
template integer_t is an amorph textblock

template<BOOST_XINT_INITIAL_APARAMS>
class integer_t: virtual public detail::integer_t_data
  <BOOST_XINT_APARAMS>, public detail::nan_functions<detail::
  integer_t_data<BOOST_XINT_APARAMS>::NothrowType::value,
  integer_t<BOOST_XINT_APARAMS>, BOOST_XINT_APARAMS>,
  public detail::fixed_functions<detail::integer_t_data
  <BOOST_XINT_APARAMS>::BitsType::value, integer_t
  <BOOST_XINT_APARAMS>, BOOST_XINT_APARAMS>, public
  detail::unsigned_negative_functions<detail::integer_t_data<
  BOOST_XINT_APARAMS>::SignType::value, BOOST_XINT_APARAMS>

instead of a structured text

template<BOOST_XINT_INITIAL_APARAMS>
class integer_t:
  virtual public detail::integer_t_data<BOOST_XINT_APARAMS>,
  public detail::nan_functions
         <
           detail::integer_t_data<BOOST_XINT_APARAMS>
             ::NothrowType::value,
           integer_t<BOOST_XINT_APARAMS>,
           BOOST_XINT_APARAMS
         >,
  public detail::fixed_functions
         <
           detail::integer_t_data<BOOST_XINT_APARAMS>
             ::BitsType::value,
           integer_t<BOOST_XINT_APARAMS>,
           BOOST_XINT_APARAMS
         >,
  public detail::unsigned_negative_functions
         <
           detail::integer_t_data<BOOST_XINT_APARAMS>
             ::SignType::value,
           BOOST_XINT_APARAMS
         >

that facilitates readability.

3.1.2 Codestyle: Filesize
=========================

integer.hpp is too long. It should be separated in smaller named
entities according to structural aspects. Filesizes can also be
reduced by decomposition of the design and by reduction of
redundancies and code replication.

3.1.3 Redundancies and Codereplication
======================================

There is a great deal of code replication in the current
implementation of xint::integer_t. This code replication reflects the
insufficient degree of decoupling of the libraries components. Not
only is the code bloated by this. Also conditional expressions that
are computable at compile time seem to be checked redundantly at
runtime many times unless compilers are smart enough to optimize them
away. But even if they do, as a developer I desire to write more
elegant code in the first place and I try to use code replication as a
guidepost to detect design flaws.

template<BOOST_XINT_CLASS_APARAMS>
integer_t<BOOST_XINT_APARAMS>& integer_t<BOOST_XINT_APARAMS>
    ::some_xint_fun (const
    integer_t<BOOST_XINT_APARAMS> b)
{
    if (Nothrow) {
        if (b.is_nan())
            data.make_nan();
        if (!is_nan()) {
            BOOST_XINT_TRY {
                some_xint_fun(data, b.data);//#1
                if (Threadsafe == true)
                    data.make_unique();
            } BOOST_XINT_CATCH {
                data.make_nan();
            }
        }
    } else {
        some_xint_fun(data, b.data);//#2
        if (Threadsafe == true)
            data.make_unique();
    }
    return *this;
}

This skeleton (and some variations of it) occurs over and over again
only to propagate the call of the function to the implementing class
at positions #1 and #2.

3.2 Implementation issues
=========================

3.2.1 Operator template overloading conflicts
=============================================

In integer.hpp 2399 and 2426, there are template macros with an
unrestricted template parameter 'typename N' in

template <typename N, BOOST_XINT_CLASS_APARAMS>

this leads to ambiguities in overload resolution with other types that
allow to combine values via operator o.

icl::interval_set<xint::integer> xi_set;
xint::integer xi;
xi_set + xi; // Adds a single value

Compilers say things like:
constructor overload resolution was ambiguous.

3.2.2 Specialization of std::numerical_limits fails
===================================================

When used with other Boost libraries, namely Boost.Rational and
Boost.Icl metacode using std::numeric_limits fails:

BOOST_AUTO_TEST_CASE(xint_and_rational)
{
  rational<xint::integer> xrat;
  //error C2975: 'x' : invalid template argument for
  //'boost::STATIC_ASSERTION_FAILURE'
  //boost/rational.hpp (127)
  //BOOST_STATIC_ASSERT( ::std::numeric_limits<IntType>::is_specialized );
  //Although is_specialized is defined in integer.hpp(2605)
}

I used msvc-9. I looks as if the compiler fails to recognize the code

template<BOOST_XINT_CLASS_APARAMS>
const bool numeric_limits<boost::xint::integer_t<BOOST_XINT_APARAMS> >::
    is_specialized = true;

as proper compile time constant. When assigned directly with the
declaration, it works.

xint/integer.h (2543)
static const bool is_specialized = true;

Unfortunately a similar problem occurs with numeric_limits<T>::digits

//--------------------------------------------------------------
//Problems with constants from std::numeric_limits
template <class Type> struct test_is_fixed_numeric
{
    typedef test_is_fixed_numeric type;
    BOOST_STATIC_CONSTANT(bool,
        value = (0 < std::numeric_limits<Type>::digits));
    //rev_xint.cpp(49) : error C2057: expected constant expression
};

BOOST_AUTO_TEST_CASE(xint_std_numeric_limits)
{
    typedef xint::integer_t<options::fixedlength<8> > fixn8;
    BOOST_CHECK_EQUAL(test_is_fixed_numeric<fixn8>::value, true);
}
//--------------------------------------------------------------

3.2.3 Specialization of boost::is_integral<T>
=============================================

You'd have to provide an instantiation of boost type trait
boost::is_integral for xint::integral_t, so meta code that is
implemented for all intergal types will be able to work with xint
instantly.

-- 
Interval Container Library [Boost.Icl]
http://www.joachim-faulhaber.de