Concepts: Why can't it be don't following duck typing - C++ language, library and standards

C++Talk.NET
C++ language newsgroups

Archives

FAQ

Memberlist

Usergroups

Profile

Concepts: Why can't it be don't following duck typing
Goto page 1, 2, 3 Next

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

View previous topic :: View next topic

Author

Message

Ganesh
Guest

Posted: Thu Nov 02, 2006 3:37 pm Post subject: Concepts: Why can't it be don't following duck typing

I was reading the paper "Concepts: Linguistic Support for Generic Programming in C++". The idea is good, but I thought one can take an alternative approach towards that. Basically, one can think of the core idea in using type parameters in templates as "duck typing": if the type looks like a type in the way that is used in the template, then it can be substituted. So, I think, an alternative way to look into the concepts is to simplify it much: template <typename T ducks POD> { // use T in the way we use a POD type } If we want to enforce the some constraint on the way the type parameter is used, it can be provided in the sample class. For example, if the type T is expected to have a virtual destructor, then it can provided in the ducks class and the compiler has to ensure that the instantiating type has the same: struct VirtualDestType { ~VirtualDestType () {} }; template <typename T ducks VirtualDestType> class Use { // use T in the way we use a Virtual dest type void foo() { T * t = new U(); // say U is derived class of T delete t; // T has a virtual destructor, so ~U will be called } } struct Empty {}; struct NoMatch { ~NoMatch(); }; struct Match1 { virtual ~Match1(); }; struct Match2 { Match2() {} virtual ~Match2(); }; Use<Empty> u1; // compiler error, destructor not found while substituting Empty for T Use<NoMatch> u2; // compiler error, destructor is not virtual while substituting NoMatch for T Use<Match1> u3; // fine, the classes basic expectations match - the expected features look alike Use<Match2> u4; // fine, the classes basic expectations match - the expected features look alike, though Match2 has extra things The core idea is this: Provide all the constraints that you want a template parameter to follow in a sample class and say that the template parameter just "ducks" the class thats given as constraint. The advantage is that this is conceptually simple, only one more keyword is required, doesn't break the backward compatibility and easy to use and explain. Thanks! -Ganesh --- [ 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: Sat Nov 04, 2006 4:29 am Post subject: Re: Concepts: Why can't it be don't following duck typing

Ganesh wrote:

Quote:

I was reading the paper "Concepts: Linguistic Support for Generic
Programming in C++". The idea is good, but I thought one can take an
alternative approach towards that.
[snip example]
The core idea is this: Provide all the constraints that you want a
template parameter to follow in a sample class and say that the
template parameter just "ducks" the class thats given as constraint.

What if you want constraints that don't involve member functions?

concept Swappable<typename T> {
void swap(T&, T&);
}

Or you want constraints that involve multiple template parameters?

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

Or constraints that involve nested ("associated") types, e.g., every
sequence has an iterator type whose value_type is equivalent to the
sequence's value type:

concept Sequence<typename X> {
typename value_type; // Sequence's value type
MutableForwardIterator iterator; // Sequence's iterator type
where SameType<value_type, iterator::value_type>; // they are the
same!
}

Quote:

The advantage is that this is conceptually simple, only one more
keyword is required, doesn't break the backward compatibility and easy
to use and explain.

I see two major disadvantages:

1) I believe that "ducks" won't be able to express all of the
requirements that templates actually have. It may appear simpler, but
it is an incomplete solution.

2) Just what attributes of a class does "ducks" pick up? Its member
functions, constructors and destructors? What if they are private?
Protected? What about friends? Free functions? Static members? The
object's size? Alignment? vtable layout? Start specifying this and I
think you'll find that "ducks" isn't so simple after all. Better to
have a new "concept" (pun intended) that ties down precisely what
requirements you want to pick up.

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 ]

Andrei Polushin
Guest

Posted: Sun Nov 05, 2006 1:09 am Post subject: Re: Concepts: Why can't it be don't following duck typing

Douglas Gregor wrote:

Quote:

What if you want constraints that don't involve member functions?

concept Swappable<typename T> {
void swap(T&, T&);
}

BTW, why did you define concept members as free functions by default?

You have:

concept Swappable<typename T> {
void T::swap(T&); // member function
void swap(T&, T&); // free function
}

Could it be:

concept Swappable<typename T> {
void swap(T&); // member function
friend void swap(T&, T&); // free function
}

In other words, could it be more user-friendly?

--
Andrei Polushin

