Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/concept_check/concept_check.htm @ 20

Last change on this file since 20 was 12, checked in by landauf, 18 years ago

added boost
File size: 12.6 KB
Line 
1<HTML>
2<!--
3  -- Copyright (c) Jeremy Siek and Andrew Lumsdaine 2000
4  --
5  -- Permission to use, copy, modify, distribute and sell this software
6  -- and its documentation for any purpose is hereby granted without fee,
7  -- provided that the above copyright notice appears in all copies and
8  -- that both that copyright notice and this permission notice appear
9  -- in supporting documentation.  We make no
10  -- representations about the suitability of this software for any
11  -- purpose.  It is provided "as is" without express or implied warranty.
12  -->
13<Head>
14<Title>Concept Check Library</Title>
15</head>
16
17<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
18        ALINK="#ff0000"> 
19<IMG SRC="../../boost.png" 
20     ALT="C++ Boost" width="277" height="86"> 
21
22<BR Clear>
23
24<H1>The Boost Concept Check Library (BCCL)</H1>
25
26<h2>
27<A NAME="sec:concept-checking"></A>
28header <a href="../../boost/concept_check.hpp">
29<tt>boost/concept_check.hpp</tt></a>
30<br>and <a href="../../boost/concept_archetype.hpp">
31<tt>boost/concept_archetype.hpp</tt></a>
32</h2>
33
34<p>
35Generic programming in C++ is characterized by the use of template
36parameters to represent abstract data types (or ``concepts'').
37However, the C++ language itself does not provide a mechanism for the
38writer of a class or function template to explicitly state what
39concept the user-supplied template argument should model (or conform
40to). The common practice is to name the template parameter after the
41required concept as a hint to the user and to state the concept
42requirements in the documentation. However, often times the
43requirements are vague, incorrect, or nonexistent, which is quite a
44problem for the user, since he or she will not know exactly what kind
45of input is expected by the template. Furthermore, the following
46problems occur:
47
48<ul>
49  <li>Compiler error messages resulting from incorrect template
50    arguments can be particularly difficult to decipher. Often times
51    the error does not point to the location of the template
52    call-site, but instead exposes the internals of the template, which
53    the user should never have to see.</li>
54
55  <li>The documented concept requirements may not fully <i>cover</i>
56   the template, meaning the user could get a compiler error even
57   though the supplied template arguments meet the documented
58   requirements.</li>
59
60  <li>The documented concept requirements may be too stringent,
61   requiring more than is really needed by the template.</li>
62
63  <li>The requirements are not explicitly stated in the code, which
64    makes the code harder to understand. Also, the code may
65    get out-of-sync with the documented requirements.</li>
66</ul>
67
68The Boost Concept Checking Library provides:
69
70<ul>
71  <li>A mechanism for inserting compile-time checks of template
72  parameters.</li>
73
74 <li>A framework for specifying concept requirements though concept
75  checking classes.</li> 
76
77 <li>A mechanism for verifying that concept requirements cover the template.</li>
78
79 <li>A suite of concept checking classes and archetype classes that
80   match the concept requirements in the C++ Standard Library.</li>
81</ul>
82
83The mechanisms use standard C++ and introduce no run-time
84overhead. The main cost of using the mechanism is in compile-time.
85
86<p>
87Any programmer writing class or function templates ought to make
88concept checking a normal part of their code writing routine. A
89concept check should be inserted for each template parameter in a
90component's public interface. If the concept is one of the ones from
91the Standard Library, then simply use the matching concept checking
92class in the BCCL. If not, then write a new concept checking class -
93after all, they are typically only a few lines long. For new concepts,
94a matching archetype class should also be created, which is a minimal
95skeleton-implementation of the concept
96
97<p>
98The documentation is organized into the following sections.
99
100<OL>
101<LI><a href="#introduction">Introduction</a></LI>
102<LI><a href="#motivating-example">Motivating Example</a></LI>
103<LI><a href="#history">History</a></LI>
104<LI><a href="#publications">Publications</a></LI>
105<LI><a href="#acknowledgements">Acknowledgements</a></LI>
106<LI><a href="./using_concept_check.htm">Using Concept Checks</a></LI>
107<LI><a href="creating_concepts.htm">Creating Concept Checking Classes</a></LI>
108<LI><a href="./concept_covering.htm">Concept Covering and Archetypes</a></LI>
109<LI><a href="./prog_with_concepts.htm" ">Programming With Concepts</a></LI>
110<LI><a href="./implementation.htm">Implementation</a></LI>
111<LI><a href="./reference.htm">Reference</a></LI>
112</OL>
113
114<p>
115<a href="../../people/jeremy_siek.htm">Jeremy Siek</a> contributed
116this library. <a href="../../people/beman_dawes.html">Beman Dawes</a>
117managed the formal review.
118
119<h2><a name="introduction">Introduction</a></h2>
120 
121A <i>concept</i> is a set of requirements (valid expressions,
122associated types, semantic invariants, complexity guarantees, etc.)
123that a type must fulfill to be correctly used as arguments in a call
124to a generic algorithm.  In C++, concepts are represented by formal
125template parameters to function templates (generic algorithms).
126However, C++ has no explicit mechanism for representing concepts ---
127template parameters are merely placeholders.  By convention, these
128parameters are given names corresponding to the concept that is
129required, but a C++ compiler does not enforce compliance to the
130concept when the template parameter is bound to an actual type.
131
132<p>
133Naturally, if a generic algorithm is invoked with a type that does not
134fulfill at least the syntactic requirements of the concept, a
135compile-time error will occur.  However, this error will not <i>per
136  se</i> reflect the fact that the type did not meet all of the
137requirements of the concept.  Rather, the error may occur deep inside
138the instantiation hierarchy at the point where an expression is not
139valid for the type, or where a presumed associated type is not
140available.  The resulting error messages are largely uninformative and
141basically impenetrable.
142
143<p>
144What is required is a mechanism for enforcing ``concept safety'' at
145(or close to) the point of instantiation.  The Boost Concept Checking
146Library uses some standard C++ constructs to enforce early concept
147compliance and that provides more informative error messages upon
148non-compliance.
149
150<p>
151Note that this technique only addresses the syntactic
152requirements of concepts (the valid expressions and associated types).
153We do not address the semantic invariants or complexity guarantees,
154which are also part of concept requirements..
155
156<h2><a name="motivating-example">Motivating Example</a></h2>
157
158We present a simple example to illustrate incorrect usage of a
159template library and the resulting error messages.  In the code below,
160the generic <tt>std::stable_sort()</tt> algorithm from the Standard
161Template Library (STL)[<a
162href="bibliography.htm#austern99:_gener_progr_stl">3</a>, <a
163href="bibliography.htm#IB-H965502">4</a>,<a
164href="bibliography.htm#stepa.lee-1994:the.s:TR">5</a>] is applied to
165a linked list.
166
167<pre>
168  <a href="./bad_error_eg.cpp">bad_error_eg.cpp</a>:
169   1  #include &lt;list&gt;
170   2  #include &lt;algorithm&gt;
171   3
172   4  int main(int, char*[]) {
173   5    std::list&lt;int&gt; v;
174   6    std::stable_sort(v.begin(), v.end());
175   7    return 0;
176   8  }
177</pre>
178
179Here, the
180<tt>std::stable_sort()</tt> algorithm is prototyped as follows:
181<pre>
182  template &lt;class RandomAccessIterator&gt;
183  void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
184</pre>
185
186Attempting to compile this code with Gnu C++ produces the following
187compiler error. The output from other compilers is listed in the
188Appendix.
189
190<pre>
191stl_algo.h: In function `void __merge_sort_loop&lt;_List_iterator
192  &lt;int,int &amp;,int *&gt;, int *, int&gt;(_List_iterator&lt;int,int &amp;,int *&gt;,
193  _List_iterator&lt;int,int &amp;,int *&gt;, int *, int)':
194stl_algo.h:1448:   instantiated from `__merge_sort_with_buffer
195  &lt;_List_iterator&lt;int,int &amp;,int *&gt;, int *, int&gt;(
196   _List_iterator&lt;int,int &amp;,int *&gt;, _List_iterator&lt;int,int &amp;,int *&gt;,
197   int *, int *)'
198stl_algo.h:1485:   instantiated from `__stable_sort_adaptive&lt;
199  _List_iterator&lt;int,int &amp;,int *&gt;, int *, int&gt;(_List_iterator
200  &lt;int,int &amp;,int *&gt;, _List_iterator&lt;int,int &amp;,int *&gt;, int *, int)'
201stl_algo.h:1524:   instantiated from here
202stl_algo.h:1377: no match for `_List_iterator&lt;int,int &amp;,int *&gt; &amp; -
203  _List_iterator&lt;int,int &amp;,int *&gt; &amp;'
204</pre>
205
206In this case, the fundamental error is that
207<tt>std:list::iterator</tt> does not model the concept of <a
208href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">
209RandomAccessIterator</a>. The list iterator is only bidirectional, not
210fully random access (as would be a vector iterator).  Unfortunately,
211there is nothing in the error message to indicate this to the user.
212
213<p>
214To a C++ programmer having enough experience with template libraries
215the error may be obvious.  However, for the uninitiated, there are several
216reasons why this message would be hard to understand.
217
218<OL>
219  <LI> The location of the error, line 6 of <tt>bad_error_eg.cpp</tt>
220    is not pointed to by the error message, despite the fact that Gnu C++
221    prints up to 4 levels deep in the instantiation stack.
222  <LI> There is no textual correlation between the error message and the
223    documented requirements for <tt>std::stable_sort()</tt> and for
224    <a
225href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">
226RandomAccessIterator</a>.
227  <LI> The error message is overly long, listing functions internal
228    to the STL that the user does not (and should not!) know or care
229    about.
230  <LI> With so many internal library functions listed in the error
231    message, the programmer could easily infer that the error is due
232    to the library, rather than to his or her own code.
233</OL>
234
235The following is an example of what we might expect from a more
236informative message (and is in fact what the Boost Concept Checking
237Library produces):
238
239<pre>
240boost/concept_check.hpp: In method `void LessThanComparableConcept
241  &lt;_List_iterator&lt;int,int &amp;,int *&gt; &gt;::constraints()':
242boost/concept_check.hpp:334:   instantiated from `RandomAccessIteratorConcept
243  &lt;_List_iterator&lt;int,int &amp;,int *&gt; &gt;::constraints()'
244bad_error_eg.cpp:6:   instantiated from `stable_sort&lt;_List_iterator
245  &lt;int,int &amp;,int *&gt; &gt;(_List_iterator&lt;int,int &amp;,int *&gt;,
246  _List_iterator&lt;int,int &amp;,int *&gt;)'
247boost/concept_check.hpp:209: no match for `_List_iterator&lt;int,int &amp;,int *&gt; &amp;
248  &lt; _List_iterator&lt;int,int &amp;,int *&gt; &amp;'
249</pre>
250
251This message rectifies several of the shortcomings of the standard
252error messages.
253
254<UL>
255<LI> The location of the error, <tt>bad_error_eg.cpp:6</tt> is
256  specified in the error message.
257<LI> The message refers explicitly to concepts that the user can look
258  up in the STL documentation (<a
259href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">
260RandomAccessIterator</a>).
261<LI> The error message is now much shorter and does not reveal
262  internal STL functions.
263<LI> The presence of <tt>concept_check.hpp</tt> and
264  <tt>constraints()</tt> in the error message alerts the user to the
265  fact that the error lies in the user code and not in the library
266  implementation.
267</UL>
268
269<h2><a name="history">History</a></h2>
270
271An earlier version of this concept checking system was developed by
272the author while working at SGI in their C++ compiler and library
273group. The earlier version is now part of the SGI STL distribution. The
274boost concept checking library differs from the concept checking in
275the SGI STL in that the definition of concept checking classes has
276been greatly simplified, at the price of less helpful verbiage in the
277error messages.
278
279<h2><a name="publications">Publications</a></h2>
280
281<ul>
282  <li><a href="http://www.oonumerics.org/tmpw00/">
283      C++ Template Workshop 2000</a>, Concept Checking</li>
284</ul>
285
286<h2><a name="acknowledgements">Acknowledgements</a></h2>
287
288The idea to use function pointers to cause instantiation is due to
289Alexander Stepanov. I am not sure of the origin of the idea to use
290expressions to do up-front checking of templates, but it did appear in
291D&amp;E[
292<a href="bibliography.htm#stroustrup94:_design_evolution">2</a>].
293Thanks to Matt Austern for his excellent documentation and
294organization of the STL concepts, upon which these concept checks
295are based. Thanks to Boost members for helpful comments and
296reviews.
297
298
299<p>
300<a href="./using_concept_check.htm">Next: Using Concept Checks</a>
301
302<br>
303<HR>
304<TABLE>
305<TR valign=top>
306<TD nowrap>Copyright &copy 2000</TD><TD>
307<A HREF="../../people/jeremy_siek.htm">Jeremy Siek</A>(<A
308HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
309Andrew Lumsdaine</A>(<A HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
310</TD></TR></TABLE>
311
312</BODY>
313</HTML> 
Note: See TracBrowser for help on using the repository browser.