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

Subject: [Boost-commit] svn:boost r54701 - sandbox/committee/LWG/proposals
From: dave_at_[hidden]
Date: 2009-07-05 23:27:57

Author: dave
Date: 2009-07-05 23:27:57 EDT (Sun, 05 Jul 2009)
New Revision: 54701
URL: http://svn.boost.org/trac/boost/changeset/54701

Log:
More

Text files modified: 
   sandbox/committee/LWG/proposals/taxonomy-of-concepts-and-maps.rst |   166 ++++++++++++++++++++++++++++----------- 
   1 files changed, 120 insertions(+), 46 deletions(-)

Modified: sandbox/committee/LWG/proposals/taxonomy-of-concepts-and-maps.rst
==============================================================================
--- sandbox/committee/LWG/proposals/taxonomy-of-concepts-and-maps.rst	(original)
+++ sandbox/committee/LWG/proposals/taxonomy-of-concepts-and-maps.rst	2009-07-05 23:27:57 EDT (Sun, 05 Jul 2009)
@@ -6,9 +6,12 @@
 :Number:  xxxx=xx-xxxx
 :Date: 2009-07-01
 
-This paper introduces a classification of concepts and concept maps into three
-categories that will allow us to discuss the implications of various
-proposed design changes.
+This paper introduces a classification of concepts and concept maps
+into categories that we help will support the discussion of various
+proposed design changes.  We use this classification to analyze the
+implications of making certain concepts ``auto``.  We hope that the
+classification can be a useful basis for discussion even if no
+consensus forms around our analysis.
 
 Three Kinds of Concepts
 =======================
@@ -129,12 +132,38 @@
 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.  This fact can be manifested in one of two
-ways.
+There are a few good reasons to make foundational concepts ``auto``:
 
-1. In c++std-lib-23956, Chris Jefferson writes:
+1. Because they are simple, foundational concepts can be very easy to
+   model correctly, which tends to factor against the diagnostic value 
+   added by an explicitly-written ``concept_map``.
+
+2. They are often so simple that the syntactic weight of an
+   explicitly-written ``concept_map`` is a significant fraction of the
+   weight of the model declaration itself:
+
+      struct case_insensitive // 67 non-whitespace characters
+      {
+          bool operator()(string const&, string const&);
+      };
+
+      // 46 non-whitespace characters.
+      concept_map BinaryPredicate<case_insensitive> {}
+
+   [This relative weight is mitigated somewhat by the need to actually
+   *implement* the model, and, if accepted, by the intentional mapping
+   syntax proposed in N2916]
+
+3. Because foundational concepts have a widely agreed-upon syntax and
+   semantics, there's a very good chance that there are already models
+   “out there in the wild,” likely designed with the abstract concept,
+   in mind, but without sepecific knowledge of the C++ ``concept``.
+
+On the other hand, syntactic properties are not an airtight criterion
+by which to correctly identify foundational concepts.  This fact can
+be manifested in one of two ways.
+
+1. **Structural Aliasing**.  In c++std-lib-23956, Chris Jefferson writes:
 
    .. epigraph::
 
@@ -147,12 +176,13 @@
      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]_ 
