Hello Doug,

Thank you very much for your thorough answers. I would like to add same
remarks.

Douglas Gregor wrote:
> You are absolutely correct. N1799 (and the proposal it is based on,
> N1758) omitted the ability to specify "associated values" or
> value-based member requirements. I've placed this on our TODO list for
> the next revision of the document, and I can't imagine any technical
> problems with introducing this feature, so expect it to be in the
> pre-Mont Tremblant mailing this September.

That sounds very promising!


> Lookup into concepts such as InputIterator are very different from
> lookups into class templates. With class templates and
> specialization, a name like ClassTemplate<T>::difference_type could
> be a type in the primary template, but then ends up to be a static
> data member for a specialization. In other words, there's no
> consistency between (partial) specializations and primary templates,
> so the compiler needs "typename" to tell it what to expect.
>
> Concepts and models are like primary templates and specializations,
> with one important difference: all models of a concept *must* be
> consistent with the concept itself. So, if the concept requires an
> associated type "difference_type", then every model of that concept
> must provide a type "difference_type." If that model omits that type,
> or tries to provide a data member or function named
> "difference_type", the model is ill-formed.

OK. I will think about the implications of this behaviour. One immediate
problem, which arises to me: How can I understand partial specialization
of concepts, like in the example of EqualComparable and
EqualComparable2? While EqualComparable2 looks like

template <typeid T, typeid U>
concept EqualComparable2 {
   bool operator==(const T& lhs, const U& rhs);
   bool operator==(const U& lhs, const T& rhs);
   ...
};

and

template <typeid T>
concept EqualComparable : EqualComparable2<T, T> {
};

how are the now "degenerated" two equal members

   bool operator==(const T& lhs, const T& rhs);
   bool operator==(const T& lhs, const T& rhs);

of EqualComparable resolved, which's both existence would violate
normal C++ rules on classes? Is there a rule, which ensures removal of
all duplicate definitions in concepts?


> We realize "partial enablement" of models with the combination of
> model templates and where clauses. For instance, we can write a
> Callable1 model like this:
>
>   template<typename T>
>   where { is_arithmetic<T>::value }
>   model Callable1<negate, T>
>   {
>     typedef T result_type;
>   };
>
> That's the direct translation. However, presumably we would have
> written an Arithmetic concept, so we rewrite the Callable1 model
> template as:
>
>   template<typeid T>
>   where { Arithmetic<T> }
>   model Callable1<negate, T>
>   {
>     typedef T result_type;
>   };
>
> Model templates are just like any other templates: they can have
> partial specializations and can be constrained by a where clause.

That is a great syntax, and much cleaner than my SFINAE thingee!


>>(3) The idea of the proposal to shift the declaration of dummy variables
>>(aliases) into the main template argument list, like on page 69 the
>>example of merge:
>>
>>"template<typeid Iter1, typeid Iter2, typeid OIter,
>>typeid T>
>>where {
>>   InputIterator<Iter1>::value_type == T,
>>   InputIterator<Iter2>::value_type == T,
>>   Convertible<OutputIterator<OIter>::value_type, T>,
>>   StrictWeakOrdering<T> }
>>Oiter merge(Iter1 first1, Iter1 last1,
>>Iter2 first2, Iter2 last2, OIter out);"
>>
>>unnecessarily complicates matters because the user of the template will
>>immediatly expect that T is somewhere part of the template type
>>list.
>
>
> Agreed. We're starting to think that was a little too clever, and
> maybe ought not to work.

It would work, I am sure. But I don't recommend it, because this syntax
stumbles the reader who's primary interest usually is the "core"
signature of the template (w/o concept incorporation). After that (s)he
will check (if at all) the concept contraints.

Now another interesting question follows: Is the where clause part of
a function template's signature? My first answer would be: Yes, it must
be, because it influences overload resolution, see 1.3.10

"[..] the information about a function that participates in overload
resolution [..]"

Do I see that right?


>>If this idea conflicts with the comma-separated list-behaviour of the
>>where one would need to introduce something like an initializer part of
>>the where clause, e.g.
>>
>>"template<typeid Iter1, typeid Iter2, typeid OIter>
>>where : typeid T = InputIterator<Iter1>::value_type {
>>   InputIterator<Iter2>::value_type == T,
>>   Convertible<OutputIterator<OIter>::value_type, T>,
>>   StrictWeakOrdering<T> }
>>Oiter merge(Iter1 first1, Iter1 last1,
>>Iter2 first2, Iter2 last2, OIter out);"
>
>
> I think it's fine to just use a comma-separated list; no need for the
> ';' even. Template parameter lists introduce names in a similar way,
> so it's not a technical problem.

