<p>C++ concepts map to recursively enumerable languages.  Since the C++ type system is Turing complete, any property of types that can be interrogated during template instantition (size, parameters, etc.) can be run through an arbitrary program simulated in the type system. </p>

CC BY-SA 3.0
2017-07-06T23:31:00.143Z
Constant expressions are Turing complete, so yes: it's a bijection.  Formalizing that requires being explicit about encodings of types; a statement that doesn't is that the set of concepts that represent subsets of the types void, C<void>, C<C<void>>, ... representing the integers in unary is exactly the R.E. languages.
Geoffrey Irving
CC BY-SA 3.0
2017-07-06T23:32:51.093Z
Of course, practical compilers have computation limits when evaluating constant expressions, but if those considerations are taken into account the answer is that there is a finite set of concepts.  Presumably that isn't the answer requested.
Geoffrey Irving
CC BY-SA 3.0
2017-07-07T00:42:42.260Z
No, I meant constant expressions.  According to the link in the question, this is entry 4 in the list of 9 types of constraints.  However, most of the other 9 are also Turing complete: e.g., it is Turing complete to decide whether a type is convertible to another in C++.
Geoffrey Irving
CC BY-SA 3.0
2017-07-07T03:00:45.343Z
http://matt.might.net/articles/c++-template-meta-programming-with-lambda-calculus.  A Google search turns up many more.  For the implicit conversation case, search for SFINAE.
Geoffrey Irving
CC BY-SA 3.0
2017-07-06T22:42:12.963Z
2017-07-06T22:42:12.963Z
Geoffrey Irving
<p>From a programming language theory perspective, as opposed to the computability perspective other answers and comments have offered, C++ templates combined with concepts correspond to <a href="https://en.wikipedia.org/wiki/Bounded_quantification" rel="noreferrer">bounded polymorphism or constrained genericity</a>. Concepts themselves correspond to the constraints or bounds placed on a type.</p>

<p>A template is type-level function, parameterised by type that are constrained by a concept to implement a particular interface. When the template is applied to a type satisfying that concept, a new type results. </p>

<p>Templates+concepts are analogous to generics in Java, Scala or Eiffel. They differ from templates in earlier C++ because they allow constraints on the type parameters to be specified and checked, whereas C++ templates did not allow that. The benefit is better static checking that the program after applying the template will be well typed.</p>

<p>A good reference is Pierce, Benjamin C. (2002). <em>Types and Programming Languages</em>. MIT Press, Chapter 26: Bounded quantification. </p>

CC BY-SA 3.0
2017-07-10T01:58:08.473Z
C++ templates have type restrictions built in to them, creating a form of structural typing, because a type must only have some set of defined operations (implicit in the template definition) to satisfy the type checker. Concepts appear to do much the same thing but allow names to be associated with those sets of behavior (a form of nominal typing) and thus provide a way to produce earlier and better error messages. I also don't think concepts are type to type functions. The linked description describes them as type predicates - or type to boolean functions.
oconnor0
CC BY-SA 3.0
2017-07-10T05:57:56.600Z
@oconnor0: You are right. Concepts + templates give bounded polymorphism. I'll update my answer.
Dave Clarke
CC BY-SA 3.0
2017-07-10T21:28:26.387Z
I am not sure I agree with this. Even sans concepts, C++ templates and parametric polymorphism seem to be only very vaguely related to me. A polytyped term is type checked so to guarantee that it will work on all its possible instances. Java generics have that (despite Java breaks parametricity). C++ templates instead employ "SFINAE", where types are not checked until instantiation time, which makes them far from universal types to me.
chi
CC BY-SA 3.0
2017-07-07T05:09:31.310Z
2017-07-10T05:59:49.633Z
2017-07-10T05:59:49.633Z
Dave Clarke
<p>I am lacking a background in theoretical computer science but I would have liked to understand to what kind of theoretical objects C++ <a href="http://en.cppreference.com/w/cpp/language/constraints" rel="noreferrer">concepts</a> corresponds to. Basically, C++ concepts allow to define a set of types that satisfy a list of constraints. So, from a theoretical standpoint, what C++ concepts correspond, or roughly correspond (and in that case what are the differences), to?</p>