+   Chris' users have a reasonable expectation to be protected from
+   such mistakes that is consistent with the C++ tradition of
+   protecting against accident rather than deliberate
+   circumvention. [#cpppl3e]_
 
-2. Perhaps because they are simple, it is common that foundational
-   concepts refine other concepts having the same or similar syntactic
+2. **Semantic Refinement**.  Perhaps because they are simple, foundational
+   concepts often refine other concepts having the same or similar syntactic
    structure.  For example, if we know the operation used with
    ``std::accumulate`` is ``Associative``, we can distribute the
    computation across N cores by breaking the input into N subranges,
@@ -185,34 +215,43 @@
 
    If ``Associative`` were declared ``auto``, even non-``Associative``
    operations would be dispatched to the parallel implementation of
-   ``accumulate`` based on their callability with two arguments, yielding
-   an incorrect result at runtime.  [#undefined]_
-
-*Ideally*, foundational concepts should be declared ``auto`` because
-the normal interpretation of the combined syntactic elements is so
-widespread that convenience outweighs the sort of danger cited by
-Chris Jefferson.  [#delmap]_ However, before making a foundational
-concept ``auto``, one must also take great care to be sure it is not,
-and *will never be*, a refinement of another concept with identical or
-very similar syntax. Changing a concept from ``auto`` to
-non-``auto`` will break any code that depended on the earlier
-automatic conformance.
-
-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.  With the notable
-exception of algebraic structures such as ``SemiRing``, [#alg]_ most
-foundational concepts known today are supplied by the standard
+   ``accumulate`` based on their callability with two arguments,
+   yielding an incorrect result at runtime.  [#undefined]_ Note:
+   Semantic refinements are especially common among the algebraic
+   structures (see SemiRing/Ring, Group/AbelianGroup,
+   BinaryOperator/SemiGroup, etc.)
+
+We believe that for foundational concepts, the normal interpretation
+of combined syntactic elements is so widespread that the convenience
+of automatic conformance usually outweighs the danger of structural
+aliasing.  [#delmap]_ 
+
+However, before making any concept ``auto``, one must also take great
+care to be sure it is not, and *will never be*, a refinement of
+another concept with identical or very similar syntax, because
+changing a concept from ``auto`` to non-``auto`` will break any code
+that depended on the earlier automatic conformance.
+[#explicit-refinement]_ This sort of concept hierarchy evolution is
+more common than one might think.  In fact, Chris Jefferson's problem
+was also a case of semantic refinement—after all, a total order *is-a*
+partial order—the only difference being that Chris hadn't (yet) found
+a use for overloading on this semantic difference.
+
+Our experience shows that it takes a long time to develop widespread
+agreement on syntax and semantics for new concepts, so we don't expect
+new foundational concepts to proliferate quickly.  Also, with the
+notable exception of algebraic structures such as ``SemiRing``, most
+foundational concepts known today are already supplied by the standard
 library.
 
-
 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.  
+Any concepts that are neither syntactic or foundational are called
+*nontrivial*.  Nontrivial concepts have generally higher complexity
+and usually cannot be 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
 
@@ -224,9 +263,21 @@
 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.
+The arguments for declaring a concept ``auto`` are not nearly as
+compelling in the case of nontrivial concepts as they are for
+foundational ones.  Nontrivial concepts are not easy to model
+correctly, so the diagnostics produced by a ``concept_map`` can be
+highly valuable to the concept author.  Declaring a new model is a
+significant job that tends to make the effort required to write a
+``concept_map`` “disappear in the noise.” Finally, because they are
+not simple, there is little chance of finding pre-existing models of
+newly-defined nontrivial concepts “in the wild.”
+
+The risks of declaring a nontrivial concept ``auto`` are also less
+compelling than for a foundational concept, because structural
+aliasing of a complex syntactic form is so unusual.  However,
+syntactic complexity doesn't seem to reduce the likelihood of eventual
+semantic refinement.
 
 Three Kinds of Concept Maps
 ===========================
@@ -238,15 +289,16 @@
 -------------------
 
 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
+the goal of modeling a particular concept.  Note that this distinction
+is unrelated to the choice to make a concept ``auto``.  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.  
+model.
 
 Intentional ``concept_maps``\ s are traditionally empty, since a
 programmer modeling a concept in C++03 must write the required
@@ -317,7 +369,7 @@
     template <LessThanComparable T, class A> 
     bool operator<=(const list<T,A>& x, const list<T,A>& y); 
 
-  which can be reduced to::
+  which can be simplified, using an exported concept map, to::
 
     template <LessThanComparable T, class A>
     export concept_map LessThanComparable<list<T,A> >
@@ -381,6 +433,16 @@
 Summary
 =======
 
+Unfortunately, with the exception of syntactic concepts, deciding
+whether to make a concept ``auto`` is unfortunately not cut-and-dried.
+Your users may demand protection from structural aliasing and may be
+willing to pay the syntactic cost of writing empty concept maps, or
+they may be intolerant of empty concept maps and willing to live with
+some accidental conformance.  You may be confident that you can
+predict the future of your concept hierarchy and be willing to break
+your users' code in case you are wrong, or you may need to ensure that
+there is room to transparently evolve your refinement hierarchy.
+
 
 The Full Grid
 =============
@@ -427,6 +489,18 @@
 
 .. _N1798: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1798.html
 
-.. [#alg] Semantic-only refinements are especially common among the
-   algebraic structures, for example SemiRing/Ring,
-   Group/AbelianGroup, BinaryOperator/SemiGroup, etc.
+.. [#explicit-refinement] Although the “explicit refinement” proposal
+   attempts to forbid the declaration of non-``auto`` concepts, it
+   requires roughly the same risk calculus with respect to semantic
+   refinement.  One can still get all the effects of an explicit
+   concept; to future-proof a concept ``MyConcept`` against hierarchy
+   evolution, one would have to write::
+
+     concept Explicit <typename T> {};
+
+     concept MyConcept : explicit Explicit
+     {
+         …
+     };     
+
+