That is right, it would even not contradict the simple picture of what
where clauses are, namely that each "member" can be understood as
bool expressions on constraints, which are logical combined by AND, so
we can interpret

typeid T = InputIterator<Iter1>::value_type

as: Ensure that InputIterator<Iter1>::value_type exists and name it
T for that scope. OK, that picture does not fit in the details, but
roughly...


>>(4) How can a concept express something like "a constructed type can be
>>uninizialized" (This situation has been thought of in proposal N1782)?
>>
>>Note that this idea differs from the concept of
>>default-constructability.
>
>
> This cannot be expressed in the concept system described in
> N1758/N1799. The closest we can get is to express the requirement as
> the default-constructibility requirement (T::T()), which allows us to
> declare variables with, e.g., "T x;", but they will always be
> default-constructed. We would probably have to invent a new syntax
> for it.
>
> Could you perhaps elaborate with an example where this behavior would
> be useful?

This point was somewhat emphasized in N1782 (at least concerning the
problem for proper distinguishing the corresponding syntax relative to
DefaultConstructible). My assumption is that such information could be
used to protect the programer from writing syntactically valid programs,
where reading access to a such constructed instance is tried (U.B. is
your friend ;-)). I can't say whether this informational win would
outperform the related difficulties for proper support of that concept.

One problem is that it is not **structurally** different from
initialization with determined contents for objects with non-static
storage duration. The definition of the DefaultConstructible
concept in M.H. Austern's book "Generic Programming and the STL" does
**not** exclude uninitialized construction, which harmonizes with the
standards definition of default-construction.

So we could say, that recognition of IndeterminedDefaultConstructible
(what a nice word ;-)) is a refinement of DefaultConstructible and
whether its potential support is of interest, should be asked the
community?


>>"template<typeid T>
>>concept EqualityComparable
>>{
>>   bool operator==(const T&, const T&);
>>   bool operator!=(const T& a, const T& b) {
>>   return !(a == b);
>>   }
>>   // == is an equivalence relation
>>};
>
>
> This syntax is actually allowed by the proposal, but it means
> something a bit different from the meaning you are giving it here. In
> the proposal, this means "if there is no suitable operator!=,
> implement it as !(a == b). It's essentially a default implementation,
> not a semantic requirement.

OK.


> I spoke briefly with two of the authors of the contract proposal
> (N1773), Thorsten Ottosen and James Widman, about integrating the
> ideas of concepts with contracts. They actually play very nicely
> together, and can solve the problem you propose in a very nice
> way. If both proposals make it into C++0x, one will be able to add
> pre- and post-conditions to the requirements in concepts that will be
> checked at run-time for all uses of those operators. So, for
> instance, EqualityComparable might look like this:
>
>   template<typeid T>
>   concept EqualityComparable
>   {
>      bool operator==(const T&, const T&);
>
>      bool operator!=(const T& a, const T& b)
>      postcondition (result) { result == !(a == b) }
>      {
>        return !(a == b);
>      }
>   };
>
> Thus, every model must provide an operation for a != b that is the
> same as !(a == b), and the result will be checked at run-time
> wherever it is used. That means that we'll get at least some run-time
> checking that models *semantically* match the requirements of their
> concepts. This would be *wonderful* for checking, e.g., the uses of
> iterators. A sufficiently brilliant compiler might also use these
> annotations to very the safety of generic functions (i.e.,
> uninstantiated templates).

This integration of N1773 sounds great. I have to read that once more
to understand the mechanism for on/off switching of contract
checking, because this will be an importand issue.


> In this case, the compiler will detect the error when this model is
> defined, because an arbitrary type T does not necessarily have the
> operators ++, *, ==, etc., that are required by the InputIterator
> concept.

Hmmh, during **definition** sounds great, but how is that done? Or do
you mean during the first instantiation for the first type not
fulfilling the constraints, which sounds more like implementable.


> So, to answer your question: concepts and where clauses make
> it possible to avoid the problems associated with unintended and
> dangerous instantiations, but these features can be subverted by
> writing unsafe model templates.

