Templates and Generics

Article
11/19/2003

Insomnia and being a workaholic is an interesting
combination. It is amazing how much work can be accomplished in the eight hours
before everyone else comes to work. J

Anyways, I spent some time working on specifying generics
in C++ yesterday so I figured I'd write about that today. Perhaps the most
important message regarding generics is that they are not templates. That is
evident in the C++ language design as it supports both generics and templates.
At the PDC, I heard comments such as "generics are templates done right". This,
sadly, is a misinformed opinion that too many people share.

Generics and templates have a minor overlap in
functionality. They both make it possible to create parameterized types which
make it possible to create type safe collections. That's where the similarity
stops. First, let's look at some features templates allow and how they are
interpreted. I'll assume that you know the syntax for templates.

Templates are instantiated at compile-time with the
source code.
Templates are type safe.
Templates allow user-defined specialization.
Templates allow non-type parameters.
Templates use "lazy structural constraints".
Templates support mix-ins.

Templates are instantiated at compile-time. This is
huge. Anyone who really wants to understand the limitations of either generics
or templates needs to know this. This means that the same template instantiated
in two different assemblies actually have different types. The CLR includes the
strong-name of the assembly in the type, and thus [A]vector<int>
is different from [B]vector<int> even if they
were instantiated from the same template. A template is always emitted to an
assembly after it has been specialized. So, really a template disappears after
compilation. It is not possible to instantiate a template from another assembly.
Rather, to instantiate a template, the programmer needs the source code for the
template.

Templates are type safe. Templates were designed to
replace what many people were using macros for. Templates are fully type checked
by the compiler. In no way is there any textual substitution or macro-like
behavior in templates. Templates are indeed verifiable as long as the
implementation of the template does not use unverifiable features.

Templates allow user-defined specialization. First,
let me explain the difference between specializations and instantiations.
Consider the following code:

       Collection<int> a;
      Collection<int> b;
      Collection<double> c;
      Collection<X> d;

Here, there are four instantiations of a template but only
three specializations. The first two variables share the same specialization.
When defining a template, every template has a "primary template". This is the
most general template that the compiler will use unless there is a better
explicit specialization or partial specialization of the template. The
usefulness of user-defined specializations cannot be understated – it allows the
programmer to choose a different implementation for different template
arguments. For instance, if templates were used in a math library, this allows
the programmer to create different implementations for integer and
floating-point calculations.

Without user-defined specializations, the compiler creates
all specializations from the primary template. These specializations can still
generate fairly different code from each other. For instance, one specialization
may inline all function calls involving template parameters. Another
specialization may not inline the same function calls.

Templates allow non-type parameters. Non-type
parameter like integers or template template parameters allow templates to have
significant expressive power. Constant values in specializations are known by
the optimizer and therefore can be passed into the code via a number of data
flow analyses such as constant propagation and copy propagation. The resulting
code is far more efficient than one that must rely on accessing variables.

The combination of specialization and non-type parameters have actually
enabled an entire programming paradigm in C++ known as template
meta-programming. While it is entirely possible to go overboard with the
capabilities templates afford, there are numerous useful techniques.

Templates use "lazy structural constraints". What
happens when a template relies on a function and it's not there? When writing
the template, the developer can call member functions on the template parameter,
use operators, or call functions that use the template parameter. The definition
of the template is kept by the compiler until later needed for a specialization.
When the compiler creates a specialization, if a function call or an operator
has no meaning for a particular parameter, then a compile-time error occurs. In
short, the constraint for a template parameter is that it supports a particular
operation (i.e. it has a function with a suitable overload or it has a valid
operator). Template constraints are enforced at specialization rather than at
definition.

I use the phrase "lazy structural constraint" with much
liberty. The notion I am trying to get across is that the constraint is enforced
lazily because compiler diagnostics appear at specialization. They are
structural constraints because they require some kind of support from a type
parameter that is not necessarily dependent on a subtype relationship.

Templates support mix-ins. A class template can
inherit from a type parameter. This enables a number of programming patterns,
such as mix-ins and policy based programming. Generics do not support directly
inheriting from a type parameter.

Now, with that brief summary of templates out of the way,
let's turn to a brief summary of generics.

