C++ concepts that wouldn’t be considered harmful

0. Background

Templates have been accepted in C++98  without concepts (although they were considered) because at that time no one saw any advantage of them. However, after some years of having long and bloated error messages when a template can’t be resolved, concepts now make sense. So lots of work was done to define such a feature for C++. The final form of concepts, implemented in an experimental ConceptGCC branch of gcc compiler, is quite well described on Wikipedia.

The works on this feature, as I can personally evaluate, were probably shifted to wrong direction, so it eventually got far away of the main goal. It’s much better that the concepts in this form have been removed from C++0x. But the problem still remains and has to be solved.

Bjarne Stroustrup enumerates several problems and misunderstandings concerning concepts, especially their latest version. It looks like the first idea of concepts has been only spoiled later. But it suffered also from one problem in the beginning: the syntax does not coincide with the syntax of templates, which makes concept a kind-of “alien” feature, not matching the rest of the language.

Because of that I have created my own proposal.

1. The basic syntax

A quick example: a template definition using a concept (that applies limitation on a type) would look like this – just like the original proposal:

template<class T>
requires LessThanComparable<T>
T min value(T x, T y) {
   return x < y? x : y;
}

and the LessThanComparable concept is defined this way:

concept<class T> LessThanComparable
{
    bool operator<( T, T );
};

Note similarity of the syntax between “template” and “concept”. Also similarly, if we want to provide this feature to a type that does logically the same as operator <, but with different name (a “concept map”), we’ll do:

concept<> LessThanComparable<std::type_info>
{
    bool operator<(const std::type_info& t1, const std::type_info& t2)
    { return t1.before( t2 ); }
};

Yes, this is also called “partial specialization”. Just like templates, concepts also may have (even partial) specializations (which functions like concept maps) and also can be instantiated (instantiation is required to “invoke” the match on a given type). Although their main use is to become a match for template entities that are expected to have particular features (concepts are always auto-applicable), additionally concepts have the following features:

  • can provide lacking features to types (“patch” a type)
  • can be derived (also multiply)
  • can be abstract (such a concept does not match anything)
  • can be bound in logical expressions
  • can be matched partially
  • can be used to synthesize a code template
  • can have multiple parameters, including variadic

The most general definition of concepts’ syntax is (names in .. are descriptive, fragments in ?{ … }? are optional):

concept<..parameters..> ..ConceptName.. ?{ <..specializationArgs..> }?
   ?{ : ..DerivedConcepts.., ... }?
?{ {
    ?{ ..specificStatements..; ... }?
    ?{ ..requirements..; ... }?
} }?
;

Where:

  • ConceptName: new concept’s name, if master definition, or existing concept name, if specialization
  • parameters: just like template parameters (no overloading or default parameters)
  • specializationArgs: arguments passed to the concept as specialization (just like in template partial specialization), used only when defining a specialization
  • DerivedConcepts: concepts that are prerequisites for the defined concept
  • requirements: definitions that should be available so that the concept can be meant satisfied: function/method definitions, requirement expressions, or requirements for elaborated types
  • specificStatements: just placeholder for future changes 🙂

The concept usage is:

1. When defining an entity template:

template<..args..>
requires|desires|constrains ..ConceptInstantiation.. , ...
..TemplatedEntity..

2. When requesting a code template synthesis:

// synthesize code in current scope as working on given type
requires ..ConceptInstantiation.. ;

// synthesize code in current scope with new type name
using ..NewTypeName.. = typename ..ConceptInstantiation..;

Where:

  • ConceptInstantiation:  an expression of ConceptName<args…>. Just a “requires” with this expression brings all type patches into all types for which any are provided by this concept, within the current scope
  • NewTypeName: a name of the type that is created by patching. The syntax using this should use only such concept that applies patches on only one type. The original type is then left untouched and the patched type is identified by this name.

New keywords: concept, requires, desires, constrains.

The definition of a requirement inside the concept must be in one of two forms:

  • interface element declaration (function, method, or type definition)
  • requirement expression (will be covered later)

The interface element declaration needs only to be provided in one of possible forms, however it’s only important that there is usually some way to call it. The real interface element may be defined different way, but still the way allowing it to be called with the same syntax. The following equivalences are allowed:

  • Type equivalence: real return type may be convertible to requested type and argument type of requested interface may be convertible to argument type of the real interface (when this is not desired, the type should be preceded by explicit)
  • An operator may be defined either as a method or as an external function
  • Non-explicit constructor A(B) requested in the concept is allowed to be satisfied by B::operator A() (again, use explicit modifier, if this is not desired)
  • A list of function or method parameters may be longer, with the excess parameters being default. Such a function is callable the same way as that mentioned in the requirements (again, use explicit modifier after the closing parenthesis of the function, if this is not desired – especially important if, for example, the function is required to have a strict signature due to being taken the address from)

The syntax like “template<LessThanComparable T>” is not possible because concepts must always be supplied with parameters where used – just like templates. Also, they can be used with more than just one parameter:

requires LessThanComparable<T>

requires Convertible<T, typename U::value_type>

requires TypeIsOneOf<T, int, char, bool>

There still is a simplified syntax for a concept with one parameter, but it’s specified in place of type, where it is used, not as a prefix in concept parameters. This will be covered later.

2. Special variants of the syntax

a. abstract concept and empty concept

The basic form of a concept is a pure abstract concept. Such a concept is never satisfied (because it’s unknown whether there is any requirement):

concept<class A, class B> IsSame;

And this is the empty concept:

concept<class T> Defined {};

