Doc. no.

P0324R0

Date

2016-05-04

Reply-to

Zhihao Yuan <zy@miator.net>

Audience

Evolution Working Group

One Concept Definition Syntax

Summary

Introduction

Discussion

An issue or a non-issue?

Overload or not?

A wording issue or a vocabulary issue?

Approaches Considered

Acknowledgements

References

Appendix: Sample Wordings

Alternative I

14.5.8  Concepts

Alternative II

Summary

We propose to replace the function-style concept and the variable-style concept in the current Concepts TS[1] with one form,

template <typename T, typename U>

concept SwappableWith = Swappable<T> && … ;

without allowing the concepts to be overloaded.

Introduction

Concepts TS specifies two forms of concept definitions:

Function concept:

template <typename T>

concept bool FC() {

    return constraint-expression;

}

Variable concept:

template <typename T>

concept bool VC = constraint-expression;

To an end-user of the concepts, in some circumstances, these two forms unavoidably bring out different interfaces:

template <typename T>

    requires FC<T>() && VC<T>

void f();

This mandates a strong coupling among libraries, users, and library specifications[13]:

Due to these usability and maintenance concerns, Ranges TS[2] switched to using only function concept.  As the concerns become real, we look for a solution in this paper.

Discussion

An issue or a non-issue?

One can argue that the problem we faced is a non-issue, since the same issue happens to, for example, data member v.s. member function.  The users need to know in which form the accessor is defined in advance to use it, and we cannot “upgrade” a variable to a function without breaking source compatibility – a true story is that we cannot make std::pair benefit from EBO since it requires the member functions first() and second().

We can keep elaborating this argument.  However, such an argument is based on the following premise: function and variable are the right abstractions to model a Concept.  Let’s recall the definition of Concepts in “The Palo Alto” report[3]:

Concepts are a kind of type predicate that determine whether their type (or non-type) arguments satisfy a set of requirements.

A type predicate is a type function to return “true” or “false”, where the type function is defined as:

[…] a compile-time function where at least one argument or the result is a type.

So a Concept is a type function.  We compare the abstractions, namely function concept and variable concept, against this quiddity.  Is a variable concept a type function?  Yes, as it forms a mapping from types to true or false.  But the word “variable” in its name is not contributing to the fact that it is a function under the definition of a type function.  Similarly, in a function concept, the function arguments are not being used to fulfill the role of a type function.  Thus, a function concept is a Concept not because it is a C++ function, and a variable concept is a Concept while being a C++ variable does not affect its essence of being a type function.  Therefore, the notions of function concept and variable concept are unrelated to the quiddity of Concepts.

But why this distinction exists?  We look back into the history of writing type functions in C++.  At the beginning, class templates are being used to represent type functions, where are called type traits.  In C++14, alias templates are being used to simplify the transformation traits[4], and in the coming C++17, variable templates are being used to simplify the predicate traits[5].  That is to say, all kinds of C++ templates – class templates, function templates, variable templates, and alias templates, may represent a type function.  As a matter of fact, the author of the concepts-lite proposal experimented the idea to allow class templates and alias templates being used as Concepts[6], and chose function templates and variable templates mostly for technical reasons[1].

In other words, the notions of function concept and variable concept are acceptable representations rather than right abstractions.

Keep refering to a concept by its representation rather than its meaning creates confusions, causes issues in practice, and does harm to the acceptance of the concept.  We therefore propose to define Concepts using a dedicated form.

Overload or not?

The current function-style concept can supersede the variable-style concept since only the former allows overloading the concept definitions, so it is a safe move for the existing libraries (Ranges TS and the text_view library[7], for instance) only use the function-style concepts.  We like the basic syntax of the variable-style concept and considered adding overloading support to it, and it turns out that we had some misconceptions about this feature:


template<typename T> concept bool C() { return true; }

template<int N> concept bool C() { return true; }

template<C c> void f();  // ill-formed

// a type U such that EqualityComparable<T, U>

template <EqualityComparable<T> U>

// a bool indicating whether T is equality comparable with itself

template <typename T> requires EqualityComparable<T>

For the last one, we suggest to rename the binary concepts EqualityComparable to EqualityComparableWith, and Swappable to SwappableWith in Ranges TS.  This naming convention follows the new C++17 traits is_swappable and is_swappable_with[8].  Similarly, overloading a function-style concept with a non-concept function or function template can use naming conventions to disambiguate, such as capitalizing the concept but not the others, or use different namespaces.

In summary, the only significant part of this feature is overloading on arities, which is not necessary, and sometimes beneficial if not being used.  Therefore we propose not to make the concept definitions overloadable.

