What are the differences between concepts and template constraints?

I want to know what are the semantic differences between the C++ full concepts proposal and template constraints (for instance, constraints as appeared in Dlang or the new concepts-lite proposal for C++1y).

What are full-fledged concepts capable of doing than template constraints cannot do?

> The following information is out of date. It needs to be updated according to the latest Concepts Lite draft.

Section 3 of the constraints proposal covers this in reasonable depth.

The concepts proposal has been put on the back burners for a short while in the hope that constraints (i.e. concepts-lite) can be fleshed out and implemented in a shorter time scale, currently aiming for at least something in C++14. The constraints proposal is designed to act as a smooth transition to a later definition of concepts. Constraints are part of the concepts proposal and are a necessary building block in its definition.

In Design of Concept Libraries for C++, Sutton and Stroustrup consider the following relationship:

> Concepts = Constraints + Axioms

To quickly summarise their meanings:

1. Constraint - A predicate over statically evaluable properties of a type. Purely syntactic requirements. Not a domain abstraction.
2. Axioms - Semantic requirements of types that are assumed to be true. Not statically checked.
3. Concepts - General, abstract requirements of algorithms on their arguments. Defined in terms of constraints and axioms.

So if you add axioms (semantic properties) to constraints (syntactic properties), you get concepts.

---

Concepts-Lite

The concepts-lite proposal brings us only the first part, constraints, but this is an important and necessary step towards fully-fledged concepts.

Constraints

Constraints are all about syntax. They give us a way of statically discerning properties of a type at compile-time, so that we can restrict the types used as template arguments based on their syntactic properties. In the current proposal for constraints, they are expressed with a subset of propositional calculus using logical connectives like && and ||.

Let's take a look at a constraint in action:

template <typename Cont>
  requires Sortable<Cont>()
void sort(Cont& container);

Here we are defining a function template called sort. The new addition is the requires clause. The requires clause gives some constraints over the template arguments for this function. In particular, this constraint says that the type Cont must be a Sortable type. A neat thing is that it can be written in a more concise form as:

template <Sortable Cont>
void sort(Cont& container);

Now if you attempt to pass anything that is not considered Sortable to this function, you'll get a nice error that immediately tells you that the type deduced for T is not a Sortable type. If you had done this in C++11, you'd have had some horrible error thrown from inside the sort function that makes no sense to anybody.

Constraints predicates are very similar to type traits. They take some template argument type and give you some information about it. Constraints attempt to answer the following kinds of questions about type:

1. Does this type have such-and-such operator overloaded?
2. Can these types be used as operands to this operator?
3. Does this type have such-and-such trait?
4. Is this constant expression equal to that? (for non-type template arguments)
5. Does this type have a function called yada-yada that returns that type?
6. Does this type meet all the syntactic requirements to be used as that?

However, constraints are not meant to replace type traits. Instead, they will work hand in hand. Some type traits can now be defined in terms of concepts and some concepts in terms of type traits.

Examples

So the important thing about constraints is that they do not care about semantics one iota. Some good examples of constraints are:

• Equality_comparable<T>: Checks whether the type has == with both operands of that same type.

• Equality_comparable<T,U>: Checks whether there is a == with left and right operands of the given types

• Arithmetic<T>: Checks whether the type is an arithmetic type.

• Floating_point<T>: Checks whether the type is a floating point type.

• Input_iterator<T>: Checks whether the type supports the syntactic operations that an input iterator must support.

• Same<T,U>: Checks whether the given type are the same.

You can try all this out with a special concepts-lite build of GCC.

---

Beyond Concepts-Lite

Now we get into everything beyond the concepts-lite proposal. This is even more futuristic than the future itself. Everything from here on out is likely to change quite a bit.

Axioms

Axioms are all about semantics. They specify relationships, invariants, complexity guarantees, and other such things. Let's look at an example.

While the Equality_comparable<T,U> constraint will tell you that there is an operator== that takes types T and U, it doesn't tell you what that operation means. For that, we will have the axiom Equivalence_relation. This axiom says that when objects of these two types are compared with operator== giving true, these objects are equivalent. This might seem redundant, but it's certainly not. You could easily define an operator== that instead behaved like an operator<. You'd be evil to do that, but you could.

Another example is a Greater axiom. It's all well and good to say two objects of type T can be compared with > and < operators, but what do they mean? The Greater axiom says that iff x is greater then y, then y is less than x. The proposed specification such an axiom looks like:

template<typename T>
axiom Greater(T x, T y) {
  (x>y) == (y<x);
}

So axioms answer the following types of questions:

1. Do these two operators have this relationship with each other?
2. Does this operator for such-and-such type mean this?
3. Does this operation on that type have this complexity?
4. Does this result of that operator imply that this is true?