Such a concept is always satisfied (because it doesn’t impose any requirements). Note though that incomplete types are not allowed to be concept’s parameters.

The IsSame concept can be then declared as satisfied by specialization:

concept<class T> IsSame<T, T> {};

It means that in general IsSame isn’t satisfied, but in a case when some type has been passed to it as first argument, which is the same as the second argument, then it matches the partial specialization shown above, and this way the concept is satisfied.

b. concept derivation and partial specialization

Concepts can be derived. The syntax is the same as for structures and the meaning is also the same: the contents of the base concept are incorporated into the derived concept. In result, the derived concepts imposes its own requirements plus all the requirements that come from the base concepts.

You can also derive an abstract concept from another non-abstract concept. The concept doesn’t become less abstract because of that, but it carries additional rule: Any partial specialization that would like to redefine the concept for specified type must also derive the same set of concepts as the master definition does.

There are two main things that make concepts different than templates:

  • concepts must always have exactly one master concept definition provided
  • partial specializations are only allowed (and required) to cover particular requirements, as defined in the master definition

The first statement means that you cannot “announce a concept and define it later” – when you created an “announced” version (that is, abstract), then later you can only add specializations.

The second one means that you cannot add requirements in the concept specialization nor can you remove them (every single requirement must be covered) – the concept specialization does not “derive” any requirements from the master definition.

RATIONALE: You may consider, why lacking definitions cannot be taken as default from the master definition. There are two reasons why this shouldn’t be done:

  • The goal of this proposal is to make concepts similar to understand as templates. So if template partial specializations do not silently derive from the contents of the master definition, so shouldn’t the concepts do.
  • Even though it is sometimes required, it should be explicitly visible for the user that there are defaults used (or every requirement is covered otherwise)

However, as it is sometimes desired that definitions from the base concept be “silently derived” by the specialization, these are the possible methods for how to provide a syntax for that:

1. “self derivation”:

concept<> Container<MyContainer>: Container<MyContainer>
{
   size_t MyContainer::size() { return this->numberItems(); }
};

Here the concept derives, however not “itself”, but “such an instance of this concept that would be generated from master definition” (because until this partial specialization is finished, this is what this concept instance resolves to).

2. using “default” keyword as derived:

concept<> Container<MyContainer>: default { ... };

3. using “default” keyword in the specialization:

concept<> Container<MyContainer>
{
    using default;
    ...
};

The self-deriving syntax has one important advantage: it suggests the user that there was a derivation, which means that the deriving entity incorporates definitions from the derived entity, just like classes do. It’s still worth considering a form of deriving syntax. On the other hand, it may cause to be allowed that concepts are being first used and later specialized, which would result to have two different concept definitions for particular type under the same name (and this will most likely lead into problems). It would be then better probably to issue an error when a type specialization was provided explicitly after it was generated.

c. concepts with variadic parameters

Concepts may have also variadic parameters:

concept<class T, class Arg, class... Args> TypeIsOneOf
{
    requires IsSame<T, Arg> or TypeIsOneOf<T, Args...>;
}

How to make a “termination” version, stating that concepts cannot be overloaded? No strict idea, although this is the proposal (it may be considered later for variadic templates, too):

The auto-expandable expressions (those that use “…”) are treated special way and they are replaced with some special concept instantiation statement, let’s name it “Nevermind”, if “Args…” resolves to nothing. Then:

  • A and Nevermind resolves to A
  • A or Nevermind resolves to A
  • not Nevermind resolves to Nevermind
  • single Nevermind, as resolved from some expression, resolves to nothing
  • requires {…something that resolves to Nevermind…} resolves to nothing
  • Any concept or template instantiated with the use of Nevermind resolves to Nevermind

In other words, the part that has “Args…”, resolved to nothing in particular case, will disappear as a whole and will drag the preceding operator with itself (and every higher level expression that contained this resulting Nevermind). If the expression was required to be nonempty by some reason, then when it resolved to nothing, an error is reported. So, the above concept, when used as:

requires TypeIsOneOf<T, int, char, bool>

will resolve to:

requires IsSame<T, int> or IsSame<T, char> or IsSame<T, bool>
  /* or Nevermind */ ;

3. Code synthesis and type patching

For example: how to define that an external function begin() and end() is required, although we can still live with methods with these names? There are two ways to accomplish that:

  • harder, first define a concept that will match a type that contains begin() and end() methods, then define a partial specialization for such a concept
  • easier, define requirements together with default implementation

Let’s try the easier one first:

concept<class T> Sequence
{
    typename iterator = T::iterator;
    iterator begin(T& c) { return c.begin(); }
    iterator end(T& c) { return c.end(); }
}

This way we provided a concept with default implementation. It means that this concept is satisfied for every type, for which the begin external function is provided (and the others as defined in the concept). However if there is no such function defined, the compiler will try to instantiate the default implementation. If the instantiation succeeds, the concept is meant as satisfied, and – pay attention – the “fix” for the type that requires it to satisfy the concept, is applied! It means, for example, that:

template <class C, class T>
requries Sequence<C>,
requires Convertible<T, typename C::value_type>
bool has(C& cont, const T& value )
{
   for ( C::iterator i = begin( cont ); i != end( cont ); ++i )
      if ( *i == value )
         return true;
   return false;
}

… in this example, it was possible to use begin( cont ) and end( cont ), even though there are no begin(C) nor end(C) functions! Of course, only inside this function because only in this function the C type has been imposed requirements of the Sequence<C> concept (and patches, by the way). In particular, C here has become not exactly the type of the 1st argument, determined by the template, but it’s C with appropriate type patches, as provided by Sequence<C> concept.

