Re: C++ Template Overloading
On Apr 11, 10:41 am, "Emerson" <emerson.cla...@gmail.com> wrote:
I just finished watching a Google tech talk presentation on concepts
in the upcoming C++0x standard and it left me wondering. The concepts
seem like a good idea, but it does concern me that such metaphore
specific notions are making it into the C++ language ahead of perhaps
more basic and useful features.
Thanks for taking the time to watch the talk and air your concerns to
the community.
The metaphore that i refer to is that off iterators. Without
iterators, STL would not be what it is. Both STL and Boost are
libraries which have been designed around a single idea, the use of C+
+ operators to provide non type specific generic algorithms and
containers. But it means that the algorithms and containers are
restricted to things which behave like pointers. C++ operators are
convinient becuase they dont require you to specify types in the
definition of your code and they support primitive types which you
cannot do directly with interfaces, but it isnt very OO and no, i dont
buy the notion of "parametric polymorphism".
There's nothing to "buy" with parametric polymorphism. It's a way of
expressing polymorphism, and it has various pros and cons relative to
subtype polymorphism, which is used by object-oriented languages, or F-
bounded polymorphism, which is used by the generics features of Java
and C#.
The boundary between the opaque and the visible for the user only
occurs when they dereference an iterator, at this point the user must
know the underlying type and the generic metaphore falls away to
expose the details of the implementation.
Not necessarily. When one dereferences an iterator whose type is
unknown, you get back a value_type for that iterator. By default, you
know nothing about that value_type, but the concept system allows you
to place constraints on that value_type to say what it must be able to
do. For example, you can say that it has a < operator allowing you to
compare to values, or that it has + and = operators that allow you to
add values and assign the result. For example, we could write a
simplified binary search over arbitrary sequences like this:
template<RandomAccessIterator Iter>
requires LessThanComparable<Iter::value_type>
bool binary_search(Iter first, Iter last, Iter::value_type const&
value) {
Iter mid = first + (last - first) / 2;
if (*first < *mid) { // okay: we know that Iter::value_type, the
type returned when derferencing an iterator has a < operator
// ...
} else {
// ...
}
}
This is a clever workaround and it has allowed libraries like Boost
and STL to flourish, but it is not the only way, and it has its
drawbacks. For instance, using the STL metaphore it is not possible
to create a function which takes only an iterator of integers because
there is no such thing as an iterator of integers, the underlying type
is hidden.
This is possible. If you truly want to accept an InputIterator
sequence for which the value_type is 'int', you can do so:
template<InputIterator Iter>
requires SameType<Iter::value_type, int>
void foo(Iter first, Iter last);
Although in general one would probably want to take any Integral type,
since C++ has so many to choose from:
template<InputIterator Iter>
requires Integral<Iter::value_type>
void foo(Iter first, Iter last);
Iterators deal only with operators, not with types or
interfaces. Its more like passing around macros, with all of the
details being obscured.
It is the essence of polymorphism to state which details are important
to satisfy the contract between a polymorphic function and its inputs,
then leave the rest of the details obscured. When writing an abstract
base class, we do exactly the same thing:
class Drawable {
public:
virtual void draw() = 0;
virtual ~Drawable() { }
};
void draw_something(Drawable* d) {
// we know that *d derives from Drawable, but we know nothing else
about it
}
So the STL metaphore necessarily does not integrate well with the
underlying C++ type system, and cannot be constrained by overloading
or inheritance.
You're right that the STL metaphor does not integrate well with the
underlying C++ type system *in today's template system*. Concepts
rectify this problem, by allowing templates to interact with types in
a natural way. Concept-based overloading, for example, allows one to
overload templates based on their concept constraints, i.e., based on
the properties of types. In the talk, the advance() example showed a
simple case of concept-based overloading, where overloads of advance()
differ based only on the kind of iterator passed to advance(). Because
a template can only be used if the types it is given meet the concept
constraints, constrained templates integrate tightly with the C++ type
system: that's how we get full type-checking of templates, better
error messages, etc.
I think we should not forget that C++ was an object
oriented language well before generic programming came about and
perhaps some of the ideas which generic programming brings with it are
better suited to functional languages.
C++ is a multi-paradigm language, and one of those paradigms is object-
oriented programming.
Not that i have anything against generic programming. Its very
useful, so long as you remember not to be the carpenter and treat
every problem as a nail.
:)
How many generic libraries actually need to
be generic beyond the 5 combinations of types that they actually use,
as opposed to collections which are truly generic.
I've worked with (and on) quite a few generic libraries, and I've
found that the deeper I go into using the libraries, the more I need
the flexibility that is there. I hypothesize that we haven't really
seen the power of generic programming in this regard, because the
current C++ template system has kept us from seeing all of the
opportunities for reuse. Who would have thought that you could take a
distributed-memory graph data structure from one library and use it
for
Generic code is unfortunately opaque, and whilst it can be amazingly
useful, there is a high price to pay in terms or readability and
debugability.
I agree with you 100%, if we're talking about today's C++ templates.
To implement a generic library with today's templates requires a huge
number of template tricks, all of which obscure the code and hide the
intent of generic programming.
The point of concepts is that they make it possible to write very
readable, very maintainable, and very powerful generic code, by taking
the ideas of generic programming and making them directly expressible
in C++(0x). For the sake of learning concepts, it's best to look at
them as a convenient extension to today's templates; for the sake of
comparison with other features, it's better to view concepts and
constrained templates as something completely different from today's C+
+ templates.
What about ensuring that C++ templates can be overloaded by interfaces
rather than just concrete types ?
template<typename Kind>
class Compare
{
public:
int Compare(Kind left, Kind right) {return left-right;}
}
template<typename Kind>
class Compare<Comparable Kind>
{
public:
int Compare(Kind left, Kind right) {return left.Compare(right);}
}
As Richard Smith points out, you can do this with concepts with a
minor change to the syntax of your code above. The same mechanisms
that make concept-based overloading work (e.g., for "advance") make it
possible to write different partial specializations with different
concept requirements.
And how about standardising the representation of function pointers so
that we can write better even handling and callbacks. What about
closures and coroutines ? Why do these ideas have to remain
"undefined" whilst we focus on much more esoteric problems.
As Richard also noted, std::function is a generalized function
pointer. You can check out the Boost.Function library at
http://www.boost.org/doc/html/function.html to see how it works. Or,
if you have GCC 4.1or Dinkumware's complete C++ Standard Library with
TR1, std::tr1::function is the same thing.
std::bind (adapted from Boost.Bind, http://www.boost.org/libs/bind/bind.html)
provides one way to do closures, and lambdas are under discussion as a
language feature.
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 ]