Notably, without overloadable concept definitions, the new section “Resolution of qualified references to concepts” (14.10.4 [temp.constr.resolve]) will be unnecessary, as we can fully rely on the existing name lookup rules.

A wording issue or a vocabulary issue?

Multiple parties raised this issue[9][10], and came up with the same design, but it is the first time we try to formalize such a design.  The syntax of this design

template <typename T>

concept ConceptName = SomeConcept<T> && expr;

is suitable for defining concept as a new kind of entity rather than a variable template declared by a concept keyword, and we do hear people, including some implementers, expressed the desire to make concept a first-class entity in the language.  Notably, while we keep talking about “Concepts”, the Concepts TS is not adding a section titled “Concepts” to the standard.  We totally understand that the core semantics of this feature are template constraints as described in the section of the same name, but one can argue that it would be beneficial in terms of education and communication if we can refer to the standard for the vocabulary “concept”, without being warned that:

This paper is not proposing a particular way to specify the concept definition in the TS.  Instead, we present all the approaches that we have considered in the section below.

Approaches Considered

  1. Keep concept as a decl-specifier.

So that we only need to drop the function-style concept.  The problem is that, given the existing grammar, it is not possible to make the type-specifier bool came after the concept keyword optional or removed.

  1. Make concept a simple-type-specifier.


So that the
bool may be optional or removed.  This approach meets our expected “reasonable” usage from an end-user’s point of view with minimal changes to the existing TS.  However, some of the users deem this approach “an implementation technique put into the standard”.


The sample wording “Alternative II”
partially illustrated this approach.

  1. Define a new concept-definition as an alternative for template-declaration.

template-declaration:

   template < template-parameter-list > requires-clauseopt declaration

   concept-definition

concept-definition:

   template < template-parameter-list > concept concept-name = constraint-expression ;

So that it is grammatically not possible to form a concept definition outside templates, and we can define concepts as separate entities.  But many template mechanisms are defined in terms of the declaration sub-production, which requires extra efforts to make this approach work.

  1. Define 3) in terms of an “implicitly-defined variable template”.

By saying that a concept in the form of

template < template-parameter-list >

concept concept-name = constraint-expression ;

implicitly defines a variable template in the form of

template < template-parameter-list >

constexpr bool concept-name = constraint-expression ;

we can forward the rules for the concept definition such as linkage and name lookup to this variable template.  But this still looks like “an implementation technique in the standard”, and since it is not a pure syntactic translation like the “range-based for” case, the specification is not easy enough to understand as expected.

This approach has been obsoleted.

  1. Define a new concept-declaration which may only appear in a template.

block-declaration:

   …

   alias-declaration

   concept-declaration

concept-declaration:

   concept identifier = constraint-expression ;

The idea comes from alias templates, with a difference such that an alias-declaration outside a template is valid but a concept declaration outside a template has to be forbidden.  Since the grammar of templates is untouched, the template mechanisms defined in terms of the declaration sub-production work out-of-box, and the kind-specific (function, class, alias, etc.) template mechanisms such as instantiations, explicit and partial specializations do not apply, which match perfectly with what we need for a concept definition.

The sample wording “Alternative I” illustrated this approach.

  1. Open a new Clause, namely Concepts [concept].

This is the ultimate thing we may be able to do in the standard, defining concept as a “true” first-class entity.  The concept definition will be a new kind of declaration in [basic]; concept-name will be a new kind of name, so that the name lookup rules need to be updated; and linkage of a concept needs to be specified since concept is not template.  This clause also needs to specify or repeat the necessary template-like mechanisms.

However, the most significant changes brought by the Concepts TS are in 14.10 [temp.constr], so a Concepts clause may not bring much new information, thus it may not worth that much significance in the standard document.

Acknowledgements

Thanks to Richard Smith, Tom Honermann, and Andrew Sutton for joining the discussion to form this paper.

References

[1]

Andrew Sutton, Ed., N4553 Working Draft, C++ extensions for Concepts.  http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2015/n4553.pdf

[2]

E. Niebler and C. Carter, Eds., N4569 Working Draft, C++ Extensions for Ranges.  http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2016/n4569.pdf

[3]

B. Stroustrup and A. Sutton, Eds., N3351 A Concept Design for the STL.  http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3351.pdf

[4]

Walter E. Brown, N3655 TransformationTraits Redux, v2.  http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3655.pdf

[5]

Stephan T. Lavavej, N3854 Variable Templates For Type Traits.  http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2014/n3854.htm

[6]

Andrew Sutton, In reply to "Why alias template can not be concept? ".  https://groups.google.com/a/isocpp.org/d/msg/concepts/fALMCb1uJrU/BbaM_EOUsbcJ