It means that inside the entity that required that particular type satisfy particular concept, this type has also additionally all the patches that this concept has defined. For types that don’t satisfy this concept the template entity cannot be instantiated.

The harder way will be shown later, together with overloading.

Let’s try another case. You know that in a part of C++ standard library, formerly called STL (I personally call it “CIA” – Containers, Iterators, Algorithms – as it still needs distinguishing from the rest of the standard library), there’s a concept of InputIterator and OutputIterator, which have one common treat, that is, they are both “single pass iterators”. The normal way to use single pass iterators is to use the “*x++” instruction. What is not allowed for this one (and it’s allowed only for multi-pass iterators) is to use only one of these operators, that is, use * operator without doing ++ in the same instruction (in particular, it’s not allowed to perform next * after previous * without ++ in the middle, and same for subsequent ++).

However the method that was used to achieve it is awkward – it’s simply the * operator does the “pass” as a whole, and ++ does nothing. It makes that it’s practically possible to make *x twice, although it will behave as if *x++ was made. It is then desired that these both things, as they should not be separated, are done by use of exactly one instruction:

 x.input();

It would be much better then, if InputIterator and OutputIterator have only defined input() and output() methods respectively (and not * nor ++ operators). This would be then:

concept<class T> InputIterator
{
    typename value_type = T::value_type;
    value_type T::input() { return *(*this)++; }
};

concept<class T> OutputIterator
{
    typename value_type = T::value_type;
    void T::output(const value_type& val) { *(*this)++ = val; }
};

The << and >> operators may be also good for that, although the >> operator doesn’t give it a chance to return the result by value, but on the other hand it would make the std::cout object also satisfy the requirements of OutputIterator.

You can guess that now only the purely single-pass iterators should have the input/output methods defined. For the others it’s just enough that they define * and ++ operators.

It would be a nice idea to have such a change in the standard library – however the current algorithms that are allowed to work on single pass iterators (most of them are: for_each, copy*, transform*, merge*, but not sort) would have to be changed. Such a change is possible to be made in the standard library, although the * and ++ operators should still be provided, with an annotation that they are obsolete so that the user algorithms working on single-pass iterators can be adjusted to the new form.

Thanks to concepts, there will be no need to provide input() and output() methods for multi-pass algorithms separately.

4. Lesser concept satisfaction requirement: desires

One of the main reasons for which the concepts were designed was to have better error messages. This is what we often want. It doesn’t simultaneously mean that we’d like to force a type satisfy the concept, as we, say, don’t really use all the features that are imposed by the concept. Practically we can live with some of definitions lacking – for example, we need that the type provide a copying operator=, but not necessarily a copy constructor. We have a CopyConstructible concept that contains both of them and we’d like to be able to use it. However we don’t really want that this type be CopyConstructible; we just use CopyConstructible to check for copying operator=. Of course, we can always define a new concept that contains only operator=, but this sounds like a usual explanation of language designers’ laziness “well, you can easily achieve that by making a new class for 200 lines of code”. It should be able to provide a user with a fragmentary matching, so that existing concepts can be reused.

When you use “desires” instead of “requires“, then you’ll still have the same simple and good error messages in case of error. When the compiler is compiling the template entity, it will check what exactly features of the type are being used, and they are matched with the “desired” concept, then a new unnamed concept will be created, for this particular case, that consists only of such features of the concept that are actually used. It means that the concept matching in this case will always succeed, although the entity is still allowed to use features from a type not covered by the concept that is “desired”. If a required feature is not covered by the type, then:

  • if the feature is not provided by the concept, a usual “very long and bloated” error message is printed
  • if the feature is provided by the concept, the compiler complains that the type does not satisfy the desired concept of specified name (and some feature of it in particular)

Note, however, that weak concept matching only means, in practice, that if a type does not provide a feature being used, the error message would refer to a not covered concept rather than showing what feature is lacking (usually with a long and bloated error message). It doesn’t provide other concept features like:

  • overloading by concept type
  • patching the type with additional definitions from the concept (even if the entity uses them)

It means that, for example, if you “desire” and InputIterator, as shown in the example above, the entity is using x.input(), and some multi-pass iterator is passed as x, it won’t work, because the mapping from x.input() to *x++ will not be created. The compiler will show an error message that the concept is not satisfied, pointing this method.

TO CONSIDER: Use “desires explicit” to only have the type fixes, as long as their definitions can be compiled in this particular case. In this case the link from x.input() to *x++ will be created as long as * and ++ are defined. Or, simpler, maybe it’s better to use this solution as default – that is, even when “desires”, the type fixes should be applied. Although this still should not allow that this declaration be used to distinguish type parameters for overloading.

5. Overloading and partial specialization

Overloading is simple:

template<class Iter>
requires RandomAccessIterator<Iter>
void sort( const Iter& begin, const Iter& end );

template<class Container, class Function>
requires RandomAccessContainer<Container>,
requires CallableAs<Function, bool(typename Container::value_type)>
void sort( Container& cont, Function predicate );

Overloading resolution is possible, even for template-parameter types, as long as the requirements imposed on these types are mutually exclusive for at least one argument position. In this particular case we have both arguments have types of mutually exclusive concepts that they satisfy, although you can theoretically think that it’s not impossible to satisfy both CallableAs with given signature and being an iterator (although it would be stupid).

A type for which a requirement was imposed becomes a kind of another type. That’s why it’s possible to treat it as if it was a separate type, only inside a template that uses it.