Generics are instantiated at run-time by the CLR.
Generics are also type safe.
Generics are cross-language.
Generics do not allow user-defined specialization.
Generics do not allow non-type parameters.
Generics use subtype constraints.

Generics are instantiated at run-time by the CLR.
Unlike templates, a generic defined in source code is emitted into MSIL as a
generic. The compiler does not specialize generics. A generic type thus has one
assembly to which it belongs. A programmer who wants to create an instantiation
of a generic must identify which assembly the generic comes from (either via
importing metadata or using the current assembly). When the runtime specializes
a generic, it creates one specialization for all ref classes. Each value type
will have its own specialization.

Generics are also type safe. Generics were designed
to be verifiable (meaning that the MSIL could be proved type safe). Like
templates, generics are only unverifiable if they use unverifiable features.

Generics are cross-language. By far the biggest
advantage to templates is that producers of cross-language frameworks need to
use generics instead of templates. While generics are not Common Language
Specification (CLS) compliant now, it is expected that they will be at some
point in the future.

Generics do not allow user-defined specialization.
As generics were designed as a runtime service, the designers of generics felt
that specialization was tied too much to the semantics of a particular language.
Thus, when writing a generic, it is only possible to write it once. This is like only being allowed to write a primary template.

Generics do not allow non-type parameters. The
primary design goal for generics was creating parameterized collections. Most
collections do not require non-type parameters, and thus the designers of
generics did not include this feature.

Generics use subtype constraints. This is the big
one. It is the mechanism by which generics are implemented on the CLR. First,
look at the following code:

       generic<typename T>
      ref class R {
        void f(T t) {
          t->g();
        }
      };

How do we know that the call to g in the function f is valid? With
templates, we'd check at specialization. With generics, it's up to the runtime
to determine that this is valid. In order to verify that a generic class is
valid, the runtime needs more information. Thus, we must fix the above
definition as follows:

       generic<typename T>
      where T : IG
      ref class R {
        void f(T t) {
          t->g();
        }
      };

With generics, overload resolution is done at the point of
definition. Thus, the call to g is done by
looking for the name g in the constraints for
T. As there is only one constraint,
g must be a member of
IG. The g
function is called through the interface rather than directly on the variable.
Consider the following example:

       interface class IMethod {
        void f();
      };
 
      ref struct R : IMethod {
        virtual void g() = IMethod::f {
          System::Console::WriteLine("R::g");
        }
 
        void f() {
          System::Console::WriteLine("R::f");
        }
      };
 
      generic<typename X>
      where X : IMethod
      void G(X x) {
        x->f();
      }
 
      template<typename X>
      void T(X x) {
        x->f();
      }
 
      int main() {
        R^ r = gcnew R;

        G(r);
        T(r);
      }

With generics, the call to f
is done through the interface IMethod. With
templates, the call to f is done directly on
the class R. Thus, the output of this program
is:

       R::g
      R::f

Explicit overrides (used for explicit interface
implementation in other languages) are not the only way this difference could be
surfaced. Function overloading will change too. Overloads within a generic only
consider the constraints as possible arguments, whereas with templates the
compiler waits until specialization so it only needs to do overload resolution
with the real type.

An unfortunate consequence of subtype constraints with
interfaces is that not all useful functions in a class can be contractually
guaranteed through an interface. An interface only demands virtual functions. So
non-virtual functions, static functions, static conversion functions, static
operators, and constructors cannot be used on a generic type parameter. As the
CLS requires operators and conversions to be static member functions, generics
cannot make use of operator overloading on generic type parameters. This means
that a type used in a sorted collection needs to implement a specific interface
rather than simply provide the less-than operator. That is a significant
drawback if you're used to templates, and this is why the Whidbey version of the
frameworks is updating all the built-in types to implement
IComparable<T>.

Now with all of that background, here is a comparison of
templates and generics:

	Generics	Templates
Constraint mechanism	Subtype constraints	Lazy structural constraints
Allows explicit specialization	No	Yes
Allows partial specialization	No	Yes
Type identity of specialization	Globally unique	Unique to each assembly
Cross language facility	Yes	No
Allowed parameters	Ref class, value class only	All types and non-type
Name lookup and binding	At definition, to constraints	At specialization, to type