[7]

Tom Honermann, P0244R0 Text_view: A C++ concepts and range based character encoding and code point enumeration library.  http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2016/p0244r0.html

[8]

Daniel Krügler, P0185R1 Adding [nothrow-]swappable traits, revision 3.  http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2016/p0185r1.html

[9]

Walter E. Brown, EWG 182 N4434 Tweaks to Streamline Concepts Lite Syntax, other Concepts TS issues.  http://cplusplus.github.io/EWG/ewg-active.html#182

[10]

Walter E. Brown, N4434 Tweaks to Streamline Concepts Lite Syntax.  http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2015/n4434.pdf

[11]

Hubert Tong, Concepts issue 16 Concept and non-concept declarations of the same variable template.  http://cplusplus.github.io/concepts-ts/ts-active.html#16

[12]

Hubert Tong, Concepts issue 15 Partial specialization of non-concept variable template as a concept definition.  http://cplusplus.github.io/concepts-ts/ts-active.html#15

[13]

Tom Honermann, Refining Concepts: The quiddity of concept definitions.  http://honermann.net/blog/2016/03/24/refining-concepts-the-quiddity-of-concept-definitions/


Appendix: Sample Wordings

For editorial convenience, the sample wordings are not equal.  Common instructions go into “Alternative I” and are not repeated in “Alternative II”.  The author can create a wording based on either one.

Alternative I

Issues fixed: concepts-ts 6, 7, 8, 15, 16, 22, 29 (N4434 cleared).

Issues closed: concepts-ts 19, 20, 25, 26, 27.

This wording is relative to N4553, Working Draft, C++ extensions for Concepts.

Revert the following instruction applied to chapter 7.1 [dcl.spec]:

Extend the decl-specifier production in paragraph 1 to include the concept specifier.

Revert the new section 7.1.7 [dcl.spec.concept].

Add the following instruction:

Extend the block-declaration production to include a concept-declaration:

block-declaration:

  simple-declaration

  asm-definition

  namespace-alias-definition

  using-declaration

  using-directive

  static_assert-declaration

  alias-declaration

  concept-declaration

  opaque-enum-declaration

nodeclspec-function-declaration:

  attribute-specifier-seqopt declarator ;

alias-declaration:

  using identifier attribute-specifier-seqopt = type-id ;

concept-declaration:

  concept identifier = constraint-expression ;

Modify the instruction applying to Clause 14 [temp] as follows:

Modify the template-declaration grammar in paragraph 1 as follows to allow a template declaration introduced by a concept.

A template defines a family of classes or functions, or an alias for a family of types, or a concept.

template-declaration:

   template < template-parameter-list > requires-clauseopt declaration

   template-introduction declaration

requires-clause:

   requires constraint-expression

The declaration in a template-declaration shall

— declare or define a function, a class, or a variable, or

— define a member function, a member class, a member enumeration, or a static data member of a class template or of a class nested within a class template, or

— define a member template of a class or class template, or

— be an alias-declaration or a concept-declaration.

A template-declaration is a declaration.  A template-declaration is also a definition if its declaration is a concept-declaration, in which case the template-declaration is referred to as concept definition, or defines a function, a class, a variable, or a static data member.  A declaration introduced by a template declaration of a variable is a variable template.  A variable template at class scope is a static data member template.  [ Example: … —end example ]

New instructions:

Add a new section 14.5.8 [temp.concept]:

14.5.8  Concepts

A concept definition declares the identifier to be a concept.  A concept defines a set of constraints (14.10).  The name of the concept is a template-name.

A concept-declaration may appear only as the declaration of a template-declaration in namespace scope.  [ Example:

  template<typename T>

  concept C1 = true;      // OK: declares a concept

  concept C2 = true;      // error: not a concept definition

  struct S {

    template<typename T>

    concept C = true;     // error: concept declared in class scope

  };

—end example ]

A concept definition shall not have associated constraints (14.10.2).

The constraint-expression (14.10.2) of a concept shall not include a reference to the concept being declared.  [ Example:

  template<typename T>

  concept C = C<T*>; // error

—end example ]

The constraint-expression of a concept shall be a core constant expression of type bool.

In a potentially-evaluated expression, when a template-id refers to a specialization of a concept, it is equivalent to a prvalue of the substituted constraint-expression of the concept.  [ Note: The concept definitions cannot be instantiated, but may be normalized (14.10.2).  —end note ]

The first declared template parameter of a concept definition is its prototype parameter.  A variadic concept is a concept whose prototype parameter is a template parameter pack.

Add a new paragraph at the end of section 14.5 [temp.decls]:

Because an alias-declaration cannot declare a template-id, it is not possible to partially or explicitly specialize an alias template.

It is also not possible to partially or explicitly specialize a concept as a concept-declaration cannot declare a template-id or a partial-concept-id.  [ Note: This prevents users from subverting the constraint system by providing a meaning for a concept that differs from its original definition.  —end note ]

For the following instruction applying to chapter 14.1 [temp.param],

Insert the following paragraphs after paragraph 8.  These paragraphs define the meaning of a constrained template parameter.

modify paragraph 9 as follows:

A constrained-parameter declares a template parameter whose kind (type, non-type, template) and type match that of the prototype parameter of the concept referred to designated by the qualified-concept-name (7.1.6.4.2) in the constrained-parameter.  The designated concept is selected by the rules for concept resolution described in 14.10.4.  Let X be the prototype parameter of the designated concept.  The declared template parameter is determined by the kind of X (type, non-type, template) and the optional ellipsis in the constrained-parameter as follows.

modify the new bullets (10.3) and (10.4) as follows:

Then, fForm an expression E as follows. If C is a variable concept (7.1.7), then E is to be the id-expression TT.  Otherwise, C is a function concept and E is the function call TT().

— Finally, iIf P declares a template parameter pack and C is not a variadic concept, E is adjusted to be the fold-expression (E && ...) (5.1.3).

as well as the example:

[ Example:

  template<typename T> concept bool C1 = true;

  template<typename... Ts> concept bool C2() { return true; }

  template<typename T, typename U> concept bool C23 = true;

  template<C1 T> struct s1;      // associates C1<T>

  template<C1... T> struct s2;   // associates (C1<T> && ...)

  template<C2... T> struct s3;   // associates C2<T...>()

  template<C23<int> T> struct s34; // associates C23<T, int>

—end example ]


In the instruction to add the chapter 14.2 [temp.intro], modify paragraph 2 as follows:

The concept designated by the qualified-concept-name is selected by the concept resolution rules described in 14.10.4.  Let C be the designated concept referred to by the qualified-concept-name.  The template parameters declared by a template-introduction are derived from its introduced-parameters and the template parameter declarations of C to which those introduced-parameters are matched as wildcards according to the rules in 14.10.4.  For each introduced-parameter I, declare a template parameter using the following rules:

and modify the bullet (5.2) as follows:

— Then, form an expression E as follows.  If C designates a variable concept (7.1.7), then E is to be the id-expression C<A1, ..., AN>.  Otherwise, C designates a function concept and E is the function call C<A1, ..., AN>().

as well as the example:

[ Example:

  template<typename T, typename U> concept bool C1 = true;

  template<typename T, typename U> concept bool C2() { return true; }

  template<typename... Ts> concept bool C23 = true;

  C1{A, B} struct s1;    // associates C1<A, B>

  C2{A, B} struct s2;    // associates C2<A, B>()

  C23{...Ts} struct s23;   // associates C23<Ts...>

  C23{X, ...Y} struct s34; // associates C23<X, Y...>

—end example ]

In the instruction to add the chapter 14.10 [temp.constr], in 14.10.2 [temp.constr.decl], modify the bullets (3.1) and (3.2) as follows:

— replace all function calls of the form C<A1, A2, ..., AN>(), where C refers to the function concept D (7.1.7) selected by the rules for concept resolution (14.10.4), with the result of substituting A1, A2, ..., AN into the expression returned by D, and

— replace all id-expressions of the form C<A1, A2, ..., AN>, where C refers to a is the variable concept D (14.5.87.1.7) selected by the rules for concept resolution (14.10.4), with the result of substituting A1, A2, ..., AN into the constraint-expression initializer of D.

Revert the new section 14.10.4 [temp.constr.resolve].

In the instruction to add the section 7.1.6.4.2 [dcl.spec.auto.constr], modify paragraph 2 as follows:

An identifier is a concept-name if it refers to a set of concept definitions (14.5.87.1.7).  [ Note: … —end note ] [ Example: … —end example ]

and modify paragraph 4 as follows:

The concept designated by a constrained-type-specifier is the one selected according to the rules for concept resolution in 14.10.4.

Apply the syntax changes to all the examples in the document.  Sample edits:

… 5.1.4 paragraph 5…  [ Example:

  template<typename T>

    concept C1 =bool C1() {

    requires(T t, ...) { t; }; // error: terminates with an ellipsis

  }

  template<typename T>

    concept C2 =bool C2() {

    requires(T t, void (*p)(T*, ...)) // OK: the parameter-declaration-clause of

    { p(t); };                        // the requires-expression does not terminate

  }                                   // with an ellipsis

—end example ]