Now let’s try similar things with templates’ partial specialization. Normally we define a partial specialization the following way:

template<class T>
class SomeClass<T*>
{
...
};

which means that we provide a specific definition of a SomeClass template, where its argument is of T* type for whatever type T. We can do the same with types that satisfy particular requirement:

template<class T>
requires SomeConcept<T>
class SomeClass<T>
{
  ...
};

or, simpler:

template<class T>
class SomeClass<typename SomeConcept<T>> // such T that is SomeConcept
{
  ...
};

Of course, please note that the T type used to specialize the SomeClass template is not the same T as in the first line. The last T is such a T that has been imposed requirements defined in SomeConcept, including default implementations. However it’s a definition of a partial specialization only for such types that satisfy SomeConcept.

As you can provide this additional thing for partial specializations of a template, you can do the same with partial specialization of concepts:

concept<class T> SomeConcept<T>
requires AnotherConcept<T>
{
 ...
};

In this particular case, “requires” does not mean that the concept (specialization) being defined imposes AnotherConcept on T, but that the concept specialization being defined concerns only such types that already satisfy AnotherConcept. All requirements being imposed on a concept being defined are defined always exclusively between { and } plus requirements provided by the derived concept.

Now we can try the harder way of providing the information about satisfying the Sequence concept for classes that have begin() and end() methods. First, we define a concept that detects whether the given class has begin() and end() methods.

concept<class T> SequenceClass
{
	typename iterator;

	iterator T::begin();
	iterator T::end();
};

Having that, we can make a specialization of Sequence concept:

concept<class T> Sequence<T>
requires SequenceClass<T>
{
	typename iterator;

	iterator begin(T t) { return t.begin(); }
	iterator end(T t) { return t.end(); }
};

Actually, we did it exactly the same way, as we still needed to provide the implementation that shows how the concept is going to be satisfied. The main difference is that this particular specialization is provided only for T classes that satisfy SequenceClass<T>, not for every possible class, for which particular default implementation can be successfully evaluated.

6. Check by usage

I’m not sure whether it’s a good idea for such a feature, however it may be meant useful. Instead of a definition to be provided that should be replicated in user’s code, we can define expressions that will be tried to be evaluated. The expression to be evaluated has also restrictions about the result type:

  • if the return type is void, it only needs to be successfully compiled
  • if the return type is bool, it requires to be successfully compiled, evaluated at compile time and it should evaluate to true
  • other types are not allowed
concept<class T> Sequence
{
	typename iterator;

	requires { (void)begin( T() ); }
	requires { (void)end( T() ); }
};

Please note though, that the practical consequence of the following code is that the requirements imposed are greater than they seem to be for the first look. We have used “T()” expression to magically create a value of T type. This magic, however, cost an additional requirement: now T is also required to have a constructor able to be called with no arguments.

You can prevent this, for example, by saying “begin( *((T*)0) )”. You can safely do it because this expression is declared to be of void type (as forced) and this way it won’t be evaluated (such an expression is never evaluated at runtime anyway, whether bool or void). Using operator comma would help, however in today C++ it’s not possible that this operator (not unlike any other operator though :)) be passed a void expression as argument. Because of that, you are still allowed to make a sequence of instructions, of which the last one must evaluate to void type (this is not allowed for bool type).

For boolean value of an expression, please note that the expression must be able to be evaluated at compile time. So, if you want to “require” an expression that will return a boolean value, even stating that you know that it will always evaluate to true, but it will call some function that is not constexpr, the compilation will fail. You’d better force (void) type for such an expression then.

The boolean expression can be done also the following way:

requires { std::has_trivial_destructor<T>::value; }

This expression can be evaluated at compile time, so it matches the requirement. It’s a similar requirement as for static_assert.

Check by usage is easier to define, but allows for making more mistakes. For requirements defined as function or method definitions there are many equivalences and additional statements:

  • argument or return type may be “auto”, which means that the exact type in this place is not imposed. Please note, though, that a concept that uses this feature is not allowed for constrained matching (see below) because it is not possible to determine whether the user entity is using the type correctly
  • argument types normally are allowed to undergo all defined conversions; if this is not desired, the argument should be preceded by “explicit”. It means, for example, that if the requirement is for “f(int,T)”, then the existence of “f(char,T)” satisfies the requirement; you should use “f(explicit int, T)” in order that the type be exactly int
  • same about the return type: if given return type can be converted to the return type in the concept definition, the concept is meant satisfied. Like with argument, you can force no conversion accepted by “explicit” modifier. This means additionally that if the requirement defines that the return type is void, the matching function’s return type may be anything
  • a constructor statement in a form A::A(B) requires that type A have a constructor with one argument of type B, or that B has a conversion operator to type A. If this is preceded by “explicit”, then only just one-argument constructor of A type is allowed (both implicit and explicit – here “explicit” does not disallow implicit A constructor, but conversion operator in B, from satisfying the requirement)
  • const T& is equivalent to T in argument types, although note that if type T has been simultaneously defined as non-copyable, it causes a conflict. In other words, if T is not required to be copyable, const T& or T&& must be used as argument
  • T& has no equivalences

7. Constrained matching

The concept matching can additionally state that the template entity, that is using the concept, is only allowed to use those type’s features that are defined in the concept. If a type feature is not defined in the concept, the template entity is not allowed to use it, even though the type itself defines it. The difference between “requires” and “constrains” is then that in the first case the template entity still can use features that were not described in the concept (although it will end up with a “usual bloated” error message, if the type doesn’t provide it). Here is then the summary of what happens when there are problems with matching the concept and finding a feature of a type, for all three cases, plus one – when the type is not matched to any concept at all:

