Entries:
Comments:
Posts:

Loading User Information from Channel 9

Something went wrong getting user information from Channel 9

Latest Achievement:

Loading User Information from MSDN

Something went wrong getting user information from MSDN

Visual Studio Achievements

Latest Achievement:

Loading Visual Studio Achievements

Something went wrong getting the Visual Studio Achievements

A Concept Design for C++

Download

Right click “Save as…”

Slides (view online)

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

Follow the Discussion

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

  • CharlesCharles Welcome Change

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

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

    C

  • David IDavid 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.

  • David IDavid 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)

  • AlgocodersAlgocoders

    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

  • AlgocodersAlgocoders

    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/

Remove this comment

Remove this thread

close

Comments Closed

Comments have been closed since this content was published more than 30 days ago, but if you'd like to continue the conversation, please create a new thread in our Forums,
or Contact Us and let us know.