Changeset 54701


Ignore:
Timestamp:
Jul 6, 2009, 3:27:57 AM (9 years ago)
Author:
Dave Abrahams
Message:

More

File:
1 edited

Legend:

Unmodified
Added
Removed
  • sandbox/committee/LWG/proposals/taxonomy-of-concepts-and-maps.rst

    r54663 r54701  
    77:Date: 2009-07-01
    88
    9 This paper introduces a classification of concepts and concept maps into three
    10 categories that will allow us to discuss the implications of various
    11 proposed design changes.
     9This paper introduces a classification of concepts and concept maps
     10into categories that we help will support the discussion of various
     11proposed design changes.  We use this classification to analyze the
     12implications of making certain concepts ``auto``.  We hope that the
     13classification can be a useful basis for discussion even if no
     14consensus forms around our analysis.
    1215
    1316Three Kinds of Concepts
     
    130133and ``constexpr`` may make a suitable convention feasible.
    131134
    132 Although foundational concepts represent an accepted convention,
    133 syntactic properties are not an airtight criterion by which to
    134 correctly identify them.  This fact can be manifested in one of two
    135 ways.
    136 
    137 1. In c++std-lib-23956, Chris Jefferson writes:
     135There are a few good reasons to make foundational concepts ``auto``:
     136
     1371. Because they are simple, foundational concepts can be very easy to
     138   model correctly, which tends to factor against the diagnostic value
     139   added by an explicitly-written ``concept_map``.
     140
     1412. They are often so simple that the syntactic weight of an
     142   explicitly-written ``concept_map`` is a significant fraction of the
     143   weight of the model declaration itself:
     144
     145      struct case_insensitive // 67 non-whitespace characters
     146      {
     147          bool operator()(string const&, string const&);
     148      };
     149
     150      // 46 non-whitespace characters.
     151      concept_map BinaryPredicate<case_insensitive> {}
     152
     153   [This relative weight is mitigated somewhat by the need to actually
     154   *implement* the model, and, if accepted, by the intentional mapping
     155   syntax proposed in N2916]
     156
     1573. Because foundational concepts have a widely agreed-upon syntax and
     158   semantics, there's a very good chance that there are already models
     159   “out there in the wild,” likely designed with the abstract concept,
     160   in mind, but without sepecific knowledge of the C++ ``concept``.
     161
     162On the other hand, syntactic properties are not an airtight criterion
     163by which to correctly identify foundational concepts.  This fact can
     164be manifested in one of two ways.
     165
     1661. **Structural Aliasing**.  In c++std-lib-23956, Chris Jefferson writes:
    138167
    139168   .. epigraph::
     
    148177     satisfying the auto concept ``LessThanComparable``.
    149178
    150    The expectation to be protected from such mistakes is consistent with
    151    the C++ tradition of protecting against accident rather than
    152    deliberate circumvention. [#cpppl3e]_
    153 
    154 2. Perhaps because they are simple, it is common that foundational
    155    concepts refine other concepts having the same or similar syntactic
     179   Chris' users have a reasonable expectation to be protected from
     180   such mistakes that is consistent with the C++ tradition of
     181   protecting against accident rather than deliberate
     182   circumvention. [#cpppl3e]_
     183
     1842. **Semantic Refinement**.  Perhaps because they are simple, foundational
     185   concepts often refine other concepts having the same or similar syntactic
    156186   structure.  For example, if we know the operation used with
    157187   ``std::accumulate`` is ``Associative``, we can distribute the
     
    186216   If ``Associative`` were declared ``auto``, even non-``Associative``
    187217   operations would be dispatched to the parallel implementation of
    188    ``accumulate`` based on their callability with two arguments, yielding
    189    an incorrect result at runtime.  [#undefined]_
    190 
    191 *Ideally*, foundational concepts should be declared ``auto`` because
    192 the normal interpretation of the combined syntactic elements is so
    193 widespread that convenience outweighs the sort of danger cited by
    194 Chris Jefferson.  [#delmap]_ However, before making a foundational
    195 concept ``auto``, one must also take great care to be sure it is not,
    196 and *will never be*, a refinement of another concept with identical or
    197 very similar syntax. Changing a concept from ``auto`` to
    198 non-``auto`` will break any code that depended on the earlier
    199 automatic conformance.
    200 
    201 Our experience shows that widespread agreement on syntax and semantics
    202 for new concepts takes a long time to develop, so we don't expect new
    203 foundational concepts to proliferate quickly.  With the notable
    204 exception of algebraic structures such as ``SemiRing``, [#alg]_ most
    205 foundational concepts known today are supplied by the standard
     218   ``accumulate`` based on their callability with two arguments,
     219   yielding an incorrect result at runtime.  [#undefined]_ Note:
     220   Semantic refinements are especially common among the algebraic
     221   structures (see SemiRing/Ring, Group/AbelianGroup,
     222   BinaryOperator/SemiGroup, etc.)
     223
     224We believe that for foundational concepts, the normal interpretation
     225of combined syntactic elements is so widespread that the convenience
     226of automatic conformance usually outweighs the danger of structural
     227aliasing.  [#delmap]_
     228
     229However, before making any concept ``auto``, one must also take great
     230care to be sure it is not, and *will never be*, a refinement of
     231another concept with identical or very similar syntax, because
     232changing a concept from ``auto`` to non-``auto`` will break any code
     233that depended on the earlier automatic conformance.
     234[#explicit-refinement]_ This sort of concept hierarchy evolution is
     235more common than one might think.  In fact, Chris Jefferson's problem
     236was also a case of semantic refinement—after all, a total order *is-a*
     237partial order—the only difference being that Chris hadn't (yet) found
     238a use for overloading on this semantic difference.
     239
     240Our experience shows that it takes a long time to develop widespread
     241agreement on syntax and semantics for new concepts, so we don't expect
     242new foundational concepts to proliferate quickly.  Also, with the
     243notable exception of algebraic structures such as ``SemiRing``, most
     244foundational concepts known today are already supplied by the standard
    206245library.
    207 
    208246
    209247Nontrivial Concepts
    210248-------------------
    211249
    212 Nontrivial concepts have generally higher complexity and cannot be
    213 easily satisfied without significant coding effort.  Examples in this
    214 category include `graph concepts`_, and the standard iterator and
    215 container concepts. 
     250Any concepts that are neither syntactic or foundational are called
     251*nontrivial*.  Nontrivial concepts have generally higher complexity
     252and usually cannot be satisfied without significant coding effort.
     253Examples in this category include `graph concepts`_, and the standard
     254iterator and container concepts.
    216255
    217256.. _graph concepts: http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/graph_concepts.html
     
    225264d. New foundational concepts don't come along every day.
    226265
    227 In our opinion, the arguments for making nontrivial concepts ``auto``
    228 are not nearly so compelling as for syntactic and foundational
    229 concepts.  We explain why below.
     266The arguments for declaring a concept ``auto`` are not nearly as
     267compelling in the case of nontrivial concepts as they are for
     268foundational ones.  Nontrivial concepts are not easy to model
     269correctly, so the diagnostics produced by a ``concept_map`` can be
     270highly valuable to the concept author.  Declaring a new model is a
     271significant job that tends to make the effort required to write a
     272``concept_map`` “disappear in the noise.” Finally, because they are
     273not simple, there is little chance of finding pre-existing models of
     274newly-defined nontrivial concepts “in the wild.”
     275
     276The risks of declaring a nontrivial concept ``auto`` are also less
     277compelling than for a foundational concept, because structural
     278aliasing of a complex syntactic form is so unusual.  However,
     279syntactic complexity doesn't seem to reduce the likelihood of eventual
     280semantic refinement.
    230281
    231282Three Kinds of Concept Maps
     
    239290
    240291Intentional concept maps occur when a programmer designs a class with
    241 the goal of modeling a particular concept.  For example, I might
    242 design a type to model ``EqualityComparable`` or
     292the goal of modeling a particular concept.  Note that this distinction
     293is unrelated to the choice to make a concept ``auto``.  For example, I
     294might design a type to model ``EqualityComparable`` or
    243295``BidirectionalIterator``.  Because ``EqualityComparable`` is an
    244296``auto`` concept, an intentional map may be automatically generated
     
    247299intentional map must be written by the author of the model.  We call
    248300both maps “intentional” because they are intended by the author of the
    249 model. 
     301model.
    250302
    251303Intentional ``concept_maps``\ s are traditionally empty, since a
     
    318370    bool operator<=(const list<T,A>& x, const list<T,A>& y);
    319371
    320   which can be reduced to::
     372  which can be simplified, using an exported concept map, to::
    321373
    322374    template <LessThanComparable T, class A>
     
    381433Summary
    382434=======
     435
     436Unfortunately, with the exception of syntactic concepts, deciding
     437whether to make a concept ``auto`` is unfortunately not cut-and-dried.
     438Your users may demand protection from structural aliasing and may be
     439willing to pay the syntactic cost of writing empty concept maps, or
     440they may be intolerant of empty concept maps and willing to live with
     441some accidental conformance.  You may be confident that you can
     442predict the future of your concept hierarchy and be willing to break
     443your users' code in case you are wrong, or you may need to ensure that
     444there is room to transparently evolve your refinement hierarchy.
    383445
    384446
     
    428490.. _N1798: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1798.html
    429491
    430 .. [#alg] Semantic-only refinements are especially common among the
    431    algebraic structures, for example SemiRing/Ring,
    432    Group/AbelianGroup, BinaryOperator/SemiGroup, etc.
     492.. [#explicit-refinement] Although the “explicit refinement” proposal
     493   attempts to forbid the declaration of non-``auto`` concepts, it
     494   requires roughly the same risk calculus with respect to semantic
     495   refinement.  One can still get all the effects of an explicit
     496   concept; to future-proof a concept ``MyConcept`` against hierarchy
     497   evolution, one would have to write::
     498
     499     concept Explicit <typename T> {};
     500
     501     concept MyConcept : explicit Explicit
     502     {
     503         …
     504     };     
     505
     506   
Note: See TracChangeset for help on using the changeset viewer.