Re: C++ templates?

Post #1,903 by neelk 7/16/01 9:52:04 AM Reply	Re: C++ templates? They are a bit similar, but not precisely the same thing. The difficulty in comparing them is mostly due to the fact that the C++ standards committee was careless in the template specification and accidentally got something a lot more powerful than they expected. As a result, templates are a very weird language construct -- they were intended to make parametric polymorphism easier to do but are actually capable of a lot more than that. Parametric polymorphism is the ability to write a function that operates the same way on multiple types. The simplest example is the identity function # let identity x = x val identity : 'a -> 'a The function identity simply returns its argument, and the type 'a -> 'a indicates that it can accept any type argument. Similarly, you can write a polymorphic length function for lists like this: # let rec len x = match x with [] -> 0 \| x :: xs -> 1 + len xs val len: 'a list -> int Here, you can see that len operates on lists of any element -- that's what the type 'a list means. The translations for identity and len in C++ are two of the first examples people see when using templates. Note that there are no type declarations in the OCaml code; the compiler automatically infers the most general typing for every expression submitted to the compiler, and will signal a compile error if there is no correct type for the code. This is different from C++, where every type has to be explicitly declared, and every polymorphic function needs to be enclosed in an explicit template expression. Note that parametric polymorphism is a very specific kind of polymorphim: a polymorphic function does exactly the same thing regardless of the types of the arguments. Sometimes you need to parameterize your code so that it does different things at different types. This is what ML offers functors for -- they let you write modules that are parameterized with other modules. C++ uses templates plus inheritance to model this case, plus some linking games. This is IME rather complicated, and doesn't map to how people think about it. Not a fatal problem, but definitely an annoyance. The real killer argument for me is that functors and parametric polymorphism do not break separate compilation and do not cause code bloat. Due to the way they are specified, a compiler can generate a single piece of code for each polymorphic function and each functor.
Post #2,093 by Arkadiy 7/17/01 3:51:58 PM Reply	Re: C++ templates? After I tried to rewrite your example in C++, I think I understand what you mean. Unless I use inheritance, the classes that implement Q will not have the same interface from compiler's point of view. Then again, what is the relationship between Q and ListQueue in your example?
Post #2,341 by jlalexander 7/19/01 2:25:31 PM Reply	Re: C++ templates? Yeah, this is a really interesting thread, but I'm having a issue translating in my head to C++... Arkadiy, any chance you can post your translated code? That'd be quite helpful. -Jason ---- My pid is Inigo Montoya. You "killed -9" my parent process. Prepare to vi.
Post #2,807 by neelk 7/25/01 1:56:55 PM Reply	Re: C++ templates? The Q signature is a module signature, and ListQueue and TreeQueue are the concrete implementations. In C++ terms, Q would be a fully abstract base class, and ListQueue and TreeQueue would be the distinct roots of concrete implementation hierarchies that each have Q as a superclass. ListQueue and TreeQueue would also be template classes, with the template parameter controlling the element type. There would also have to be a method to compare different elements, either as part of the Queue implementation or the element implementation. (This is what the functor argument Elt : ORD means; it says that elements have to have a comparison operation.) I'd appreciate it if you could post your C++ translations. The last time I wrote any C++ was ~5 years ago, so while I can read it I can't write it anymore. :)
Post #2,963 by Arkadiy 7/27/01 2:45:51 PM Reply	Re: C++ templates? Actually, I suspect that STL is just such a translation. map versus set versus multimap is about the same as your queue implementations. >>>>>>> There would also have to be a method to compare different elements, either as part of the Queue implementation or the element implementation. (This is what the functor argument Elt : ORD means; it says that elements have to have a comparison operation.) <<<<<<<< And therein lies an error. The comparison does not have to be a member in either queue or element. It can be another template parameter. So, you'd have something like template <class Element> class less { /operator () is used for lots of things in STL, ini this context it's just a comparison function / bool operator()(const Element &e1, const Element &e2) { return e1 < e2; } } template <class Element> class more bool operator()(const Element &e1, const Element &e2) { return e1 > e2; } } class customCompare { bool operator()(const MyVeryOwnType &e1, const MyVeryOwnType &e2) { return e1.field1 < e2.field1; } } template <class Element, class Comparison> class set { set() {}; /* use this constructor when comparison depends on external data (almost never) / set(Comparison &comp) : less(comp) {} / here in the set I can use less(e1, e2) (which is actually less.operator()(e1, e2) */ Comparison less; } typedef set <int, less<int> > ascendingSet typedef set <int, more<int> > descendingSet typedef set <MyVeryOwnType, customCompare> customSortedSet

Welcome to IWETHEY!