---
[ 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: Sun Nov 05, 2006 7:34 pm Post subject: Re: Concepts: Why can't it be don't following duck typing

Andrei Polushin wrote:

Quote:

Douglas Gregor wrote:
What if you want constraints that don't involve member functions?

concept Swappable<typename T> {
void swap(T&, T&);
}

BTW, why did you define concept members as free functions by default?

Several reasons, including:

1) Because member functions are unfriendly toward built-in types
(e.g., int* can't have a member "swap", but there can be a free
function "swap" for int*'s). This is the reason that most interfaces to
templates rely on free functions and operators, rather than member
functions. Concepts need to model those kinds of interfaces.

2) Because it would be unclear *which* parameter to the concept the
functions are a member of. For example, let's try writing an
EqualityComparable concept with member functions by default:

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

Are those operator== member functions in T, or in U? Or is it different
for each of them? With the free function form, it's clear because we
have to state which type parameter the operator is a member of:

concept EqualityComparable<typename T, typename U> {
bool T::operator==(U);
bool U::operator==(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 ]

Andrei Polushin
Guest

Posted: Mon Nov 06, 2006 1:51 am Post subject: Re: Concepts: Why can't it be don't following duck typing

Douglas Gregor wrote:

Quote:

Andrei Polushin wrote:
BTW, why did you define concept members as free functions by default?

Several reasons, including:

1) Because member functions are unfriendly toward built-in types
(e.g., int* can't have a member "swap", but there can be a free
function "swap" for int*'s). This is the reason that most interfaces to
templates rely on free functions and operators, rather than member
functions. Concepts need to model those kinds of interfaces.

Got your point. Does it encourage me to abandon OO programming in
preference to free functions, like in C? While you are defining the
concepts for the C++ Standard, you are dealing primarily with the
built-in types inherited from C, so it's practically correct. But will
it still be the better solution in the modern OO world? Wouldn't it be
better to enhance those built-in types with members:

concept Swappable<typename T> {
void T::swap(T&) { swap(*this, T); } // member function
bool swap(T, T); // free function
};

Quote:

2) Because it would be unclear *which* parameter to the concept the
functions are a member of. For example, let's try writing an
EqualityComparable concept with member functions by default:

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

Are those operator== member functions in T, or in U? Or is it different
for each of them? With the free function form, it's clear because we
have to state which type parameter the operator is a member of:

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

Probably, there is no need for template parameter T (just like there is
no need to pass 'this' parameter to our member functions - it is passed
implicitly all the time):

concept EqualityComparableTo<typename U> {
bool operator==(U); // member of T
bool U::operator==(EqualityComparableTo); // member of U
}

In other words, concept is just a template with an implicitly passed
first template-parameter. Thus you can reuse the hundreds of rules and
design issues we already have for templates, not reinventing them
specially for concepts. For example, the "concept map" could be called
a "concept specialization", modeling the template specialization, etc.

Surprisingly, you concede to this view with "inline requirements"
(N2081, section 3.4.2):

// your syntax
concept ConvertibleTo<typename T, typename U> {
operator U();
};

// my syntax
concept ConvertibleTo<typename U> {
operator U();
};

// both yours and mine syntax
template <typename U, ConvertibleTo<U> T>
U convert(const T& t) {
return t;
}

But "inline requirements" is an exception for the rules you propose.

--
Andrei Polushin

