Templates Explained

[Solar]

This would probably belong into the Programming forum, but since it's spawned from a thread in this forum... here goes.

Schol-R-LEA, in the thread "BASIC for OS-Development?", wrote on 2003-08-26 19:45:

Templates as they exist in C++ are a workaround due to the lack of a singly rooted object hierarchy, or such as my understanding. In a language where all variables are objects off of a single root, they are completely unnecessary; you'd simply declare the method as class Object (or whatever the root class is) and apply to whatever classes you wish.

Before you can do anything on a Object, you have to cast it into the actual type supporting the operation. But, what type would that be? The vector code doesn't know the type, so it's your client code that has to know what's going on.

And what happens if you add polimorphy? If you have a vector of Object, and cast them to BaseClass, you have... well, you have objects of type BaseClass. Since Java doesn't have pointers, you have just sheared off any information on derived type. (IIRC.)

With a template, the type held in a vector is still known, to both client and vector code; yet still, the vector code can handle the type as being generic. If the type is a pointer type, you even preserve information on derived type.

Casting Java Object to whatever the container contents actually are also involves a greater risk of run-time errors: The Java container is not type-safe. C++ templates, on the other hand, are instantiated at compile time, including type checking. If the objects inserted into vector<T> don't support the operation called on them, your compiler will complain (instead of your code failing at run-time).

And templates are not only about containers. In the STL, you have algorithms that function on generic containers, and containers you can use generic algorithms on. When you implement a new algorithm, you have to implement it only once to have it work with many different container types - even those you don't even know about - without sacrificing run-time efficiency.

That's for starters. I'm open for questions, and if I can't answer them, I'll forward them to my co-worker, who really should know since he helped setting the standard.

[Pype.Clicker]

this sounds quite close from what i remembered

Casting Java Object to whatever the container contents actually are also involves a greater risk of run-time errors: The Java container is not type-safe.

a usual practice when dealing with Java containers is to use an instanceof check before you cast to make sure you can do it.
This is boring, but at least if you tried to fool the compiler with something like

Code: Select all

   Vector onlyMammalsHere=new Vector();
   fooler (Car vroom) {
      Object any=(Object)vroom;
      onlyMammalsHere.add(any); // nothing prevents us doing it :'(
   }

    lunchtime () {
       for (Enumeration e=onlyMammalsHere.elements();) {
           Mammal kiki=(Mammal)e.nextElement();
           kiki.feed();
       }
    }

you'll get an Exception due to runtime checking when trying to cast the object.

I'm unsure whether C++ could handle that kind of savage casting: if you have

Code: Select all

  void* it=&vroom;
  only_mammals_here->add((Mammal*) it);

...

especially considering that in an OS you usually have no runtime type checking support Thus if you make the compiler believe your object *is* of the right type, it will hardly know you're wrong ...

Except of course if vector<T>::add(obj) makes sure <dynamic_cast>(T)obj isn't null, but this would mean vector<T> requires run-time support (RTTI) ...

Does it make sense ?

[Solar]

A usual practice when dealing with Java containers is to use an instanceof check before you cast to make sure you can do it.

1) slow;
2) still requires the code using the container to implement a given interface so the container can do its magic. What do you do if you need a container of int's?

you'll get an Exception due to runtime checking when trying to cast the object.

Only if your code is actually executed, as with all run-time error handling... this might be during your testing, but it might also happen only at your client's site...

I'm unsure whether C++ could handle that kind of savage casting...

No it cannot. If you tell the compiler it's a Mammal you're pointing to, the compiler believes you. If you have RTTI support, you could of course check the typeid(), just as you did in your Java example with instanceof().

especially considering that in an OS you usually have no runtime type checking support

It's not that much of a black magic; I'm working on it.

Except of course if vector<T>::add(obj) makes sure <dynamic_cast>(T)obj isn't null, but this would mean vector<T> requires run-time support (RTTI) ...

If you have a vector<T>, and you try to add an object that isn't of type T, you get a compile time error.

Code: Select all