That sounds like a very consistent approach!


One final nit-pick for the next review of N1799: The example

vector<int> v(istream_iterator<int>(cin),
   istream_iterator<int>());

should be corrected, because it acts as function declaration....

Greetings,

Daniel Kr   gler

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Daniel Kr   gler wrote:
> Douglas Gregor wrote:
> OK. I will think about the implications of this behaviour. One immediate
> problem, which arises to me: How can I understand partial specialization
> of concepts, like in the example of EqualComparable and
> EqualComparable2? While EqualComparable2 looks like
>
> template <typeid T, typeid U>
> concept EqualComparable2 {
>    bool operator==(const T& lhs, const U& rhs);
>    bool operator==(const U& lhs, const T& rhs);
>    ...
> };
>
> and
>
> template <typeid T>
> concept EqualComparable : EqualComparable2<T, T> {
> };
>
> how are the now "degenerated" two equal members
>
>    bool operator==(const T& lhs, const T& rhs);
>    bool operator==(const T& lhs, const T& rhs);
>
> of EqualComparable resolved, which's both existence would violate
> normal C++ rules on classes? Is there a rule, which ensures removal of
> all duplicate definitions in concepts?

As you've guessed, there is a rule that ensures removal of duplicate
definitions. Since the types of the two operator=='s are identical,
there is in essence only one requirement for an operator== with that
signature, so the second one is discarded (no diagnostic).

What if they differed only in return type? I would say that it's an
error, which can be fixed by introducing a same-type constraint between
the return types so that they are equivalent.

> That is a great syntax, and much cleaner than my SFINAE thingee!

:)

We're hoping that most of the SFINAE tricks can go away. The grand
vision of concepts is to make Generic Programming (and, to some lesser
extent, Generative- and Template Meta-programming) easier and safer.

> Now another interesting question follows: Is the where clause part of
> a function template's signature? My first answer would be: Yes, it must
> be, because it influences overload resolution, see 1.3.10
>
> "[..] the information about a function that participates in overload
> resolution [..]"
>
> Do I see that right?

Yes. Where clauses must be part of a function template's signature
because we need to be able to determine if a call to that function
template is valid without having the definition. They're also needed to
distinguish function templates that differ only by the where clause,
e.g., std::distance for InputIterators and for RandomAccessIterators.

> This point was somewhat emphasized in N1782 (at least concerning the
> problem for proper distinguishing the corresponding syntax relative to
> DefaultConstructible). My assumption is that such information could be
> used to protect the programer from writing syntactically valid programs,
> where reading access to a such constructed instance is tried (U.B. is
> your friend ;-)). I can't say whether this informational win would
> outperform the related difficulties for proper support of that concept.

Oh, okay. Yes, this information could be used to provide better error
checking.

> One problem is that it is not **structurally** different from
> initialization with determined contents for objects with non-static
> storage duration. The definition of the DefaultConstructible
> concept in M.H. Austern's book "Generic Programming and the STL" does
> **not** exclude uninitialized construction, which harmonizes with the
> standards definition of default-construction.

Right. As you say below, however, it's not actually a problem...

> So we could say, that recognition of IndeterminedDefaultConstructible
> (what a nice word ;-)) is a refinement of DefaultConstructible and
> whether its potential support is of interest, should be asked the
> community?

. because you've given the real answer.
IndeterminedDefaultConstructible would probably have some additional
requirements. For instance, we could have:

template<typeid T>
concept DefaultConstructible
{
  T::T();
  T::~T();
};

template<typeid T, typeid U = T>
concept Assignable
{
  T& operator=(T&, const U&);
};

template<typeid T>
concept IndeterminedDefaultConstructible : DefaultConstructible<T>,
Assignable<T>
{
  // Semantic requirement: the only things one can do with a
default-constructed T are
  //   (1) Assign to it, or
  //   (2) Destruct it.
};

> > In this case, the compiler will detect the error when this model is
> > defined, because an arbitrary type T does not necessarily have the
> > operators ++, *, ==, etc., that are required by the InputIterator
> > concept.
>
> Hmmh, during **definition** sounds great, but how is that done? Or do
> you mean during the first instantiation for the first type not
> fulfilling the constraints, which sounds more like implementable.

Model templates will be checked just like any other template. For
instance, consider how we would type-check the std::for_each algorithm,
which looks like this in its concept-enabled incarnation:

template<typeid Iter, typeid F>
where { InputIterator<Iter>, Callable1<F, reference>,
CopyConstructible<F> }
F for_each(Iter first, Iter last, F f)
{
  while (first != last) {
    f(*first);
    ++first;
  }
  return f;
}

The "typeid Iter" and "typeid F" tell us that we can do nothing with
those types or any values of those types, except what is explicitly
allowed by the where clause.  So, how do we type-check "first != last"?
We need to search through the requirements in the where clause. When we
do, we find that InputIterator<Iter>refines EqualityComparable<Iter>,
which defines an operation:

  bool operator!=(const Iter&, const Iter&);

Ah-ha! We select that operation and know that it has a 'bool' return
value, so the while condition type-checks as well. Continuing on, when
type-checking "*first" we find this signature in the InputIterator
concept:

  reference operator*(const Iter&);

So "*first" is well-typed and the return type is the associated type
InputIterator<Iter>::reference. When searching for a function-call
operator for f(*first), we'll find this definition in Callable1<F,
reference>:

  result_type operator()(F&, reference);

Type-checking continues, and eventually we see that all of the
functions and types needed by for_each are satisfied by the where
clause, so the function type-checks properly. Better yet, if the
arguments that you give to for_each meet the requirements stated in the
where clause, for_each will always instantiate properly, with no
errors. If the arguments don't meet the requirements of the where
clause, the compiler won't let you instantiate it.

The same ideas apply to model templates. For instance, let's take
InputIterator for pointers:

template<typeid T>
model InputIterator<T*>
{
  typedef T value_type;
  typedef T& reference;
  typedef T* pointer;
  typedef std::ptrdiff_t difference_type;

  // These will be implicitly generated if not written here, but I'm
being intentionally verbose
  reference operator*(T* const &ptr) { return *ptr; }
  pointer operator->(T* const &ptr) { return ptr; }
  T*& operator++(T*& ptr) { return ++ptr; }
  T* operator++(T*& ptr) { return ptr++; }
  // ...
};

Now, consider how each of those functions in the model are
type-checked. In operator*, can we type-check "*ptr". Sure, because ptr
is a pointer, and dereferencing a pointer to a T gives a T&, which
matches the return type of operator*. The same logic follows for the
other functions I've show (and those that I haven't). The end result is
that we can type-check the entire body of the template definition,
because all of the operations are satisfied by built-ins. Next, let's
consider a more interesting example using containers and stacks.

template<typeid Seq>
concept BackInsertionSequence
{
  typename value_type = Seq::value_type;
  typename reference = Seq::reference;
  void Seq::push_back(const value_type&);
  void Seq::pop_back();
  reference Seq::back();
  bool Seq::empty() const;
};

template<typeid S>
concept Stack
{
  typename value_type = S::value_type;
  typename reference = S::reference;
  void push(S&, const value_type&);
  void pop(S&);
  reference top(S&);
  bool empty(const S&);
};

Now, we can define a model that tells how any BackInsertionSequence can
be used as a stack:

template<typeid Seq>where { BackInsertionSequence<Seq> }
model Stack<Seq>
{
  typedef BackInsertionSequence<Seq>::value_type value_type;
  typedef BackInsertionSequence<Seq>::reference reference;
  void push(Seq& seq, const value_type& x) { seq.push_back(x); }
  void pop(Seq& seq) { seq.pop_back(); }
  reference top(Seq& seq) { return seq.top(); }
  bool empty(const Seq& seq) { return seq.empty(); }
};

Consider how we type-check each function within the model of Stack. For
instance, how do we type-check "seq.push_back(x)"? Well, the only think
we know about Seq is that it satisfies BackInsertionSequence<Seq>, so
we search in there for a member named push_back, and we find:

  void Seq::push_back(const value_type&);

Since the Stack's value_type is the same as the sequence's value_type,
it type-checks fine. The rest of the functions type-check this way has
well. Had we tried do write something like "seq.pop_front()", we
wouldn't be able to find an operation in BackInsertionSequence<Seq> for
"pop_front", so we could get an error at template definition time.

> One final nit-pick for the next review of N1799: The example
>
> vector<int> v(istream_iterator<int>(cin),
>    istream_iterator<int>());
>
> should be corrected, because it acts as function declaration....

Hah! So it is. I've added this to the issues list; we'll fix it for the
next revision. Thanks!

  Doug


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Hello C++ community,

fortunately there are currently great efforts to introduce concepts and
models of those into the C++ language. After reading the public=20
available state of N1799, see

http://www2.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1799.pdf

(1) I notice the lack of support for (static) value members and
"templateability". This becomes immediatly obvious if we consider for=20
example the description of the model n of an MPL Integral Constant,
which according to

http://www.boost.org/libs/mpl/doc/refmanual/integral-constant.html

has to provide a typename

n::value_type

(which is supported in the proposal),

but also an integral constant expression, namely

n::value

Such value-based member requirements seems not to be supported by the
current proposal. If there are supported, than the assertion made in
N1799, that the typename keyword could me removed from typeid
expressions (typeid in the sense of the proposal) seems not obvious to
me. E.g. the example on page 61

"template<typeid Iter> where { InputIterator<Iter> }
InputIterator<Iter>::difference_type
distance(Iter first, Iter last)
{
InputIterator<T>::difference_type result =3D 0;
for (; first !=3D last; ++first)
++result;
return result;
"

claims not to need typename in front of

"InputIterator<T>::difference_type"

which seems not understandable to me in the presence of required static
member values.


(2) Which ideas exist to realize "partial enablement" of models (which
currently is done via SFINAE), e.g. page 58 is currently written as

"concept Callable1<F,T1> {
   typename F::result_type;
   F f; T1 t1;
   (F::result_type)(f(t1));
};

struct negate {
template<typename T> operator()(T x) { return -x; }
};

static_assert Callable1<negate, int>
{ typedef int negate::result_type; };

static_assert Callable1<negate, float>
{ typedef float negate::result_type; };
"

One obvious improvement would be something like

static_assert Callable<negate, typeid U, typeid Enable =3D
typename enable_if<is_arithmetic<U>, U>::type >
{
   typedef U negate::result_type;
}

Or are there even better approaches?

(3) The idea of the proposal to shift the declaration of dummy variables
(aliases) into the main template argument list, like on page 69 the
example of merge:

"template<typeid Iter1, typeid Iter2, typeid OIter,
typeid T>
where {
   InputIterator<Iter1>::value_type =3D=3D T,
   InputIterator<Iter2>::value_type =3D=3D T,
   Convertible<OutputIterator<OIter>::value_type, T>,
   StrictWeakOrdering<T> }
Oiter merge(Iter1 first1, Iter1 last1,
Iter2 first2, Iter2 last2, OIter out);"

unnecessarily complicates matters because the user of the template will
immediatly expect that T is somewhere part of the template type list. It
seems as if one should add the concept of "local type variables", which
would restrict the "type requirements maths" on the where block, e.g.

"template<typeid Iter1, typeid Iter2, typeid OIter> // No typeid T here!
where {
   typeid T =3D InputIterator<Iter1>::value_type;

   InputIterator<Iter2>::value_type =3D=3D T,
   Convertible<OutputIterator<OIter>::value_type, T>,
   StrictWeakOrdering<T> }
Oiter merge(Iter1 first1, Iter1 last1,
Iter2 first2, Iter2 last2, OIter out);"

If this idea conflicts with the comma-separated list-behaviour of the
where one would need to introduce something like an initializer part of
the where clause, e.g.

"template<typeid Iter1, typeid Iter2, typeid OIter>
where : typeid T =3D InputIterator<Iter1>::value_type {
   InputIterator<Iter2>::value_type =3D=3D T,
   Convertible<OutputIterator<OIter>::value_type, T>,
   StrictWeakOrdering<T> }
Oiter merge(Iter1 first1, Iter1 last1,
Iter2 first2, Iter2 last2, OIter out);"

If we look at currently existing type math libraries, like boost::mpl,
one doesn't need much fantasy to expect that temporary (local) type
variables would be quite useful and that the new "where" part could
become even larger than the typical implementation part.

(4) How can a concept express something like "a constructed type can be
uninizialized" (This situation has been thought of in proposal N1782)?

Note that this idea differs from the concept of
default-constructability.

(5) Selfconsistency of concepts: On page 7 EqualityComparable is
described as:

"template<typeid T>
concept EqualityComparable
{
   bool operator=3D=3D(const T&, const T&);
   bool operator!=3D(const T&, const T&);
   // =3D=3D is an equivalence relation
   // !=3D is the complement of =3D=3D
};
"