1. when a template entity uses the feature that is provided by: not using any concept desires requires constrains
concept: no; type: no usual error message usual error message usual error message error: feature not defined in the concept
concept: yes; type: no usual error message error: type doesn’t match the concept error: type doesn’t match the concept error: type doesn’t match the concept
concept: no; type: yes not a problem not a problem not a problem error: feature not defined in the concept
2. when type just doesn’t match the concept N/A not a problem error: type doesn’t match the concept error: type doesn’t match the concept

It’s not covered a case, when we’d like to forbid using a feature that wasn’t defined in the concept (as constrains does), while not requiring that the type matches the concept, but that it only provide those features that were actually used (as desires does).

8. Type interfaces and logical matching expressions

Let’s explain first one thing. Like templates, concepts are being instantiated. When templates are instantiated, this results in a new class or function. When a concept is instantiated, it results with one or more type interfaces. This type interface is next used as a “patched” interface of a type that was imposed concept’s requirements on. As you know, when there are forwarding definitions in the concepts, which cause that there be some fixes provided to the type (like begin(T) external function that redirects to T::begin()), they are applied to the type, depending on what type of imposing was used:

  • requires: the type interface contains all things that are normally available for given type plus fixes provided by the concept
  • desires: the type interface contains all things that are normally available for given type, but not fixes provided by the concept
  • constrains: the type interface contains only things that have been defined in the concept, including fixes, but not things provided by the original type not covered by the concept (that is, elements of the type interface that haven’t been defined in the concept are removed from the resulting type interface)

Type interfaces may be also shared – one function may require several different types of arguments, so each such argument type is said to be provided a new part of type interface for itself. It means then that it is not unusual that one concept provide multiple type interfaces at a time (which could be similar to having an overloaded function – multiple functions under one name). However, when for particular type there was provided a type interface, then no new type interface can be provided for the same type anymore. This would be something like creating two different typedefs with the same type name. Because of that if you want to create multiple requirements for the same type coming from multiple concepts, you must bind these concepts into a concept expression. It’s especially required if you want to define, that a type should not match a concept.

You can then bind particular concepts into logical expressions using andor and not. Note that this is only allowed for requires and constrains (not desires, and constrains may only be used as a defined requirement) and the expression has strong influence on the resulting type. The full expression must be passed just after requires keyword and, exceptionally, only the andor and not keywords are allowed for use, not the equivalent logical operators “&&”, “||” nor “!”. For example:

requires not Assignable<T>

requires Assignable<T> and CopyConstructible<T>

(RATIONALE: using &&, || and ! operators will suggest that the logical operations are being used with the C++ bool type. This is due to a tradition of C++, also coming from C; also some coding standards disable using the word-operators. The common sense then is that if symbolic operators are used, then the expression is surely an expression that requires boolean types, so it should be sure for the common sense people that concepts themselves can be used as boolean expressions, which isn’t true. Because of that it is reasonable to make use of already existing keywords that are predicted to be used in logical expressions, although the use of them is quite rare today, and they better compose with these more high level instructions.)

Two separate concepts applied for one type compose its type interface (see below) together, so it must be explicitly stated how it is built – if you then use two separate concept matches for the same types, you create two different type interfaces for the same type, which causes a conflict. In other words, if you have once used some type in one “requires” statement, it can’t be used in any other requires statement in the same entity anymore. If you use concepts that have more arguments than one, and the types are not equally distributed between used concepts, you’ll probably have to compose a complex logical expression to express it:

  requires MutuallyExclusive<A, B> and CopyConvertible<B,C>
       and ReverseIterable<A, C>;

It’s not unusual that one “requires” statement provide three separate type interfaces in result. It’s not allowed, however, that separate statements each provide two separate sets of requirements for the same type.

The situation is complicated in case when the type is a class that defines some type inside it. If a concept does not impose additional requirements to some type defined inside it (and it usually doesn’t), then using the internal type is a separate thing to using the external type. It means, for example, that you can define a concept matching for T in one requires statement and for T::value_type in another. This is allowed, but only in case when the concept being matched for T does not require that T has value_type and additionally imposes some requirements on it. If it does, then – just by a case – the concept imposed on T is imposed also on T::value_type (implicitly because it’s defined inside the concept definition), so this way adding a separate concept matching statement for T::value_type will also result in a conflict (and you need to compose them in a logical expression, if you want to solve the conflict).

RATIONALE: Why to require that type be used only once? The reason is to not allow the user code to become bloated and having too many hidden and implicit interconnections (it’s the same as not allowing classes to be open). In other words, if a user would like to make a bloated and messed up concept interconnections, let it define it as a complex, long and unreadable expression tree – and if it’s unable to do it, it’s good because probably we have saved this way someone’s one week of work.

Of course, there is a special case when it is allowed: if, by a case, two separate requires statements used for the same type require exactly the same concept to be imposed (that is, you can impose the same concept multiple times – two separate type interfaces in one entity are allowed, as long as they result in the same, just like two separate typedefs for the same name are allowed, as long as they resolve to the same type). It is reasonless for normal “requires” statements, of course, but may be helpful in case when there is some implicit requirement for some internal type.

Using things like “constrains not“, on the other hand, may cause erasing some unwanted feature from a type. Imagine, for example, that you have three classes:

  • A, that contains operator=
  • B, that contains operator= and assign()
  • C, that contains only assign()

