[Boost-commit] svn:boost r54574 - sandbox/committee/LWG/proposals

Subject: [Boost-commit] svn:boost r54574 - sandbox/committee/LWG/proposals
From: dave_at_[hidden]
Date: 2009-07-01 22:41:39

Author: dave
Date: 2009-07-01 22:41:38 EDT (Wed, 01 Jul 2009)
New Revision: 54574
URL: http://svn.boost.org/trac/boost/changeset/54574

Log:
add taxonomy of concepts,maps paper
Added:
   sandbox/committee/LWG/proposals/taxonomy-of-concepts-and-maps.rst   (contents, props changed)
Text files modified: 
   sandbox/committee/LWG/proposals/Makefile |     5 ++++-                                   
   1 files changed, 4 insertions(+), 1 deletions(-)

Modified: sandbox/committee/LWG/proposals/Makefile
==============================================================================
--- sandbox/committee/LWG/proposals/Makefile	(original)
+++ sandbox/committee/LWG/proposals/Makefile	2009-07-01 22:41:38 EDT (Wed, 01 Jul 2009)
@@ -1,2 +1,5 @@
 exported-concept-maps.html: exported-concept-maps.rst exported-concept-maps.css
-	rst2html.py --stylesheet=exported-concept-maps.css --embed-stylesheet exported-concept-maps.rst exported-concept-maps.html
\ No newline at end of file
+	rst2html.py --stylesheet=exported-concept-maps.css --embed-stylesheet exported-concept-maps.rst exported-concept-maps.html
+
+taxonomy-of-concepts-and-maps.html: taxonomy-of-concepts-and-maps.rst exported-concept-maps.css
+	rst2html.py --stylesheet=exported-concept-maps.css --embed-stylesheet taxonomy-of-concepts-and-maps.rst taxonomy-of-concepts-and-maps.html
\ No newline at end of file