vector<int> vec;
vec.push_back(42);
vec.push_back(23);
vec.push_back(1.0); // compiler error

Same goes for pointer-to-type. So, unless you do the evil casting, C++ templates are type-safe.

[Pype.Clicker]

but for instance if you want to write a list<Something> for a library, you cannot expect your clients not to do evil casts while list<T>.add()'ing stuff, so you're likely to wish a safe_list<T> instead that would do the runtime checking anyway ...

Well, actually my concern goes a bit beyond the scope of "type-safe", and may that's why i'm arguing. One of my purpose was to say "the fact the compiler allowed you to include X in a list<T> doesn't guarantee that X has been generated by the constructor of T" ...

But this is one of the inherent problems of C++ which tries to offer "safety" (guarantee that objects are only changed through methods) in an unsafe environment (where pointers manipulations may crash a lot of your attemps to make things safer) ...

[Solar]

but for instance if you want to write a list<Something> for a library, you cannot expect your clients not to do evil casts while list<T>.add()'ing stuff, so you're likely to wish a safe_list<T> instead that would do the runtime checking anyway ...

You could do a safe_list<T> in C++, too, if T has a virtual function. Then, you could see if dynamic_cast<> throws an exception.

However, as Dietmar just put it: "C++ protects against Murphy, not Machiavelli"...

C++ allows you to do things Java just simply doesn't - like, providing memory allocators on a per-class basis. Try creating a Java container that uses contiguous memory for its contents, in order to minimize page faults...

Java is "safe", C++ is efficient. The thing is that templates offer much more than just a workaround for single-root hierarchies. And we're still talking only about containers, whereas templates can be just as well used for functions...

[Schol-R-LEA]

Before you can do anything on a Object, you have to cast it into the actual type supporting the operation. But, what type would that be? The vector code doesn't know the type, so it's your client code that has to know what's going on.

Er, I have to admit, I'd not had that in mind when I wrote my comment; but then, I was think in terms of Smalltalk, not Java. In Smalltalk, objects have types, but object references (variables) do not. Any variable which currently set to null can be assigned any object, regardless of class, even if it previously had referenced an object of a different class (doing so is a lousy practice, but it can be done).

And what happens if you add polimorphy? If you have a vector of Object, and cast them to BaseClass, you have... well, you have objects of type BaseClass. Since Java doesn't have pointers, you have just sheared off any information on derived type. (IIRC.)

No. It is true that in C++, upcasting an object to a statically declared object of it's superclass would shear off the data specific to the subclass. However, the situation simply doesn't arise in Java, because it is impossible to create an object statically (there are some non-object types such as int and char, and variables of those types are always local variables, but that's a side issue).

In Java, all variables of a class type are technically references to objects of the type, not objects themselves, and are usually implemented as pointers - you simply cannot access the reference's own pointer value directly, just like with C++ reference variables. The objects themselves are always generated by a [tt]new[/tt] call which dynamically allocates the memory for it; by default, an object variable is initialized to null until assigned an object reference.

So, if Foo is the superclass of Bar, and you assign a Bar object to a Foo variable, variable gets the object's reference and the whole object is intact (though you couldn't pass it a message specific to Bar).

With a template, the type held in a vector is still known, to both client and vector code; yet still, the vector code can handle the type as being generic. If the type is a pointer type, you even preserve information on derived type.

Casting Java Object to whatever the container contents actually are also involves a greater risk of run-time errors: The Java container is not type-safe. C++ templates, on the other hand, are instantiated at compile time, including type checking. If the objects inserted into vector<T> don't support the operation called on them, your compiler will complain (instead of your code failing at run-time).

I think it is possible to specialize a subclass of a collection so that it only accepts objects of a specific class, and incorrect assignments would be detected at compile time, but I could be wrong. I'll have to check into it if I get the chance.

And templates are not only about containers. In the STL, you have algorithms that function on generic containers, and containers you can use generic algorithms on. When you implement a new algorithm, you have to implement it only once to have it work with many different container types - even those you don't even know about - without sacrificing run-time efficiency.