Your entity is using operator= for whatever type is passed, and there may be passed classes like A, B and C. You’d like to use this class’s operator=, however if the assign() method is provided, it is preferred over possible operator=.

You can’t make it normal way because if you provide a concept that provides a default implementation for operator= as redirecting to assign(), for B class operator= will be used, not assign(), as it is required. For this particular case you have to use something like that:

concept<class T> AssignOnly
{
     void T::operator=(auto x)
     { return this->assign( x ); } // restore operator=
};

concept<class T> AssignOnly<T>
requires Assignable<T> and HasAssign<T>, //operator = and .assign
{
     constrains not HasAssign<T>; // but erase operator=
     // now restore operator=
     void T::operator=(auto x) { return this->assign( x ); }
};

Here “auto” has been used, which just means that we don’t care what exactly the argument’s type is. Note that in expressions defining the requirements the “requires” may be also followed by a requirement, which is merely the same as deriving a requirement. You should only remember that, by the same rule, there can’t be two separate requirement expressions with concepts that impose requirements on the same type.

Of course, the truth is that in this particular case it was simpler to make the user entity use assign() instead of operator= and make a concept that only defines “assign” with default redirection to operator=. In this case it will work. But there still may be more complicated cases where various conditions have to be imposed on various parts of the type in a concept and in this case such a simple inversion would not be possible.

Concept expressions may also be used to create an integrate concept with simplified syntax:

concept<class T> ValueType:  DefaultConstructible<T>
                            and CopyConstructible<T>
                            and CopyAssignable<T> {};

Note that this is a syntax for deriving concepts and the rule of not using the same type in separate expressions applies here as well. Note that you can also create an abstract, though deriving concept.

9. Explicit type interfaces and simplified matching syntax

Normally, without the concept, the type that is produced when instantiating a class template isn’t exactly the same as the template defines. There are created all internal parts (fields), but from all the features (that is, methods) there are extracted only those that are actually used (SFINAE rule). It means that the resulting instance of a template is a specific set of definitions composed out of what has been used by the type.

It’s not exactly the same in case when the type is imposed a concept on. In this case, all things that are needed to satisfy the concept, are instantiated, even if the template entity is not going to use some of them. However, as far as the other features are concerned, the selective use of features is still in charge.

Type interface is something that comprises a full definition of type’s features, that is, includes all natural features of the type and those that have been additionally imposed on a type as added from the concept. When you define a template, and one of template arguments has been imposed a concept, this type-argument becomes a type interface. It doesn’t matter whether the concept has only one parameter, or more. Even if the type is just one of several parameters of a concept, the succeeded match of a concept causes that for this type several additional statements might have been imposed.

It’s also allowed that such a composed type, out of the type itself and all additional definitions provided by the concept, be created explicitly:

using TypeInfo = std::type_info
         requires LessThanComparable<std::type_info>;

This syntax is required because there may be a case to say something like:

   requires Convertible<MyType, typename OtherType::value_type>;

However, exceptionally for concepts that yield one type interface (usually it’s the same as a concept with one parameter – not sure whether there are cases when it’s not true – note that concepts cannot be overloaded nor can have default parameters), we have a simplified syntax: we can use the “instantiated” concept as a type:

using TypeInfo = typename LessThanComparable<std::type_info>;

or, the old style:

typedef typename LessThanComparable<std::type_info> TypeInfo;

(CONSIDER: it would be nice to provide this “patched type” availability by declaring it inside the concept. For example, by using the following syntax:

concept<typename T> GoodLooking {
    using type = concept typename T;
    ...
}

you can make the patched type T exposed as GoodLooking<SomeType>::type instead of typename GoodLooking<SomeType>).

Note though that the full requirement for being able to use this syntax is that the concept imposes requirements on only one type at a time (not that it only requires to have exactly one argument), in particular, the imposed requirement may yield exactly one type interface.

Let’s repeat also the example from the beginning:

template <class C, class T>
requires Convertible<T, typename C::value_type>
bool has(typename Sequence<C>& cont, const T& value )
{
   for ( C::iterator i = begin( cont ); i != end( cont ); ++i )
      if ( *i == value )
         return true;
   return false;
}

Similarly it can be used with template partial specializations:

template<class T>
class SomeClass<typename SomeConcept<T>>
{
  ...
};

And, of course, it also works with C++14 generic lambdas:

auto L = [](const typename Integer<auto>& x,
             typename Integer<auto>& y)
{ return x + y; };

Please note that the type interface may differ, depending on the concept matching keyword:

  • desires: the type interface is exactly the same as the original type
  • requires: the type interface contains all of that the type provides plus possibly additional declarations provided by the concept
  • constrains: the type interface contains only those declarations that are mentioned in the concept, in a form that is actually provided by the original type (features that do not match anything in the concept are removed)

10. Concept as a code template synthesizer

Normally a template may only be a function template or a class template. When instantiating, you can only get a single class or a single function from the template. Sometimes it’s required that you generate a set of functions or classes by making a simple magic one shot definition. In current C++ if you want to achieve this the only possibility is to use #defines.

Concepts have additional feature that allows them to bring the additional fixes made to the code into any other scope. Normally such fixes are available only inside the template entity that required some concepts to be satisfied. The following statement brings the fixes just to the current scope – that is, this makes that std::type_info becomes, in the scope where this declaration is provided, the same as TypeInfo declared above:

using LessThanComparable<std::type_info>;

After this is specified (see LessThanComparable in the beginning), you can safely do (until the scope with this “using” ends):

 if ( typeid(X) < typeid(Y) ) ...

