Generic Programming Is Better

Following on from InterfacesAreGood:

GenericProgramming is better because it doesn't require the attributes of the objects being manipulated to be explicitly declared or known. The canonical example is the templated max() function: 

  template <typename T>
  T max (T a, T b){
      return (b < a) ? a : b;
  }
Under what circumstances will T be acceptable to the max function? First, it has to have a strict weak ordering with other objects of its class (operator < must be defined). Second, it must be possible to make a new T from an old T (as is implicitly done by the return statement). Contrast this with the sample problem solved using interfaces: 

  interface Comparable{
      bool isLess(Comparable x);
  }


  Comparable max (Comparable a, Comparable b){
      return b.isLess(a) ? a : b;
  }
I'm not suggesting, however, that C++'s template facility is perfect: it is often necessary to artificially restrict the class of entities that a template function of class may operate on or with. This leads to all sorts of hackery with typename tags, c.f. bidirectional_iterator_tag.

-- DavidKTurner

So could somebody explain to this open-minded Java programmer why the template above is better than the interface above? I'm used to looking at interfaces and so the advantage of templates in the example above isn't clear to me. Maybe some elaboration on the comment "doesn't require the attributes of the objects being manipulated to be explicitly declared or known" would help me. -- DustinAleksiuk

One problem with the interfaces implementation is that if you decide to write a new method that depends on some property of your objects not covered explicitly by the existing interfaces, you then have to go back and extend each of your existing objects with a new interface. Also you tend to pollute your objects with a whole lot of interfaces only indirectly related to the object's function. Plus the usage syntax is a bit ugly.

I think NiceLanguage has something to support this sort of problem, and I know ScalaLanguage has type bounds, although they can't do everything. In Nice: 

     abstract interface Comparable<T> {
          bool compareTo(T other);
     }
     <Comparable<T> T> T max(T a, T b) = a.compareTo(b) ? a : b;
And in Scala, provided that everything you use with max() descends from Comparable: 
     def max[T <: Comparable[T]](a : T, b : T) = if(a.compareTo(b)) a else b
Please correct the Nice example if it's wrong.

could somebody explain to this open-minded Java programmer why the template above is better than the interface above?

