Concepts Question - C++ language, library and standards

C++Talk.NET
C++ language newsgroups

Archives

FAQ

Memberlist

Usergroups

Profile

Concepts Question
Goto page 1, 2, 3 Next

C++Talk.NET Forum Index -> C++ language, library and standards

View previous topic :: View next topic

Author

Message

Scott Meyers
Guest

Posted: Thu Dec 21, 2006 10:10 am Post subject: Concepts Question

I understand the general idea behind concepts, but I'm not clear on the details of how they are likely to be integrated into C++0x. Consider the following text from the June 24, 2006, paper on Concepts (N2042 -- http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2042.pdf): Here is the definition of LessThanComparable: auto concept LessThanComparable<typename T> { bool operator<(T, T); }; [...] Inside the body of the concept, we list the declarations that we expect to have, i.e., an operator< that takes two T parameters and returns a bool. Is this really what the above specifies? I'd expect it to mean that that there must be a function named operator< that can be called with two objects of type T and that returns a type implicitly convertable to bool, i.e., that given objects t1 and t2 of type T, the following expression is legal: bool b(t1<t1); Is my expectation correct, or do concepts really specify specific function signatures? Thanks, Scott --- [ 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.comeaucomputing.com/csc/faq.html ]

Douglas Gregor
Guest

Posted: Thu Dec 21, 2006 4:53 pm Post subject: Re: Concepts Question

Scott Meyers wrote:

Quote:

Consider the following text from the June 24, 2006, paper on Concepts
(N2042 --
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2042.pdf):

Here is the definition of LessThanComparable:

auto concept LessThanComparable<typename T> {
bool operator<(T, T);
};

[...]
Inside the body of the concept, we list the declarations that we
expect to have, i.e., an operator< that takes two T parameters and
returns a bool.

Is this really what the above specifies? I'd expect it to mean that
that there must be a function named operator< that can be called with
two objects of type T and that returns a type implicitly convertable
to bool, i.e., that given objects t1 and t2 of type T, the following
expression is legal:

bool b(t1<t1);

Is my expectation correct, or do concepts really specify specific
function signatures?

Yes.

To both.

The LessThanComparable concept really specifies that there is a
function with the signature "bool operator<(T, T)". That's the
declaration we see when we're inside a constrained template like min:

template<typename T>
where LessThanComparable<T>
const T& min(const T& x, const T& y) {
return x < y? x : y; // x < y finds
LessThanComparable<T>::operator<
}

Your explanation is also correct: for a given type X to be
LessThanComparable, one needs an operator< whose parameters can be
initialized with values of type X and whose result type is convertible
to bool.

However, the operator< in LessThanComparable and the operator< for your
type X aren't the same function. LessThanComparable for X has its own
operator<, which will be implicitly generated with the following
definition:

bool LessThanComparable<X>::operator<(const X& x1, const X& x2) {
return x1 < x2;
}

So LessThanComparable's operator< has exactly the signature we said it
did [*], but the actual < it binds to in its definition has the looser
requirements you described, e.g., it could be:

struct Y { Y(const X&); };
int operator<(Y, Y);

The definition of LessThanComparable<X>::operator< will find this "int
operator<(Y, Y)" and bind to it.

LessThanComparable<X>::operator< is actually part of the "concept map"
LessThanComparable<X>. Concept maps state how a given set of types
(here, the type "X") meet the requirements of a concept. In this case,
the concept map LessThanComparable<X> and its operator< are implicitly
generated by the compiler.

With "auto" concepts like LessThanComparable, the compiler will
implicitly define concept maps when we need them. However, we're always
free to define our own concept map, which can either use
implicitly-generated members like operator<

concept_map LessThanComparable<X> { }; // operator< is implicitly
generated, as above

or can specify implementations of members:

concept_map LessThanComparable<X> {
bool operator<(X x1, X x2) {
return x1.equals(x2);
}
};

Cheers,
Doug

[*] The "const &" is implicitly added to eliminate unwanted copies when
passing parameters into signatures.

---
[ 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.comeaucomputing.com/csc/faq.html ]

Scott Meyers
Guest

