Re: [boost] Dynamic Bitset Formal Review June 8-17

From: Dan'l Miller (optikos_at_[hidden])
Date: 2002-06-11 23:25:31

  For those STL-related recipients who are joining this email reply already in progress, the original email is quoted at the end of this reply far below.  The boost_at_[hidden] address is an email distribution list & newsgroup to all Boost developers.  Sending email/newsgroup-posting to Boost developers via boost_at_[hidden] requires registration as a member of Boost at http://lists.boost.org/mailman/listinfo.cgi/boost.  General explanation of the Boost movement may be found at http://www.boost.org..

  [ FORMAL REVIEW OF DYNAMIC BITSET ]

  Allow me to start with a complement, the boost::dyn_bitset does an excellent job of taking compile-time-sized bitset as a reference and evolving its interface into a run-time-sized analogue.  Even the tougher issues such as operator = and the concept of a reference to a bit were addressed.  (Pun intended, I suppose.)

  But now on to my harsh concerns which lead me to a firm vote of: NO!  PLEASE DO NOT EVER ACCEPT THIS AS A LIBRARY IN BOOST.  PLEASE DO NOT EVER SUBMIT THIS LIBRARY FOR STANDARDIZATION IN C++0x.  BECAUSE OF THE FIVE SEVERE DEFECTS ENUMERATED BELOW, THE ONLY WAY THAT I SEE TO FIX boost::dyn_bitset IS TO WITHDRAW boost::dyn_bitset IN ITS ENTIRETY.  An already extant replacement strategy is interspersed below.

  [ DEFECT #1: design which diverges against SGI STL's bit_vector ]

  This boost::dyn_bitset class should not exist outside of a private-implementation Boost detail directory because it reinvents the wheel needlessly in compilers which do not support partial explicit specialization.  Instead use Alexander Stepanov's SGI STL's bit_vector if such a class template is desired.

  from http://www.sgi.com/tech/stl/bit_vector.html
  "A bit_vector is essentially a vector<bool>: it is a Sequence that has the same interface as vector. The main difference is that bit_vector is optimized for space efficiency. A vector always requires at least one byte per element, but a bit_vector only requires one bit per element."

  from http://www.sgi.com/tech/stl/bit_vector.html
"Warning: The name bit_vector will be removed in a future release of the STL. The only reason that bit_vector is a separate class, instead of a template specialization of vector<bool>, is that this would require partial specialization of templates. On compilers that support partial specialization, bit_vector is a specialization of vector<bool>. The name bit_vector is a typedef. This typedef is not defined in the C++ standard, and is retained only for backward
compatibility."

  from http://www.sgi.com/tech/stl/bitset.html
"Bitset is very similar to vector<bool> (also known as bit_vector): it contains a collection of bits, and provides constant-time access to each bit. There are two main differences between bitset and vector<bool>."

  These quotations together form a clear statement from the progenitors of STL that the intended run-time-sized efficiently-packed alternative to STL's bitset is SGI STL's explicit specialization of vector<bool>.

  When it comes to post-C++98 evolution of STL, the progenitor(s) of STL must be respected.  It is inappropriate to compete in any way with Alexander Stepanov for control of the post-C++98 evolution of STL.  Cease and desist pursuing a divergent boost::dyn_bitset approach which is outside of the intended direction of SGI STL which is the expression of the progenitors of STL regarding their intended post-C++98 evolution of STL.  I expect the authors of boost::dyn_bitset to withdraw boost::dyn_bitset as part of their public endorsement of SGI STL's explicit specialization of vector<bool>.

  [ DEFECT #2: design which diverges against SGI STL's vector<bool> explicit specialization ]

  This boost::dyn_bitset class should not exist outside of a private-implementation Boost detail directory because it reinvents yet another wheel needlessly in compilers which support partial explicit specialization.  Instead use an explicit specialization of SGI STL's vector<bool> as recommended by Alexander Stepanov at http://www.sgi.com/tech/stl/bit_vector.html.

  When it comes to post-C++98 evolution of STL, the progenitor(s) of STL must be respected.  It is inappropriate to compete in any way with Alexander Stepanov for control of the post-C++98 evolution of STL.  Cease and desist pursuing a divergent boost::dyn_bitset approach which is outside of the intended direction of SGI STL which is the expression of the progenitors of STL regarding their intended post-C++98 evolution of STL.  I expect the authors of boost::dyn_bitset to withdraw boost::dyn_bitset as part of their public endorsement of SGI STL's explicit specialization of vector<bool>.

  [ DEFECT #3: omission in design & vision ]

  The implication of expecting an explicit specialization of vector<bool> to satisfy the expectations of the concept of a run-time-sized bitset is that vector<bool> omits the bitwise arithmetic operators such as &=, |=, and ^=.  The divergent boost::dyn_bitset does not correct this deficiency of vector<bool>.  Instead of (re)inventing a whole new class named boost::dyn_bitset [a revolutionary approach], please design a way to extend an explicit specialization of vector<bool> to provide the bitwise arithmetic operators such as &=, |=, and ^= [an evolutionary approach].  Please work with Alexander Stepanov at SGI and Boris Fomitchev at STLport http://www.stlport.org to contribute to an even better SGI STL which can be submitted for C++0x standardization.

  Likewise boost::dyn_bitset omits vector<bool>'s iterators.

  Cease and desist pursuing a divergent boost::dyn_bitset approach which does not improve minor deficiencies within the SGI STL.  I expect the authors of boost::dyn_bitset to withdraw boost::dyn_bitset and instead contribute their efforts to the addition of the bitwise arithmetic operators such as &=, |=, and ^= to the SGI STL explicit specialization of vector<bool>.

  [ DEFECT #4: omission in documentation ]

  The libs/dyn_bitset/dyn_bitset.html file does not contain any explanation regarding why the SGI STL explicit specialization of vector<bool> was rejected.  Furthermore, it does not even mention anything whatsoever about vector<bool>, in either its automatic/naive specialization or its explicit specialization.  There is a passing see-also reference to vector which does not quench my thirst.

  [ DEFECT #5: lack of vision ]

  SGI STL is not yet part of Boost.  Boost's post-C++98 evolution of STL must be merged with SGI STL's post-C++98 evolution of STL.  This dyn_bitset was a prime opportunity for such merger.  Instead the opportunity was missed.  The window of opportunity has not yet closed.  SGI STL can become part of Boost.  Boost can endorse SGI STL or STLport as an external adjunct against which it won't compete.

  Because of the five aforementioned defects in the macrocosm, I have decided to not evaluate the implementation of boost::dyn_bitset in the microcosm.

  Because of the five aforementioned defects, this boost::dyn_bitset may be useful only as an implementation of an explicit specialization of vector<bool>.

  Because of the five aforementioned defects, I do not ever intend to use this library directly as a public API.  Instead I shall use SGI STL's explicit specialization of vector<bool> even if I must add the bitwise arithmetic operators such as &=, |=, and ^= myself.

  The effort which I expended on this review is limited to investigating boost::dyn_bitset's API & mission & documentation versus the API & mission & documentation of SGI STL's explicit specialization of vector<bool>.

  I consider myself very knowledgeable about the problem domain.  Indeed, essentially what I am asking for via these five defect reports in this review is for the authors of boost::dyn_bitset to become more knowledgeable about the problem domain and to become more compliant to the prior art in SGI STL regarding this problem domain.

  Dan'l Miller
  optikos_at_[hidden]

===============================================================================================
Subject: 
       [boost] Dynamic Bitset Formal Review June 8-17
   Date: 
       Sat, 08 Jun 2002 10:45:39 -0700
  From: 
       Mat Marcus <mmarcus_at_[hidden]>
    To: 
       boost_at_[hidden], boost-users_at_[hidden], boost-announce_at_[hidden]

> The formal review of Dynamic Bitset by Chuck Alison and Jeremy 
> Siek
> will commence today Saturday June 8th and run through Monday, 
> June 17th.
> 
> The library is currently available at
> <http://groups.yahoo.com/group/boost/files/dyn_bitset.tar.gz>
> 
> 
> Below is an excerpt from the library's documentation:
> 
>     The dyn_bitset class represents a set of bits. It provides
>     accesses to the value of individual bits via an operator[]
>     and provides all of the bitwise operators that one can
>     apply to builtin integers, such as operator&& and
>     operator<<. The number of bits in the set is specified at
>     runtime via a parameter to the constructor of the
>     dyn_bitset.
> 
>     Each bit represents either the Boolean value true (set) or
>     false (reset). To toggle a bit is to change the value to
>     true if it is false and to false if it is true. Each bit
>     has a non-negative position pos. The position pos == 0
>     corresponds to the least significant bit and pos == size()
>     - 1 is the most significant bit. When converting an
>     instance of dyn_bitset to or from an unsigned long, the bit
>     position pos corresponds to the bit value 1 << pos.
> 
>     The dyn_bitset class is nearly identical to the std::bitset
>     class. The difference is that the size of the dyn_bitset
>     (the number of bits) is specified at run-time during the
>     construction of a dyn_bitset object, whereas the size of a
>     std::bitset is specified at compile-time through an integer
>     template parameter.
> 
> 
> For information about submitting a Formal Review, see
> http://www.boost.org/more/formal_review_process.htm
> 
> Please try out the library and comment during the review 
> period. Be sure to say whether or not you think the library 
> should be accepted by Boost.
> 
> Compiler notes: This library has been tested using the 
> following compiler platforms:
> 
> Gcc 2.95 and 3.01
> Kai C++
> Metrowerks Codewarrior 8 (beta, Mac)
> Visual C++ 7.0
> Comeau
> 
> The library presently requires template friend support and is 
> known not to compile with CodeWarrior 7.2 or Visual C++ 6.0.
> 
> The library has not been tested with Borland.
> 
> 
> The Formal Review manager is Mat Marcus.
>