Most sophisticated strongly and statically type-checked languages usually have a "programming" language at the type level whose "execution" takes place at compile time. By this we not only mean that type checking or type reconstruction may require substantial computational effort, but that some form of compile-time "execution" of type-level terms is also taking place (e.g. application of type-level functions to type-level arguments). How involved this execution is depends on the complexity of the type-level language. This feature has been exploited in unexpected ways in many richly typed languages.
For instance, in the Simply (Explicitly) Typed Lambda Calculus, the type-level language is rather small (base types and arrow type operator). Type-level computation is just type checking: making sure "abstractions" (functions) and "applications" (function calls) are well-typed. In the Simply (Implicitly) Typed Lambda Calculus, the type checker has to do some more work: it needs to infer the type of formal parameter variables from their use in the abstraction's body.
When programmer-defined parameterised type operators are added to these languages in the form of data type definitions, type-level execution (reduction) takes place in the form of type application, where type operators are instantiated with type arguments. Another form of type application takes place in the various lambda calculi modelling polymorphism like the predicative, impredicative (or System F), and type:type polymorphic lambda calculi of which the predicative, ML variant with let-polymorphism is the most popular and widely known. In these languages, type abstraction and type application are expressions, but since they play no computational role (no computational decision is made in terms of types; this is the so-called parametricity property of parametric polymorphism) they can be erased by the compiler after type checking.
Modern programming languages are convenient for real programming because of their many features and derived forms. The type-level language of C is approximately a monomorphic language of products with restricted higher-order features (pointers to functions). The pure, non-strict functional programming Haskell has some sort of prolog-ish language (which includes the simply typed lambda calculus) at the type level due to its "type class" mechanism.
What is the type-level language of C++? This question seems to have been of little concern to C++ designers or implementors, who have tackled the design and compilation of the language from a practical perspective, offering extremely clever but arguably ad-hoc solutions to looming problems.
Writing a formal type system for C++ would have been quite laborious indeed but it would have shed light on the type-level language and would have improved the language's design, its compiler, and helped determine the real power of C++ which does not seem to be widely known. New possibilities keep emerging, a recently striking one being the Turing-compleness of templates — which is perhaps a partial answer to our question about the type-level language.
What are templates? In short, C++'s mechanism for static universal polymorphism in its dependent, unbounded parametric, and bounded parametric variants, albeit with some restrictions and peculiarities. It is not the "static" (e.g. compile-time) bit what makes templates different to other notions of polymorphism, but the mechanics of instantiation, which turns them into type-parameterised macros for what after instantiation are a set of overloaded functions and classes, with "late" overloading resolution performed at link time if necessary.
This generative, macro-expansion approach to their implementation still has the advantage of reducing the number of source-code definitions but it has the disadvantage of producing many concrete instantiations, a problem known as code bloating. However, templates are not implemented in this fashion out of theoretical necessity, but for reasons of instrumentation: other approaches may require significant changes to existing compilers; notice that proposed new features to the language are carefully examined by the C++ designers' committee with implementation, smooth integration and backwards compatibility in mind. The interaction between templates and other language features (e.g. inheritance, automatic conversion) can have surprising and powerful consequences.
Let's explain this in more detail.
Templates allow classes (types) and functions to be parameterised by classes (types), by integral values (integer, enumeration, pointers or references to objects with external linkage), and other parameterised types, called template-templates. More precisely, the template keyword instructs the compiler to treat the entity that follows as a parameterised entity. Entities can be classes and functions. The keyword is followed by a list of type, value, or template-template parameters enclosed in angle brackets.
Within the parameter list, the keyword typename followed by an identifier signals to the compiler that the identifier must be treated within the template's scope as a type identifier rather than a value identifier. For example, the template function
template<typename T> T id(T x) { return x; }
defines an identity function parameterised by a type T and a value of type T (we leave references and temporaries aside for the moment). Here template plays a role similar to big lambda in Girard and Reynold's System F. The template definition is a sort of type abstraction.
The application id(3) actually means id<int>(3), where id<int> is a sort of type application. An expression of the form id<T>, where T does not stand for a concrete type but for a type variable, is a legal type application when it is embedded in a type abstraction:
template<typename T> T another_id(T x) { return id<T>(x); }
Specialisation takes place when an actual value for T is given.
There are some important differences with System F in the range (bounded, unbounded) and kind (typenames, values, template-templates) of parameters allowed, and the mechanics of instantiation:
int id(int x) { return x; }
int id(int x) { return x; } double id(double x) { return x; }
Generated definitions are conceptually overloaded: they share the same name and structure but differ only in type annotations. However, the compiler can give each generated function a unique name that does not conflict with any other function name, for instance:
int id_INTEGER(int x) { ... } double id_DOUBLE(double x) { ... }
These new names are also introduced in applications, so that id(3) is replaced by id_INTEGER(3) and id(4.0) is replaced by id_DOUBLE(4.0).
Templates are very powerful because ad-hoc polymorphism (overloading) resolved in terms of scopes and type annotations is very powerful, if perhaps not very elgant or optimal in terms of code size. One of the key insights of the C++ designers was to realise that many forms of parametric polymorphim can be instrumented in this fashion, in terms of type-parameterised macros that can be recursively defined and instantiated, and which are more reliable than mere textual macros as they are an integral part of the type system.
template<typename T> T& id(T& x) { return x; }
We use references now to avoid temporaries and unnecessary copying, but since compilers generate copy constructors by default, dispensing with references does not make the identity bounded parametrically polymorphic.
template<typename T> T& max (T& a, T& b) { return a < b ? b : a; }or operator=
template<typename T> void swap (T& a, T& b) { T temp = a; a = b; b = temp; }
Unfortunately, there is no type annotation specifying which operators or methods must be implemented by class T, one has to look at the code to find out about the constrains or rely on the compiler, which might issue the error messages at link time.
max(3,4); // OK, T=int max(3,4.0); // Error: T=int and T=double. max<double>(3,4.0); // Explicit T=double; 3 converted to double.
template<int I> void add(int j) { return I + j; }
The actual argument for I is provided at compile-time so it can only be an expression whose value can be determined statically.
add<3*4>(6);
Another example:
template<typename T, typename T::Iterator* I> void foo(...) { ... }
The second template parameter I is not a type but a pointer to a value of type T::Iterator. Function foo() is not really parametrically polymorphic but constrained to work on types with a public local dedeclaration of the type Iterator, which is available to foo() in the template variable I.
template<typename T, template<typename R> typename C> void foo(C<T> x) { ... }
Typename C must be a template class with one typename parameter R. Template-template arguments can only be parameterised classes.
Function foo() is parameterised by a parameterised class, which gives it an extra level of polymorphism, but this is not a form of polytypism, where functions are parameterised by parameterised type operators of a fixed, known arity and order (technically called the kind of the type operator). The definition of foo() would have to use reflection in order to access the definitional structure of class C like polytypic functions do, but then the advantages static type-checking are lost. Proper polytypism would require a language extension or a preprocessor.
In the case that both a template and non-template function are equally good matches the compiler chooses the non-template one. The programmer may override this default by writing an explicit type application with empty argument, e.g., a call max<>(3,4) instructs the compiler to choose the best match from templated-overloaded max functions. No automatic conversions are possible here.
template<typename T> void foo(T x, T y = 3) { ... } foo(1,2); // Ok, T=int foo('A','B') // Ok, T=char (default value ignored) foo(1); // Ok, T=int foo('A'); // Ok, T=int (automatic conversion) foo("A"); // Error, T=const char* does not match T=int
Recal that formal parameters cannot be used in a default argument expression:
template<typename T> void foo(T x, T y = x) // Error, x not in scope.
Just like functions, classes can be parameterised by typenames, values, and other parameterised classes.
template<typename T> class List { private: bool empty; T& hd; List<T>& tl; public: List(); List(T&,List<T>&); T& head(); List<T>& tail(); bool isEmpty(); };
Member functions of List<T> are not template member functions, they are member functions of a template class. Nonetheless, when the function bodies are provided outside the class definition the use of template is required to signal that T is a type parameter:
template<typename T> T& head() { return hd; }
The typename can appear within the class definition anywhere a type is expected, i.e., in type annotations; in particular it may appear in type applications
template<typename T> class Stack { private: Vector<T> elems; ... };
Stack<T> uses internally a vector of Ts. The expression Vector<T> is a type application.
class C { public: template<typename T,typename R> T foo(R r) { ... } };
The following is an example of a template class with a template member function; that is, of a parametrically polymorphic class with a parametrically polymorphic method.
template<typename A> class C { public: template<typename T,typename R> T foo(R r) { ... } };
The following is another example of a template class with a template member function but the method is polymorphic on the type parameter of the class:
template<typename A> class C { public: template<typename T> T foo(A a) { ... } };
int main() { List<int> list_of_ints; List<double> list_of_doubles; List<std::string> list_of_strings; List<List<int>> list_of_list_of_chars; } List<char>* map(char(*f)(int), List<int>* myList) {...}
It might be advisable to leave a space between two consecutive "greater-than" symbols as some compilers might mistake it for the input-output overloaded operator>>.
template<> class List<double> { ... };
The empty argument list informs the compiler that the following class is just a specialisation. For unbounded parametrically polymorphic classes specialisation might seem unecessary as the typename is immaterial to the behaviour of the class. For bounded parametrically polymorphic classes this needs not be the case.
General definition:
template<typename T1, typename T2> class C { ... };
A possible specialisation: both arguments of the same type:
template<typename T> class C<T> { ... };
Another specialistaion: first argument must be a list of int:
template<typename T> class C<List<int>,T> { ... };
Or this specialistaion: the second parameter must be a pointer to something of the type of the first parameter:
template<typename T> class C<T,T*> { ... };
As illustrated by these examples, the different specialised type parameters can be related or have nothing in common. A partial specialisation is not a way of imposing a constraint on possible type parameters. The general, non-specialised definition is still available; partial specialisations just offer the possibility of providing more specific definitions for less general type parameters.
template<typename T = int> class List { ... };
A default type parameter may depend on previous type names, e.g.:
template<typename T, typename R = List<T>> class C ...
template<typename T, int n> Vector { private: T* vector; public: Vector() { vector = new T[n]; } ... };
The sort of depentent classes we can define is very much restricted: we can program classes dependent on a fixed value that is determined at compile time. It does not make sense, for example, to define the class of lists of length n for a fixed n, for the size of a list changes during the execution of the program.
template<template<typename R> class P> class C { R r; // Error. P<int> l; // OK. };
Here class C is parameterised by a template class P that has one typename parameter. Since typename variable R is not used, it can be omitted:
template<template<typename> class P> class C { P<int> l; };Possible instantiations are:
C<List> clist; C<Stack> cstack;
It is interesting to reflect on the use of template-template parameters. Notice that an instantiated template like List<int> is a valid typename. But here instead of C<List<int>>, we are passing the template class as an argument and perform the instantiation inside class C. One possible use of this arises when we instantiate containers that are parameterised by other containers. A typical example would be the class of stacks of Ts implemented using container R:
template<typename T, typename R> class Stack { private: R container; int num_elts; public: T& pop(); void push(T&); ... };The following instantiations are possible:
Stack<int,Vector<int>> // Ok Stack<double,Vector<int>> // Legal, but not ok !
This problem is avoided if the types are coordinated inside the stack class:
template<typename T, template<typename> class R> class Stack { private: R<T> container; int num_elts; public: ... };
In fact, most users of the stack type will not care about a particular container implementation and use a default argument:
template<typename T, template<typename> class R = Vector> class Stack { private: R<T> container; int num_elts; public: ... };
Template-template parameters are also useful in the implementation of policy classes and trait classes.
template<class Parent> class Child : public Parent { ... }
Notice the use of the keyword class. A typename need not be a class.