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

From: David Abrahams (dave_at_[hidden])
Date: 2004-09-14 08:04:00

Terje Slettebø <tslettebo_at_[hidden]> writes:

> 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)
> {
>   // ...
> }

enable_if doesn't always improve error messages.  Sometimes you get a
long list of candidate functions when what you really wanted was a
message from inside just one of the overloads that indicates how
concept conformance was violated.

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

Isn't that what we've already been discussing in
http://news.gmane.org/find-root.php?message_id=%3cchr3k4%241b1%241%40sea.gmane.org%3e
(http://tinyurl.com/4fx3u) ?

> 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:
>
<snip real concepts>

Real concepts have the advantage of being able to dispatch to the
"most-refined" overload.

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

Things have changed quite a bit since the last release of MPL.  Are
you sure you're up-to-date?

> - 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.
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>

-- 
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com