Re: C++ Template Overloading
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.
Your welcome...
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#.
I understand the idea behind the expression, i was really just trying
to say that i don't equate templating with polymorphism in an OO
sense. Templates give you types which can be composed in many
different ways, but this is far from the concept of OO polymorphism
where derived types share a relationship. Without notions like
concepts in the C++0x standard templates dont really share any
relationship with other templates. They can't be used as interfaces,
and they can't be passed as polymorhpic arguments (in the OO sense)
except in other templates. There is a distinct boundary between
templates and OO, it can be difficult to see and even harder to cross.
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:
...
Your example was very good, and i do like the concept system. It
addresses many of the problems with the STL/Boost metaphor and the use
of type traits. Specifically, most STL and Boost templates use
typedefs like value_type to get around the fact that the types are
unknown. Personally, i dont much like that. I find it too opaque,
which is why if you look in the Reason::Structure namespace of the
framework which i wrote you will find that most collections return
actual types which are always known i.e. Iterand<int> for any
collection working with "int" and likewise iterators are always of
some type and can be passed and constrained as arguments i.e.
Iterator<int>
But remember that concepts are fixing problems that exist with the STL/
Boost metaphor. They will be very useful to other metaphors too so
long as they are not constructed in a STL/Boost specific way. When
looking at examples like the "foreach" loop, things start to get a
little bit too specific, especially if "foreach" is defined in terms
of concepts which support begin() and end(). Thats blurring the lines
between language and library...
It can be quite difficult to conceptualise how the operator
overloading used in STL/Boost is both a blessing and a curse. Its a
blessing becuase operators provide a way to effectively expression
"anonymous" interfaces in C++. All types support operators, but you
dont have to explicitly say that a type inherits from interfaces like
"LessThanComparable", "GreaterThanComparable", "EqualsComparable".
The curse is that in exchange for that magic you have to trade all
your knowledge of the type that you are working with and you can no
longer easily integrate your templates with OO programming models. So
what you end up with is some very complicated and opaque code, with
lots of workarounds and messy business like type traits to try to
compensate.
You will note that the interfaces like "LessThanComparable" which i
mentioned above match pretty closely the kindof examples that are used
in the Google tech talk about concepts. In a way its kindof pointing
to the fact that the STL/Boost metaphor has a flaw, and that in the
end we really need a way of expressing and verifying those constraints
and ideas in an "interface" like way.
In the Reason framework i tried very hard to find an alternative which
gave me better association with OO priciples, yet still had the
anonymous power of the STL/Boost metaphor. The solution can be seen
in the classes Template<Kind>, Type<Kind> and in interfaces like
Comparable<Kind> and Disposable<Kind>. In Reason there is no
requirement for type traits, becuase types are transparent, likewise
the code is simpler and more easily understood. Comparable<Kind>
provides a mapping between the anonymous operators and OO interfaces
like those provided by the Object class. By avoiding heavy reliance
on the STL/Boost operator metaphor, i was able to avoid some of the
associated traps. Even the templates that exist in Reason are very
OO. They are fundamentally inheritable becuase they are closer to
being classes than they are to being generics.
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);
Yes, its possible with concepts, which i think is great. But
unfortunately were all going to have to wait a while to get our hands
on that... :)
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);
How deep does the concept go here ? Is an integral type just a type
which supports + and - or does it enforce rules of associativity and
other mathematical properties. If it does then that is very exciting
indeed. I think there was mention of this in the tech talk...
Ive used similar ideas to resolve dispitutes between polymorphic types
before, but in an OO only way. There are rare cases when you have a
singly rooted object heirarchy but need to make sure that if A is
compared to B then it is always done in such a way that B.Compare(A)
is called instead of A.Compare(B). This can be useful when sorting
lists of multiple types of items, a little like a priority queue.
Being able to enforce such requirements with concepts would be very
cool.
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
}
I didnt quite follow that, were you implying that becuase STL/Boost
style iterators drop the unimportant details they are polymorphic ?
Too me, polymorphism is too closely linked with the notion of
inheritance and type. Without type there is a disconnect, its not so
much polymorphism as it is just anonymous abstraction.
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.
Yes, i agree, thats a fantastic feature. And im very pleased to hear
that template overloading based on polymorphic (OO) type is also
supported through the same mechanism.
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.
Ok. I think i was just trying to say that generic programming is a
relatively new focus for the language though. Templates initially im
sure were merely an advanced macro mechanism for avoiding code
duplication.
And by the way, just becuase generic programming is popular with a
subset of C++ users does not make it necessarily important. There has
always been a tendancy for programmers to gravitate towards what is
new and exciting, and even sometimes complicated. Im not sure i
really understand the psychology, but non the less, it is a
phenomenon. And it goes without saying that sometimes creating
simpler things is actually far more difficult than creating complex
things.
I do however accept the point that there are things which can be done
in generic programming which cant be done in functional languages, and
so it has its niche. In fact i think its a little bit of a shame that
the C++0x standard is not more far reaching. The concepts which are
flirted with in generic programming are actually quite close to the
ideas of domain specific languages, lisp, and intentional
programming. True generics, in an asbtract algorithmic sense is a
software development holy grail.
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.
:)
See above :)
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
Agreed.
However i havnt found many examples where all my code needs to be
generic. Im sure there are examples where generic libraries truly
benefit from being generic, but i think there are a lot of generic
libraries which are only generic becuase the authors are stuck on the
STL/Boost metaphor and cant get off it (see the comment above about
carpenters and nails). This is probably partly due to knowledge, once
you know a certain way of working it becomes easier for you, but also
partly due to the fact that the STL/Boost metaphor is actually hard to
break out of once you start using it because it does not easily blend
back in with the more OO principles of C++.
Its kindof a shame to see a language like C++ diverge into class based
programming and generic programming. We should be trying to merge
them back together i think, and hopefully concepts will go a long way
towards doing this...
For me, the cost of abstraction in generic libraries like GIL (Generic
Image Library) which i happened across the other day, outweigh the
benefits. I like to always see what im dealing with in my code, down
to the point that i would rather use "char" than "typedef char byte"
because abstractions make things harder to understand. Even Charles
Symonyi (See NASA TV) would now agree that abstractions like the
dreaded "hungarian" notation (which he helped to design) are no longer
a good idea.
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.
Im totally sold on concepts and i am glad that you agree thats there
is a problem with todays templates...
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 athttp://www.boost.org/doc/html/function.htmlto 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.
Theres a huge difference between using some of the amazingly clever
hacks and tricks in Boost to having native language support for things
like function pointers and coroutines though. For a start the syntax
would be a lot simpler, and there would be no where near so many hoops
to jump through or caveats and special cases to avoid.
I think the efforts to make things like std::function and std::bind
are admirable, but far from acceptable. I still find it astonishing
that C++ lets you do that kindof stuff, how many other languages out
there have the same kindof loop holes and tricks ? Makes me think
that either the initial standards were very loose, or the language is
far too complicated, or perhaps people are just extremely ingenious ?
Maybe a bit of everything :)
Emerson
---
[ 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 ]