Using this method you can also provide a whole set of functions to types, which’s definitions you cannot change. It includes also operators, such as those provided by std::rel_ops. Using std::rel_ops namespace makes that since this declaration these operators are available for all types and only require to have == and < operators defined, which not necessarily is what you want. Using the “using concept” statement you can provide this set of operators only to exactly one specified type. This is a very useful feature for enums:

enum eSize { SMALL, MEDIUM, LARGE };
using OrderableEnum<eSize> // adds operator <
  and EquivalentOperators<eSize>; // adds rest of the operators

11. Name clash problems

Of course, names of types and of functions being defined are assigned to particular namespace. But the concept may be defined in other namespace than that when it was used by a template entity. In practice it means that the names of functions or classes being used in the concept requirement statements shouldn’t be the same as the namespace in which the concept was defined.

Names are, then, qualified in the namespace where they are being required. It means that the concept is “instantiated” in the namespace, in which it is used. It doesn’t mean much the exact namespace, in which the statements are instantiated. What is important is whether at the location where the concept is used, particular functions are already available in the current namespace – no matter whether they are defined in this namespace or are imported from another one. On the other hand, you can always put a namespaced name in the concept, and in this case the function is looked for in exactly this namespace. Note that this is the case when “constrains” can be made use of. If you wanted to use, for example, std::begin because this is mentioned in the concept, and you mistakenly used just “begin” and did not make “using namespace std”, the constrain won’t let you use it, even if you have a begin() function in the current namespace that is defined for this type.

12. Things that are not going to be supported

One of the main things that are not supported are explicit concepts, that is, concepts that are not satisfied by default, unless explicitly specified in the concept map. This was the default in the original proposal, here it is not supported at all.

This feature can be easily achieved using the following way: define an abstract concept with a name that you’d like your concept to have, then define (empty) partial specializations for types that you explicitly define that they satisfy this concept (the “whitelist” method). Or opposite way – define an empty concept, which means that every type satisfies it, then define a partial specialization as an abstract concept, for types that, exceptionally, should not satisfy it (the “blacklist” method).

You want to put additional requirements for them to have? What for? Isn’t it enough that you just specify that the type should satisfy it? Ok, if you really need this, you can use concept derivation: define a concept normal way, then define another concept, that you expect to be explicit, as abstract, and then derive it from the previous one. This way you’ll have an abstract concept, which can be only explicitly defined as satisfying the requirement, and additionally it imposes some requirements on a type.

I also haven’t described in this proposal any kind of “axiom”. I’m not quite convinced to that it’s worth to implement such a feature. But I think it could be just added to this proposal without change, in the original form. The only problem is that I’m not quite convinced that this should be a part of concepts. This rather should be a part of class definition, so that the class type defines what simplifications can be used by the compiler. Then, concepts may have this axiom mentioned in its requirements, but for concepts this thing will still be derived.

I also haven’t added anything about “late_check”, however I think this feature may be accomplished by using the “desires” keyword, which already means that the underlying expression may be imposed requirements, but not as a must. I haven’t done any research for that yet.

13. Additional things to be considered

One of the important additional changes to be considered is to provide multiple default implementations for a concept’s feature. It would be selected as the first one that works. For example:

concept<class T>
LessThanComparable
{
    bool T::operator<(const T& oth)
       { return this->before( oth ); }
    or { return this->precedes( oth ); }
};

I’m not convinced that it makes sense. The same result (and more readable) can be achieved by using also different concepts and make concept maps basing on partial specializations for classes that satisfy some other concept.

This brings back the discussion about accidental concept match: the fact that a class has some method with some name and with matching argument types, need not necessarily mean that this method can be used as a replacement for some lacking feature. It was better, for example, to provide LessThanComparable specifically for std::type_info because we know this type has the before() method that is to be used for ordering, so for the rules of CIA (STL) this is equivalent for operator<. But it doesn’t mean that any other type that has before() method, which accidentally returns bool and accepts an object of the same type, has specified meaning.

The practice is that if we want to make sure about correct feature recognition, then there must be used some “common sense” things. Operators like == or < are meant common sense. Also operator << meaning “send to” and >> meaning “receive from” (not shift left or shift right) can be also meant common sense. But operator >= for the operation “push on the stack” is not a common sense.

However this discussion may unnecessarily bring back the doubts whether it makes sense to blindly match the concept by method name, while it’s already proven to be a minor problem. First, usually concepts are not based on just one method. Second, concepts should be build to help developers, not to protect them against anything. For this one then, it’s better to use common sense in defining concepts: the before() method for preceding is not the common sense – common sense for this operation is operator<. Likewise, common sense is to have size() method to return the number of items the object has, while any numberItems() or length() or anything alike is a specific naming for particular data type, so the concept specialization should be provided for this one.

Another thing to be considered is to make it possible to create requirements “on the fly” when needed for some other definition. For example, you’d like to define a concept specialization only for types that have operator=, but you don’t want to define a separate concept that will only detect whether operator= exists for this type. This way, instead of “requires Assignable<T>”, you’d say “requires { auto T::operator=(auto); }”.

I have an ambivalence about this. From one point of view it will allow users to create very bloated code definitions. On the other hand, without this feature users will be again forced to “spell up the name and consequently use it”, which works always against users. That’s why “auto” is such a great feature in C++11 because it doesn’t require that users define typedefs and spell up some name.