That is, they are concerned entirely with the semantics of types and operations on those types. These things cannot be statically checked. If this needs to be checked, a type must in some way proclaim that it adheres to these semantics.

Examples

Here are some common examples of axioms:

• Equivalence_relation: If two objects compare ==, they are equivalent.

• Greater: Whenever x > y, then y < x.

• Less_equal: Whenever x <= y, then !(y < x).

• Copy_equality: For x and y of type T: if x == y, a new object of the same type created by copy construction T{x} == y and still x == y (that is, it is non-destructive).

Concepts

Now concepts are very easy to define; they are simply the combination of constraints and axioms. They provide an abstract requirement over the syntax and semantics of a type.

As an example, consider the following Ordered concept:

concept Ordered<Regular T> {
  requires constraint Less<T>;
  requires axiom Strict_total_order<less<T>, T>;
  requires axiom Greater<T>;
  requires axiom Less_equal<T>;
  requires axiom Greater_equal<T>;
}

First note that for the template type T to be Ordered, it must also meet the requirements of the Regular concept. The Regular concept is a very basic requirements that the type is well-behaved - it can be constructed, destroyed, copied and compared.

In addition to those requirements, the Ordered requires that T meet one constraint and four axioms:

• Constraint: An Ordered type must have an operator<. This is statically checked so it must exist.
• Axioms: For x and y of type T:
  • x < y gives a strict total ordering.
  • When x is greater than y, y is less than x, and vice versa.
  • When x is less than or equal to y, y is not less than x, and vice versa.
  • When x is greater than or equal to y, y is not greater than x, and vice versa.

Combining constraints and axioms like this gives you concepts. They define the syntactic and semantic requirements for abstract types for use with algorithms. Algorithms currently have to assume that the types used will support certain operations and express certain semantics. With concepts, we'll be able to ensure that requirements are met.

In the latest concepts design, the compiler will only check that the syntactic requirements of a concept are fulfilled by the template argument. The axioms are left unchecked. Since axioms denote semantics that are not statically evaluable (or often impossible to check entirely), the author of a type would have to explicitly state that their type meets all the requirements of a concept. This was known as concept mapping in previous designs but has since been removed.

Examples

Here are some examples of concepts:

• Regular types are constructable, destructable, copyable, and can be compared.

• Ordered types support operator<, and have a strict total ordering and other ordering semantics.

• Copyable types are copy constructable, destructable, and if x is equal to y and x is copied, the copy will also compare equal to y.

• Iterator types must have associated types value_type, reference, difference_type, and iterator_category which themselves must meet certain concepts. They must also support operator++ and be dereferenceable.

The Road to Concepts

Constraints are the first step towards a full concepts feature of C++. They are a very important step, because they provide the statically enforceable requirements of types so that we can write much cleaner template functions and classes. Now we can avoid some of the difficulties and ugliness of std::enable_if and its metaprogramming friends.

However, there are a number of things that the constraints proposal does not do:

1. It does not provide a concept definition language.

2. Constraints are not concept maps. The user does not need to specifically annotate their types as meeting certain constraints. They are statically checked used simple compile-time language features.

3. The implementations of templates are not constrained by the constraints on their template arguments. That is, if your function template does anything with an object of constrained type that it shouldn't do, the compiler has no way to diagnose that. A fully featured concepts proposal would be able to do this.

The constraints proposal has been designed specifically so that a full concepts proposal can be introduced on top of it. With any luck, that transition should be a fairly smooth ride. The concepts group are looking to introduce constraints for C++14 (or in a technical report soon after), while full concepts might start to emerge sometime around C++17.

See also "what's 'lite' about concepts lite" in section 2.3 of the recent (March 12) Concepts telecon minutes and record of discussion, which were posted the same day here: http://isocpp.org/blog/2013/03/new-paper-n3576-sg8-concepts-teleconference-minutes-2013-03-12-herb-sutter .

My 2 cents:

1. The concepts-lite proposal is not meant to do "type checking" of template implementation. I.e., Concepts-lite will ensure (notionally) interface compatibility at the template instantiation site. Quoting from the paper: "concepts lite is an extension of C++ that allows the use of predicates to constrain template arguments". And that's it. It does not say that template body will be checked (in isolation) against the predicates. That probably means there is no first-class notion of archtypes when you are talking about concepts-lite. archtypes, if I remember correctly, in concepts-heavy proposal are types that offer no less and no more to satisfy the implementation of the template.

2. concepts-lite use glorified constexpr functions with a bit of syntax trick supported by the compiler. No changes in the lookup rules.

3. Programmers are not required to write concepts maps.

4. Finally, quoting again "The constraints proposal does not directly address the specification or use of semantics; it is targeted only at checking syntax." That would mean axioms are not within the scope (so far).