Posted: Fri Dec 22, 2006 10:10 am Post subject: Re: Concepts Question

Douglas Gregor wrote:

Quote:

Yes.

To both.

Oh, this is going to be fun to explain to people....

Thanks for the explanation, which, upon third reading, actually began to
make sense :-)

Scott

---
[ 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.comeaucomputing.com/csc/faq.html ]

Anders Dalvander
Guest

Posted: Fri Dec 22, 2006 11:39 pm Post subject: Re: Concepts Question

Douglas Gregor wrote:

Quote:

[*] The "const &" is implicitly added to eliminate unwanted copies when
passing parameters into signatures.

Shouldn't a rvalue reference be used instead of a lvalue reference?

// Anders Dalvander

---
[ 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.comeaucomputing.com/csc/faq.html ]

Guest

Posted: Fri Dec 22, 2006 11:47 pm Post subject: Re: Concepts Question

Douglas Gregor wrote:

Quote:

Scott Meyers wrote:
Consider the following text from the June 24, 2006, paper on Concepts
(N2042 --
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2042.pdf):

Here is the definition of LessThanComparable:

auto concept LessThanComparable<typename T> {
bool operator<(T, T);
};

[...]
Inside the body of the concept, we list the declarations that we
expect to have, i.e., an operator< that takes two T parameters and
returns a bool.

Is this really what the above specifies? I'd expect it to mean that
that there must be a function named operator< that can be called with
two objects of type T and that returns a type implicitly convertable
to bool, i.e., that given objects t1 and t2 of type T, the following
expression is legal:

bool b(t1<t1);

Is my expectation correct, or do concepts really specify specific
function signatures?

Yes.

To both.

The LessThanComparable concept really specifies that there is a
function with the signature "bool operator<(T, T)". That's the
declaration we see when we're inside a constrained template like min:

template<typename T
where LessThanComparable<T
const T& min(const T& x, const T& y) {
return x < y? x : y; // x < y finds
LessThanComparable<T>::operator
}

Your explanation is also correct: for a given type X to be
LessThanComparable, one needs an operator< whose parameters can be
initialized with values of type X and whose result type is convertible
to bool.

However, the operator< in LessThanComparable and the operator< for your
type X aren't the same function. LessThanComparable for X has its own
operator<, which will be implicitly generated with the following
definition:

bool LessThanComparable<X>::operator<(const X& x1, const X& x2) {
return x1 < x2;
}
..

OK, let me throw this beer bottle from here in the bleachers:

Seems like LessThanComparable could itself be just a template. Doesn't
really save me that much work to have a separate syntax for "concepts".

template<typename T>
using LessThanComparable<T> // substitution failure IS an error.
const T& min(const T& x, const T& y) {
return x < y? x : y; }

template <typename T>
struct LessThanComparable
{
// This would have to be made legal, including for
// T of built-in type. "explicit" means declaration is
// not visible within class without LessThanComparable::
// prefix.
explicit static bool operator < (const T&x, const T&y)
{ return(x < y); }
};

With this approach, whether there's a default definition or not can
be decided independently for each concept member function.

Does all the new syntax give us clearer instantiation error
messages? If so, discussion of that fact would help build
support.

---
[ 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.comeaucomputing.com/csc/faq.html ]

David Abrahams
Guest

Posted: Sun Dec 24, 2006 3:10 am Post subject: Re: Concepts Question

usenet (AT) aristeia (DOT) com (Scott Meyers) writes:

Quote:

Douglas Gregor wrote:
Yes.

To both.

Oh, this is going to be fun to explain to people....

Thanks for the explanation, which, upon third reading, actually began
to make sense Smile

Hi Scott,

Once you've explained how boost/tr1::function works, the signatures of
concepts also make a lot of sense. And vice-versa. If the analogy
isn't immediately obvious to you, just ask :)

--
Dave Abrahams
Boost Consulting
www.boost-consulting.com

---
[ 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.comeaucomputing.com/csc/faq.html ]

Thorsten Ottosen
Guest

Posted: Sun Dec 24, 2006 6:25 pm Post subject: Re: Concepts Question

Douglas Gregor wrote:

Quote:

This is ok for arguments that are read-only. But what if I have a
function that has these two overloads:

auto concept Foo<class T>
{
void foo(T);
};

struct Bar
{
void foo( const T& );
void foo( T&& );
};

How will the concept forward to the rigth one s.t. efficiency is
preserved? Will there be generated two functions?

-Thorsten

---
[ 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.comeaucomputing.com/csc/faq.html ]

perrog@gmail.com
Guest

Posted: Tue Dec 26, 2006 11:23 pm Post subject: Re: Concepts Question

wkaras (AT) yahoo (DOT) com skrev:

Quote:

I could somewhat agree. It feels like concepts are some kind of
extroverted disposition of class norms, implemented via a class-like
phenomenon (the concept-body) that wraps the original class. Thus,
pointer to member functions, "concept pointers", and "array of
concept elements" becomes orthogonal types to its real types.

But what if some concepts were "introverted", i.e. members of the
concepts are members of the class...? How could this be combined with
concepts?

Unfortunately, pointer and reference to concepts are excluded in
current proposal. Albeit, there are a few "concept pointers"
already today. For example, "int *" points to a type that
implements certain kinds of operators. Basically, if pointer to
concepts should be prohibited, it feels like we need to prohibit
pointer to POD-types in C++.

Merry Christmus in late,
Roger

---
[ 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.comeaucomputing.com/csc/faq.html ]

Douglas Gregor
Guest

Posted: Tue Jan 02, 2007 3:00 pm Post subject: Re: Concepts Question

Thorsten Ottosen wrote:

Quote:

Douglas Gregor wrote:
This is ok for arguments that are read-only. But what if I have a
function that has these two overloads:

auto concept Foo<class T
{
void foo(T);
};

struct Bar
{
void foo( const T& );
void foo( T&& );
};

How will the concept forward to the rigth one s.t. efficiency is
preserved? Will there be generated two functions?

You'll get the first Bar::foo, always. If your "Foo" concept allows one
to have different behavior based on an lvalue vs. an rvalue argument,
put both "foo" functions into the concept definition, e.g.,

auto concept Foo<class T>
{
void foo(T); // same as void foo(const T&);
void foo(T&&);
}

Cheers,
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.comeaucomputing.com/csc/faq.html ]

Douglas Gregor
Guest

Posted: Tue Jan 02, 2007 3:00 pm Post subject: Re: Concepts Question

perrog (AT) gmail (DOT) com wrote:

Quote:

wkaras (AT) yahoo (DOT) com skrev:
With this approach, whether there's a default definition or not can
be decided independently for each concept member function.

The behavior described above is handled by "concept maps" in the
concepts proposal. Anyway...

Quote:

First of all, one can write signatures inside concepts that require
certain member functions; aside from the syntax, concepts don't really
distinguish between member functions and free functions. For instance,
if we want to require member functions "begin" and "end" in our
container concept, we can just write:

concept Container<typename X> {
InputIterator iterator = X::iterator;

iterator X::begin();
iterator X::end();
}

vector<int> would meet the requirements of the concept, as would
list<int>, map<string, int>, etc.

If concepts were to map members of the concepts members of the class,
we'd run into a bit of a problem with multi-parameter concepts, e.g.,

auto concept EqualityComparable<typename T, typename U> {
bool operator<(T, U);
}

Which class is operator< a part of, T or U? What if neither T nor U is
a class?

Quote:

Unfortunately, pointer and reference to concepts are excluded in
current proposal.

Many of us (myself included) come from an object-oriented background,
and because of this one of the hardest things to grasp with concepts is
that concepts are not types. In the OO world, when we want to model an
animal, we write an Animal abstract base class and write specific kinds
of animals (say, Beaver) as subclasses of Animal. So Animal acts as
both a way to describe the requirements on animals (because its members
are common to all animals) and as a way to manipulate any kind of
animal without knowing which one ("Animal*" can point to any subclass
of Animal, i.e., any kind of animal).