… 5.1.4 paragraph 7…  [ Example:

  template<typename T> concept bool C =

    requires {

    new int[-(int)sizeof(T)]; // ill-formed, no diagnostic required

  };

—end example ]

Update all the references to 7.1.7 to reference 14.5.8.


Alternative II

Issues fixed: concepts-ts 7, 8, 22.

Issues closed: concepts-ts 19, 20, 25, 26, 27.

Revert the following instruction applied to chapter 7.1 [dcl.spec]:

Extend the decl-specifier production in paragraph 1 to include the concept specifier.

Modify the instruction applying to section 7.1.6.2 [dcl.type.simple] as follows:

Add constrained-type-specifier and the concept specifier to the grammar for simple-type-specifiers.

void

auto

concept

decltype-specifier

constrained-type-specifier

Modify the instruction adding a new section 7.1.7 [dcl.spec.concept] as follows:

The concept type-specifier specifier shall be applied only to the definition of a function template or variable template, declared in namespace scope (3.3.6).  A function template definition having the concept specifier is called a function concept.  A function concept shall have no exception-specification and is treated as if it were specified with noexcept(true) (15.4).  When a function is declared to be a concept, it shall be the only declaration of that function.  A variable template definition having the concept type-specifier specifier is called a variable concept.  A concept definition refers to either a function concept and its definition or a variable concept and its initializer.  [ Example:

  template<typename T>

  concept bool F1() { return true; } // OK: declares a function concept

  template<typename T>

  concept bool F2();                 // error: function concept is not a definition

  template<typename T>

  constexpr bool F3();

  template<typename T>

  concept bool F3() { return true; } // error: redeclaration of a function as a concept

  template<typename T>

  concept Cbool V1 = true;            // OK: declares a variable concept

  template<typename T>

  concept Cbool V2;                   // error: variable concept with no initializer

  struct S {

    template<typename T>

    static concept bool C = true;    // error: concept declared in class scope

  };

—end example ]

Every concept definition is implicitly defined to be a constexpr declaration (7.1.5) of type bool.  A concept definition shall not be declared with any other the thread_local, inline, friend, or constexpr specifiers, nor shall a concept definition have associated constraints (14.10.2).

The definition of a function concept or the initializer of a variable concept shall not include a reference to the concept being declared.  [ Example:

  template<typename T>

  concept bool F() { return F<typename T::type>(); } // error

  template<typename T>

  concept Cbool V = CV<T*>;                            // error

—end example ]

The first declared template parameter of a concept definition is its prototype parameter.  A variadic concept is a concept whose prototype parameter is a template parameter pack.

A function concept has the following restrictions:

— No function-specifiers shall appear in its declaration (7.1.2).

— The declared return type shall have the type bool.

— The declaration’s parameter list shall be equivalent to an empty parameter list.

— The declaration shall have a function-body equivalent to { return E; } where E is a constraint-expression (14.10.1.3).

[ Note: Return type deduction requires the instantiation of the function definition, but concept definitions are not instantiated; they are normalized (14.10.2).  —end note ] [ Example:

  template<typename T>

  concept int F1() { return 0; }      // error: return type is not bool

  template<typename T>

  concept auto F2() { return true; }  // error: return type is deduced

  template<typename T>

  concept bool F3(T) { return true; } // error: not an empty parameter list

—end example ]

A variable concept has the following restrictions:

— The declared type shall have the type bool.

— The declaration shall have an initializer.

The initializer of a concept shall be a constraint-expression (14.10.2) followed by = (equal).

[ Example:

  template<typename T>

  concept Cbool V1 = 3 + 4; // error: initializer is not a constraint-expression

  concept Cbool V2 = 0;     // error: not a template

  template<typename T> concept bool C = true;


  template<C T>

  concept Cbool V3 = true;  // error: constrained template declared as a concept

—end example ]

The first declared template parameter of a concept definition is its prototype parameter.  A variadic concept is a concept whose prototype parameter is a template parameter pack.

A program shall not declare an explicit instantiation (14.8.2), an explicit specialization (14.8.3), or a partial specialization of a concept definition.  [ Note: This prevents users from subverting the constraint system by providing a meaning for a concept that differs from its original definition.  —end note ]


[1] In addition to the cited material, I will add that, inline functions and variables with initializers are easier for normalization (into conjunctions and disjunctions).

[2] Naturally curried languages exist, but I don’t know of a precedence allowing overloading and currying to work together.

[3] The sample wording “Alternative I” does emphasise these in a different place, but they are already grammatically not possible.

[4] If an extension is applied to allow evaluating concepts in more contexts.