No 'Concepts' in C++0x

At the July 2009 Frankfurt meeting of the ISO C++ Standards Committee (WG21) [ ISO ], the 'concepts' mechanism for specifying requirements for template arguments was 'decoupled' (my less-diplomatic phrase was 'yanked out'). That is, 'concepts' will not be in C++0x or its standard library. That - in my opinion - is a major setback for C++, but not a disaster; and some alternatives were even worse.

I have worked on 'concepts' for more than seven years and looked at the problems they aim to solve much longer than that. Many have worked on 'concepts' for almost as long. For example, see (listed in chronological order):

• Bjarne Stroustrup and Gabriel Dos Reis: 'Concepts - Design choices for template argument checking'. October 2003. An early discussion of design criteria for 'concepts' for C++. [ Stroustrup03a ]
• Bjarne Stroustrup: 'Concept checking - A more abstract complement to type checking'. October 2003. A discussion of models of 'concept' checking. [ Stroustrup03b ]
• Bjarne Stroustrup and Gabriel Dos Reis: 'A concept design' (Rev. 1). April 2005. An attempt to synthesize a 'concept' design based on (among other sources) N1510, N1522, and N1536. [ Stroustrup05 ]
• Jeremy Siek et al.: Concepts for C++0x. N1758==05-0018. May 2005. [ Siek05 ]
• Gabriel Dos Reis and Bjarne Stroustrup: 'Specifying C++ Concepts'. POPL06. January 2006. [ Reis06 ]
• Douglas Gregor and Bjarne Stroustrup: Concepts. N2042==06-0012. June 2006. The basis for all further 'concepts' work for C++0x. [ Gregor06a ]
• Douglas Gregor et al.: Concepts: Linguistic Support for Generic Programming in C++. OOPSLA'06, October 2006. An academic paper on the C++0x design and its experimental compiler ConceptGCC . [ Gregor06b ]
• Pre-Frankfurt working paper (with 'concepts' in the language and standard library): 'Working Draft, Standard for Programming Language C++'. N2914=09-0104. June 2009. [ Frankfurt09 ]
• B. Stroustrup: Simplifying the use of concepts. N2906=09-0096. June 2009. [ Stroustrup09 ]

It need not be emphasized that I and others are quite disappointed. The fact that some alternatives are worse is cold comfort and I can offer no quick and easy remedies.

Please note that the C++0x improvements to the C++ features that most programmers see and directly use are unaffected. C++0x will still be a more expressive language than C++98, with support for concurrent programming, a better standard library, and many improvements that make it significantly easier to write good (i.e., efficient and maintainable) code. In particular, every example I have ever given of C++0x code (e.g., in 'Evolving a language in and for the real world: C++ 1991-2006' [ Stroustrup07 ] at ACM HOPL-III [ HOPL ]) that does not use the keywords 'concept' or 'requires' is unaffected. See also my C++0x FAQ [ FAQ ]. Some people even rejoice that C++0x will now be a simpler language than they had expected.

'Concepts' were to have been the central new feature in C++0x for putting the use of templates on a better theoretical basis, for firming-up the specification of the standard library, and a central part of the drive to make generic programming more accessible for mainstream use. For now, people will have to use 'concepts' without direct language support as a design technique. My best scenario for the future is that we get something better than the current 'concept' design into C++ in about five years. Getting that will take some serious focused work by several people (but not 'design by committee').

What happened?

'Concepts', as developed over the last many years and accepted into the C++0x working paper in 2008, involved some technical compromises (which is natural and necessary). The experimental implementation was sufficient to test the 'conceptualized' standard library, but was not production quality. The latter worried some people, but I personally considered it sufficient as a proof of concept.

