Refining Concepts: The quiddity of concept definitions

In Why Concepts didn’t make C++17 [Twitter] [Reddit], I summarized a number of technical concerns that were raised during the C++ standard committee meeting in Jacksonville.  In this post, I’ll be discussing #3 on that list; the forms of concept definitions.

A quick review; the Concepts TS [Concepts] 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;

Function concepts are function template definitions declared with a concept specifier and variable concepts are variable template definitions declared with a concept specifier.  The form that is used to define a concept dictates usage syntax in some contexts.  For example, the above concepts can be referenced with the same syntax in the following constrained function template declaration:
    template<FC T, VC U>
    void f();

However, in the following equivalent declaration, the form in which the concept definition is declared determines the syntax used to evaluate each concept.  (Note the added () following FC<T>)
    template<typename T, typename U>
      requires FC<T>() && VC<U>
    void f();

The requirement for distinct syntax imposes both usability and maintenance concerns:

  • Library specifications must dictate the form in which a concept definition is provided and implementers must adhere to the specified form.
  • Users of a library that provides concept definitions must be aware of the form in which the concepts are defined when referencing them other than as a constrained-type-specifier.  (Note: constrained-type-specifier should be renamed [Issue#31])
  • Changing a concept definition from one form to the other breaks source compatibility.  Overloading is not supported for variable concepts, so a desire to provide an overloaded concept definition might motivate such a change.

The function form has a distinct advantage over the variable form due to its support for overloading based on template parameter kind and arity.  The variable form offers a slightly more terse syntax for defining and using concepts, but I’m not aware of any other benefits (the ability to prohibit overloading can sometimes be useful, but those uses don’t seem applicable to concept definitions).  All concepts that can be defined using the variable form can be defined using the function form.

So, would dropping the variable form resolve the above concerns?  I think it would.  But, before we kick variable concepts out of the specification, lets look at the current forms a bit more closely.

Function concepts are defined as function templates.  However, adding the concept specifier brings along a host of restrictions:

  • The template parameters must not be constrained.
  • The return type must be declared as bool; return type deduction is not allowed (deduction requires instantiation and function concepts are not instantiated).
  • The parameter list must be empty (or void).
  • An exception specification must not be specified.
  • The body must be a single return statement that returns a constraint-expression.
  • The function must not be declared in conjunction with the thread_local, inline, friend, or constexpr specifiers (though the function will be implicitly defined as constexpr).
  • The function cannot be forward declared.
  • The function must be declared at namespace scope (class member declarations are not permitted).
  • The function cannot be explicitly instantiated or implicitly or explicitly specialized.
  • The function address cannot be taken (kind of.  gcc currently permits it, but since the function is not actually instantiated, unresolved symbol errors occur at link time).

Likewise, the variable form has its own set of similar restrictions:

  • The template parameters must not be constrained.
  • The variable type must be declared as bool; type deduction is not allowed.
  • The variable Initializer must be a constraint-expression.
  • The variable cannot be forward declared (though the specification is currently a little unclear regarding this; see concepts TS issue 16 [Issue#16]).
  • The variable must be declared at namespace scope (class member declarations are not permitted).
  • The variable cannot be explicitly instantiated or implicitly or explicitly specialized.
  • The variable address cannot be taken; concept variable references are prvalues.

Those restrictions lead me to wonder if functions and variables are a good match for expressing concept definitions.  In one sense, they nicely reflect the predicate based boolean algebra of the algorithms that determine constraint satisfaction and partial ordering.  However, I expect most users won’t think about concepts in terms of those algorithms, so the expression of concepts as boolean variables and functions seems a bit of a leaky abstraction.  But, if not a function or a variable, then what should concept definitions be?  What is their quiddity?

Concept definitions serve exactly one purpose; they associate a name with a parameterized constraint-expression and make that name available for use as a constrained-type-specifier as an alternative for use of a requires-clause or in contexts where a requires-clause is not permitted, such as for placeholders in deduced variable and return types.  All other uses of concept definitions can be accommodated with constexpr functions or variables.

[Edit: Concept definitions do serve an additional purpose as described by Botond in the comments]

Concepts do not just constrain types (again, constrained-type-specifier is a misnomer); they may constrain non-type and template template parameters as well.  The idea of a named constraint that is applicable to types, non-types, and templates strikes me as quite novel and leads me to conclude that concepts are a new kind of entity and therefore deserving of a distinct syntax for definition.

I’m not alone in this opinion; concepts TS issue 6 [Issue#6] was opened following a paper [N4434] submitted for the 2015 meeting in Lenexa and proposes adopting the variable form, sans the currently required bool variable type, as a declaration of a first class concept entity.  Let’s take a look at a moderately complicated example concept defined in that form.
    template<typename T>
    concept C =
      Regular<T> &&                 // requires-clause
      requires (T t)                // requires-expression
      {
        typename T::type;           // type-requirement
        requires T::value;          // nested-requirement
      };

I like this form.  It now looks like an entity of a unique kind is being declared, the syntax is concise, the association of a name and a constraint-expression is clear, and the existing requires-clause and requires-expression productions are unchanged in both their definition and usage.  What’s not to like?

The challenge is, how do we specify it?  Overloading based on template kind and arity is desirable as demonstrated by the EqualityComparable, Swappable, and other concepts defined in the Ranges TS [Ranges].  But at present, overloading is only defined for functions.  What would it mean to add an additional overloadable entity?  Would it be permissible to declare functions and concepts with the same name, but with distinct template parameter lists?

The current concepts design allows overloading of concept and non-concept functions as a consequence of each being functions, but is this useful?  Or perhaps a recipe for confusion?  Concepts TS issue 20 [Issue#20] touches on this question.  Consider the following code.  The concept overload is usable as a constrained-type-specifier, but the other overload is not.  Both may be used to define constraints however.
    template<typename T>
    concept bool C() { return true; }
     
    template<typename T, typename U>
    constexpr bool C() { return true; }
     
    template<C T>              // Ok.
    void f1() {}
     
    template<C<int> T>         // Ill-formed, C<T,int> is not a concept.
    void f2() {}
     
    template<typename T>
      requires C<T>()          // Ok.
    void f3() {}
     
    template<typename T>
      requires C<T, int>() // Ok.
    void f4() {}

Without a strong incentive for supporting mixed concept and function overloading, my inclination is to prohibit it to avoid having to specify behavior for code like that above.

So, back to the question of how we specify concepts as a first class entity.  I don’t have a full answer for that question.  The following is a rough sketch of the kinds of changes I think would be required.

  1. Remove concept as a declaration specifier.
  2. Add a new concept-definition production to the grammar:
    concept-definition:
        template < template-parameter-list > concept concept-name = constraint-expression ;
  3. Add concept-definition as an additional alternative for template-declaration.
  4. Audit all references to template-declaration and update as needed for the concept-definition alternative.
  5. Audit all references to template-id and update as needed for references to concept definitions.
  6. Update id-expression to define the semantics for reference to a template-id that specifies a concept-name.
  7. Update clause 13 to define concept overloading and to prohibit declarations of functions and concepts with the same name in the same scope.

That last one is the big one.  It might be eased by defining concept overloading in terms of a function template with an empty or void parameter list.  If may also be possible to specify it such that an implementation is permitted to lower concept definitions to function templates in such a way that the current gcc implementation would be conforming with relatively minor changes.

Drafting the changes that would be required to the standard to specify an additional overloadable entity entails significant effort.  Would it be worth it?  I think so.  I expect concepts will be quite popular and defining them as a first class entity will enable their evolution without compromise.  Would interesting use cases be enabled by allowing them to be passed as template parameters like class and alias templates?  What else might we do with concepts if they are freed from the bounds of variables and functions?

References:

[Concepts] “C++ Extensions for concepts”, ISO/IEC technical specification 19217:2015.
http://www.iso.org/iso/home/store/catalogue_tc/catalogue_detail.htm?csnumber=64031
[Issue#6] “C++ Concepts Active Issues List (Revision 3)”, Issue 6: “Simplify concept definitions”, 2016.
http://cplusplus.github.io/concepts-ts/ts-active.html#6
[Issue#16] “C++ Concepts Active Issues List (Revision 3)”, Issue 16: “Concept and non-concept declarations of the same variable template”, 2016.
http://cplusplus.github.io/concepts-ts/ts-active.html#16
[Issue#20] “C++ Concepts Active Issues List (Revision 3)”, Issue 20: “Concept-names and overload sets with non-concept functions”, 2016.
http://cplusplus.github.io/concepts-ts/ts-active.html#20
[Issue#31] “C++ Concepts Active Issues List (Revision 3)”, Issue 31: “Constrained-type-specifiers introduce non-type placeholders”, 2016.
http://cplusplus.github.io/concepts-ts/ts-active.html#31
[N4434] Walter E. Brown, “Tweaks to Streamline Concepts Lite Syntax”, N4434, 2015.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4434.pdf
[Ranges] Eric Niebler and Casey Carter, “Working Draft, C++ Extensions for Ranges”, N4560, 2015.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4560.pdf

3 Responses to “Refining Concepts: The quiddity of concept definitions”

  1. Botond Says:

    Great article!

    One minor comment: there’s one other difference between concepts and constexpr variables/functions. A constexpr variable/function is always an atomic constraint, while a concept behaves as if its constraint-expression were “inlined” into the call site (so it can be e.g. a conjunction of constraints if the constraint-expression is a conjunction). The difference matters when deciding which of several matching overloads is “more constrained” and thus a better match.

    (P.S. “quiddity” is my word of the day :) ).

  2. Tom Honermann Says:

    Thanks, Botond! I forgot about that difference, very good point.

  3. Vicente Botet Escriba Says:

    Thanks for these posts on Concepts.

    I agree with you that we should try to see how to define concepts as an independent language entity. Saying what can be done instead of what cannot be done, should be clearer.

    I was wondering since a long time why concept partial specialization (as we have for class templates) has not been considered as an alternative. Why do we imperatively need overloading on concepts expressions?

    Because a Concept has a value? I like to see concepts as a type traits having an implicit bool value.