There is one more thing that comes to my mind. Possibly there should be provided some method that allows to define a concept for some type, and then some partial specializations, but disallows that this definition be open for further extensions. For example, it would be nice to be able to define an IsSame concept, which will not be allowed to be later specialized a way not intended by the original concept definition, that is, to define that char is same as int. Similarly, there should be some standard concept that says that the type is one of builtin integer types. Such a concept should not be possible to be later extended for the other types because this way a user may break the basic statement of the concept’s logical definition.

The problem is that the concept together with its specializations can’t be defined as a closed entity (like a class is). The only feasible syntax that comes to my mind is that after all specializations have been provided, you should say at the end:

concept<> BuiltinInteger final;

or something like that. From this definition on, no additional partial specialization of a concept may be provided.

I know this syntax is awkward, so maybe someone else will have some better proposal. Note that any better proposal needs that partial specializations be alternatively provided also inside the concept definition. If such a syntax can be proposed and well explained, then the concept can be marked final and then any external concept specialization will be rejected. The problem is that if such an additional thing is provided it increases the complexity of the solution – mostly because this creates an additional difference to template partial specializations.

One more thing that came to my mind is that a concept may additionally help during development when an interface is going to change. For example, in current C++11 we can have a code that is independent on function’s return type:

auto n = GetFreeSpace(device);

You expect that the return type may change in future or be different in other code configurations. By using auto you make your code independent on possible return type. However, you still would like to use this value some way, and you want to be sure that if your code wouldn’t work because of some basic statements violated towards this return type, it will be early detected. So we can say instead:

Integer<auto> n = GetFreeSpace(device);

This way it’s still auto, but it’s additionally checked if this type also satisfies requirements imposed by Integer concept. Similarly we can impose such a requirement as PointerTo<T, P>, which checks if T is a pointer to P, that is, not only T is P*, but also unique_ptr<P> or shared_ptr<P>, and whatever else type declares that it is a smart pointer.

14. Summary – can this be easily explained?

Simplicity is one of the most important thing for any new feature to be added to C++. C++ is already a complicated language, and as it can’t attract people who just don’t accept languages that are that complicated, it’s best to keep new features simple enough.

The explanation for concepts should start with examples of standard concepts, standard entities that use concepts, and how to interpret possible errors reported by the compiler. Then, how to do it yourself. Let’s begin with the well known Comparable:

concept<class T> Comparable
{
    bool operator==(T,T);
};

Objects must be comparable in order to be found. Because of that the find algorithm imposes this requirement on the value type:

template<class Iter>
requires InputIterator<Iter>,
requires Comparable<typename Iter::value_type>
Iter find( Iter from, Iter to, typename Iter::value_type val )
...

If you pass as ‘val’ something that doesn’t have operator ==, the compiler will complain that your type does not satisfy the Comparable concept because it doesn’t have operator== with specified signature – not that “bla bla bla (1000 characters of text) your value_type doesn’t have operator== with bla bla bla (1000 characters of text) signature”.

However, if you have to find an object of SomeClass, which can be compared for equality, but only using some EqualTo method, you can declare this especially for this class, as a partial specialization:

concept<> Comparable<SomeClass>
{
    bool operator==(T a, T b) { return a.EqualTo(b); }
};

This causes that objects of type SomeClass can always be compared by operator==, as long as the attempt happens inside the entity that requested that the type is imposed Comparable concept on. Of course, alternatively you can define an external == operator for this type, but operator== is in a lucky situation to be able to be provided as a standalone function. It’s not possible with all operators as long as with methods. Additional advantage is that you don’t have to provide global definition of ==, so you don’t make a garbage in the other’s code.

You can define your own class or function template, stating that you expect that some type satisfies the concept, just like find is shown above. If you have more than one requirement to be imposed on a type, however, you must bind them in one logical expression, using ‘and’, ‘or’ and ‘not’ keywords.

Using concept requirement imposed on a type, you can more strictly define what this type is, and distinguish it from the other types assigned to template parameters. This way you can also use concepts to make partial specialization of templates:

template<class T>
class Wrapper     // master definition (general)
{ ... };

template<class T>
class Wrapper<T*> // partial specialization for pointer types
{ ... }; 

template<class T>
requires ValueType<T> // partial specialization for ValueType
class Wrapper<T> { ...  };

// or simpler:
template<class T>
class Wrapper<ValueType<T>> { ... };

and overloading

template<class T>
requires SequenceIterator<T>
pair<T,T> range( T a, T b )
{ return make_pair( a, b ); }

template<class T>
requires Integer<T>
integer_range<T> range( T a, T b )
{ return create_int_seq( a, b, 1 ); }

Satisfying a concept is enough to distinguish the type to the other that doesn’t satisfy the concept. Although the overload resolution will fail in case when you pass such a type that satisfies both requirements (from two overloaded functions) simultaneously.

You can define requirements for types (beside things like types or constants inside the type) in your concept by two ways:

  1. Provide a declaration that describes what should be available for your type. In this case the requirement is meant satisfied if provided feature can be called the same way
  2. Provide a requires {} statement with an expression that should be possible to be performed on the object of this type, which can be either a void expression (then it’s only required to compile), or a compile-time constant boolean expression (in this case it also must evaluate to true)

Please note that incomplete types cannot be checked for satisfying the concept.

This feature has the following main purposes:

  • support overloading of function templates (for arguments that are of template parameter type)
  • provide better error messages
  • create ability to synthesize code templates (without preprocessor and code generator)

Currently that’s all for starters.

So I hope I have covered everything that is needed and expected from concepts in C++. It’s at least a good starting point.

strong

Advertisements
This entry was posted in Uncategorized and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s