Concepts work differently, because they only describe the requirements
on types. So, a concept 'Animal' says what all animals do (in its
members), and anything that behaves like an animal will have a "concept
map" stating how it meets the requirements of the Animal concept. If
you want to manipulate any kind of animal without knowing what specific
kind of animal you have, create a template parameter 'A' and state that
it meets the requirements of the 'Animal' concept. So, concepts
separate the mechanism of describing the properties and behavior of
types (concepts) from the mechanism for writing generic
functions/classes that can act on any type that meets those properties
(templates).

Concepts support a truly different paradigm---we call it "generic
programming"---than the existing mechanisms for object-oriented
programming.

Cheers,
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.comeaucomputing.com/csc/faq.html ]

Douglas Gregor
Guest

Posted: Tue Jan 02, 2007 5:46 pm Post subject: Re: Concepts Question

wkaras (AT) yahoo (DOT) com wrote:

Quote:

Does all the new syntax give us clearer instantiation error
messages? If so, discussion of that fact would help build
support.

Concepts eliminate instantiation-time errors almost entirely. You will
either get an error at template definition time (before instantiation
time) or you get an error in the use of the template (it will not be
instantiated). For example, if one were to write "max" like this:

template<typename T>
where LessThanComparable<T>
const T& max(const T& x, const T& y) {
return x > y? x : y;
}

LessThanComparable only provides "<", so the compiler would produce an
error stating that there is no ">" operation for two values of type
"T". Note that we haven't instantiated "max" yet; we're checking the
uninstantiated template definition. For reference, ConceptGCC says:

honk.cpp: In function 'const T& max(const T&, const T&)':
honk.cpp:6: error: no match for 'operator>' in 'x > y'

Similarly, when we try to call (a corrected) max with a type that does
not provide a suitable "<" operator, the compiler will produce an error
says that the requirements of "max" are not met. It will not try to
instantiate "max", because the instantiation might fail. Again, here's
the ConceptGCC error message (I've invented the type 'X'):

honk.cpp: In function 'int main()':
honk.cpp:13: error: no matching function for call to 'max(X&,
X&)'
honk.cpp:5: note: candidates are: const T& max(const T&, const T&)
[with T = X] <where clause>
honk.cpp:13: note: no concept map for requirement
'std::LessThanComparable<X, X>'

While concepts do improve template error messages, they also improve
the template system in many other ways. The papers and proposals
describe all of the various features of concepts, but the ones that
stand out---aside from separate type checking for templates---are
concept-based overloading, which allows you to overload based on, e.g.,
RandomAccessIterator vs. BidirectionalIterator, and syntax remapping
via concept maps, which allows you to adapt the syntax of a type to
meet the expectations of a template without changing either one.

Cheers,
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.comeaucomputing.com/csc/faq.html ]

Thorsten Ottosen
Guest

Posted: Wed Jan 03, 2007 9:31 pm Post subject: Re: Concepts Question

Douglas Gregor wrote:

Quote:

Thorsten Ottosen wrote:

Douglas Gregor wrote:
This is ok for arguments that are read-only. But what if I have a
function that has these two overloads:

auto concept Foo<class T
{
void foo(T);
};

template< class T >

Quote:

struct Bar
{
void foo( const T& );
void foo( T&& );
};

How will the concept forward to the rigth one s.t. efficiency is
preserved? Will there be generated two functions?

You'll get the first Bar::foo, always. If your "Foo" concept allows one
to have different behavior based on an lvalue vs. an rvalue argument,
put both "foo" functions into the concept definition, e.g.,

auto concept Foo<class T
{
void foo(T); // same as void foo(const T&);
void foo(T&&);
}

Ok. I was thinking that perhaps the generated signature would be as follows:

template< class T >
void Foo<Bar<T>>::foo( T&& r )
{
Bar::foo( std::forward(r) );
}

or something along those lines. The call to std::forward() being the
important thing.

-Thorsten

---
[ 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.comeaucomputing.com/csc/faq.html ]

Guest

Posted: Thu Jan 04, 2007 5:20 pm Post subject: Re: Concepts Question

Douglas Gregor wrote:
..

Quote:

concept-based overloading, which allows you to overload based on, e.g.,
RandomAccessIterator vs. BidirectionalIterator
..

