Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/concept_check/prog_with_concepts.htm @ 13

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

added boost
File size: 6.2 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>Programming With Concepts</Title>
15<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
16        ALINK="#ff0000"> 
17<IMG SRC="../../boost.png" 
18     ALT="C++ Boost" width="277" height="86"> 
19
20<BR Clear>
21
22<h2><a name="programming-with-concepts">Programming with Concepts</a></h2>
23
24The process of deciding how to group requirements into concepts and
25deciding which concepts to use in each algorithm is perhaps the most
26difficult (yet most important) part of building a generic library.
27A guiding principle to use during this process is one we
28call the <i>requirement minimization principle</i>.
29
30<p>
31<b>Requirement Minimization Principle:</b> Minimize the requirements
32on the input parameters of a component to increase its reusability.
33
34<p>
35There is natural tension in this statement.  By definition, the input
36parameters must be used by the component in order for the component to
37accomplish its task (by ``component'' we mean a function or class
38template). The challenge then is to implement the component in such a
39way that makes the fewest assumptions (the minimum requirements) about
40the inputs while still accomplishing the task.
41
42<p>
43The traditional notions of <i>abstraction</i> tie in directly to the
44idea of minimal requirements. The more abstract the input, the fewer
45the requirements.  Thus, concepts are simply the embodiment of generic
46abstract data types in C++ template programming.
47
48<p>
49When designing the concepts for some problem domain it is important to
50keep in mind their purpose, namely to express the requirements for the
51input to the components.  With respect to the requirement minimization
52principle, this means we want to minimize concepts. 
53
54<!-- the following discussion does not match the Standard definition
55 of LessThanComparable and needs to be changed -Jeremy
56
57<p>
58It is important to note, however, that
59minimizing concepts does not mean simply
60reducing the number of valid expressions
61in the concept.
62For example, the
63<tt>std::stable_sort()</tt> function requires that the value type of
64the iterator be <a
65href="http://www.sgi.com/tech/stl/LessThanComparable.html">
66LessThanComparable</a>, which not only
67includes <tt>operator&lt;()</tt>, but also <tt>operator&gt;()</tt>,
68<tt>operator&lt;=()</tt>, and <tt>operator&gt;=()</tt>. 
69It turns out that <tt>std::stable_sort()</tt> only uses
70<tt>operator&lt;()</tt>.  The question then arises: should
71<tt>std::stable_sort()</tt> be specified in terms of the concept
72<a
73href="http://www.sgi.com/tech/stl/LessThanComparable.html">
74LessThanComparable</a> or in terms of a concept that only
75requires <tt>operator&lt;()</tt>?
76
77<p>
78We remark first that the use of <a
79href="http://www.sgi.com/tech/stl/LessThanComparable.html">
80LessThanComparable</a> does not really violate the requirement
81minimization principle because all of the other operators can be
82trivially implemented in terms of <tt>operator&lt;()</tt>. By
83``trivial'' we mean one line of code and a constant run-time cost. 
84More fundamentally, however, the use of <a
85href="http://www.sgi.com/tech/stl/LessThanComparable.html">
86LessThanComparable</a> does not violate the requirement minimization
87principle because all of the comparison operators (<tt>&lt;</tt>,
88<tt>></tt>, <tt><=</tt>, <tt>>=</tt>) are conceptually equivalent (in
89a mathematical sense).  Adding conceptually equivalent valid
90expressions is not a violation of the requirement minimization
91principle because no new semantics are being added --- only new
92syntax. The added syntax increases re-usability.
93
94<p>
95For example,
96the
97maintainer of the <tt>std::stable_sort()</tt> may some day change the
98implementation in places to use <tt>operator>()</tt> instead of
99<tt>operator<()</tt>, since, after all, they are equivalent.  Since the
100requirements are part of the public interface, such a change could
101potentially break client code.  If instead
102<a
103href="http://www.sgi.com/tech/stl/LessThanComparable.html">
104LessThanComparable</a> is given as the requirement for
105<tt>std::stable_sort()</tt>, then the maintainer is given a reasonable
106amount of flexibility within which to work.
107
108-->
109
110<p>
111Minimality in concepts is a property associated with the underlying
112semantics of the problem domain being represented.  In the problem
113domain of basic containers, requiring traversal in a single direction
114is a smaller requirement than requiring traversal in both directions
115(hence the distinction between <a
116href="http://www.sgi.com/tech/stl/ForwardIterator.html">
117ForwardIterator</a> and
118<a
119href="http://www.sgi.com/tech/stl/BidirectionalIterator.html">
120BidirectionalIterator</a>). The semantic difference can be easily seen
121in the difference between the set of concrete data structures that
122have forward iterators versus the set that has bidirectional
123iterators. For example, singly-linked lists would fall in the set of
124data structures having forward iterators, but not bidirectional
125iterators.  In addition, the set of algorithms that one can implement
126using only forward iterators is quite different than the set that can
127be implemented with bidirectional iterators. Because of this, it is
128important to factor families of requirements into rather fine-grained
129concepts.  For example, the requirements for iterators are factored
130into the six STL iterator concepts (trivial, output, input, forward,
131bidirectional, and random access).
132
133<p>
134<a href="./implementation.htm">Next: Implementation</a><br>
135<a href="./concept_covering.htm">Prev: Concept Covering and Archetypes</a>
136
137<br>
138<HR>
139<TABLE>
140<TR valign=top>
141<TD nowrap>Copyright &copy 2000</TD><TD>
142<A HREF="../../people/jeremy_siek.htm">Jeremy Siek</A>(<A
143HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
144Andrew Lumsdaine</A>(<A HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
145</TD></TR></TABLE>
146
147</BODY>
148</HTML> 
Note: See TracBrowser for help on using the repository browser.