A Concept Design for C++

Download this episode

Download Video

Description

C++ does not provide facilities for directly expressing what a function template requires of its set of parameters. This is a problem that manifests itself as poor error messages, obscure bugs, lack of proper overloading, poor specification of interfaces, and maintenance problems.

Many have tried to remedy this (in many languages) by adding sets of requirements, commonly known as "concepts." Many of these efforts, notably the C++0x concept design, have run into trouble by focusing on the design of language features.

This talk presents the results of an effort to first focus on the design of concepts and their use; Only secondarily, we look at the design of language features to support the resulting concepts. We describe the problem, our approach to a solution, give examples of concepts for the STL algorithms and containers, and finally show an initial design of language features. We also show how we use a library implementation to test our design.

So far, this effort has involved more than a dozen people, including the father of the STL, Alex Stepanov, but we still consider it research in progress rather than a final design. This design has far fewer concepts than the C++0x design and far simpler language support. The design is mathematically well founded and contains extensive semantic specifications (axioms).

Tags:

C++11, C++

Day:

2

Level:

400

Embed

Format

Available formats for this video:

Actual format may change based on video formats available and browser capability.

    The Discussion

    • User profile image
      Gregory81

      Great stuff. I'm only little worried that they have both axioms and automatic concept derivation. Trying to deduce semantic requirements from syntax seems like a bad idea. 

    • User profile image
      Charles

      Here's a link to the research paper referenced in this excellent talk:

      http://www2.research.att.com/~bs/sle2011-concepts.pdf

      C

    • User profile image
      David I

      I really love the ultimate goal that concepts try to address. The goal of being more explicit about what we expect from the code can go a lot way in making templates easier to understand and use correctly (a common source of frustration among my co-workers).

      Where I think it becomes a bit difficult to cope with (ex: try to explain to my co-workers) is when we start composing a lot of very primitive concepts as Mr. Stroustrup addressed. It can lead to quite an explosion of concepts when we're composing them from concepts as primitive as "Assignable", "Copyable", "LessThanComparable", or combinations of those.

      I actually think if the goal was a bit more modest by eliminating the 'requires' keyword and just sticking to the basic form that does not allow concepts to be composed:

      template <InputIterator Iterator, class Value>
      InputIterator find(InputIterator first, InputIterator last, const Value& val)
      {
      ...
      }

      Note that I did not even attempt to define a concept for Value here because I haven't come up with a good concept or name for that yet (EqualComparable?), and I think that's fine. We solved at least part of the problem and better defined the iterator argument's requirements and this solution can grow over time.

      I really think something like this might have a better chance of being adopted and slowly flourish as it's not an all-or-nothing kind of approach. It can be applied in the areas where the concepts being applied will very concisely apply the necessary constraints (i.e., without the need for composing numerous concepts).

      I think the main problem with concepts was that it was too grand in scope. Initially it appeared to be affecting every aspect of how the STL was described by the standard. If it's treated more like an optional feature to gradually work our way towards better expressing the intentions of the code -- something applied only in the areas where it very clearly and concisely expresses intent with higher-level concepts that have already very clearly been established (InputIterator, BidirectionalIterator, Number, etc.), I think that would be a perfectly fine start. It doesn't have to solve everything in the beginning.

    • User profile image
      David I

      Apologies,

      template <InputIterator Iterator, class Value>
      InputIterator find(InputIterator first, InputIterator last)

      ... should actually read as:

      template <InputIterator Iterator, class Value>
      Iterator find(Iterator first, Iterator last)

    • User profile image
      Algocoders

      This is really fantastic!

      Where do we get to see the concepts getting implemented strictly using C++11 language and library features? We will prefer a simple library to start using it right away.

      We were referring to the famous paper "A Concept Design for the STL" by Dr. Bjarne Stroustrup et al., which inspired us to dive into Origin C++ Libraries, which is an implementation using C++11. We ended up collating the ideas with our experiments to put these into work in our book : "Foundation of Algorithms in C++11, Volume 1 : Using And Extending C++11, Boost And Beyond". But to go further, we need a complete set-up for C++11 concepts and Origin libraries are still very incomplete and experimental in nature.Can someone point to a library, which is put to practice? Any pointer will be very helpful.

      To be clear, we do not mean "C++ Concepts & Axioms" which (as originally proposed) cannot be fully implemented as a library feature.


      For example, the paper "A Concept Design of STL" proposes the following interface for the STL Algorithm "std::copy_backward":

      template<BidirectionalIterator I, BidirectionalIterator Out>
      requires IndirectlyCopyable<I, Out> Out copy_backward(I first, I last, Out result);



      which cannot be implemented using just library features.

      So we reduced it to look like the following :


      template<typename I, typename I>
      requires<IndirectlyCopyable<I, Out>() && Bidirectional_Iterator<I>()>
      Out copy_backward(I first, I last, Out result);



      This we were able to get it easily using sfinae feature : enable_if. But we are looking for something like this in a form of a full blown C++11 library.


      Using template alias and sfinae, simulation of requires may look like :

      #include <type_traits>
      template <bool Condition, typename T = void>
      using requires = typename std::enable_if<Condition, T>::type;



      And the Conditions being passed to requires can be simulated using the language feature "constexpr" like:

      template <typename I, typename Out>
      constexpr bool IndirectlyCopyable() { ...}

      template <typename I>
      constexpr bool Bidirectional_Iterator() { ...}



      So, all we are looking for a C++11 library, which fully implement C++11 Algorithms using Concepts as part of algorithm's interface as in :


      template<typename I, typename I>
      requires<IndirectlyCopyable<I, Out>() && Bidirectional_Iterator<I>()>
      Out copy_backward(I first, I last, Out result);



      or

      template<typename I, typename I>
      auto copy_backward(I first, I last, Out result)
      -> requires<IndirectlyCopyable<I, Out>() && Bidirectional_Iterator<I>(), Out>;



      or something similar. Origin C++ library has similar components in place, but it is still a work in progress. Boost.Contract(Contract++) takes a different approach to simulate the above.

      Does any one know of any such library in use?

      Thanks a lot in advance.

      Cheers,
      Algocoders
      http://www.algocoders.com

    • User profile image
      Algocoders

      Our work on concept design using C++11 can be seen in Part III of our C++11 Cookbook: "Foundation of Algorithms in C++11, Volume 1(Revised Edition): Using and Extending C++11, Boost And Beyond" is available @amazon:
      http://www.amazon.com/Foundation-Algorithms-Volume-Revised-Edition/dp/1481965549/

    Comments closed

    Comments have been closed since this content was published more than 30 days ago, but if you'd like to send us feedback you can Contact Us.