---
[ 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: Mon Nov 06, 2006 3:49 pm Post subject: Re: Concepts: Why can't it be don't following duck typing

Andrei Polushin wrote:

Quote:

Even in the modern world, we often prefer free functions to member
functions, and not because of the built-in types we inherited from C.
Here's what Scott Meyers has to say about prefering free functions to
improve encapsulation:

http://www.ddj.com/dept/cpp/184401197

Free functions are also better for interoperability. It's easy to add a
new free function for a built-in type or a class that you didn't write,
but it's not so easy to add a new member function to a built-in type
(they can't have member functions!) or a class that you didn't write
(e.g., it might come from a library that you can't modify). There's an
important point here: the problems that one has with using built-in
types in an OO context (such as the inability to add a new member
function or derive from a new abstract base class) are also problems
with any classes that you didn't write.

Quote:

But will
it still be the better solution in the modern OO world? Wouldn't it be
better to enhance those built-in types with members:

concept Swappable<typename T> {
void T::swap(T&) { swap(*this, T); } // member function
bool swap(T, T); // free function
};

Concepts fix the inability to add new member functions, in the sense
that you can use a concept map to make it look like a certain type has
that member function (even when it doesn't). So, if you want to write
all of your concepts to use member functions rather than free
functions, go ahead: the concept system can handle it.

Quote:

2) Because it would be unclear *which* parameter to the concept the
functions are a member of. For example, let's try writing an
EqualityComparable concept with member functions by default:

concept EqualityComparable<typename T, typename U> {
bool operator==(T);
bool operator==(U);
}
[snip]
Probably, there is no need for template parameter T (just like there is
no need to pass 'this' parameter to our member functions - it is passed
implicitly all the time):

concept EqualityComparableTo<typename U> {
bool operator==(U); // member of T
bool U::operator==(EqualityComparableTo); // member of U
}

Note that this has slightly different semantics than the
EqualityComparable that uses a free operator==(T, U), because of the
way C++ treats the implicit object parameter.

Quote:

In other words, concept is just a template with an implicitly passed
first template-parameter.

This was discussed a few years ago, and eventually rejected. The
implication of this code is that EqualityComparableTo is a type, in the
same sense that a OO interface or abstract base class is a type. This
is not the case: concepts describe requirements on types, but they are
not types themselves. Using a syntax like the above confuses the issue
greatly.

Quote:

I tried to turn concept maps into concept specializations at one point,
for the same reason you mention, and it turned out to be a bad idea:
people were very confused by the use of specialization syntax, whereas
they seem to understand the concept map syntax much better.

Quote:

Surprisingly, you concede to this view with "inline requirements"
(N2081, section 3.4.2):

// your syntax
concept ConvertibleTo<typename T, typename U> {
operator U();
};

That should be:

operator U(T);

Quote:

But "inline requirements" is an exception for the rules you propose.

Inline requirements is a shortcut that is useful for many common cases.
We kept it out of the concept system for a long time because it can be
confusing (the "type-of-a-type" view of concepts breaks down
eventually). However, it's such a good shortcut syntactically that it
just kept coming back :)

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 ]

Andrei Polushin
Guest

Posted: Mon Nov 06, 2006 8:09 pm Post subject: Re: Concepts: Why can't it be don't following duck typing

Douglas Gregor wrote:

Quote:

The use of the word "encapsulation" in his article is very doubtful.
I've already answered to it:
http://groups.google.com/group/comp.lang.c++.moderated/msg/fb30c8094d82aef2

Quote:

Free functions are also better for interoperability. It's easy to add a
new free function for a built-in type or a class that you didn't write,
but it's not so easy to add a new member function to a built-in type
(they can't have member functions!) or a class that you didn't write
(e.g., it might come from a library that you can't modify). There's an
important point here: the problems that one has with using built-in
types in an OO context (such as the inability to add a new member
function or derive from a new abstract base class) are also problems
with any classes that you didn't write.

But will
it still be the better solution in the modern OO world? Wouldn't it be
better to enhance those built-in types with members:

concept Swappable<typename T> {
void T::swap(T&) { swap(*this, T); } // member function
bool swap(T, T); // free function
};

Concepts fix the inability to add new member functions, in the sense
that you can use a concept map to make it look like a certain type has
that member function (even when it doesn't). So, if you want to write
all of your concepts to use member functions rather than free
functions, go ahead: the concept system can handle it.

Rereading this and the previous part of your answer, I'm also in doubt.
Concept system *can handle* adding new member functions, so there is
*no problem* with the inability to add new member functions for foreign
classes and built-in types. Probably, concepts still support legacy
programming practices, invented for the lack of modern concepts.

Quote:

2) Because it would be unclear *which* parameter to the concept the
functions are a member of. For example, let's try writing an
EqualityComparable concept with member functions by default:

concept EqualityComparable<typename T, typename U> {
bool operator==(T);
bool operator==(U);
}
[snip]
Probably, there is no need for template parameter T (just like there is
no need to pass 'this' parameter to our member functions - it is passed
implicitly all the time):

concept EqualityComparableTo<typename U> {
bool operator==(U); // member of T
bool U::operator==(EqualityComparableTo); // member of U
}

Note that this has slightly different semantics than the
EqualityComparable that uses a free operator==(T, U), because of the
way C++ treats the implicit object parameter.

Yes, we define binary operators as free functions, but I was answering
to the "unclear *which* parameter to the concept the functions are a
member of", so translating your example literally, to illustrate how
it would look clear and familiar for us.

Quote:

In other words, concept is just a template with an implicitly passed
first template-parameter.

This was discussed a few years ago, and eventually rejected. The
implication of this code is that EqualityComparableTo is a type, in the
same sense that a OO interface or abstract base class is a type. This
is not the case: concepts describe requirements on types, but they are
not types themselves. Using a syntax like the above confuses the issue
greatly.

We don't have the keyword "interface" in C++, but we do not hesitate
to constraint our classes by interfaces.

Really: interface is a type that constraints any class for use by the
function that operates on that interface.

Likewise: concept is a template-type that constraints any type for use
by the template-function that operates on that concept.

I'm not confused with this metaphor, but I feel its more natural.
Concept could be the type in the same sense as interface is a type.

Quote:

Thus you can reuse the hundreds of rules and
design issues we already have for templates, not reinventing them
specially for concepts. For example, the "concept map" could be called
a "concept specialization", modeling the template specialization, etc.

I tried to turn concept maps into concept specializations at one point,
for the same reason you mention, and it turned out to be a bad idea:
people were very confused by the use of specialization syntax, whereas
they seem to understand the concept map syntax much better.

Did you try the following syntax (keyword "class" denotes constrained
class; keyword "typename" denotes another concept-parameter):

template <class> // primary concept (non-specialized)
concept Iterator {
typename value_type; // requirement for type
typename reference; // requirement for type
typename pointer; // requirement for type

reference operator*() = 0; // requirement for member
pointer operator->() // requirement for member
{
return &operator*(); // default implementation
}
};

template <typename T> // specialization for T*
concept Iterator<T*> {
typedef T value_type;
typedef T& reference;
typedef T* pointer;

reference operator*() = 0;
pointer operator->() = 0;
};

Here I define the primary concept and the concept specialization, just
following the syntax of templates. Probably, it could be much better
understood than concept map, because we are already familiar with such
syntax.

Another issue is the "= 0" at the end of pure requirement, so we may
define the "default implementation" somewhere else, probably in a
separate translation unit. Currently, you allow this for concept maps
(N2081, 3.3.1/3), but not for concepts themselves.

There are many generalizations I see when following this way.

Quote:

Surprisingly, you concede to this view with "inline requirements"
[...]
But "inline requirements" is an exception for the rules you propose.

Inline requirements is a shortcut that is useful for many common cases.
We kept it out of the concept system for a long time because it can be
confusing (the "type-of-a-type" view of concepts breaks down
eventually). However, it's such a good shortcut syntactically that it
just kept coming back Smile

I would like to see how it breaks down :)

--
Andrei Polushin

---
[ 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: Mon Nov 06, 2006 10:38 pm Post subject: Re: Concepts: Why can't it be don't following duck typing

Andrei Polushin wrote:

Quote:

Douglas Gregor wrote:
Probably, concepts still support legacy
programming practices, invented for the lack of modern concepts.

Not all of us agree that the use of free functions instead of member
functions is "legacy"; I prefer to think of it as "post-modern" :)

Quote:

Really: interface is a type that constraints any class for use by the
function that operates on that interface.

Likewise: concept is a template-type that constraints any type for use
by the template-function that operates on that concept.

I'm not confused with this metaphor, but I feel its more natural.
Concept could be the type in the same sense as interface is a type.

Did you try the following syntax (keyword "class" denotes constrained
class; keyword "typename" denotes another concept-parameter):

template <class> // primary concept (non-specialized)
concept Iterator {
typename value_type; // requirement for type
typename reference; // requirement for type
typename pointer; // requirement for type

reference operator*() = 0; // requirement for member
pointer operator->() // requirement for member
{
return &operator*(); // default implementation
}
};

You can find examples of this in some of the very early work on
concepts in C++, e.g., N1510

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1510.pdf

It has since been rejected, in part because we need a name for the type
of the implicit "this" parameter.

Quote:

template <typename T> // specialization for T*
concept Iterator<T*> {
typedef T value_type;
typedef T& reference;
typedef T* pointer;

reference operator*() = 0;
pointer operator->() = 0;
};

Here I define the primary concept and the concept specialization, just
following the syntax of templates. Probably, it could be much better
understood than concept map, because we are already familiar with such
syntax.

We tried almost exactly this syntax in N1849 (but with free functions
as the basis, not member functions):

http://www.generic-programming.org/languages/conceptcpp/papers/n1849.pdf

It confused people. I'm not speculating, I'm reporting my experiences
teaching people concepts: the specialization syntax does not work.

Quote:

Doesn't work, unfortunately. We need to check the default
implementation of a concept whenever the user writes a concept map for
that concept (or matches an "auto" concept). Even if we could get
around that (say, by making default implementations fully type-checked
when they are defined), then we'd be requiring separate compilation of
these default implementations, which amounts to separate compilation of
templates.

Quote:

Let's look at this example again:

concept EqualityComparableTo<typename U> {
bool operator==(U); // member of T
bool U::operator==(EqualityComparableTo); // member of U
}

First, a point on syntax: we've not qualified the first operator==, so
it's a part of the implicit type "T"; effectively, we're looking for
T::operator==. We have qualified the second operator==, but rather than
being "T::U::operator==", as the first might suggest, it's just
"U::operator==". I find that nonuniformity rather unsatisfying.

Now, that EqualityComparableTo parameter in the second operator==...
does that mean
(1) The type of the implicit "this" parameter, what we've been
calling "T"?, or
(2) Any type that meets the requirements of EqualityComparableTo<U>?

If it's (1), we now have a big difference from the way
interfaces/abstract base classes work, because they are based on a
subtyping relationship. That's doable, but it weakens the OO analogies
significantly.

If it's (2), we now have an operator== that is effectively a template,
because the right-hand side can accept *any* type that meets the
requirements of EqualityComparableTo<U>. This is okay in OO land,
because one would just use virtual functions in U to do the
comparison... but we don't have virtual functions in the world of
concepts.

I think the issues might crop up with non-parameterized concepts. If
one wrote something like this:

concept EqualityComparable1 {
bool operator==(EqualityComparable1);
}

Aside from concept maps and their use in adaptation of syntax, how does
that differ from the abstract base class:

class EqualityComparable {
bool equals(const EqualityComparable&) = 0;
};

?

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 ]

Andrei Polushin
Guest

Posted: Tue Nov 07, 2006 5:04 am Post subject: Re: Concepts: Why can't it be don't following duck typing

Douglas Gregor wrote:

Quote:

Andrei Polushin wrote:
Did you try the following syntax (keyword "class" denotes constrained
class; keyword "typename" denotes another concept-parameter):

template <class> // primary concept (non-specialized)
concept Iterator {
typename value_type; // requirement for type
typename reference; // requirement for type
typename pointer; // requirement for type

reference operator*() = 0; // requirement for member
pointer operator->() // requirement for member
{
return &operator*(); // default implementation
}
};

[...]
It has since been rejected, in part because we need a name for the type
of the implicit "this" parameter.

I've omitted that name for the purposes of the example above. You can
read it as

template <class T> // implicit type T is unused
concept Iterator {
// ...
}

Quote:

template <typename T> // specialization for T*
concept Iterator<T*> {
typedef T value_type;
typedef T& reference;
typedef T* pointer;

reference operator*() = 0;
pointer operator->() = 0;
};

(I'm quoting this just for context).

Quote:

Another issue is the "= 0" at the end of pure requirement, so we may
define the "default implementation" somewhere else, probably in a
separate translation unit. Currently, you allow this for concept maps
(N2081, 3.3.1/3), but not for concepts themselves.

Doesn't work, unfortunately. We need to check the default
implementation of a concept whenever the user writes a concept map for
that concept (or matches an "auto" concept). Even if we could get
around that (say, by making default implementations fully type-checked
when they are defined), then we'd be requiring separate compilation of
these default implementations, which amounts to separate compilation of
templates.

?? Yes, concepts will greatly simplify the task of separate compilation
of templates because they provide all neccessary type-checking.
Concepts are predictable "interfaces" for template code, and the code
that provides a predictable interface could be compiled separately.
Thus the "export" problem could be solved, I don't know why you didn't
mention that benefit in your proposal.

BTW, by "separate compilation" I mean a compilation into some specific
"byte code", not into binary objects.

Quote:

Surprisingly, you concede to this view with "inline requirements"
[...]
But "inline requirements" is an exception for the rules you propose.
Inline requirements is a shortcut that is useful for many common cases.
We kept it out of the concept system for a long time because it can be
confusing (the "type-of-a-type" view of concepts breaks down
eventually). However, it's such a good shortcut syntactically that it
just kept coming back Smile

I would like to see how it breaks down :)

Let's look at this example again:

concept EqualityComparableTo<typename U> {
bool operator==(U); // member of T
bool U::operator==(EqualityComparableTo); // member of U
}

First, a point on syntax: we've not qualified the first operator==, so
it's a part of the implicit type "T"; effectively, we're looking for
T::operator==. We have qualified the second operator==, but rather than
being "T::U::operator==", as the first might suggest, it's just
"U::operator==". I find that nonuniformity rather unsatisfying.

Now, that EqualityComparableTo parameter in the second operator==...
does that mean
(1) The type of the implicit "this" parameter, what we've been
calling "T"?, or
(2) Any type that meets the requirements of EqualityComparableTo<U>?

I would like to recall a better syntax, quoted at the beginning
of this post:

// keyword "class" denotes constrained class
// keyword "typename" denotes another parameter

template <class T, typename U = T>
concept EqualityComparableTo {
bool operator==(U) = 0; // member of T
bool U::operator==(T) = 0; // member of U - accepts T
}

Now the answer is: (1) The type of the implicitly passed T parameter.
(This parameter is *passed* implicitly, but we still can mention it
everywhere in concept, and create specializations on it.)

Now the prevous question

Quote:

We have qualified the second operator==, but rather than
being "T::U::operator==", as the first might suggest, it's just
"U::operator==". I find that nonuniformity rather unsatisfying.

Could be resolved this way:

// parameter U is already constrained

template <class T, EqualityComparableTo<T> U = T>
concept EqualityComparableTo {
bool operator==(U) = 0; // member of T
}

Here we constrain exactly one type in each concept.
And I'm rather satisfied with that uniformity :)

Quote:

I think the issues might crop up with non-parameterized concepts. If
one wrote something like this:

concept EqualityComparable1 {
bool operator==(EqualityComparable1);
}

Aside from concept maps and their use in adaptation of syntax, how does
that differ from the abstract base class:

class EqualityComparable {
bool equals(const EqualityComparable&) = 0;
};

I would like the concepts as base classes, so I need no difference.
There are useful applications of this feature: we can use them
in place of CRTP, or use them to implement mix-in classes.

--
Andrei Polushin

---
[ 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: Tue Nov 07, 2006 6:37 am Post subject: Re: Concepts: Why can't it be don't following duck typing

"Douglas Gregor" <doug.gregor (AT) gmail (DOT) com> writes:

Quote:

Andrei Polushin wrote:

Douglas Gregor wrote:

the "type-of-a-type" view of concepts breaks down
eventually
...

I would like to see how it breaks down :)

Let's look at this example again:

<snip long example>

not to mention the much simpler fact that the "type-of-a-type" view
doesn't support multi-type concepts. Justifying the need for
multi-type concepts takes a little doing, but I think it might be a
lot less text than the long example.

--
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 ]