OK, I'll admit that I cannot think of any way to do that in Java, at least not off the top of my head. In Smalltalk or CLOS, where you can generate new object classes programmatically at run time, it wouldn't so necessary - you would merge the generic iterator class with the collection class to create the specific iterator class - but the runtime efficiency would be a serious issue.

That's for starters. I'm open for questions, and if I can't answer them, I'll forward them to my co-worker, who really should know since he helped setting the standard.

OK, I think you have made your point. While I am familiar with generic programming in the context of Ada, I had assumed that polymorphism would have largely eliminated the need for it; I see that I was mistaken.

[Solar]

So, if Foo is the superclass of Bar, and you assign a Bar object to a Foo variable, variable gets the object's reference and the whole object is intact (though you couldn't pass it a message specific to Bar).

Well, that is what I meant: You cast the object "up" before entering it into the collection; you cast it "down" to Foo before calling its methods.

But if the object added to the collection was actually a Bar... well, you're still stuck with a Foo after the downcast, and can't call Bar::method().

Other than that, it has been a pleasure. (I know how confused I was upon first encountering template programming... )

[mystran]

Templates can help with statically typed languages, yes, but we have typesafe upcast in C++ too. It does NOT lose any of it's data when this is done.

You lose stuff only when you make copy of an upcasted object, which is easy enough to do by a mistake. The reason you lose with STL, is that STL does not store the actual object, but a copy of it.

Templates don't solve this problem if you ever need to store sevaral subclasses to the same container. Basicly, you probably want to use copy-safe smart pointers, or something like that, and make the copy constructor of the class private. This problem comes from C++ typing being static and weak, not from the lack of common superclass.

If you only store one type per container, then you are just as happy with Java, since you know that there's only one type in there. As for instanceof being slow, so is upcast, if you want it to be type-safe, and you have that stuff in C++ too, but when a container is supposed to only hold one type, you should make sure that only one type is stored there anyway. With Java you still suffer the upcast time penalty, with C++ templates you duplicate object code.

It's a memory vs. speed tradeoff.

I agree that templates can catch some errors at compile time, but in places where you don't need casting in C++, your cast won't throw any exceptions in Java, so the only advantage comes from templates allowing the compiler to check that you know what you are doing.

Personally, I think that what is wrong with both C++ and Java is the static typing. Strong, dynamic typing makes life much easier. Most of the time you just don't have the same type-problems you have with statically typed languages.

As for runtime exceptions only happening on client site, because some code was never run during testing, I'd suggest improving your development practices. Every piece of code should be tested well enough, even if it's error handling, so that the rest of it can be proven. This has nothing to do with programming languages.

Now, there are all kinds of nice things you can do with templates, but they are really just an advanced form of macros.

Code: Select all

template <class T> T i(T t) { return t; }

means simply that for each type T, an identity function i should be created, if such a function is ever needed.

[Schol-R-LEA]

So, if Foo is the superclass of Bar, and you assign a Bar object to a Foo variable, variable gets the object's reference and the whole object is intact (though you couldn't pass it a message specific to Bar).

Well, that is what I meant: You cast the object "up" before entering it into the collection; you cast it "down" to Foo before calling its methods.

But if the object added to the collection was actually a Bar... well, you're still stuck with a Foo after the downcast, and can't call Bar::method().

I know that this is a bit of thread necromancy (not that it's ever stopped anyone here before), but it just occered to me to mention that in in Smalltalk and CLOS (and possibly Objective-C, too), you can send a subclass-specific message to an upcast object. In fact, you can send any message you damn well like, as it is up to the object to determine at runtime whether it is valid or not; you can even generate a message on the fly to be passed to a object, IIRC.

I should add that in Squeak (and most other dialects of Smalltalk AFAIK) anyone can bring up an object browser and edit any class at any time, including critical system objects like Kernel: Methods: InstructionStream, and all objects of the class will immediately recognize it. While this makes for a wonderfully flexible system, secure it is not.

I'm not sure how relevant any of that is, however. C&CW.