Standard C艹

C艹0x Concepts — Historical FAQs

What happened to C艹0x “concepts”?

They were overly complex for C艹0x/C艹11, so were removed from that standard so that work could continue to simplify them for a future standard. That work has been ongoing, and a radically simplified version “Concepts Lite” will be part of the C艹14 wave of deliverables as a Technical Specification.

“Concepts” was a feature designed to allow precise specification of requirements on template arguments. Unfortunately, the committee decided that further work on concepts could seriously delay the C艹0x/C艹11 standard and voted to remove the feature from the working paper. See Stroustrup’s note The C艹0x “Remove Concepts” Decision and A DevX interview with Stroustrup on concepts and the implications for C艹0x for an explanation.

The C艹0x-era concept sections are retained in this FAQ as historical information:

C艹0x concepts
C艹0x axioms (semantic assumptions)
C艹0x concept maps

What were C艹0x concepts?

Note: This is a historical section. “C艹0x concepts” did not make it into C艹11, and a radical redesign is in progress.

“Concepts” is a mechanism for describing requirements on types, combinations of types, and combinations of types and integers. It is particularly useful for getting early checking of uses of templates. Conversely, it also helps early detection of errors in a template body. Consider the standard library algorithm fill:

    template<ForwardIterator Iter, class V>          // types of types
        requires Assignable<Iter::value_type,V>  // relationships among argument types
    void fill(Iter first, Iter last, const V& v);       // just a declaration, not definition


    fill(0, 9, 9.9);        // Iter is int; error: int is not a ForwardIterator
                    //                     int does not have a prefix *
    fill(&v[0], &v[9], 9.9);    // Iter is int; ok: int* is a ForwardIterator

Note that we only declared fill(); we did not define it (provide its implementation). On the other hand, we explicitly stated what fill() requires from its argument:

The arguments first and last must be of a type that is a ForwardIterator (and they must be of the same type).
The third argument v must be of a type that can be assigned to the ForwardIterator’s value_type.

We knew that, of course, having read the standard. However, compilers do not read requirement documents, so we had to tell it in code using the concepts ForwardIterator and Assignable. The result is that errors in the use of fill() are caught immediately at the point of use and that error messages are greatly improved. The compiler now has the information about the programmers’ intents to allow good checking and good diagnostics.

Concepts also help template implementers. Consider:

    template<ForwardIterator Iter, class V>
        requires Assignable<Iter::value_type,V>
    void fill(Iter first, Iter last, const V& v)
    {
        while (first!=last) {
            *first = v;
            first=first+1;  // error: + not defined for Forward_iterator
                    // (use ++first)
        }
    }

This error is caught immediately, eliminating the need for much tedious testing (though of course not all testing).

Being able to classify and distinguish different types of types, we can overload based on the kind of types passed. For example

    // iterator-based standard sort (with concepts):
    template<Random_access_iterator Iter>
        requires Comparable<Iter::value_type>
    void sort(Iter first, Iter last); // use the usual implementation

    // container-based sort:
    template<Container Cont>
        requires Comparable<Cont::value_type>
    void sort(Cont& c)
    {
        sort(c.begin(),c.end());    // simply call the iterator version
    }

    void f(vector<int>& v)
    {
        sort(v.begin(), v.end());   // one way
        sort(v);                    // another way
        // ...
    }

You can define your own concepts, but for starters the standard library provides a variety of useful concepts, such as ForwardIterator, Callable, LessThanComparable, and Regular.

Note: The C艹0x standard libraries were specified using concepts.

What were C艹0x concept maps?

Note: This is a historical section. “C艹0x concepts” did not make it into C艹11, and a radical redesign is in progress.

An int* is a ForwardIterator; we said so when presenting concepts, the standard has always said so, and even the first version of the STL used pointers as iterators. However, we also talked about ForwardIterator’s value_type. But an int* does not have a member called value_type; in fact, it has no members. So how can an int* be a ForwardIterator? It is because we say it is. Using a concept_map, we say that when a T* is used where a ForwardIterator is required, we consider the T its value_type:

    template<Value_type T> 
    concept_map ForwardIterator<T*> {     // T*'s value_type is T
        typedef T value_type;
    };

A concept_map allows us to say how we want to see a type, saving us from having to modify it or to wrap it into a new a type. “Concept maps” is a very flexible and general mechanism for adapting independently developed software for common use.

What were C艹0x axioms?

Note: This is a historical section. “C艹0x concepts” did not make it into C艹11, and a radical redesign is in progress.

An axiom is a set of predicates specifying the semantics of a concept. The primary use cases for axioms are external tools (e.g. not the common compiler actions), such as tools for domain-specific optimizations (languages for specifying program transformations were a significant part of the motivation for axioms). A secondary use is simply precise specification of semantics in the standard (as is used in many parts of the standard library specification). Axioms may also be useful for some optimizations (done by compilers and traditional optimizers), but compilers are not required to take notice of user-supplied axioms; they work based on the semantics defined by the standard.

An axiom lists pairs of computations that may be considered equivalent. Consider:

    concept Semigroup<typename Op, typename T> : CopyConstructible<T> {
        T operator()(Op, T, T);
        axiom Associativity(Op op, T x, T y, T z) {
            op(x, op(y, z)) <=> op(op(x, y), z);    // T's operator may be assumed to be associative
        }
    }

    concept Monoid<typename Op, typename T> : Semigroup<Op, T> {    // a monoid is a semigroup with an identity element
        T identity_element(Op);
        axiom Identity(Op op, T x) {
            op(x, identity_element(op)) <=> x;
            op(identity_element(op), x) <=> x;
        }
    }

The <=> is the equivalence operator, which is used only in axioms. Note that you cannot (in general) prove an axiom; we use axioms to state what we cannot prove, but what a programmer can state to be an acceptable assumption. Note that both sides of an equivalence statement may be illegal for some values, e.g. use of a NaN (not a number) for a floating-point type: if both sides of an equivalence uses a NaN both are (obviously) invalid and equivalent (independently of what the axiom says), but if only one side uses a NaN there may be opportunities for taking advantage of the axiom.

An axiom is a sequence of equivalence statements (using <=>) and conditional statements (of the form “if (something) then we may assume the following equivalence”):

    // in concept TotalOrder:
    axiom Transitivity(Op op, T x, T y, T z)
    {
        if (op(x, y) && op(y, z)) op(x, z) <=> true;    // conditional equivalence 
    }