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?
$\begingroup$
$\endgroup$
3
-
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$– user1338Commented Jul 6, 2017 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$– holfCommented Jul 6, 2017 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$– user1338Commented Jul 6, 2017 at 18:38
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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.
answered Jul 7, 2017 at 5:09
-
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$– oconnor0Commented Jul 10, 2017 at 1:58
-
$\begingroup$ @oconnor0: You are right. Concepts + templates give bounded polymorphism. I'll update my answer. $\endgroup$ Commented Jul 10, 2017 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$– chiCommented Jul 10, 2017 at 21:28
$\begingroup$
$\endgroup$
7
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.
-
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$– user1338Commented Jul 6, 2017 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$ Commented Jul 6, 2017 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$ Commented Jul 6, 2017 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$– user1338Commented Jul 6, 2017 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$ Commented Jul 7, 2017 at 0:42