8
$\begingroup$

I am lacking a background in theoretical computer science but I would have liked to understand to what kind of theoretical objects C++ concepts 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?

$\endgroup$
  • 1
    $\begingroup$ C++ programs are like Turing machines. Functions are like oracles, they just take more time. C++, like many programming languages, is like the lambda calculus. The run-time creation of functions is apparently new as of C++11. $\endgroup$ – Philip White Jul 6 '17 at 17:22
  • 6
    $\begingroup$ @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. $\endgroup$ – holf Jul 6 '17 at 18:07
  • $\begingroup$ My mistake...I followed the link but didn't read it too closely. (I had never found a need to learn/use concepts in C++ myself.) $\endgroup$ – Philip White Jul 6 '17 at 18:38
11
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – oconnor0 Jul 10 '17 at 1:58
  • $\begingroup$ @oconnor0: You are right. Concepts + templates give bounded polymorphism. I'll update my answer. $\endgroup$ – Dave Clarke Jul 10 '17 at 5:57
  • $\begingroup$ 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. $\endgroup$ – chi Jul 10 '17 at 21:28
-3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I have read a little more on concepts. (Apparently concepts are new in C++.) Of course any C++ function is going to accept a recursively enumerable language; that's trivial. Are you asserting that the mapping from concepts to r.e. languages is a bijection? This seems obviously false; if you glance at the concepts section, it says that function concepts "must consist only of a return statement, whose argument must be a constraint-expression," while when it comes to variable concepts, "the initializer must be a constraint expression." So these concepts do not sound Turing-complete to me. $\endgroup$ – Philip White Jul 6 '17 at 23:18
  • 1
    $\begingroup$ 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. $\endgroup$ – Geoffrey Irving Jul 6 '17 at 23:31
  • 1
    $\begingroup$ 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. $\endgroup$ – Geoffrey Irving Jul 6 '17 at 23:32
  • 1
    $\begingroup$ You mean constraint expressions. According to the resource, there are 9 types of constraint expressions, and each concept may use only one constraint expression. Also, representing the integers in unary is not a meaningful bijection between r.e. languages and C++ concepts. In particular, it does not preserve semantic equivalence. $\endgroup$ – Philip White Jul 6 '17 at 23:44
  • 1
    $\begingroup$ 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++. $\endgroup$ – Geoffrey Irving Jul 7 '17 at 0:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.