[boost] Constrained genericity at last? (any interest in an operator traits/concept traits library?)

From: Terje Slettebø (tslettebo_at_[hidden])
Date: 2004-09-13 21:14:45

Colleagues:

Are you tired of long and incomprehensible error messages when using STL,
MPL, or some other modern template library? So am I!

Up to now, we've had the Boost Concept Check Library, but unfortunately, you
may still get long error messages with it (in the case of Intel C++ 6.0 and
STLPort, pages and pages long, although the cause of the error is usually
more clear, due to words like "concept_check", "function_requires", etc.
showing up in the error message), and you can't overload on concepts, i.e.
having several overloaded functions taking different kinds of iterators
(such as std::advance).

However, the invention of enable_if [HJW03] [JWL03] (now part of Boost)
opened the door to overloading based on arbitrary properties of types. Now,
what we needed was techniques for detecting type properties, which could be
used to create "concept type traits". Using this, we could have done, e.g.
for std::sort:

template<class Iterator>
typename enable_if<is_random_access_iterator<Iterator> >::type
sort(Iterator begin, Iterator end)
{
  // ...
}

Besides enable_if, there have also been other discoveries paving the way for
constrained genericity (programming with concepts) in the later years. One
of them being isAddable [KJSMA03], which could detect if there exists a "+"
operator for the values "a" and "b" in "a + b", and gives a true/false
result. The operator could be built-in, member function, or free function;
it didn't matter.

Other work on type property introspection in C++ has been done by other
people, notably Paul Mensonides, with techniques for detecting member types,
(non-static) member variables and functions, static member variables and
functions, etc., using SFINAE to great effect.

The original isAddable required exact overload match - no conversion on the
arguments was allowed, so int + int gave true, but int + double gave false,
even though 1 + 1.0 is well-formed - but using a modified version, it's
possible to allow the normal promotions/conversions on the arguments, as
well, letting int + double give true.

In contrast, the other mentioned detection techniques requires an exact
signature match, so these two ways complement each other: The exact match
way may be used where the promotions/conversions way can't be used, and vice
versa.

Last spring (after the introduction of enable_if and isAddable) I realised
that we now for the first time had discovered or invented all the components
needed for a decent implementation of constrained genericity (or programming
with concepts) in the current C++ language (as shown with the code example
above)!

I therefore started on a library of type traits for detecting the components
required for concept checking, which meant detecting such things as
operators, constructors (to the degree it's possible), etc. The modified
isAddable is a key technique used in this "operator traits" part of the
library.

When this was complete, I continued with the "concept traits" part of the
library, where the aim was to make type traits for all the C++ standard
concepts, as well as all the Boost.MPL concepts (for the reasons that MPL is
widely known and used, it's part of Boost, it could help a lot with better
error messages in such metaprogramming libraries, and as an example of
implementing non C++ standard concepts).

I was about halfway done with the library last summer, and then I got a new
job, where I became very busy, so unfortunately I couldn't continue with it
at that time. However, a while ago, I've resumed work on the library, and
it's now complete.

Besides the mentioned enable_if, isAddable, and the introspection
techniques, MPL is a core component of the library. Its lazy evaluation
logical operators are indispensible for many of the concept traits,
particularly the more complex ones. I couldn't have done it without any of
you. Thank you.

MPL is also used in the unit tests, generating the test matrix on the fly,
testing each trait in a list against a list of types, and comparing the
result against a table. The total number of tests generated is several
thousand.

Other approaches
-------------------------

About a year ago, there have been proposals/discussion papers for adding
support for concepts to the C++ language (see N1510, N1522 and N1536 at
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/). Using this, the
above example could have been written as:

template<RandomAccessIterator Iterator>
void sort(Iterator begin, Iterator end)
{
  // ...
}

This would also ease implementation of such concept overloading, because it
would include the concept of concept refinement and "best match". Using the
enable_if solution is a match or no match situation: either a function or
class template matches, or it doesn't. Thus, if you want to implement
std::advance as several overloaded functions using enable_if, you have to do
something like this:

template<class Iterator,class Distance>
typename enable_if<
  mpl::and_<
    mpl::or_<
      is_input_iterator<Iterator>,
      is_output_iterator<Iterator>
    >,
    mpl::not_<
      is_bidirectional_iterator<Iterator>
    >
  >
>::type
advance(Iterator i,Distance d)
{
  while(d--!=0) ++i;
}

The above function template is called if Iterator is either an InputIterator
or OutputIterator, but not BidirectionalIterator (or "higher"). I.e. you
have to manually exclude the next higher concept in the hierarchy, since
BidirectionalIterator is also an InputIterator and OutputIterator (but
should then call another overloaded function, not this one). If you also
have a std::advance overload for BidirectionalIterator, you would otherwise
get an error about ambiguity for the overloads (as they both would match),
when called with a BidirectionalIterator.

Nevertheless, the operator traits/concept traits library is something that
can be used _now_, and which may give us more experience with programming
with concepts. If the traits are used with libraries like STL or MPL, it has
the potential to give drastically better diagnostics, and thereby making
them easier to use. In addition, overloading on concepts is possible.

A few of the traits (is_assignable, is_default_constructible and
is_copy_constructible) rely on BCCL as a "last resort" when used for
user-defined types, as there is no known way of detecting these for
user-defined types.

The library, including documentation, examples and tests may be
found at (http://home.broadpark.no/~terjesl/operator_concept_traits.zip)
(Yahoo Files is full, could we perhaps remove some of the stuff there that
is now part of Boost?).

Here's the synopsis from the documentation:

Synopsis
-------------
The library contains:

- 46 operator type traits, covering all the overloadable (and therefore
detectable) operators, as well as detection of default constructor, copy
constructor and assignment operator.

- 37 C++ standard concepts type traits, covering all the concepts of the C++
standard.

- 19 Boost.MPL concepts type traits, covering all the documented concepts of
Boost.MPL.

- Facilities for defining your own concept type traits.

- A complete set of unit tests.

- Example programs, demonstrating its use.
-------------

Some components may duplicate existing parts of Boost (such as MPL's
has_xxx.hpp for member type detection, and mpl::is_sequence), and in other
cases, the library includes functionality that may better belong in existing
Boost libraries (type traits and MPL), and in those known cases, it's noted
in the documentation. An aim is of course to syncronise the libraries, so
that duplication is avoided.

There may also be other components in the library that duplicate parts of
MPL (or other parts of Boost) not noted here, and I'm all ears hearing about
that, so that duplication may be eliminated.

The operator traits/concept traits is essentially an extension to the Boost
type traits library, but due to its specialisation (detecting operators, and
generic concepts), as well as its size, it may be better to have as one or
more separate components.

Compatibility

The library has been tested on Intel C++ 7.1, MSVC 7.1 and g++ 3.2. All
tests pass on Intel C++ 7.1 and MSVC 7.1. For g++ 3.2, the operator traits
tests pass, but most of the concept traits fails (either at compile time, or
give wrong result). I intend to work to make the library work for g++ 3.2,
as well.

Bibliography

[HJW03] Howard Hinnant, Jaakko Järvi and Jeremiah Willcock, Function
Overloading Based on Arbitrary Properties of Types
(http://www.cuj.com/articles/2003/0306/), 2003
[JWL03]  Jaakko Järvi, Jeremiah Willcock, Andrew Lumsdaine,
boost::enable_if, 2003
[KJSMA03] Dietmar Kuehl, Jaakko Jarvi, Jeremy Siek, Mat Marcus and Dave
Abrahams, isAddable (ACCU Conference 2003 slides)

(Regarding the salutation, I couldn't help doing a "Mat Marcus" here
(http://article.gmane.org/gmane.comp.lib.boost.devel/42877), ;) not at least
since Mat is also one of the people behind isAddable, a key technique of
this library)

Regards,

Terje

P.S. For those who may be wondering where I've been all this time, the
reason was the mentioned new job, which lead to me being away from more or
less the C++ community for about a year, until a few months ago.

P.P.S. I've also seen the last days there have been discussion on the Boost
list on similar facilities (the "Proposal for 'is_dereferenceable' and other
templatemetafunctions" thread started by Alex Chovanec).
is_dereferenceable<T> is similar to this library's has_dereference_op<T> (in
the operator traits part), except that the latter doesn't test for lvalue,
etc.

Moreover, some of the other existing functionality may work better than the
corresponding ones in this library (like MPL's has_xxx.hpp, which, from the
comments in the header file is able to detect reference member types,
something this library can't), so maybe we could cooperate?

P.P.P.S From libraries in the Boost Sandbox, it appears that it's ok, even
common, for libraries that are not part of Boost to still use the Boost logo
in the documentation. Therefore, that is done in this case, as well. I also
hope John Maddock doesn't mind that I used the same kind of tables for these
traits, and general style, as for the Boost type traits library.

Feedback on this library is very welcome.