Certainly, there will be evangelists for either option. The
best option for C++ is to support both mechanisms. Having both templates and
generics satisfies anyone who believes one is better than the other. Of course,
any pragmatic programmer will realize that having both gives the programmer the
ability to use the right feature to solve the problem at hand. Both generics and
templates have shortcomings, but using both features together actually yields an
even more expressive language.

A very compelling scenario is using templates to create
highly efficient data structures, but exposing that type at the assembly
boundary through a generic interface. This is similar to a factory pattern that
uses private types that inherit from public interfaces. Using this pattern, a
specialized C++ collection class can take advantage of frameworks APIs that use
the interface and allows other languages to make use of the type through the
interface.

This technique is exactly how the STL.NET collection
library will be implemented. The collections will be C++ templates that employ
the STL design of iterators and separate algorithms. The collections will
implement generic interfaces such as IList<T>.
I think that the potential for combining templates and generics is great, and
we're just starting to scratch the surface. Much of uses for combining templates
and generics were driven by Anson Tsao, Martyn Lovell, and Eric Niebler while
they were investigating STL.NET.

Hopefully, this was a lucid (after all I am not sleeping)
explanation of the fundamental differences between generics and templates. As
both features are significant, I very well could write a dozen more pages. As I
did with handles, I will later spend time writing about the design rationale
behind both generics and templates.

Comments

Anonymous
November 19, 2003
The comment has been removed
Anonymous
November 20, 2003
This is SO GOOD news! I am addicted to C++ templates, like they are used by STL and ATL, and have worried that CLR Generics will be too restrictive for me to take the plunge into C#/.NET for all my projects. If MC++ will let me do both, and use each method's strengths, it is a big deal. Really big. Now, I will be able to compile verifiable assemblies with MC++, right? (I mean, no unsafe constructs or native code.)
Anonymous
November 20, 2003
Thanks Andrew! You're right about derivation from type parameters. I updated the entry to mention that.
Anonymous
November 20, 2003
And of course, generics also solve the problem the infamous 'export' reserved word was designed for, at least so far as generics/templates overlap. This may be one of the biggest selling points for the established C++ community!
Anonymous
November 21, 2003
The comment has been removed
Anonymous
February 01, 2004
???? C# Generics ?????: An Introduction to C# Generics by Juval Lowy Brandon Bray ? C++ Templates ? C# Generics ??????????...
Anonymous
June 30, 2004
Thanks Andrew! You're right about derivation from type parameters. I updated the entry to mention that.
Anonymous
July 28, 2004
Nice overview of the difference between generics and templates! The best I have seen on the web yet.
Anonymous
November 11, 2004
Went to OOPSLA a couple of weeks ago, and it really blew me away. Steve McConnell and Herb Sutter are both amazing speakers, and Herb's talk on the new C++ extensions rocked. I can't wait until Visual Studio 2005 officially...
Anonymous
August 01, 2005

Developer.com posted
a&nbsp;pithy
article today on STL.NET.&nbsp; This whole templates...
Anonymous
August 04, 2005
where - Visual C++
Anonymous
August 04, 2005
where - Visual C++
Anonymous
January 10, 2007
One of the major missing features in the 1.0 and 1.1 .NET Framework was generics (similar to "templates"
Anonymous
January 13, 2007
C : Template Specialization
Anonymous
May 11, 2007
This document attempts to compare some of the object oriented features available in the Delphi, C , C# and Java programming languages. Introductory paragraphs to each section to explain the concept being compared in the section are available, but are
Anonymous
January 18, 2009
PingBack from http://www.keyongtech.com/1317384-rad-studio-roadmap-updated/13
Anonymous
January 21, 2009
PingBack from http://www.keyongtech.com/4480720-why-no-language-improvements/15
Anonymous
May 29, 2009
PingBack from http://paidsurveyshub.info/story.php?title=visual-c-internals-and-practices-templates-and-generics
Anonymous
June 08, 2009
PingBack from http://insomniacuresite.info/story.php?id=19
Anonymous
June 09, 2009
PingBack from http://menopausereliefsite.info/story.php?id=1013
Anonymous
June 16, 2009
PingBack from http://topalternativedating.info/story.php?id=4348

Share via

Templates and Generics

Comments

Additional resources