CC BY-SA 3.0
2017-07-06T18:07:36.583Z
@PhilipWhite I think you miss the point of the question. The OP is not asking for a theoretical explanation of various concepts of C++ but for a theoretical explanation of a construction of C++ called concept. I am not knowledgeable enough in PL to answer the question but from what I understand, concepts are some kind of mechanism to restrict polymorphism. I do not know if such mechanisms have been already studied formally but it looks like a reasonable mechanism to add to a type system.
holf
<pl.programming-languages><type-theory><algebra><ct.category-theory>
What kind of theoretical object corresponds to a C++ concept?
Vincent
# What kind of theoretical object corresponds to a C++ concept?

(Asked by: username_0 on 2017-07-06)

I am lacking a background in theoretical computer science but I would have liked to understand to what kind of theoretical objects C++ [concepts](http://en.cppreference.com/w/cpp/language/constraints) corresponds to. Basically, C++ concepts allow to define a set of types that satisfy a list of constraints. So, from a theoretical standpoint, what C++ concepts correspond, or roughly correspond (and in that case what are the differences), to?

**Tags:** pl.programming-languages, type-theory, algebra, ct.category-theory
> **Comments:**
> **username_1**: @PhilipWhite I think you miss the point of the question. The OP is not asking for a theoretical explanation of various concepts of C++ but for a theoretical explanation of a construction of C++ called concept. I am not knowledgeable enough in PL to answer the question but from what I understand, concepts are some kind of mechanism to restrict polymorphism. I do not know if such mechanisms have been already studied formally but it looks like a reasonable mechanism to add to a type system.  

---

## 2 answers

### Answer by username_3 on 2017-07-07. Score: 12 | Accepted answer

From a programming language theory perspective, as opposed to the computability perspective other answers and comments have offered, C++ templates combined with concepts correspond to [bounded polymorphism or constrained genericity](https://en.wikipedia.org/wiki/Bounded_quantification). Concepts themselves correspond to the constraints or bounds placed on a type.

A template is type-level function, parameterised by type that are constrained by a concept to implement a particular interface. When the template is applied to a type satisfying that concept, a new type results.

Templates+concepts are analogous to generics in Java, Scala or Eiffel. They differ from templates in earlier C++ because they allow constraints on the type parameters to be specified and checked, whereas C++ templates did not allow that. The benefit is better static checking that the program after applying the template will be well typed.

A good reference is Pierce, Benjamin C. (2002). *Types and Programming Languages*. MIT Press, Chapter 26: Bounded quantification.

> **Comments:**
> **username_4**: C++ templates have type restrictions built in to them, creating a form of structural typing, because a type must only have some set of defined operations (implicit in the template definition) to satisfy the type checker. Concepts appear to do much the same thing but allow names to be associated with those sets of behavior (a form of nominal typing) and thus provide a way to produce earlier and better error messages. I also don't think concepts are type to type functions. The linked description describes them as type predicates - or type to boolean functions.  
> **username_3**: @oconnor0: You are right. Concepts + templates give bounded polymorphism. I'll update my answer.  
> **username_5**: I am not sure I agree with this. Even sans concepts, C++ templates and parametric polymorphism seem to be only very vaguely related to me. A polytyped term is type checked so to guarantee that it will work on all its possible instances. Java generics have that (despite Java breaks parametricity). C++ templates instead employ "SFINAE", where types are not checked until instantiation time, which makes them far from universal types to me.  

---

### Answer by username_2 on 2017-07-06. Score: -2

C++ concepts map to recursively enumerable languages. Since the C++ type system is Turing complete, any property of types that can be interrogated during template instantition (size, parameters, etc.) can be run through an arbitrary program simulated in the type system.

> **Comments:**
> **username_2**: Constant expressions are Turing complete, so yes: it's a bijection.  Formalizing that requires being explicit about encodings of types; a statement that doesn't is that the set of concepts that represent subsets of the types void, C<void>, C<C<void>>, ... representing the integers in unary is exactly the R.E. languages.  
> **username_2**: Of course, practical compilers have computation limits when evaluating constant expressions, but if those considerations are taken into account the answer is that there is a finite set of concepts.  Presumably that isn't the answer requested.  
> **username_2**: No, I meant constant expressions.  According to the link in the question, this is entry 4 in the list of 9 types of constraints.  However, most of the other 9 are also Turing complete: e.g., it is Turing complete to decide whether a type is convertible to another in C++.  
> **username_2**: http://matt.might.net/articles/c++-template-meta-programming-with-lambda-calculus.  A Google search turns up many more.  For the implicit conversation case, search for SFINAE.  

---

