In the last article in this series, I mentioned that we’ve solved the problem with polymorphic lambdas and concepts, and I promised to discuss it here. So here we go!
Quick concepts review
Just like type declarations, concepts would add two kinds of type-checking to the C++ template system. To understand how, let’s first look at an ordinary C++ function:
void f(int& x);
The parameter type int constrains the type of argument that can be
passed to f: you can pass a non-const int lvalue or anything that
can be implicitly converted to one, and that’s it. If you pass the
wrong thing, say a string, you find out immediately, at the point
where it is passed:
f("hi there"); // <== Error: f requires an int, not string
This is the first kind of type checking, which results in an error
at the function’s point of use. The second kind of type
checking happens at the function’s point of definition. If the
author of f tries to write something in the body that violates the
constraints imposed by the function parameter declaration, he gets
an error right away:
void f(int& x) { x += "hello"; // <== Error: can't add int and string literal }
This separate checking of interfaces and implementations is one of
the most important features of statically-checked languages: it
allows us to partition our applications into layers with
well-defined interfaces and responsibilities. I like to use the
shorthand that it allows the user of f and its author to be
different people. The user doesn’t have to see how f is
implemented and the author of f doesn’t need to see how it is
used.
Hosed or Golden?
Unfortunately, as we know them today, templates drop both types of checking:
template <class T> void g(T& x);
At the point of use, can I call g(i), where i is an int? Well,
maybe. The real answer is, “it depends on the body of g.” Now
let’s ask the second question: at g‘s point of definition, have I
done anything illegal inside g?
template <class T> void g(T& x) { x += "hello"; }
well, that really depends on how g is called, doesn’t it? If the
argument turns out to be a vector<char>, we’re hosed. If it’s a
std::string, we’re golden. The problem is, there’s no information
in g‘s interface that tells us so.
template <class T> void g(T& x) { x += "hello"; // <== Error here } int i; g(i); // <== Error here
And that’s the main cause of the giant template error message
stacks we all know and love so well. In this case, the stack is
two levels deep, but if g calls other functions, it could go on
arbitrarily long.
Enter Concepts
One way to see concepts is as an attempt to give templates meaningful
interfaces. So for example, we could constrain g‘s interface with a
concept StringAppendable1 that represents the
ability to append a string literal using +=:
concept StringAppendable<typename T> { operator+=(T&, char const*); }; template <StringAppendable T> void g(T& x);
Now let’s ask the same questions we asked before.
Can I call
g(1)? Clearly not, and it doesn’t matter what the inside ofglooks like.Can I implement
gthis way?template <StringAppendable T> void g(T& x) { x.append("hello"); }
No, I can’t.
StringAppendabledoesn’t say there is an “append” member function onT; I have to use+=. The point is that the body ofgcan be checked against the constraints imposed by its template parameter concepts just like the body offcan be checked against the constraints imposed by its function parameter types.
Method of Constraint
So how does it work? The mechanism used in ConceptGCC, and proposed
for standardization, was actually pioneered by Jeremy Siek in the
Boost ConceptCheck library.
The idea is to come up with an “archetype” of the StringAppendable
concept: a class that has only those operations specified by
StringAppendable and no others. For example:
struct SA_archetype { operator=(SA_archetype const&) = delete; SA_archetype(SA_archetype const&) = delete; ~SA_archetype() = delete; void operator+=(char const*); };
Then, you try to instantiate g using this archetype. The resulting
function would look like this:
template <> void g<SA_archetype>(SA_archetype& x) { x.append("hello"); }
Since SA_archetype doesn’t declare an “append” member function,
the instantiation fails. Presto, you’ve checked the template body!
When you use the Boost ConceptCheck library, you have to come up with
SA_archetype manually (for the most part—the library helps a little).
The great thing about concepts-the-language-feature is that the
compiler generates the archetype internally when it sees the declaration
of StringAppendable, and it does the instantiation internally when it
sees the definition of g, before it has encountered any actual
models of the StringAppendable concept.
Depth of Constraint
Concepts look like they make things pretty simple, don’t they?
But what about this implementation of g; is it OK?
template <StringAppendable T> void g(T& x) { implementation_detail_of_g(x); }
The answer depends on whether implementation_detail_of_g can be
called with a StringAppendable. Clearly, we don’t want to specify
in our StringAppendable concept that implementation_detail_of_g
can be called: our goal is to protect g‘s clients from knowing
about its implementation details. If implementation_detail_of_g
also has concept constraints, though, we can know whether this call is
OK. For example, if we see this declaration somewhere:
template <StringAppendable T> void implementation_detail_of_g(T& x);
then we know any body defined for implementation_detail_of_g will
have been fully checked to work on StringAppendables. However, if
implementation_detail_of_g is just some ordinary unconstrained template, we
don’t know at this point whether it’s going to work out. In order to
make it possible to type-check g at its point of definition, the
concepts proposals say that implementation_detail_of_g also has to
be concept-constrained. This requirement has far-reaching
implications, as we shall see.
Sticky Business
So, back to polymorphic lambdas. The type of a polymorphic lambda
would be an ordinary struct with an templated function-call operator.
That is, it would be an unconstrained template. If you want to call
a constrained template from an unconstrained one, there’s no problem.
That’s like converting an int& to an int const&: it increases
the constraint, so it can happen automatically. If you want to call
an unconstrained template from a constrained one, though, that’s a
different story.
In C++ we generally don’t let you loosen type constraints without a
horrible, ugly piece of code that says “hey, I’m about to bypass
static checking and potentially violate the type system here…” that is
to say, a cast. To allow unconstrained templates to be called from
constrained ones, we essentially added a cast called “late_check“.
The idea was that if you had some legacy unconstrained code that you
wanted to use in a constrained context, you could wrap it in a
constrained template labeled with late_check, and the compiler
would hold off checking its body until later, when you actually
tried to use it.
For example, suppose we wanted to add concept constraints to our
function template g, above, but we weren’t ready to do all the
work to conceptify implementation_detail_of_g. Well, we could
simply label g “late_check.” That would allow g to be used by
other constrained code, but all checking would be deferred until
the time that g was actually instantiated.
late_check template <StringAppendable T> void g(T& x) { // body not checked implementation_detail_of_g(x); } ... A x; g(x); // <== g<A> checked here
This is analogous to presenting a const-correct interface, but using
const_cast internally to call some legacy function that doesn’t
mutate data, but also wasn’t declared const (this exact thing
happens all over the place in the implementation of Boost.Python).
Concepts and Lambdas in practice
Let’s look at a simple example of what the concept feature
designers faced. For example, here’s an unconstrained
std::transform implementation:
template <class InIter, class OutIter, class Op> OutIter transform( InIter first, InIter last, OutIter result, Op op) { for (;first != last; ++first, ++result) *result = op(*first); // <==== return result; }
Now concentrate on the line with the arrow. The constraints for a
conceptified version of this function would have to say (among other
things) that the result of calling an Op with the value_type of
InIter can be written into an OutIter. For the curious, that’s
expressed in the first three lines of the conceptified declaration
below:
template<InputIterator InIter, class OutIter, Callable<auto, const InIter::value_type&> Op> requires OutputIterator<OutIter, Op::result_type> && CopyConstructible<Op> OutIter transform(InIter first, InIter last, OutIter result, Op op);
If we pass a function pointer with well-defined parameter types, the compiler can easily check whether those constraints are satisfied, just by looking at the type of the function pointer.
Playing Compiler
Now, suppose you’re the compiler, and I hand you this code, which uses a hypothetical polymorphic lambda:
template<InputIterator InIter, OutputIterator OutIter> void times2(InIter first, InIter last, OutIter result) { std::transform(first, last, result, [](x){return x*2;}); }
Should it compile? How do we know whether the result of x*2 can
be written into an OutIter? We don’t even know what x is. This
looks hard…
Solving the Problem
…or so we thought. The solution turns out to be surprisingly simple:
when type-checking times2, instantiate the lambda expression on the
archetypes and see if that fits the surrounding constraints. Let’s
start by translating the hypothetical polymorphic lambda above into
the equivalent unconstrained template:
struct __lambda1 { template <class T> auto operator()(T x) const -> decltype(x*2) { return x * 2; } };
Recall that the requirements for transform say that we have to be able
to pass the InputIterator‘s value_type to the function and write
the result of that call into the OutputIterator. Well, inside of
times2, the InputIterator archetype’s value_type is another
archetype, with minimal capabilities:
struct __InputIterator_archetype { struct value_type { operator=(value_type const&) = delete; value_type(value_type const&) = delete; ~value_type() = delete; }; __InputIterator_archetype& operator++(); value_type operator*() const; // ...etc... };
Heck, we can’t even copy the value_type! But __lambda1 takes
its argument by value, which implies a copy, so that’s going to
be a problem. The body of times2 should clearly not compile.
Playing User Again
Let’s fix up our declaration of times2 to account for pass-by-value:
template<InputIterator InIter, OutputIterator OutIter> requires CopyConstructible<InIter::value_type> void times2(InIter first, InIter last, OutIter result) { std::transform(first, last, result, [](x){return x*2;}); }
Now should it compile? Well, the additional requirement on
times2 has expanded the definition of its InputIterator archetype
to include copyability of the value_type:
struct __InputIterator_archetype { struct value_type { operator=(value_type const&) = delete; value_type(value_type const&); // <=== here ~value_type() = delete; }; __InputIterator_archetype& operator++(); value_type operator*() const; // ...etc... };
so we get past the instantiation of the declaration of
__lambda1::operator(). However, since the lambda is an
unconstrained template, full checking demands that we go on to
instantiate its body, too. At that point, we find that the
value_type of the archetype has no multiplication operator
defined, and once again compilation of times2 should fail—this
time, while instantiating the body of the lambda.
We need to say two further things: first, to finish instantiating
the body of the lambda, we need to say that the value_type can be
multiplied by an int:
template<InputIterator InIter, OutputIterator OutIter> requires CopyConstructible<InIter::value_type> && requires HasMultiply<InIter::value_type, int> void times2(InIter first, InIter last, OutIter result) { std::transform(first, last, result, [](x){return x*2;}); }
and finally, to be able to pass the lambda on to transform, we’ll
need to say that the resulting type can be written into the
output iterator:
template<InputIterator InIter, class OutIter> requires CopyConstructible<InIter::value_type> && OutputIterator< OutIter, HasMultiply<InIter::value_type, int>::result_type > void times2(InIter first, InIter last, OutIter result) { std::transform(first, last, result, [](x){return x*2;}); }
If you adjust the archetypes so that all those things are true,
finally, the body of times2 can be allowed to compile. [Writing
down what the archetypes look like is left as an exercise for the
reader. The beauty of the concepts feature is that the compiler
generates the archetypes for us].
This demonstrates that we can check a constrained template that uses a polymorphic lambda. But there may be an easier way to prove to yourself that it works: just go back to the Boost ConceptCheck library method. Throw an archetype at a function template that calls another function template. They both get instantiated; if there’s a problem with the inner one, bada-bing bada-boom, you get an error. Yes, there’s a two-level template backtrace, but think about it: with a lambda used in the usual way, both levels of the backtrace would point to the same line of code.
What This Really Means
Big deal, you say? My friend, this is huge. Since a polymorphic
lambda is just an ordinary template, we can apply the same technique
to any unconstrained template we like. It means we can throw out
late_check. It means that concept-constrained templates and
unconstrained ones can interoperate freely, and that we can add a
constrained interface to any library without having to go back and
constrain its implementation.
Again, yes, the person adding the constraints will have to deal with a template error backtrace in the event that one of the unconstrained templates used in the implementation violates the constraints on the interface, but users of the constrained interface will be protected from inscrutable errors. That’s a price I’d be willing to pay for interoperability and the ability to gradually constrain things.2
What it Really, Really Means
I think there’s something much more important going on here: as you
can see from the final declaration of our times2 function, or from
the built-in transform algorithm, the buildup of concept constraints
gets pretty heavy, pretty quickly. I have a lot of sympathy for the
programmer who doesn’t want to look at these constraints all the time
(something we’ll come back to in the series’ next article). When the
author and the user of a function are different people (as on a
library boundary), the constraints offer a major benefit to everyone:
errors are detected at the earliest possible location, with users
getting comprehensible feedback and library authors getting more
assurance that their code won’t break in the field. But when I’m
calling my own code, I’d be able to choose whether I want to take the
time to constrain everything or whether I’d rather decipher an ugly
error message in case of an error.
I have a vision: that C++ could become a loose/tight language. We could have rigor and constraint where we want it, while also supporting free-form prototyping and the smooth evolution of a quick trial into production code.
Up Next
If you read my last article, the one about pythy syntax, I’m sure it
wasn’t lost on you that our times2 template has more code in its
constraints than it does in its body. There’s gotta be something we
can do about that; we’ll see if there is, next in this series.
-
This is a terrible example of a concept in the sense that it doesn’t represent any kind of meaningful abstraction. Purists will also object to the use of the addition operator for a non-commutative operation. So sue me. It’s a fine example for demonstrating the language mechanics. ↩
-
Crazy idea: we could even go so far as to allow templates with a mixture of constrained and unconstrained parameters, so you could add constraints one at a time. I’m just not sure how useful that would be, since any interaction of the constrained and unconstrained parameters would have to be treated as unconstrained. ↩
- Having it all: Pythy syntax for C++
- A Breakthrough for Concepts
No matter how long it will take; C++ will be a mathematical language (in the broad sense) at some point. That’s why I was following the “Algebraic Data Types in C++” by Sankel with much interest, a pity that nothing else was published on that direction. — Thanks for the nice article!
As fate would have it, I’ve been spending a fair amount of time with Boost Concept Checking library lately and I would make a couple of observations about this:
a) I’ve found that inserting concept checking into code and documentation simultaneously has been extremely useful in clarifying my thoughts about what I want to do. I don’t think this aspect widely appreciated. As someone noted, it IS “fun” to work with concepts as it keeps me “on track” as to what I really want the code to do as opposed to writing code and trying to fix the conceptual bugs later.
b) In the course of doing this, I wanted to check some template parameters which would be some sort of mpl types. For example I would write a meta-function which might require that the the template parameter be mpl::set<…. some list …>. The appeal of this is that when a user plugs in the wrong type of template argument he only gets one page of errors instead of the usual 50. So far so good.
c) Until it becomes obvious that mpl doesn’t implement concept checking. Damn – oh well, I need the practice anyway. So I role up my sleeves and make concepts for boost::mpl::ForwardIterator, ForwardSequence, AssociativeIterator and AssociativeSquence. This turns out to be a damn site more tricky than first meets the eye. An mpl forward iterator should support next and return another mpl forward iterator. – unless it’s not dereferencible – that is the end. This opens up another can of worms since the end iterator type is different for mpl::list, and the others. if it is dereferenciable, then the check of the result of next sets up a recursion to the end of the sequence which brings up compile time concerns as well as long error lists. Anyway, I did get manage to get this to work to where I thought it might be useful and uploaded it to the vault. so all in all this was OK – but a lot more work than I thought it was going to be.
d) Now the Archetypes. Implementing these for my concepts turned out to be beyond me. I did do it but I don’t think that they actually covered the concepts. Again, a big problem with recursive type iterators. I didn’t have confidence in my archetypes but I did “check” the concepts by instantiating them with examples of mpl::list and mpl::set instances.
After all this, I feel that I have a good understanding of the value of concepts and the way that BCC library works. I just don’t feel that it’s so obvious to use in many real cases.
I also don’t see how the Archetypes could be automatically handled by the compiler since the compiler can only see what the program wrote in the concept not what the programmer had in mind when he wrote the concept. That is, I see the Archetype as sort of a logical inverse of the concept that have to complement each other to demonstrate that the concept is correct and consistent.
I don’t know if this is interesting but there it is.
Robert Ramey
Hi Robert,
Kudos to you for throwing yourself into working with concepts so completely!
Just a few remarks:
concepts weren’t really designed for purely-compile-time notions like MPL iterators, and BCCL was never designed for that either. It doesn’t surprise me at all that you found it awkward to use BCCL for these things. To clarify what you’re up against, a runtime iterator has a type separate from its value, and you can check that type for the availability of certain operations, like
++, without actually performing those operations. An MPL iterator’s type is its value, so the compile-time check for the existence of an operation likenext<It>::typeis the same as the evaluation of that operation. A whole new paradigm for concept checking might well be needed in such situations.I believe that the number of people who will have “real cases” where they want to apply concept-checking to purely-compile-time constructs is a tiny, tiny fraction of all those who could apply concept-checking, and there are still many “real cases” that could exploit this technology in “obvious” ways.
Checking for something as specific as a specialization of
mpl::setis somewhat anti-idiomatic for code that’s doing concept checking. Normally you’d look for AssociativeSequence or something. Is that what you actually implemented?Generating archetypes from concepts is a mechanical transformation. Take two looks at
concept StringAppendableandstruct SA_Archetypedeclared above and call me in the morning if the similarities aren’t obvious to you.I realize this might be sort of off topic. But I wanted to illustrate that the idea isn’t as generally applicable as it would first seem. In particular boost documentation uses the “concept” and BCL leaves one with the impression that the application is sort of “mechanical” when in my opinion it’s not.
Things like tuples (which are the same as MPL sequences but with values) is in my experience very important to check, and fairly ubiquitous. In the generic world, it’s too easy for people not to write code that’s consistent with the abstractions.
For MPL/Fusion sequences, the problem is mostly that you should not call next if you’ve reached the end, so you need some sort of static if or a recursive definition specialized for the terminal case.
Yeah, it’s a bit worse than that. Since
next<It>::type(ornext(it)in the case of fusion) is supposed to be an Iterator too, you end up checking the whole sequence… or you realize that you have to be able to handle infinite sequences too and you bail out with an incomplete check.“it’s too easy for people not to write code that’s consistent with the abstractions.”
Right, also
it’s too easy for people to write code which is inconsistent with the abstractions and the error messages don’t help much.
I did make concepts as I described above. They seemed to work as I hoped – though I certainly had concerns about how much compile time might be affected. And I had a lot of reservations as to whether I was doing it right. I uploaded the code to a trac item as a suggested enhancement to the mpl library. I’ll leave to the others to determine whether this has any value beyond my ?narrow? application.
I did conclude that it was doable – but that it would be better if the concepts built into the library at the start rather than trying to add them on afterwards. That is, I felt that I could have made it work better if I had been willing to stick my fingers into the mpl library which is not ever going to happen. Actually this exercise has led me to a few conclusions.
Hi Dave, I’m not an expert in Concepts but I’ve been following the developments because I’ve been in tons of cases where it would have been so much helpful…
Anyway, after reading the ConceptC++ Tutorial you posted, I have a question about the complexity of the code to write when using Concepts as a template class writer :
If I write a class using Concepts, like this
template<std::CopyConstructible T> requires Addable<T>, Assignable<T> class MyContainer { public: void process(); T grab(); void clear(); // ... };Then I have to type all this ?:
template<std::CopyConstructible T> requires Addable<T>, Assignable<T> void MyContainer<T>::process() { //... } template<std::CopyConstructible T> requires Addable<T>, Assignable<T> T MyContainer<T>::grab() { //... } template<std::CopyConstructible T> requires Addable<T>, Assignable<T> void MyContainer<T>::clear() { //... }If yes, then do you have any idea of new syntax or maybe typedef/using-like expression that would help just limit so much repetition and garbage? I’ve been working on a project with a lot of abuse of templates (that’s one orthogonal problem) that was unreadable because of similar repetitions in the code.
I was thinking about something to “sum up” the template parameters and requirements. I don’t have any idea of syntax but maybe a definition of template with parameters and requirements using the “using” expression, then used with a special syntax everywhere you need to repeat it (like the type name of this type’s member function implementations).
What do you think?
As a side note, I’m even more interested in the Modules feature development. I’d like to ask those questions as you seem to know a lot about it:
No, don’t worry; you don’t need to type all that
You might try downloading a copy of conceptgcc just to see for yourself.
As for modules, I’ve never quite understood the strong connection people seem to want to make between modules and DLLs, so if there’s something there I’m probably blind to it. The development of modules is going on in the Clang mainline codebase, and I’ll try to get its author to post an article here about it soon. For more information on a shorter timescale I’d try asking on the clang mailing lists or IRC channel.
Perfect, I’ll check this. Thanks.
Thanks, didn’t know it was in the mainline codebase…
I think the thing with dlls/so and modules is that, from what I remember reading in the last proposal (2006 or 2007), there would be a generated file gathering the public informations from an object file (maybe gathered into one file per project) that would be used for compilation and linking of other binaries. In combination with public/private code, it looks like a perfect solution to not expose symbols of a so/dll without having to divide the code itself into, for example, pimpl idioms.
But maybe it’s just that the Modules concept isn’t just clear enough yet to people not in the commitee (like me).
Oh, well, yeah, you can tie symbol exposure to module-public-ness and then you avoid having to do it with declspecs or attributes. So in that respect I guess it would address some issues of dynamic libraries. But anyone wanting to fully integrate those into C++ still has to deal with load/initialization order and especially unload-ability, i.e. the dynamic part
, with which modules don’t help.
Oh ok, you mean there is still no way to manage “plugins” dynamically, like the boost::extension proposal (http://boost-extension.redshoelace.com/docs/boost/extension/index.html).
So my understanding seems correct: modules could help with organising binaries/libraries/dependencies loaded on the executable beginning. However for plugins/extensions/modules-loaded-on-the-fly you still need something like boost::extension.
I’m not familiar with that work, but from this page I’d be inclined to say that library is trying to do way more than I imagine would be included in any standard extensions for the support of shared libraries.
It is a little bit of topic. I am not an expert in concepts, but I really like the idea of constraints. However, the way it is presented is to confuse people. The main reason for concepts is to offer a way to define a more powerful “point of truth” or elements of a “contract” that could be checked statically between the interface users and its developers.
void f( int ); spells out, something that can be passed to operator int() can be passed to f, and the ‘f’ developers can then pass the thing to something that an ‘int’ can be passed to.
template< typename T > f( T ); says that anything can be passed to f, and the developers can then pass the thing to anything. The point of truth for the user and developers happens in lay function signatures (but it didn’t have to be). I guess it just happened that way, and it is fine.
The basic question that a static checker (compiler) has to ask is ‘can A be passed to B’, yes or no? It is about passage rules. Concepts are invented to spell out the rules to the compiler. IMO, the definition of passage rules as some “archetypes” (a type but not quite) could be useful but I’d like have something more straightforward, something that I could use right where the interface (point of truth) is specified, if I don’t care about reusing my rules anywhere else…
template< typename T > void f( T )
What about following for the syntax
template< typename T =
{
![ T operator=( const T& ) ]; //must not be copy constructible
T operator*( T, int); //must be multipliable by int
}
![…] – means NOT
This feature is intended to enforce the constraints on the interface users first of all. The interface developers are free to add more constraints internally of course. The details need to be worked out by the language experts, but I think the main idea is clear.
Hi Gene, thanks for posting.
I like your characterization of concepts as providing a more powerful “point of truth.” I’m not sure if you understood, but in the concepts language feature proposals, archetypes are an implementation/specification detail of the language. You don’t ever write them, see them, or use them.
Thanks for the clarification, Dave. I thought that you could define your own concepts (archetypes) too. Anyway, I guess my main point is to have a flexible syntax for defining constraints as part of function signatures by using the existing language features as much as possible, for example operator +(…) for the constraint of being passable to ‘+’.
Oh, you can certainly define your own concepts. Concepts aren’t exactly the same thing as archetypes, but since the archetypes are derived by the compiler from the concepts, I can understand why you might think of them as equivalent. As for using operator+ in that way… great minds think alike, because that’s what the concepts proposals already do! Check out the ConceptC++ tutorial for an example that defines the
Addableconcept.Hi Dave, sorry for the confusion about concepts and archetypes. I think I get it now. Thanks! I looked at the tutorial. I do like it but I still think that I’d be useful to be able define concepts in-line and without involving any headers of external ‘concept’ definitions. Also, I am concerned about this quote from the tutorial, “Concepts are a little bit like class templates.”. I think it’s confusing. I may then ask if I can assign one concept to another a “little” or multiply them.
Hi Dave, Just to give some perspective on what’s possible: Concepts and type inference work very well together in Haskell (they are called type classes there), so it’s not an either/or proposition. Of course, type inference in C++ is drastically limited.
The two also work together in imperative languages like Chapel. The person who’s working on Chapel concepts is the same Jeremy Siek who worked on C++ concept proposal.
Personally, I think programming with concepts is more fun. If forces you to create meaningful abstractions for your template parameters, which makes reasoning about them so much easier. And, as a bonus, the compiler can verify them at a much earlier stage in development.
Hi Bartosz,
I’m aware of Jeremy’s work, thanks, and of type classes (did they ever get support for associated types in Haskell?). In fact, Jeremy was the one who told me about the difficulty of debugging programs written in Haskell that rely heavily on type inference.
I feel kind of dumb asking this, but with all the languages you mentioned it’s not entirely clear… more fun than what? Programming without them?
Dave, you probably know Haskell better than I do. My comment was for the sake of this (very interesting) discussion. Not everybody knows that concepts have been explored in other languages before they popped up in C++.
Haskell approaches associated types from a slightly different angle: they are additional type parameters to a (multi-parameter) type class. But since mutli-parameter type classes sometimes lead to ambiguities in type inference, Haskell added functional dependencies, which essentially tell the compiler how to infer some of the types. For instance:
specifies that the type c is uniquely inferred from types a and b. Multi-parameter type classes and functional dependencies are not part of Haskell 98 but most compilers support them.
Programming with concepts is more fun than programming without them.
They have associated data types too, as you can see on that page: http://www.haskell.org/haskellwiki/GHC/Type_families#An_associated_data_type_example
@Alp: I had a look at this article. I think it’s an example of different nomenclature used in different languages. I wouldn’t call “
GMap k” an associated type — it’s really a function from types to types (* -> *). It requires one more type parameter,v, to become a type. It’s more like associated function than associated type.Yeah sure, but you can also have something of kind * there (i.e, an associated type).
I’m not sure how this would work. The syntax
type T :: *doesn’t work. Also I don’t think this would have any advantage over passing the associated type as a class parameter.Thanks for the update on associated types, Bartosz. BTW, I don’t really know Haskell at all! I just know a few things about it. P.S. fun counts for a lot, in my book!
If the body of __lambda1::operator() is invalid, then it won’t be instantiated (SFINAE). The error you’d get if the lambda-body was inconsistent with the template constraints would be “cannot find overload for __lambda(Type_of_X)”
This is essentially the same as name resolution when concepts are involved: if the arguments do not match the concept requirements, the overloads are discarded from name resolution, and you get a similar message.
The good implementation of a polymorphic lambda is with SFINAE that constrains its declaration to only be valid when its definition is; this is making the best use of the fact that you cannot declare but not define a lambda-function. This is trivial to do when the definition of a polymorphic lambda is a single return statement; it’s more difficult when considering arbitrary statements. C++ would need some kind of statement-to-expression translation.
Hi Mathias!
Yeah… because of SFINAE on the
decltype(…)part of the signature.I guess I’m not sure what point you’re making here. Are you suggesting that compilers would be unable to offer a better error message in the presence of concepts just because the underlying mechanism for detecting the problems already has an error response?
I’m not convinced that SFINAE is what we want here… in fact, I think I’m convinced it’s not what we want. Finding out that there’s no suitable overload is not nearly so enlightening as learning the particular operations inside the lambda that caused the problem. SFINAE is great when there’s an overload set involved, but when it’s clear what function implementation you’re trying to invoke it’s usually better to let instantiation failure cause an error.
Hmm, neat idea: when there’s an error due to SFINAE taking the only candidate out of the overload set, we could have compilers go on to report the details of the substitution failure. I wonder if any compilers are already doing that?
What I meant to say is that, since concepts give similar error messages to SFINAE (but I may be wrong about that, haven’t tested ConceptGCC in a while as I said in another part of the thread), then that kind of error message should be good enough for integration with concepts.
None that I ever heard of.
FWIW, I am told that the Clang team is looking favorably on this request.
The < and > characters have been interpreted as HTML. I try again:
template < class InIter, class OutIter, class F > OutIter transform( InIter first, InIter last, OutIter result, Op op)
should be:
template < class InIter, class OutIter, class Op > OutIter transform( InIter first, InIter last, OutIter result, Op op)
Thanks for the fix; applied!
The point you made about separation of concerns is becoming pivotal in my understanding of static vs. dynamic typing. In essence I might say:
Static typing is about more than just compile-time error checking and taking advantage of optimization opportunities. It also creates a bridge between the designer and the user, so that the user can only use types and functions in a manner the designer intended, and the designer can make assumptions about the nature of the data he’s working with.
In dynamic languages — as with any kind of type-erased programming such as templates without concept checking in C++ — this bridge is removed and it becomes possible for users to misuse the designer’s code, or for the designer to misuse the data passed in, without any kind of checking or validation required until the moment such misuse causes a problem.
I really don’t find concepts all that interesting, it just seems like something the compiler should be capable of doing without user help. Kind of annoying that we didn’t get polymorphic lambda already just because of stupid concepts:(
How about adding some of the D language features to C++ to make templates easier to work with
static_if mixins
etc..
Now I’m going to point back at the analogy between concepts and function signatures in my “brief intro to concepts” at the beginning of the article. Let’s just map what you’re saying back into non-template land for a moment. Function signatures then also “seem like something the compiler should be capable of doing without user help.” In other words, function signatures are redundant information. I’m serious, they are!
Well, there are languages without function signatures. They’re either like Python—fully dynamic languages where you get no help from the compiler to ensure correctness at the time you write the function—or a statically-checked language with “type inference” (and, usually, optional signatures)… which are subject to the same kind of inscrutable backtraces from the type system as we get from templates… only, in reverse. And here’s the problem: without that “redundant information,” the compiler has nothing against which it can check your function definition until its point of use. Furthermore, it has nothing against which it can check your use of the function independently from its implementation.
So you have a choice between tying your interface to your implementation—so you can never re-implement a function without breaking its clients—or putting redundant information somewhere. You can put it in the documentation, as we do today with templates, and as Python programmers do today with everything, and you will ship incorrect and/or underspecified code. Or, you can give the compiler the information it needs to check that your stated requirements (“this argument must be [convertible to] an
int“) are consistent with both the interface and the implementation of the function.And that, my friend, is exactly what concepts do, at the template level. So, no, without concepts-in-the-language, the compiler doesn’t have the “redundant” information it needs to do the same checks, and the same kind of results are not in fact possible.
I still don’t see how using something like this..
struct SA_archetype { operator=(SA_archetype const&) = delete; SA_archetype(SA_archetype const&) = delete; ~SA_archetype() = delete;
};
Is any different than the compiler attempting to compile the code, noticing the class doesn’t supply a += operator, and spitting out an error.
Are concept error messages really that much better? I guess I don’t really know what a concept error message would look like.. but wouldn’t they still have to spit out most of the template chain, else how would you know where the error originated?
I guess it does tell you what the type must implement at the signature, which could be useful at times, but eh.. still seems like small potatoes compared to polymorphic lambda or other language features C++ is lacking.
Also a solid IDE/compiler should be capable of displaying what any type must implement to be passed to a template.
Like hover over the template signature, and it could simply generate something akin to “SA_archetype” in a little overlay window.
Take a look at this and then this for a concrete idea of what happens to error messages with concepts.
But that said, there’s one thing that should be clear to you by now (or I haven’t explained things vey well): with concepts, your template bodies are checked at their point of definition, against the requirements you put in the signature. Without concepts, they can only be checked at the point of use, against the type you happen to instantiate them on. That type (assuming you do get around to instantiating the template) typically has many capabilities that aren’t in the template’s documented requirements, so it doesn’t ensure your implementation is staying within the limits that it should. You just can’t do that check accurately without declared concept requirements.
I think the main point of all this is to help localize where the error is. As things stand now (without concepts), your compiler will tell you that there is a problem, but it isn’t able to tell you where the mistake is. It could be that the caller passed the wrong type of object, or it could be that the implementation called the wrong method. The compiler has no way of knowing the difference because it doesn’t understand what was intended.
In C++, we can build type inference on top of SFINAE (albeit it only works on expressions for now, not general statements).
I don’t see how the error messages you get from this are any different from what you get with concepts, from the library user point of view.
From the library author point of view, though, concepts are useful because they allow to check that what you write is consistent with concepts that you have formalised and given a name to.
Have you played with ConceptGCC? That should give you some idea of what’s possible in the realm of error messages. Keep in mind that it’s a prototype and not everything works or works well—but it does give good error messages.
I did quite some time ago, and it was a lot of “cannot find overload for f(X, Y), candidates are: …” I don’t have a computer I can install it on right now, but I don’t see how it could give anything significantly better for function templates. For class templates, however, it should be pretty good. I don’t remember what it said.
Would you happen to have some examples?
Here‘s one. Yes, it does tell you there’s no matching function, but it also tells you that the problem is that your list iterators are not random access. There are also some good examples in this paper (search for “message”).
There is quite a bit of support for adding something like static_if. Mixins on the other hand, from the D documentation, appear to be disguised macros.
static_if can already be implemented through monomorphic lambdas.
I would like to see such code, this sounds amazing. I once wrote static_if and it worked within templates, but it only worked with GCC because of the way GCC implicitly instantiates local classes within function templates: It delays the instantiation of their member functions (“operator()” of a lambda) until used, which not all compilers do. I tested on EDG, which does not delay instantiation of members of local classes within function templates. Clang behaves like GCC in this regard. Don’t know about MSVC.
I meant it can be done with the technique that you showed me; indeed there is some problem on fully standard-conforming compilers.
To delay instantiation, the only way is to have local templates. These should definitely be in the next C++ standard, and they’re independent from polymorphic lambdas.
Hi Dave,
One of the objections to Concepts in C++11 was compile time speed. (being awful) The second was that by tightening the interface to match the implementation, we were standardizing the algorithm. And that the internal algorithm was seen as a QOI, and shouldn’t be standardized.
As for your idea, if it does indeed work out, I will be really happy about using it! Even with the new language Lambdas, there still seems a place for the boost library version.
Hi Gary,
I’m not sure what you want me to say about those objections or how they’re connected—except in a vague way—to the subject of the article, but…
It isn’t really legitimate to draw any conclusions about compile-time speed yet. ConceptGCC was a prototype and not representative of the speed we could expect with a production compiler. A legit objection would be that we don’t have a production-quality implementation that could prove it would be fast enough. That said, I’m not worried, in part because I think it can be fast as designed and in part because I think having module support—which I believe is coming—will make it even faster.
That second objection—no offense—just sounds bogus to me. The interface to STL algorithms is already tight. The fact that some of the tightness can only be represented in documentation today doesn’t give implementors of those algorithms any leeway that would evaporate due to translating documented constraints into compiler-enforced constraints.
Re 2: “Bogusity”
Well I was at one of the standards meetings where the objection to having to spell out every operation necessary in the interface, whether or not it was actually used was brought up by Bill. Sorry, but I don’t recall the algorithm that was under discussion at the time.
On the other hand, as a user of an algorithm, I’d prefer to know what the minimal interface that was necessary. And I’d prefer the error message at the call site, which is what concepts gives us.
Also have you seen this paper? http://www.jot.fm/issues/issue_2011_01/article10.pdf
All due respect to Bill (and I have lots), the information has got to be spelled out somewhere, somehow. But part of the point of concepts (not the language feature, but the idea) is to cluster together common groups of requirements so you don’t have to write out every single operation. Instead you just write
ForwardIterator.Hadn’t seen the paper, no. It looks very interesting!
If I understand it correctly, if you are using concepts, you look through the function and check for any use of the template arguments. e.g. has a copy constructor, is string append able etc. Isn’t the compiler capable of doing that himself? Isn’t it possible to automatically generate these concepts by the compiler, and let him thereby generate proper error messages?
Hi Tobias,
I’m not sure exactly what you’re suggesting; some example would surely help.
He says that the compiler should be able to project the missing code over the input types as requirements to that type.
He basically asks what I am asking in this post: http://cpp-next.com/archive/2011/12/a-breakthrough-for-concepts/comment-page-1/#comment-1799
Hmm, is that right, Tobias? It doesn’t sound like the same question to me. Anyway, if not, I’m happy to try to answer if you can clarify.
Tobias seems to be suggesting that compilers can synthesize concept-like constraints from the completely instantiated templates, and then tell the user what’s wrong with their arguments without dumping the entire template stack in the process. In other words, “no implementation of operator*(InIter::value_type = T, int) found” doesn’t need to tell you the code context that asked for it. I suspect those errors, while shorter, would actually be harder to understand in practice than the current very verbose things.
However, it does suggest a useful tool for library developers: a concept-generator. A developer should be able to write an unconstrained template, and then point this tool at it. The tool should analyze what operations are applied to the template arguments, and spit out the concept describing that set of operations, which the developer can then plop into the declaration.
A more refined version of the tool could recognize common things like CopyConstructible and mention them by name instead of repeating them. It could also do a sort of common subexpression identification on generated concepts in a file, to merge them and ask the developer to name the concept described. That suggests a concept refactoring toolkit that could split and merge different parts of concept declarations while checking that all of the affected things were still OK.
That’s one possible explanation of Tobias’ intent among several that occurred to me as well, but I didn’t want to guess
That’s a very interesting idea for a tool. It would definitely have to support refactoring and clustering of requirements into concepts, though. You really don’t want all algorithms constrained by their minimal syntactic requirements.
See this for such a tool.
Funny, I actually spent the summer working with the first author of that paper. Neat.
It’s seems to me the ability of compilers (or external tools) to generate constraints from the code is greately overestimated. Imagine you have a code as simple as “a >> b;”, where a and b are two template instantiation. What concept should compiler (tool) have generated? Is that Shiftable and say b is convertible to int, or maybe Streamable and a is convertible to stream, or something else? “a >> b” is just an expression that can be satisfied with various concepts. In fact, we want to go beyond error messages and use concepts for proper overloading, and only the code writer (not a compiler) can specify the concepts for that.
Concepts will be a very important addition to c++, but before seeing that in working compilers, could we please have template error messages improved, by reporting the point of use as the error position before reporting a definition as the error position?
In other words, when we have a function like this:
template <class T> void g(T& x) { x += "hello"; }and code like this:
Then, the error could be this:
Could we please have this improved form of error reporting?
Hi Achilleas,
A couple of things about this: first, by all means, if you think you know how to improve error reporting, do it! Clang is pretty easy to hack on, and already has quite sophisticated machinery for good error messages. The great thing about a change like that is, if you can make a real improvement, no new standard is needed and all vendors can go ahead and implement it right away. Second, though, I don’t think it’s as simple as you seem to. In many cases the type involved in the error doesn’t appear directly in the top-level function signature at all; it might be that the result of calling
foo()on the result of dereferencing an iterator that is the result of callingbegin()on one of the arguments doesn’t supportoperator+=. So,Well, it might be true that in many cases the type involved in the error does not appear directly in the top-level function signature, but I think the compiler can always follow up as to what produced what and reach the top-level function.
For example, if the code is like this:
template <class T> void g(T &t) { t.begin()->foo() += "hello"; }The compiler could do the following:
a) see that the type returned by foo(), let’s say type T1, does not define operator += (const char *).
b) see that the operator -> is invoked on the return type of begin(); let’s say type T::value_type.
c) see that begin() is invoked on the type T.
So, if the usage of the above function is:
class Foo { int &foo(); } list<Foo> data; g(data);The compiler would see this:
a) the type ‘int’ does not have operator += (const char *).
b) operator -> returns type T::value_type, which is type ‘Foo’.
c) begin() is invoked on type T.
Then, the error report would be:
I may checkout clang sometime. Thanks for the tip.
I had in mind a deeper instantiation stack, where begin happens one level down, the dereference happens two levels down, and the call to foo three levels down. But, maybe what you are thinking of makes sense and I just don’t get it yet. Implement it! Let’s try it! Maybe it’ll be awesome.
I think that, no matter how deep the stack is, if the error is related to a type of the top-level function, then an error report can be produced that involves the top-level function.
I think this because the type relations are all there in the code – a compiler would simply have to follow back up the chain of code. Compilers already do this, because they already report the top-level function where the error happens (msvc, for example). It is just a matter of choosing the appropriate elements from the error report to make it better.
Okay… but how do you know that the top-level function is where the error report belongs? If I am working on a function template and I do something wrong, and I get a bunch of error reports pointing at the non-templated part of the program (maybe that’s just
main()!), I’m not sure it’s going to help. That could even add a whole bunch of irrelevant information. But again, there’s no substitute for trying it and seeing what happens.The error report could start with the outermost function that caused the error, and report all intermediate calls that lead up to actual error inside the template. The innermost error position could also be reported in the first line.
Something like this (assuming the error was in function g3(), called by function g2(), called by function g()):
As a developer of the template code, you would know that the error was at file foo3.hpp, inside the template code, and as a user of the template library, you would know that you used the wrong type somewhere, that led to an error inside a template.
Isn’t that exactly what we get today from every C++ compiler?
If you don’t like the order in which the error appears, try a different compiler (they vary in that regard) or try STLFilt for gcc with the
/hdr:LDoption.Just out of curiosity, any reason your sample code opt not to use type_traits<Iter>::value_type?
Yeah:
type_traitsare essentially a hack that we use today because we don’t have concepts. With concepts, you access associated types through the concept itself, e.g.InputIterator<InIter>::value_type, or, if it’s unambiguous,InIter::value_type, or, if it’s still unambiguous, justvalue_type.I think the concept
HasMultiply<OutIter value_type, int>should beHasMultiply<InIter::value_type, int>. Or am I missing something?Quite so! Thanks very much for the fix!
Oh…, template’s less than and greater than escape didn’t work correctly in my comment. Let me retry. I mean, should HasMultiply be HasMultiply<InIter::value_type, int> ?
Look above; I fixed it for you
So when can we expect to see this in a working compiler, since C++0x was just standardized does that mean it will be 5-10 years:(
Fortunately, when you’ll get to see a feature in a working compiler can be independent of the pace of standardization. I can’t make any promises of course, but I hope we’ll get a chance to find out how well this works soon, in ConceptClang.
Hi Dave,
thanks for another great article on C++Next!
Since I have not delved too deeply in C++ concepts in the past two years, I have not much to offer to substantiate this, and thus might be completely misled, but my gut feeling is that late_check can’t, or at least shouldn’t, be dropped.
For polymorphic lambdas the technique you described is perfectly reasonable and works out as expected, but for generic unconstrained templates (or function overloads) I see problems:
If an unconstrained template has specializations (partial or full) or a function has overloads they can’t be checked against the archetype.
To apply the technique to templates with specializations a, possibly large, number of alternative constraint sets would have to be added to the calling/surrounding structure making it a burden to implement and maintain.
Also, if an unconstrained template or a function is part of a third party library, applying the technique you described would leak information about the implementation details of said code to the signature of the embedding piece of code. For lambdas this is perfectly valid as they are an actual part of the self-authored code. But for third party libraries I might want to be able to express the set of constraints my piece of code has and explicitly defer checking unconstrained code using late_check.
Am I missing something that negates these and other, similar issues?
Best regards, Kimon
Hi Kimon,
You make some good points. However, point 1 existed for fully constrained templates: specializations and overloads make it possible to create errors that can only be detected at the point of instantiation. So this is nothing new. Concepts give you an almost-but-not-quite-bulletproof check at the point of definition, but you still have to do typechecking again at the point of instantiation to weed out those cases. A related thing might still be an issue, though: if there’s no primary template, there might be nothing to check against. There are a number of ways to handle that, e.g. defer all checking to instantiation time (and issue a warning as a matter of QOI).
I’m not sure what you mean about point 2. Are you talking about a constrained template with specializations calling an unconstrained template, or a constrained template calling an unconstrained template with specializations, or…? An example would help.
On point 3… I was one of the first people to raise the leaking of implementation details as an issue for constrained templates. I’m not sure what kind of detail you have in mind, but I was thinking of things involving little metaprograms:
So
gis missing a requirement that sayssome_metafunctionneeds to be instantiable withT. This is a real issue, and I’m out of time to write about it just now, but there are several ways of looking at it…Thanks for writing!