Added: sandbox/committee/LWG/proposals/taxonomy-of-concepts-and-maps.rst
==============================================================================
--- (empty file)
+++ sandbox/committee/LWG/proposals/taxonomy-of-concepts-and-maps.rst	2009-07-01 22:41:38 EDT (Wed, 01 Jul 2009)
@@ -0,0 +1,379 @@
+=======================================
+A Taxonomy of Concepts and Concept Maps
+=======================================
+
+:Authors: Dave Abrahams <dave_at_[hidden]> and Doug Gregor <doug.gregor_at_[hidden]>
+:Number:  xxxx=xx-xxxx
+:Date: 2009-07-01
+
+This paper introduces classifies concepts and concept maps into three
+categories that will allow us to discuss the impliciations of various
+proposed design changes.
+
+Three Kinds of Concepts
+=======================
+
+These are the three basic categories of concepts.
+
+Syntactic Concepts
+------------------
+
+Syntactic concepts such as ``HasPlus`` and ``Callable`` represent purely structural
+information about types::
+
+  auto concept HasPlus<typename T, typename U> { 
+      typename result_type; 
+      result_type operator+(const T&, const U&);
+  } 
+
+such concepts have two main uses:
+
+1. preserving backward compatibility while constraining legacy
+   templates whose requirements have been written in syntactic terms.
+   For example, the C++03 definition of ``std::inner_product`` taking
+   four arguments is as follows:
+
+   ::
+
+     template <class InputIterator1, class InputIterator2, class T> 
+     T inner_product(InputIterator1first1, InputIterator1last1, 
+     InputIterator2first2, T init); 
+
+   :Effects: Computes its result by initializing the accumulator
+     ``acc`` with the initial value ``init`` and then modifying it
+     with ``acc = acc + (*i1) * (*i2)`` for every iterator ``i1`` in
+     the range [``first``, ``last``) and iterator ``i2`` in 
+     the range [``first2``, ``first2 + (last - first)``) in order. 
+
+   :Requires: ``T`` must meet the requirements of CopyConstructible
+     (20.1.3) and Assignable (23.1) types
+
+   The ideal signature for C++0x would probably be something like::
+
+    template <InputIterator Iter1, InputIterator Iter2, Iter1::value_type T> 
+    requires SemiRing<Iter1::value_type> 
+      && SameType<Iter1::value_type, Iter2::value_type>
+    T inner_product(Iter1 first1, Iter1 last1, Iter2 first2, T init);
+
+   but that would add quite a few requirements, many of them subtle,
+   to those implied by the C++03 specification.  In C++0x, to maintain
+   the same requirements, the signature must be written as::
+
+    template <InputIterator Iter1, InputIterator Iter2, MoveConstructible T> 
+    requires HasMultiply<Iter1::reference, Iter2::reference> 
+      && HasPlus<T, HasMultiply<Iter1::reference, Iter2::reference>::result_type> 
+      && HasAssign<T, 
+          HasPlus<T, 
+            HasMultiply<Iter1::reference, Iter2::reference>::result_type
+          >::result_type
+        > 
+    T inner_product(Iter1 first1, Iter1 last1, Iter2 first2, T init);
+
+2. constraining components such as the operators in Boost.Lambda, whose
+   sole purpose is syntax adaptation:
+
+   .. parsed-literal::
+
+     // The function object generated by an expression such as _1 + 42
+     template <typename Lambda, typename RHS>
+     struct add_right
+     {
+         template <typename ...Args>
+            requires Callable<Lambda, Args...>
+              && **HasPlus<Callable<Lambda, Args...>::result_type, RHS>**
+         auto operator()(Args ...args) -> decltype(f(args...) + r)
+         {
+             return f(args...) + r;
+         }
+
+         add_right(Lambda r, RHS const& r)
+           : f(f), r(r)
+
+         Lambda f;
+         RHS const& r;
+     };
+
+Syntactic concepts indicate nothing more than structural properties of
+types, which are perfectly detectable by the compiler, and thus should
+always be ``auto``.  They tend to be highly granular, so the size of
+this category of concepts is bounded by the grammar of the core
+language: there are only so many individual syntactic components.  
+
+As you can see from the first example above, syntactic concepts are
+often associated with generic functions whose documentation
+essentially exposes implementation details, and as such their use is
+discouraged.  Sean Parent has gone so far as to label them “partial
+concepts,” and the committee has agreed on the ``Has``\
+*SyntacticFeature* naming convention to distinguish them from concepts
+with semantic implications.
+
+Foundational Concepts
+---------------------
+
+Foundational concepts have low complexity and a single agreed-upon
+syntactic structure and semantics.  This category includes concepts
+like ``CopyAssignable``, that capture the usual meaning of core language
+constructs; like ``SemiRing``, that reflect well-known mathematical
+ideas; and like ``Swappable``, whose operations have
+broadly-established syntax and conventional meaning.
+
+Note that ``SemiRing``, mentioned above, might not quite fit the
+criteria today, since there is no widely-accepted C++ syntax for
+producing the additive and multiplicative identity elements.  The
+usual mathematical syntaxes are “0” and “1” respectively, and a
+corresponding C++ syntax should be established.  User-defined literals
+and ``constexpr`` may make a suitable convention feasible.
+
+Although foundational concepts represent an accepted convention,
+syntactic properties are not an airtight criterion by which to
+correctly identify them.  In c++std-lib-23956, Chris Jefferson writes:
+
+.. epigraph::
+
+  I have a type I use regularly where ``operator<`` does not define a
+  total ordering (but it defines a very natural operation). On
+  occasion, people have given this type to ``std::sort``, and expected it
+  to work, instead their program tends to crash in unpredictable ways.
+  
+  I had hoped that concepts were going to help me sort this out, but
+  at the moment they do not, as there is no way to mark my type as not
+  satisfying the auto concept ``LessThanComparable``.
+
+The expectation to be protected from such mistakes is consistent with
+the C++ tradition of protecting against accident rather than
+deliberate circumvention. [#cpppl3e]_ Nonetheless, these
+concepts should generally be declared ``auto`` because the normal
+interpretation of the combined syntactic elements is so widespread
+that convenience outweighs danger.  A separate mechanism (such as
+deleted concept maps) may be needed to assert that a type with a
+common syntax does not fit the usual semantic assumptions.
+
+A large proportion of foundational concepts are covered by the
+standard library.  Our experience shows that widespread agreement on
+syntax and semantics for new concepts takes a long time to develop, so
+we don't expect new foundational concepts to proliferate quickly.
+
+
+Nontrivial Concepts
+-------------------
+
+Nontrivial concepts have generally higher complexity and cannot be
+easily satisfied without significant coding effort.  Examples in this
+category include `graph concepts`_, and the standard iterator and
+container concepts.  
+
+.. _graph concepts: http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/graph_concepts.html
+
+We expect a large majority of concepts written outside the standard
+library to be nontrivial, since:
+
+a. The number of granular syntactic concepts is bounded
+b. The standard library already supplies most syntactic concepts
+c. The standard library already supplies many foundational concepts
+d. New foundational concepts don't come along every day.
+
+In our opinion, the arguments for making nontrivial concepts ``auto``
+are not nearly so compelling as for syntactic and foundational
+concepts.  We explain why below.
+
+Three Kinds of Concept Maps
+===========================
+
+Whether explicitly written or implicitly generated, concept maps can
+be classified by their intended purpose:
+
+Intentional Mapping
+-------------------
+
+Intentional concept maps occur when a programmer designs a class with
+the goal of modeling a particular concept.  For example, I might
+design a type to model ``EqualityComparable`` or
+``BidirectionalIterator``.  Because ``EqualityComparable`` is an
+``auto`` concept, an intentional map may be automatically generated
+when the type is passed where ``EqualityComparable`` is required.  In
+the case of the non-``auto`` concept ``BidirectionalIterator``, an
+intentional map must be written by the author of the model.  We call
+both maps “intentional” because they are intended by the author of the
+model.  
+
+Intentional ``concept_maps``\ s are traditionally empty, since a
+programmer modeling a concept in C++03 must write the required
+definitions of associated functions in class or namespace scope, and
+people are accustomed to doing things that way.
+
+In C++0x, associated functions can be written in the scope of the
+``concept_map`` itself::
+
+    template <class T, class U>
+    struct pair
+    {
+        // Just the data, M'am
+        T first;
+        U second;
+    };
+
+    template <CopyConstructible T, CopyConstructible U>
+    concept_map CopyConstructible<pair<T,U> >
+    {
+        pair<T,U>::pair(pair<T,U> const& rhs)
+          : first(rhs.first), second(rhs.second) {}
+        pair<T,U>::pair(T const& first, U const& second)
+          : first(first), second(second) {}
+    };
+
+    template <DefaultConstructible T, DefaultConstructible U>
+    concept_map DefaultConstructible<pair<T,U> >
+    {
+        pair<T,U>::pair() {}
+    };
+
+    template <Swappable T, Swappable U>
+    concept_map Swappable<pair<T,U> >
+    {
+        swap(pair<T,U>& lhs, pair<T,U>& rhs) 
+        { 
+            using std::swap; 
+            swap(lhs.first,rhs.first); 
+            swap(lhs.second,rhs.second);
+        }
+    };
+
+    …etc…
+
+This style, sometimes called “Mat's Mechanism,” [#mat]_ has a number
+of expressive advantages over the “traditional” approach:
+
+* It groups the operations associated with modeling a concept
+  together, within the concept map.
+
+* It makes explicit and visible the relationship between the
+  properties of the model's template arguments and of the model itself
+  (even if the concept is ``auto``).  For example, a ``pair<T,U>`` is
+  ``CopyConstructible`` if both ``T`` and ``U`` are
+  ``CopyConstructible``.
+
+* When combined with exported concept maps as proposed by
+  N2918=09-0108, it can substantially reduce verbosity (even when the
+  concepts are ``auto``), because the requirements associated with a
+  group of such operations are not repeated.  For example, when
+  declared in the traditional way, the part of the ``std::pair`` interface
+  given in the first concept map above looks like:
+
+  .. parsed-literal::
+
+    template <class T, class A>
+    struct pair
+    {
+        …
+        **requires CopyConstructible<T> && CopyConstructible<U>**
+        pair(pair<T,U> const& rhs)
+          : first(rhs.first), second(rhs.second) {}
+
+        **requires CopyConstructible<T> && CopyConstructible<U>**
+        pair(T const& first, U const& second)
+          : first(first), second(y) {}
+        …
+    };
+
+  The difference is more dramatic when there are defaults involved.
+  The part of the ``std::list`` interface needed to make it satisfy
+  ``LessThanComparable`` looks like::
+
+    template <LessThanComparable T, class A> 
+    bool operator< (const list<T,A>& x, const list<T,A>& y); 
+    template <LessThanComparable T, class A> 
+    bool operator> (const list<T,A>& x, const list<T,A>& y); 
+    template <LessThanComparable T, class A> 
+    bool operator>=(const list<T,A>& x, const list<T,A>& y); 
+    template <LessThanComparable T, class A> 
+    bool operator<=(const list<T,A>& x, const list<T,A>& y); 
+
+  which can be reduced to::
+
+    template <LessThanComparable T, class A>
+    export concept_map LessThanComparable<list<T,A> >
+    {
+        bool operator<(const list<T,A>& x, const list<T,A>& y);
+    };
+
+  (without exported concept maps, the intended public interface would
+  be unavailable except in constrained contexts)
+
+Of course, it remains to be seen whether either of these styles, or
+some other one, will be preferred in the long run, but it is worth
+noting that intentional maps need not be empty.
+
+We expect a vast majority of concept maps to be of the intentional
+variety.  That expectation is strongest where nontrivial concepts are
+concerned, since the likelihood of accidentally creating a type whose
+syntax and semantics exactly match those of a nontrivial concept is
+very low.
+
+Post-hoc Mapping
+----------------
+
+A types can be mapped to a concept *post-hoc* when the type's creator
+had no specific intention to model the concept in question.  Post-hoc
+mapping can happen implicitly, as when a type happens to provide the
+expected syntax and semantics for an ``auto`` concept like
+``EqualityComparable``, or explicitly, via a ``concept_map``.
+
+While most concept mapping is intentional, post-hoc mapping is still
+an important feature because it allows built-in and 3rd-party types to
+model both non-``auto`` concepts and ``auto`` concepts not designed
+with those types in mind.  These use cases demand that the most
+general syntax for ``concept_map``\ s be non-intrusive.
+
+Adaptive Mapping
+----------------
+
+Adaptative mapping is used to fulfill a concept's requirements that
+are already expressed, but in a different form.  For example, one can
+use adaptive mapping to represent the edge connectivity of a graph
+using the nonzero elements of a sparse matrix (a technique used in
+efficiently solving systems of equations), or an iterator over
+integers using an actual ``int``::
+
+  concept_map RandomAccessIterator<int>
+  {
+      int const& operator*(int const& x) { return x; }
+      int operator[](int const& x, std::size_t n) { return x + n; }
+      // int already supplies the other operations
+  };
+
+An adaptive ``concept_map`` is always explicitly written.  Syntax
+adaptation is most commonly associated with post-hoc mapping, but can
+be done intentionally as part of Mat's Mechanism.
+
+The Full Grid
+=============
+
+This is our analysis of how these categories of concepts and mappings
+combine:
+
++--------------------+--------------------+--------------------+--------------------+
+|            Concept:|     Syntactic      |    Foundational    |     Nontrivial     |
+|                    |                    |                    |                    |
+|             Mapping|                    |                    |                    |
++====================+====================+====================+====================+
+|            Adaptive|rare, explicit,     |rare, explicit,     |rare, explicit,     |
+|                    |nonempty            |nonempty            |nonempty            |
++--------------------+--------------------+--------------------+--------------------+
+|            Post-Hoc|usually implicit and|common, usually     |rare, usually       |
+|                    |empty               |implicit and empty  |explicit and        |
+|                    |                    |                    |nonempty            |
++--------------------+--------------------+--------------------+--------------------+
+|         Intentional|moderately rare,    |very common, usually|common, usually     |
+|                    |usually implicit and|implicit and empty  |explicit and empty  |
+|                    |empty               |                    |                    |
++--------------------+--------------------+--------------------+--------------------+
+
+
+-----
+
+.. [#cpppl3e] Bjarne Stroustrup, *The C++ Programming Language, Special
+  Edition*, section 10.2.2, page 226
+
+.. [#mat] Thanks to Mat Marcus for describing this style, which he
+  discovered during some research work done with Jakko Jarvi
+  using ConceptGCC.