My concern was with the design of 'concepts' and in particular with the usability of 'concepts' in the hands of 'average programmers'. That concern was shared by several members. The stated aim of 'concepts' was to make generic programming more accessible to most programmers [ Stroustrup03a ], but that aim seemed to me to have been seriously compromised: Rather than making generic programming more accessible, 'concepts' were becoming yet another tool in the hands of experts (only). Over the last half year or so, I had been examining C++0x from a user's point of view, and I worried that even use of libraries implemented using 'concepts' would put new burdens on programmers. I felt that the design of 'concepts' and its use in the standard library did not adequately reflect our experience with 'concepts' over the last few years.

Then, a few months ago, Alisdair Meredith (an insightful committee member from the UK) and Howard Hinnant (the head of the standard library working group) asked some good questions relating to who should directly use which parts of the 'concepts' facilities and how. That led to a discussion of usability involving many people with a variety of concerns and points of view; and I eventually - after much confused discussion - published my conclusions [ Stroustrup09 ].

To summarize and somewhat oversimplify, I stated that:

• 'Concepts' as currently defined are too hard to use and will lead to disuse of 'concepts', possibly disuse of templates, and possibly to lack of adoption of C++0x.
• A small set of simplifications [ Stroustrup09 ] can render 'concepts' good-enough-to-ship on the current schedule for C++0x or with only a minor slip.

That's pretty strong stuff. Please remember that standards committee discussions are typically quite polite, and since we are aiming for consensus, we tend to avoid direct confrontation. Unfortunately, the resulting further (internal) discussion was massive (hundreds of more and less detailed messages) and confused. No agreement emerged on what problems (if any) needed to be addressed or how. This led me to order the alternatives for a presentation in Frankfurt:

• 'fix and ship'

  Remaining work: remove explicit 'concepts', add explicit refinement, add 'concept'/type matching, handle 'concept' map scope problems
  Risks: no implementation, complexity of description
  Schedule: no change or one meeting