Andrei Polushin
Guest

Posted: Tue Nov 07, 2006 8:20 pm Post subject: Re: Concepts: Why can't it be don't following duck typing

David Abrahams wrote:

Quote:

"Douglas Gregor" <doug.gregor (AT) gmail (DOT) com> writes:
Andrei Polushin wrote:
Douglas Gregor wrote:
the "type-of-a-type" view of concepts breaks down
eventually
...
I would like to see how it breaks down Smile

You do not provide an example, so I was stumbled to understand what
problem you mean. Then I've found that N2081 prohibits use of inline
requirements shortcut for multi-type parameters (3.4.2/4).
In contrast, I did provide an example in another post, in assumption
that this syntax is already allowed:

// EqualityComparableTo<T> is not allowed by N2081

template <class T, EqualityComparableTo<T> U = T>
concept EqualityComparableTo {
bool operator==(U) = 0;
}

That prohibition looks strange for me, but I've discovered that Doug
also tends to allow it (in article from his blog):
http://conceptgcc.wordpress.com/2006/06/02/parameterized-types-of-types/

It has the status of "shortcut" there, but we see how it simplifies
the whole story (32 lines => 21 lines => 13 lines, see the article):

template<InputIterator Iter1, InputIterator Iter2, typename T,
typename BinOp1,
Callable2<Iter1::reference, Iter2::reference> BinOp2>
where Callable2<BinOp1, T, BinOp2::result_type>&&
Assignable<
T,
Callable2<BinOp1, T, BinOp2::result_type>::result_type

Quote:

inner_product(Iter1 first1, Iter1 last1,
Iter2 first2, T init,
BinOp1 binary_op1,
BinOp2 binary_op2)

Now imaging the following "type-of-a-type" syntax for the constrained
templates:

template-declaration:
*template* </template-parameter-list/> /where-clause/ /declaration/

where-clause:
*where* </template-parameter-list/>

(only 2 syntactic rules; compare to syntax in N2081 3.4 and 3.4.1).

Having this, I can redefine the inner_product in a shorter way:

template<InputIterator Iter1, InputIterator Iter2, typename T,
typename BinOp1,
Callable2<Iter1::reference, Iter2::reference> BinOp2>
where <Callable2<T, BinOp2::result_type> BinOp1,
Assignable<BinOp1::result_type> T>
T
inner_product(Iter1 first1, Iter1 last1,
Iter2 first2, T init,
BinOp1 binary_op1,
BinOp2 binary_op2)

Note that I've used the "type-of-a-type" view for the rather complex
example and encounter no problem. There is still the need for the
"where" clause, but I do not even try to argue against it.

Other example constraints the nested type:

template<InputIterator Iter1, ForwardIterator Iter2>
where <EqualityComparableTo<Iter1::reference> Iter2::reference>
Iter1 find_first_of(Iter1 first1, Iter1 last1,
Iter2 first2, Iter2 last2);

The comma inside the where<,,,> clause is an AND constraint. Let's
try to consider the need for the OR and NOT constraints.

An example with OR constraint (the authors of N2081 are in doubt
about the need for OR constraint):

template<Integral T> T abs(T x) { return x < 0 ? -x : x; }
template<Floating T> T abs(T x) { return x < 0 ? -x : x; }

Two templates - is it bad? With the "type-of-a-type" view, we are
suggested to introduce a base concept "Signed":

template<Signed T> T abs(T x) { return x < 0 ? -x : x; }

Thus I see no need for OR constraint.

The NOT constraint is rather more redundant: it is "used to direct
concept-based overloading", so that the overload *knows in advance*
that another overload exists. The result is identical once we have
the declarations of both overloads, so I think we don't need the
NOT constraint.

I still hope to see how the "type-of-a-type" view breaks down.

--
Andrei Polushin

---
[ 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: Wed Nov 08, 2006 10:10 am Post subject: Re: Concepts: Why can't it be don't following duck typing

"Andrei Polushin" <polushin (AT) gmail (DOT) com> writes:

Quote:

David Abrahams wrote:
"Douglas Gregor" <doug.gregor (AT) gmail (DOT) com> writes:
Andrei Polushin wrote:
Douglas Gregor wrote:
the "type-of-a-type" view of concepts breaks down
eventually
...
I would like to see how it breaks down Smile

Let's look at this example again:

snip long example

not to mention the much simpler fact that the "type-of-a-type" view
doesn't support multi-type concepts. Justifying the need for
multi-type concepts takes a little doing, but I think it might be a
lot less text than the long example.

You do not provide an example, so I was stumbled to understand what
problem you mean. Then I've found that N2081 prohibits use of inline
requirements shortcut for multi-type parameters (3.4.2/4).
In contrast, I did provide an example in another post, in assumption
that this syntax is already allowed:

// EqualityComparableTo<T> is not allowed by N2081

template <class T, EqualityComparableTo<T> U = T
concept EqualityComparableTo {
bool operator==(U) = 0;
}

This only works for "dependent" multi-type concepts. What you can't
do is write a matrix-vector multiplication function that requires that
together, the matrix and vector satisfy the VectorSpace<M,V> concept.

template <class M, class V>
where VectorSpace<M,V>
V mul(M m, V v)
{
...
}

and, no, I don't consider

template <class M, class V>
V mul(M m, FormsAVectorSpaceWith<M> V v)
{
...
}

to be acceptable. What happens when the first argument has to
be the Vector type?

template <class V, class M>
V mul2(V v, MatrixOfAVectorSpaceWith<V> M m)
{
...
}

template <class M, class V>
V mul(M m, VectorOfAVectorSpaceWith<M> V v)
{
...
}

It doesn't scale.

--
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 ]

Douglas Gregor
Guest

Posted: Wed Nov 08, 2006 9:10 pm Post subject: Re: Concepts: Why can't it be don't following duck typing

Andrei Polushin wrote:

Quote:

Douglas Gregor wrote:
?? Yes, concepts will greatly simplify the task of separate compilation
of templates because they provide all neccessary type-checking.
Concepts are predictable "interfaces" for template code, and the code
that provides a predictable interface could be compiled separately.

Almost. The fact is that you can't get "perfect" type checking unless
you throw away or restrict specialization, and without perfect type
checking you can't do true separate compilation. Here's my favorite
example where specialization breaks the type-checking that concepts
provide:

template<CopyConstructible T>
void foo(vector<T>& vec) {
T& x = vec.front();
}

Does it type check? Yup.
Does it work for T = int? Yup.
Does it work for T = bool? Nope, vector<bool>'s front() method returns
a class type, not a bool&.

Here, we ended up getting a specialization at instantiation time that
didn't exactly have the same interface as the primary template. The
issue (along with ambiguity issues that crop up at instantiation time
with concepts) is covered in more depth in this paper:
http://portal.acm.org/citation.cfm?id=1133981.1134014

Quote:

Thus the "export" problem could be solved, I don't know why you didn't
mention that benefit in your proposal.

BTW, by "separate compilation" I mean a compilation into some specific
"byte code", not into binary objects.

Export might be easier to implement for constrained templates; I don't
really know. Actual separate compilation would be an interesting
research project, but there are significant challenges ahead.

Quote:

Oh, that's subtle. Especially given that "T" in the example below
doesn't actually have to be a class.
Do you want to teach programmers that "class" and "typename" mean
exactly the same thing in templates, unless that template happens to be
a concept?

Quote:

Now the prevous question

We have qualified the second operator==, but rather than
being "T::U::operator==", as the first might suggest, it's just
"U::operator==". I find that nonuniformity rather unsatisfying.

Could be resolved this way:

// parameter U is already constrained

template <class T, EqualityComparableTo<T> U = T
concept EqualityComparableTo {
bool operator==(U) = 0; // member of T
}

Here we constrain exactly one type in each concept.

Sounds very limiting; see David Abrahams' examples.

Quote:

And I'm rather satisfied with that uniformity Smile

Are you satisfied with the recursive constraint specification? "int" is
only EqualityComparableTo<long> if "long" is EqualityComparableTo<int>,
which only holds if "int" is EqualityComparableTo<long>...

Quote:

Aside from concept maps and their use in adaptation of syntax, how does
that differ from the abstract base class:

class EqualityComparable {
bool equals(const EqualityComparable&) = 0;
};

I would like the concepts as base classes, so I need no difference.

I have a hard time understanding how the "SameType" concept, which
states that its two type parameters are precisely the same type (not
subclasses of the same type), can work when concepts are base classes.

If A inherits SameType<B>, and A == B, then B inherits SameType<A>...
but, well, we have another recursive constraint, which is rather weird.
Also, if one then inherits A in a new subclass D, we can't have D
inherit SameType<B> (even though A inherits SameType<B>!), because D !=
B.

Note that if you can't handle SameType, you can't express the concept
constraints in the C++ Standard Library.

Quote:

There are useful applications of this feature: we can use them
in place of CRTP, or use them to implement mix-in classes.

We already do CRTP and mix-in classes, and concepts support those uses.

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: Wed Nov 08, 2006 9:12 pm Post subject: Re: Concepts: Why can't it be don't following duck typing

Andrei Polushin wrote:

Quote:

You do not provide an example, so I was stumbled to understand what
problem you mean. Then I've found that N2081 prohibits use of inline
requirements shortcut for multi-type parameters (3.4.2/4).

3.4.1/1 explicitly allows the use of inline requirements for multi-type
parameters. 3.4.2/4 only deals with multi-type parameters that have
defaulted arguments after the first argument.

Quote:

An example with OR constraint (the authors of N2081 are in doubt
about the need for OR constraint):

template<Integral T> T abs(T x) { return x < 0 ? -x : x; }
template<Floating T> T abs(T x) { return x < 0 ? -x : x; }

Two templates - is it bad? With the "type-of-a-type" view, we are
suggested to introduce a base concept "Signed":

template<Signed T> T abs(T x) { return x < 0 ? -x : x; }

Thus I see no need for OR constraint.

Right. The current formulation of concepts supports the same notion;
just write a "Signed" concept (with one type parameter). Integral and
Floating would either refine Signed (if you happen to be able to change
Integral and Floating!), or there would be concept maps mapping from
Integral and Floating to Signed.

Quote:

There might not be an ordering among those two overloads based only on
their normal constraints. It doesn't happen often, and it doesn't
happen in the simple cases. The NOT constraint allows you to handle the
hard cases where you truly have disjoint requirements in two overloads,
but you need concept-based overloading to order them. unique_copy is a
truly intruiging example where the C++ standard describes several
variants of the algorithm that have some constraints that aren't
ordered:

http://conceptgcc.wordpress.com/2006/04/27/unique_copy-is-truly-unique/

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 ]

Andrei Polushin
Guest

Posted: Wed Nov 08, 2006 10:31 pm Post subject: Re: Concepts: Why can't it be don't following duck typing

Douglas Gregor wrote:

Quote:

The NOT constraint is rather more redundant: it is "used to direct
concept-based overloading", so that the overload *knows in advance*
that another overload exists. The result is identical once we have
the declarations of both overloads, so I think we don't need the
NOT constraint.

There might not be an ordering among those two overloads based only on
their normal constraints. It doesn't happen often, and it doesn't
happen in the simple cases. The NOT constraint allows you to handle the
hard cases where you truly have disjoint requirements in two overloads,
but you need concept-based overloading to order them. unique_copy is a
truly intruiging example where the C++ standard describes several
variants of the algorithm that have some constraints that aren't
ordered:

http://conceptgcc.wordpress.com/2006/04/27/unique_copy-is-truly-unique/

I've found that we can write four overloads instead of three to resolve
the issue with unique_copy:

// 1
template<InputIterator InIter,
OutputIterator<
InIter::value_type> OutIter>
where <EqualityComparable InIter::value_type,
Assignable InIter::value_type,
CopyConstructible InIter::value_type>
// !ForwardIterator InIter
// !MutableForwardIterator OutIter
OutIter unique_copy(InIter first, InIter last, OutIter result);

// 2
template<ForwardIterator InIter,
OutputIterator<
InIter::value_type> OutIter>
where <EqualityComparable InIter::reference>
// !MutableForwardIterator OutIter
OutIter unique_copy(InIter first, InIter last, OutIter result);

// 3
template<InputIterator InIter,
MutableForwardIterator OutIter>
where <EqualityComparable<
InIter::value_type> OutIter::reference>
Assignable<
InIter::reference> OutIter::reference>
// !ForwardIterator InIter
OutIter unique_copy(InIter first, InIter last, OutIter result);

// 4
template<ForwardIterator InIter,
MutableForwardIterator OutIter>
where <EqualityComparable InIter::reference>
OutIter unique_copy(InIter first, InIter last, OutIter result);

In short, it's like the following:

unique_copy(InputIterator, InputIterator, OutputIterator);
unique_copy(ForwardIterator,ForwardIterator,OutputIterator);
unique_copy(InputIterator, InputIterator, MutableForwardIterator);
unique_copy(ForwardIterator,ForwardIterator,MutableForwardIterator);

where the 4th overload resolves an ambiguity between 2nd and 3rd.

In general, 2 different requirements for each of N parameters will
require 2*N overloads. It's bad, but knowing in advance that another
overload exists is worse, IMHO.

--
Andrei Polushin

---
[ 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