The interestings points are the comments "=3D=3D is an equivalence relati=
on"
  and "!=3D is the complement of =3D=3D". While I see no simple solution =
to
check whether =3D=3D is indeed an equivalence relation, one could at leas=
t
easily enforce something like

"template<typeid T>
concept EqualityComparable
{
   bool operator=3D=3D(const T&, const T&);
   bool operator!=3D(const T& a, const T& b) {
   return !(a =3D=3D b);
   }
   // =3D=3D is an equivalence relation
};
"

(6) Last but not least a more detailed question: Is concept checking in
where clauses guaranteed **not** to instantiate the corresponding class
templates? Under current rules an expression like

my_template<T>::value_type

will indeed instantiate all static members and member type definitions
of my_template<T> with all its side effects like potentially leading to
invalid instances. I assume, that concept checking will **not** have
these effects, right?


Greetings from Bemen,

Daniel Kr=FCgler

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Hello Daniel,

Daniel Kr   gler wrote:
> fortunately there are currently great efforts to introduce concepts and
> models of those into the C++ language. After reading the public
> available state of N1799, see
>
> http://www2.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1799.pdf

We appreciate the feedback! Concepts could be a big step forward for
C++ and Generic Programming, and any discussion gives the C++
committee a better shot at getting it right.

> (1) I notice the lack of support for (static) value members and
> "templateability". This becomes immediatly obvious if we consider for
> example the description of the model n of an MPL Integral Constant,
> which according to
>
> http://www.boost.org/libs/mpl/doc/refmanual/integral-constant.html
>
> has to provide a typename
>
> n::value_type
>
> (which is supported in the proposal),
>
> but also an integral constant expression, namely
>
> n::value
>
> Such value-based member requirements seems not to be supported by the
> current proposal.

You are absolutely correct. N1799 (and the proposal it is based on,
N1758) omitted the ability to specify "associated values" or
value-based member requirements. I've placed this on our TODO list for
the next revision of the document, and I can't imagine any technical
problems with introducing this feature, so expect it to be in the
pre-Mont Tremblant mailing this September.

> If there are supported, than the assertion made in
> N1799, that the typename keyword could me removed from typeid
> expressions (typeid in the sense of the proposal) seems not obvious to
> me. E.g. the example on page 61
>
> "template<typeid Iter> where { InputIterator<Iter> }
> InputIterator<Iter>::difference_type
> distance(Iter first, Iter last)
> {
> InputIterator<T>::difference_type result = 0;
> for (; first != last; ++first)
> ++result;
> return result;
> "
>
> claims not to need typename in front of
>
> "InputIterator<T>::difference_type"
>
> which seems not understandable to me in the presence of required static
> member values.

Lookup into concepts such as InputIterator are very different from
lookups into class templates. With class templates and
specialization, a name like ClassTemplate<T>::difference_type could
be a type in the primary template, but then ends up to be a static
data member for a specialization. In other words, there's no
consistency between (partial) specializations and primary templates,
so the compiler needs "typename" to tell it what to expect.

Concepts and models are like primary templates and specializations,
with one important difference: all models of a concept *must* be
consistent with the concept itself. So, if the concept requires an
associated type "difference_type", then every model of that concept
must provide a type "difference_type." If that model omits that type,
or tries to provide a data member or function named
"difference_type", the model is ill-formed.

> (2) Which ideas exist to realize "partial enablement" of models (which
> currently is done via SFINAE), e.g. page 58 is currently written as
>
> "concept Callable1<F,T1> {
>    typename F::result_type;
>    F f; T1 t1;
>    (F::result_type)(f(t1));
> };
>
> struct negate {
> template<typename T> operator()(T x) { return -x; }
> };
>
> static_assert Callable1<negate, int>
> { typedef int negate::result_type; };
>
> static_assert Callable1<negate, float>
> { typedef float negate::result_type; };
> "
>
> One obvious improvement would be something like
>
> static_assert Callable<negate, typeid U, typeid Enable =
> typename enable_if<is_arithmetic<U>, U>::type >
> {
>    typedef U negate::result_type;
> }
>
> Or are there even better approaches?

We realize "partial enablement" of models with the combination of
model templates and where clauses. For instance, we can write a
Callable1 model like this:

  template<typename T>
  where { is_arithmetic<T>::value }
  model Callable1<negate, T>
  {
    typedef T result_type;
  };