• 'Yank and ship'

  Remaining work: yank (core and standard library)
  Risks: old template problems remain, disappointment in 'progressive' community ('seven year's work down the drain')
  Schedule: five years to 'concepts' (complete redesign needed) or never

• 'Status quo'

  Remaining work: details
  Risks: unacceptable programming model, complexity of description (alternative view: none)
  Schedule: no change

I and others preferred the first alternative ('fix and ship') and considered it feasible. However, a large majority of the committee disagreed and chose the second alternative ('yank and ship', renaming it 'decoupling'). In my opinion, both are better than the third alternative ('status quo'). My interpretation of that vote is that given the disagreement among proponents of 'concepts', the whole idea seemed controversial to some, some were already worried about the ambitious schedule for C++0x (and, unfairly IMO, blamed 'concepts'), and some were never enthusiastic about 'concepts'. Given that, 'fixing concepts' ceased to be a realistic option. Essentially, all expressed support for 'concepts', just 'later' and 'eventually'. I warned that a long delay was inevitable if we removed 'concepts' now because in the absence of schedule pressures, essentially all design decisions will be re-evaluated.

Surprisingly (maybe), there were no technical presentations and discussions about 'concepts' in Frankfurt. The discussion focused on timing and my impression is that the vote was decided primarily on timing concerns.

Please don't condemn the committee for being cautious. This was not a 'Bjarne vs. the committee fight', but a discussion trying to balance a multitude of serious concerns. I and others are disappointed that we didn't take the opportunity of 'fix and ship', but C++ is not an experimental academic language. Unless members are convinced that the risks for doing harm to production code are very low, they must oppose. Collectively, the committee is responsible for billions of lines of code. For example, lack of adoption of C++0x or long-term continued use of unconstrained templates in the presence of 'concepts' would lead to a split of the C++ community into separate sub-communities. Thus, a poor 'concept' design could be worse than no 'concepts'. Given the choice between the two, I too voted for removal. I prefer a setback to a likely disaster.

Technical issues

The unresolved issue about 'concepts' focused on the distinction between explicit and implicit 'concept' maps (see [ Stroustrup09 ]):

1. Should a type that meets the requirements of a 'concept' automatically be accepted where the 'concept' is required (e.g. should a type X that provides +, -, *, and / with suitable parameters automatically match a 'concept' C that requires the usual arithmetic operations with suitable parameters) or should an additional explicit statement (a 'concept' map from X to C) that a match is intentional be required? (My answer: Use automatic match in almost all cases).
2. Should there be a choice between automatic and explicit 'concepts' and should a designer of a 'concept' be able to force every user to follow his choice? (My answer: All 'concepts' should be automatic).
3. Should a type X that provides a member operation X::begin() be considered a match for a 'concept' C<T> that requires a function begin(T) or should a user supply a 'concept' map from T to C? An example is std::vector and std::Range. (My answer: It should match).

The answers 'status quo before Frankfurt' all differ from my suggestions. Obviously, I have had to simplify my explanation here and omit most details and most rationale.

I cannot reenact the whole technical discussion here, but this is my conclusion: In the 'status quo' design, 'concept' maps are used for two things:

1. To map types to 'concepts' by adding/mapping attributes
2. To assert that a type matches a 'concept'.

Somehow, the latter came to be seen an essential function by some people, rather than an unfortunate rare necessity. When two 'concepts' differ semantically, what is needed is not an assertion that a type meets one and not the other 'concept' (this is, at best, a workaround - an indirect and elaborate attack on the fundamental problem), but an assertion that a type has the semantics of the one and not the other 'concept' (fulfills the axiom(s) of the one and not the other 'concept').

For example, the STL input iterator and forward iterator have a key semantic difference: you can traverse a sequence defined by forward iterators twice, but not a sequence defined by input iterators; e.g., applying a multi-pass algorithm on an input stream is not a good idea. The solution in 'status quo' is to force every user to say what types match a forward iterator and what types match an input iterator. My suggested solution adds up to: If (and only if) you want to use semantics that are not common to two 'concepts' and the compiler cannot deduce which 'concept' is a better match for your type, you have to say which semantics your type supplies; e.g., 'my type supports multi-pass semantics'. One might say, 'When all you have is a 'concept' map, everything looks like needing a type/'concept' assertion.'

At the Frankfurt meeting, I summarized:

• Why do we want 'concepts'?

  To make requirement on types used as template arguments explicit
  Precise documentation
  Better error messages
  Overloading

Different people have different views and priorities. However, at this high level, there can be confusion - but little or no controversy. Every half-way reasonable 'concept' design offers that.

• What concerns do people have?

  Programmability
  Complexity of formal specification
  Compile time
  Run time

My personal concerns focus on 'programmability' (ease of use, generality, teachability, scalability) and the complexity of the formal specification (40 pages of standards text) is secondary. Others worry about compile time and run time. However, I think the experimental implementation (ConceptGCC [ Gregor06b ]) shows that run time for constrained templates (using 'concepts') can be made as good as or better than current unconstrained templates. ConceptGCC is indeed very slow, but I don't consider that fundamental.

When it comes to validating an idea, we hit the traditional dilemma. With only minor oversimplification, the horns of the dilemma are:

• 'Don't standardize without commercial implementation'
• 'Major implementers do not implement without a standard'

Somehow, a detailed design and an experimental implementation have to become the basis for a compromise.

My principles for 'concepts' are:

• Duck typing

  The key to the success of templates for GP (compared to OO with interfaces and more).

• Substitutability

  Never call a function with a stronger precondition than is 'guaranteed'.

• 'Accidental match' is a minor problem

  Not in the top 100 problems.

My 'minimal fixes' to 'concepts' as present in the pre-Frankfurt working paper were:

• 'Concepts' are implicit/auto

  To make duck typing the rule.

• Explicit refinement

  To handle substitutability problems.

• General scoping of 'concept' maps

  To minimize 'implementation leakage'.

• Simple type/'concept' matching

  To make vector a range without redundant 'concept' map

For details, see [ Stroustrup09 ].

No C++0x, long live C++1x

Even after cutting 'concepts', the next C++ standard may be delayed. Sadly, there will be no C++0x (unless you count the minor corrections in C++03). We must wait for C++1x, and hope that 'x' will be a low digit. There is hope because C++1x is now feature complete (excepting the possibility of some national standards bodies effectively insisting on some feature present in the formal proposal for the standard). 'All' that is left is the massive work of resolving outstanding technical issues and comments.

A list of features and some discussion can be found on my C++0x FAQ [ FAQ ]. Here is a subset:

• atomic operations
• auto (type deduction from initializer)
• C99 features
• enum class (scoped and strongly typed enums)
• constant expressions (generalized and guaranteed; constexpr)
• defaulted and deleted functions (control of defaults)
• delegating constructors
• in-class member initializers
• inherited constructors
• initializer lists (uniform and general initialization)
• lambdas
• memory model
• move semantics; see rvalue references
• null pointer (nullptr)
• range for statement
• raw string literals
• template alias
• thread-local storage (thread_local)
• unicode characters
• uniform initialization syntax and semantics
• user-defined literals
• variadic templates
• and libraries:
• improvements to algorithms
• containers
• duration and time_point
• function and bind
• forward_list a singly-liked list
• future and promise
• garbage collection ABI
• hash_tables; see unordered_map
• metaprogramming and type traits
• random number generators
• regex a regular expression library
• scoped allocators
• smart pointers; see shared_ptr, weak_ptr, and unique_ptr
• threads
• atomic operations
• tuple

Even without 'concepts', C++1x will be a massive improvement on C++98, especially when you consider that these features (and more) are designed to interoperate for maximum expressiveness and flexibility. I hope we will see 'concepts' in a revision of C++ in maybe five years. Maybe we could call that C++1y or even 'C++y!'

References

[FAQ] Bjarne Stroustrup, 'C++0x - the next ISO C++ standard' (FAQ), available from: http://www.research.att.com/%7Ebs/C++0xFAQ.html

[Frankfurt09] 'Working Draft, Standard for Programming Language C++', a pre-Frankfurt working paper, June 2009, available from: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2914.pdf

[Gregor06a] Douglas Gregor and Bjarne Stroustrup, June 2006, 'Concepts', availabe from: http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2006/n2042.pdf

[Gregor06b] Douglas Gregor, Jaakko Jarvi, Jeremy Siek, Bjarne Stroustrup, Gabriel Dos Reis and Andrew Lumsdaine, October 2006, 'Concepts: Linguistic support for generic programming in C++', available from: http://www.research.att.com/~bs/oopsla06.pdf

[HOPL] Proceedings of the History of Programming Languages conference 2007, available from: http://portal.acm.org/toc.cfm?id=1238844

[ISO] The C++ Standards Committee - http://www.open-std.org/jtc1/sc22/wg21/

[Reis06] Gabriel Dos Reis and Bjarne Stroustrup, January 2006, 'Specifying C++ concepts', available from: http://www.research.att.com/~bs/popl06.pdf

[Siek05] Jeremy Siek, Douglas Gregor, Ronald Garcia, Jeremiah Willcock, Jaakko Jarvi and Andrew Lumsdaine, May 2005, 'Concepts for C++0x', available from: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1758.pdf

[Stroustrup03a] Bjarne Stroustrup and Gabriel Dos Reis, October 2003, 'Concepts - Design choices for template argument checking', available from: http://www.research.att.com/~bs/N1522-concept-criteria.pdf

[Stroustrup03b] Bjarne Stroustrup, October 2003, 'Concept checking - A more abstract complement to type checking', available from: http://www.research.att.com/~bs/n1510-concept-checking.pdf

[Stroustrup05] Bjarne Stroustrup and Gabriel Dos Reis, April 2005, 'A concept design (Rev. 1)' available from: http://www.research.att.com/~bs/n1782-concepts-1.pdf

[Stroustrup07] Bjarne Stroustrup, May 2007, 'Evolving a language in and for the real world: C++ 1991-2006', available from: http://www.research.att.com/~bs/hopl-almost-final.pdf

[Stroustrup09] Bjarne Stroutstrup 'Simplifying the use of concepts'. Available from: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2906.pdf