Type-safety (in addition to the "must-explicitly-descend-from-the-interface" problem. If we assume that autoboxing is on pretend that Integer descends from Comparable, you must use the Java example like this: 

     int a = ...; int b = ...;
     int c = (int) max(a, b);
That's alright. It's just one extra cast. But then, consider: 
     int a = ...; String b = ...;
     int c = (int) max(a, b);
In this case, there's no telling just what Integer#compareTo(String) would do. Probably throw an exception. The thing is, there's no typechecking for this sort of thing, so it can't be checked at runtime. Remember, in Java, generics are actually just syntactic sugar for inserting casts everywhere, but they are also typechecked. In this case, parameterizing either the type Comparable or the method max() would solve the problem, although parameterizing Comparable would require parameterizing max(). Additionally, you could do something as simple and stupid as this: 
     String a = ...; String b = ...;
     // Really long amount of code later:
     int c = (int) max(a, b) // oops!  Should be int c = max(String.parseInt(a), String.parseInt(b)), but the compiler can't check that!
Instead, max() should be written: 
     public <T extends Comparable> T max(T a, T b) {
         if (a.compareTo(b) > 0) return a; return b;
     }
And that solves the problem. Integers can only be compared to integers, strings to strings, etc.

There's another problem, where we don't know that T is comparable to itself. In theory, T could implement Comparable<U> where U has nothing to do with T (I agree, it doesn't make sense for anyone would do that, but the type system must be rigorous, so must not allow such unsafe possibilities.) Parameterizing Comparable to Comparable<T> would help solve this problem: 

      public <T extends Comparable<T>> T max(T a, T b) {
         if (a.compareTo(b) > 0) return a; return b;
     }
However, there's one more problem that has to do with subclassing. Supppose class A implements Comparable<A>. Then suppose class B extends A. Then class B automatically inherits the implementation of Comparable<A>. Class B can't also implement Comparable<B> in addition to Comparable<A>, because at runtime there is just one compareTo() method. Since class B doesn't implement Comparable<B>, our max() method doesn't work for type B. To solve this, we allow a slightly looser bound on the parameter of Comparable: 
      public <T extends Comparable<? super T>> T max(T a, T b) {
         if (a.compareTo(b) > 0) return a; return b;
     }
This is the final form that addresses all the problems. This is the same signature that is used for similar functions in the Java library.

I have not found generics in general or C++ templates in particular to be very advantageous. It often requires quite a bit of programmer effort to force a class to work with a template and often the amount of work to adapt the class is equal to or exceeds the amount of value provided by the template.

The generic part of the code is usually the trivial part. Please reference the example above. The comparison code is the difficult part to write. Once that is written returning the maximum of two values is simple.

--WayneMack

Implementing generics in C++ can be a pain, and I dislike the design of templates in C++, but the advantages to the users of genericized services is vast and undeniable. C++ is crippled without them. -- DougMerritt

I agree - implementing and particularly debugging template classes and methods is a lot harder than it should be. There's another advantage which I forgot to mention - generic code tends to help keep the details in places where they're relevant. When you want to use a particular [generic] property of a collection of objects you don't necessarily have to go extending each and every object to support a new interface. Mind you, traits classes and attributive typedefs can be even more hairy than a long list of "implements...". -- DKT.

As my experience is limited to the use of C++ STL, could someone explicitly list the advantages? Could someone fill me in on what I am missing? -- WayneMack

How about CuriouslyRecurringTemplates?

The argument at the top of this page is not really about generics but about DynamicTyping. The advantages described are as true about dynamically typed languages as they are about generic types or generic functions. Some implementations of generics (Java generics, for example) do not allow the programmer to avoid type declarations.

Note: C++ templates are a dynamically typed, TuringComplete FunctionalProgrammingLanguage.

C++ templates are not dynamically typed. C++ templates use static (CompileTime) ParametricPolymorphism. The two typing methods in the above code examples exhibit differences of NominativeAndStructuralTyping, not DynamicTyping vs StaticTyping.

[True, but templates emulate dynamic typing, while still being static. A dynamic type system would have no need for templates.]

No, templates are a way to support StructuralTyping, not DynamicTyping. It just seems like DynamicTyping because many languages which are dynamically typed use a form StructuralTyping. An example would be SmallTalk, which decides if two objects are the same type by considering "does object X have method/attribute Y", which is a form of StructuralTyping.

[Well.... never heard of StructuralTyping, but deciding if two methods implement method/attribute Y is how Smalltalk does Polymorphism, and most call that DynamicTyping. Also... looking at the TypingQuadrant, I don't think anyone else has heard of StructuralTyping either.]

I've heard of StructuralTyping. C++ templates are normally considered StaticTyping, because the type is determined at compile time. Templates cannot use information available only at runtime to make type decisions, while SmallTalk can. However, they do reduce to DynamicTyping in the limiting case, because it's possible to write whole programs in C++ templates, that are then evaluated by the compiler. See TemplateMetaprogramming. In this case, templates do indeed become DynamicTyping, because runtime moves to compile time. -- JonathanTang

I believe the template language qualifies as using DynamicTyping. Each slot in a template can hold any type at evaluation time. Type errors are caught when the template is actually instantiated (run), not when the instantiation itself is syntactically mentioned (compiled).

Templates in C++ are not compiled when syntactically mentioned, and they are not run when the template is actually instantiated. Templates are compiled when actually instantiated, and basically ignored when just syntactically mentioned. I don't believe this qualifies as using DynamicTyping, at all.

Translation, please?

C++ templates are a turing complete functional language that is executed at compile time and performs calculations upon the types of objects that exist at runtime. There are very few type declarations in the template language itself: a template argument is either an integral value (int, long, char, etc.) or a C++ type. The template type declarations do not declare any constraints upon the C++ types being processed. Therefore, the type compatibilty of template arguments is determined when the template is being expanded and compiled -- during the runtime of the template expander. This makes C++ templates a DynamicallyTyped language as well as a StructurallyTyped? language.

Calling the execution of the compiler "runtime" seems to be a bit of a stretch.

C++ templates are defined by a language for manipulating C++ types. That language is interpreted by the C++ compiler, and is therefore executed at compile time. The running of the compiler is the runtime of the template language. The runtime of the template language is NOT THE SAME as the runtime of the C++ code that is produced by expanding the templates.

Assuming a multi-pass compile still seems to be quite a stretch to call template compilation "runtime" (and I don't even want to discuss what is the "runtime" when the linker executes). I could just as easily state the following.

C++ is a language for manipulating C++ types. That language is interpreted by the C++ compiler, and is therefore executed at compile time. The running of the compiler is the runtime of the C++ language. The runtime of the C++ language is NOT THE SAME as the runtime of the code that is produced by expanding the C++ language.

"Well.... never heard of StructuralTyping, but deciding if two methods implement method/attribute Y is how Smalltalk does Polymorphism, and most call that DynamicTyping. Also... looking at the TypingQuadrant, I don't think anyone else has heard of StructuralTyping either"

A language can have dynamic, nominative typing. LISP and Scheme are examples. Smalltalk is an example of a language that has dynamic, structural typing. Modula-2 has static, structural typing.

And yes, it does look as if few people have heard of StructuralTyping, which is surprising. Isn't this stuff taught in most programming courses? And if not, why not?

See: NominativeAndStructuralTyping, LatentTypesSmell, ThereAreNoTypes, ObjectOrientationIsaHoax (article)

CategoryLanguageTyping

EditText of this page (last edited June 9, 2011) or FindPage with title or text search