That's the direct translation. However, presumably we would have
written an Arithmetic concept, so we rewrite the Callable1 model
template as:

  template<typeid T>
  where { Arithmetic<T> }
  model Callable1<negate, T>
  {
    typedef T result_type;
  };

Model templates are just like any other templates: they can have
partial specializations and can be constrained by a where clause.

> (3) The idea of the proposal to shift the declaration of dummy variables
> (aliases) into the main template argument list, like on page 69 the
> example of merge:
>
> "template<typeid Iter1, typeid Iter2, typeid OIter,
> typeid T>
> where {
>    InputIterator<Iter1>::value_type == T,
>    InputIterator<Iter2>::value_type == T,
>    Convertible<OutputIterator<OIter>::value_type, T>,
>    StrictWeakOrdering<T> }
> Oiter merge(Iter1 first1, Iter1 last1,
> Iter2 first2, Iter2 last2, OIter out);"
>
> unnecessarily complicates matters because the user of the template will
> immediatly expect that T is somewhere part of the template type
> list.

Agreed. We're starting to think that was a little too clever, and
maybe ought not to work.

> It
> seems as if one should add the concept of "local type variables", which
> would restrict the "type requirements maths" on the where block, e.g.
>
> "template<typeid Iter1, typeid Iter2, typeid OIter> // No typeid T here!
> where {
>    typeid T = InputIterator<Iter1>::value_type;
>
>    InputIterator<Iter2>::value_type == T,
>    Convertible<OutputIterator<OIter>::value_type, T>,
>    StrictWeakOrdering<T> }
> Oiter merge(Iter1 first1, Iter1 last1,
> Iter2 first2, Iter2 last2, OIter out);"

Yep, that might be a good idea. I don't see any technical issues with
it.

> If this idea conflicts with the comma-separated list-behaviour of the
> where one would need to introduce something like an initializer part of
> the where clause, e.g.
>
> "template<typeid Iter1, typeid Iter2, typeid OIter>
> where : typeid T = InputIterator<Iter1>::value_type {
>    InputIterator<Iter2>::value_type == T,
>    Convertible<OutputIterator<OIter>::value_type, T>,
>    StrictWeakOrdering<T> }
> Oiter merge(Iter1 first1, Iter1 last1,
> Iter2 first2, Iter2 last2, OIter out);"

I think it's fine to just use a comma-separated list; no need for the
';' even. Template parameter lists introduce names in a similar way,
so it's not a technical problem.

> If we look at currently existing type math libraries, like boost::mpl,
> one doesn't need much fantasy to expect that temporary (local) type
> variables would be quite useful and that the new "where" part could
> become even larger than the typical implementation part.

It's possible, although I hope it doesn't get that bad. I think with
this issue we should wait and see: if it looks like we're going to
get a lot of big where clauses, where we really need to introduce
local type variables, then we should add them as you
describe. However, I'm hoping that we don't have to complicate where
clauses any more.

> (4) How can a concept express something like "a constructed type can be
> uninizialized" (This situation has been thought of in proposal N1782)?
>
> Note that this idea differs from the concept of
> default-constructability.

This cannot be expressed in the concept system described in
N1758/N1799. The closest we can get is to express the requirement as
the default-constructibility requirement (T::T()), which allows us to
declare variables with, e.g., "T x;", but they will always be
default-constructed. We would probably have to invent a new syntax
for it.

Could you perhaps elaborate with an example where this behavior would
be useful?

> (5) Selfconsistency of concepts: On page 7 EqualityComparable is
> described as:
>
> "template<typeid T>
> concept EqualityComparable
> {
>    bool operator==(const T&, const T&);
>    bool operator!=(const T&, const T&);
>    // == is an equivalence relation
>    // != is the complement of ==
> };
> "
>
> The interestings points are the comments "== is an equivalence relation"
>   and "!= is the complement of ==". While I see no simple solution to
> check whether == is indeed an equivalence relation, one could at least
> easily enforce something like
>
> "template<typeid T>
> concept EqualityComparable
> {
>    bool operator==(const T&, const T&);
>    bool operator!=(const T& a, const T& b) {
>    return !(a == b);
>    }
>    // == is an equivalence relation
> };

This syntax is actually allowed by the proposal, but it means
something a bit different from the meaning you are giving it here. In
the proposal, this means "if there is no suitable operator!=,
implement it as !(a == b). It's essentially a default implementation,
not a semantic requirement.

I spoke briefly with two of the authors of the contract proposal
(N1773), Thorsten Ottosen and James Widman, about integrating the
ideas of concepts with contracts. They actually play very nicely
together, and can solve the problem you propose in a very nice
way. If both proposals make it into C++0x, one will be able to add
pre- and post-conditions to the requirements in concepts that will be
checked at run-time for all uses of those operators. So, for
instance, EqualityComparable might look like this:

  template<typeid T>
  concept EqualityComparable
  {
     bool operator==(const T&, const T&);

     bool operator!=(const T& a, const T& b)
     postcondition (result) { result == !(a == b) }
     {
       return !(a == b);
     }
  };

Thus, every model must provide an operation for a != b that is the
same as !(a == b), and the result will be checked at run-time
wherever it is used. That means that we'll get at least some run-time
checking that models *semantically* match the requirements of their
concepts. This would be *wonderful* for checking, e.g., the uses of
iterators. A sufficiently brilliant compiler might also use these
annotations to very the safety of generic functions (i.e.,
uninstantiated templates).

> (6) Last but not least a more detailed question: Is concept checking in
> where clauses guaranteed **not** to instantiate the corresponding class
> templates? Under current rules an expression like
>
> my_template<T>::value_type
>
> will indeed instantiate all static members and member type definitions
> of my_template<T> with all its side effects like potentially leading to
> invalid instances. I assume, that concept checking will **not** have
> these effects, right?

Unfortunately, there no simple "yes" or "no" answer to this.

Let's consider a simple, type-safe for_each implementation:

  template<typeid Iter, typeid F>
  where { InputIterator<Iter>, Callable1<F, reference> }
  F for_each(Iter first, Iter last, F f)
  {
    for (; first != last; ++first)
      f(*first);
  }

What happens in the compiler when we write this?

  struct printme
  {
    template<typename T> void operator()(const T& t)
    { std::cout << t; }
  };

  for_each(17, 42, printme());

Without concepts, we get an error in the body of for_each telling us
that, e.g., the type "int" does not have an operator*.

With concepts, the compiler is going to search for a model
InputIterator<int> before resolving the call to the for_each
template. When it searches for InputIterator<int>, it doesn't
instantiate anything else unless it finds an actual model. Since none
exists, the compiler does not instantiation anything else, it just
replaces that there is no function "for_each" that satisfies the
call. A smarter compiler mile point out that if there was a model
InputIterator<int>, the for_each above could have matched.

Now, let's imagine that we write another for_each that actually would
work with integers, because it's based on arithmetic types:

  template<typeid T, typeid F>
  where { Arithmetic<Iter>, Callable1<F, T> }
  F for_each(T first, T last, F f)
  {
    for (; first != last; ++first)
      f(first);
  }

Since we don't dereference first, all is well. Now what happens with
our function call?

  model Arithmetic<int> {};

  for_each(17, 42, printme());

The compiler is going to check both for_each's against this call. For
the first one, it does not find a model InputIterator<int>, so the
first for_each doesn't match. The second for_each, however, does
match because there is a model Arithmetic<int>. The second one gets
called and there were no unintended or dangerous
instantiations. Had we used enable_if/SFINAE tricks to try to do
this, we might have run into the invalid instantiations that you're
concerned about. However, we're safe with concepts... so far.

The system is still open to abuse, however. One could write a bogus
model template like this:

  template<typename T>
  model InputIterator<T>
  {
  };

Now when the compiler looks for InputIterator<int>, it sees this
template and tries to instantiate it. We get errors because, e.g.,
int does not support operator*, etc. How could we have avoided this
problem? Well, it isn't really the case that every T models
InputIterator. Only specific T's model InputIterator, so we should
write only models (or model templates) for those. Better yet, we
should make our model templates type-safe with typeid:

  template<typeid T>
  model InputIterator<T>
  {
  };

In this case, the compiler will detect the error when this model is
defined, because an arbitrary type T does not necessarily have the
operators ++, *, ==, etc., that are required by the InputIterator
concept.

So, to answer your question: concepts and where clauses make
it possible to avoid the problems associated with unintended and
dangerous instantiations, but these features can be subverted by
writing unsafe model templates.

  Cheers,
  Doug Gregor


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]