RandomAccessIterator would also (presumably) be a
BidirectionalIterator. Suppose I'm writing a RandomAccessIterator,
but I forget some obscure required member of
RandomAccessIterator (but not a member of BidirectionalIterator).
Would the compiler quietly use the
BidirectionalIterator overload of the template, leaving me to wonder
why my application is running slower than I expected?

---
[ 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.comeaucomputing.com/csc/faq.html ]

Douglas Gregor
Guest

Posted: Thu Jan 04, 2007 8:52 pm Post subject: Re: Concepts Question

wkaras (AT) yahoo (DOT) com wrote:

Quote:

Douglas Gregor wrote:
.
concept-based overloading, which allows you to overload based on, e.g.,
RandomAccessIterator vs. BidirectionalIterator
.

RandomAccessIterator would also (presumably) be a
BidirectionalIterator.

Yes, absolutely. In concept-speak, the RandomAccessIterator concept is
a "refinement" of the BidirectionalIterator concept.

Quote:

Suppose I'm writing a RandomAccessIterator,
but I forget some obscure required member of
RandomAccessIterator (but not a member of BidirectionalIterator).
Would the compiler quietly use the
BidirectionalIterator overload of the template, leaving me to wonder
why my application is running slower than I expected?

Overload resolution would not complain, because it has unambiguously
found a function that matches.

However, in the scenario you describe, the compiler will not stay
silent. To tell the compiler what kind of iterator your type is (input,
forward, mutable bidirectional, etc.), you will need to write a concept
map, e.g.,

concept_map MutableRandomAccessIterator<my_iterator_type> { }

Since you've now claimed that your type is a mutable random access
iterator, the compiler will check that your type meets all of the
syntactic requirements stated by that concept... and emit an error if
you forgot to implement some obscure requirement (like operator[]).

Cheers,
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.comeaucomputing.com/csc/faq.html ]

perrog@gmail.com
Guest

Posted: Thu Jan 04, 2007 10:38 pm Post subject: Re: Concepts Question

Douglas Gregor skrev:

Quote:

perrog (AT) gmail (DOT) com wrote:
wkaras (AT) yahoo (DOT) com skrev:
With this approach, whether there's a default definition or not can
be decided independently for each concept member function.

The behavior described above is handled by "concept maps" in the
concepts proposal. Anyway...

I could somewhat agree. It feels like concepts are some kind of
extroverted disposition of class norms, implemented via a class-like
phenomenon (the concept-body) that wraps the original class. Thus,
pointer to member functions, "concept pointers", and "array of
concept elements" becomes orthogonal types to its real types.

But what if some concepts were "introverted", i.e. members of the
concepts are members of the class...? How could this be combined with
concepts?

First of all, one can write signatures inside concepts that require
certain member functions; aside from the syntax, concepts don't really
distinguish between member functions and free functions. For instance,
if we want to require member functions "begin" and "end" in our
container concept, we can just write:

concept Container<typename X> {
InputIterator iterator = X::iterator;

iterator X::begin();
iterator X::end();
}

vector<int> would meet the requirements of the concept, as would
list<int>, map<string, int>, etc.

I'm afraid I didn't got the picture clear even after this hint. Should
this notation be matched with a concept_map free function syntax taking
the type as first parameter? Or will this act as a "formal" constraint
on types (such as STL vector, list, map, etc.) that already implements
begin() and end()? In constrast to other types, that may use
concept_maps to provide an implicit (default) definition and, hence,
becomes more "informal" constraints. Example:

template<T> where Constrain<T> foo(T &t);

typedef std::vector<int> A;

struct B {
typedef char *iterator;
char *data;
int length;
};

A a;
B b;
foo(a); // ok
foo(b); // error

concept_map Constrain<B> {
iterator begin(B &b) { return b.data; }
iterator end(B &b) { return b.data+b.length; }
};

foo(b); // now ok

---
[ 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.comeaucomputing.com/csc/faq.html ]

Display posts from previous:

	C++Talk.NET Forum Index -> C++ language, library and standards	All times are GMT Goto page 1, 2, 3 Next
Page 1 of 3

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum