104

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?

Rapptz
  • 20,807
  • 5
  • 72
  • 86
Rayniery
  • 1,557
  • 2
  • 12
  • 17
  • 2
    [The constraints proposal](http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3580.pdf) goes into this. – chris Mar 27 '13 at 21:12
  • I was recalling **4.8 Designing Concepts**, but there actually isn't much listed in the way of how concepts further constraints. If anything, Googling concepts now might reveal some easily-spottable differences after gaining a better understanding of constraints from the proposal. – chris Mar 27 '13 at 22:59
  • IMHO concepts improve readability and provide clearer programmatic abilities as requested long ago by the likes of Alexander Stepanov in 'Elements of Programming'. The lite proposal is just a move towards this to ease the burden of weird enable_if type constraints that are required at the moment. The sooner the better for generic programming. – dirvine Mar 27 '13 at 23:04

3 Answers3

141

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.

Joseph Mansfield
  • 108,238
  • 20
  • 242
  • 324
  • 5
    It should be noted that concepts-lite doesn't check the constraints against the implementation of the template itself. So you could claim that any DefaultConstructable can be used, but the compiler won't stop you from using a copy constructor by accident. A more fully-featured concepts proposal would. – Nicol Bolas Mar 27 '13 at 23:18
  • @NicolBolas I'm planning to add more and that will go somewhere. Thanks. I thought I'd throw this out for a first draft. – Joseph Mansfield Mar 27 '13 at 23:18
  • 24
    *That* is a *first draft?!* – Nicol Bolas Mar 27 '13 at 23:28
  • 2
    @sftrabbit, very good answer. But I have a question: how a compiler will check that a type fulfills the semantic requirements of a concept? – Rayniery Mar 27 '13 at 23:44
  • @Rayniery In the latest concepts design, the compiler will only check the constraint requirements and not the axioms. In previous designs, concept maps were used to map types to concepts. You would have had to have specified explicitly that your type meets the requirements of a certain concept. – Joseph Mansfield Mar 28 '13 at 00:00
  • 1
    Will (w/ a lot of uncertainty) the 'axioms' be checked during run-time, or they will only serve as kind of promise tags? – Red XIII Mar 29 '13 at 13:31
  • @RedXIII Under the latest design, they just won't be checked. Most axioms cannot possibly be checked. To quote the design: "All concepts in the library are automatically checked. Implementing a concept library that requires users to write explicit concept maps would require us to do so for every data structure tested. That approach is not needed for the STL and, in our opinion, does not scale well. Axioms are not (and cannot be) checked by the compiler so for our validation we treat them as comments." – Joseph Mansfield Mar 29 '13 at 16:31
  • 1
    What is the reasoning behind the inability to check the axioms ? – ScarletAmaranth Jun 07 '13 at 22:24
  • 4
    @ScarletAmaranth: Because it boils down to automatically proving a theorem in finite bounded time. There are two obstacle to this: 1. Proving any theorem in finite bounded time which is extremely hard in theory, and impossible with current technology. 2. You can't prove an axiom, unless the proof is based on other axioms. (In which case it mathematically becomes "not an axiom") These axioms are intended to tell the compiler "Of course you can reverse the comparison if you deem it useful...", or "Yes, an EmptySet used in an intersection always gives the same result." – Laurent LA RIZZA Jun 26 '13 at 07:31
  • 1
    Even without checking that types match them, axioms could be powerful: if the compiler can assume the axiom holds, it can replace a `<` with a !`>=`, or a code that runs if `<` or `==` is true with a `<=` check. In short, you could pull off the kind of optimizations you can do with known-to-compiler types like `int` without the compiler having to prove each optimization is valid... – Yakk - Adam Nevraumont Jul 25 '13 at 20:12
  • Any updates on what's been included in C++14 or decidedly removed from consideration? – Kerrek SB Oct 19 '13 at 19:35
  • @KerrekSB I unfortunately don't have much time at the moment to keep up to date with it or post on SO, so I've made the post a community wiki. Hopefully people will feel more inclined to help keep it up to date. – Joseph Mansfield Oct 22 '13 at 09:24
  • Does it now state that concepts-lite checks the definition of the template itself, as the real concepts would have done? I think that's way too important to miss in such an answer with that many upvotes. – Johannes Schaub - litb Dec 28 '13 at 15:47
  • @JohannesSchaub-litb Concepts lite is in a bit of messy state where the use of "concepts" and "constraints" is not particular clear, so I'm putting off updating this answer for a short while. However, I don't think what you're suggesting will be part of concepts-lite. The proposal specifically says "Finally, constraints do not constrain template definitions. That is, the modular type checking of template definitions is not supported by template constraints. We expect this feature to be a part of a final design for concepts." – Joseph Mansfield Dec 29 '13 at 18:38
22

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 .

Herb Sutter
  • 1,888
  • 1
  • 14
  • 14
4

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

Sumant
  • 4,286
  • 1
  • 23
  • 31