Templates

Templates are parametrized types, i.e. functions and types that depend (have as parameter) other types. To better understand what they are and why they are useful it is better to look at practical situations where they are useful.

Container structures like arrays, lists, sets,… are very common in programs. If one looks closely he can see that, the operations needed to handle each kind of container are basically the same within one type of container:an array of integers from this point of view is very similar to an array of matrices. Thus one could want to have just one generic implementation for each type of container structure.

Fortran for example provides a very nice generic implementation of arrays, lisp one for lists,… A natural question is then: how can I build a generic implementation of (for example) linked lists if my language of choice does not natively support it? One way to achieve this is to have a way to pass blobs of data, that then the caller know how to interpret (by typecasting them back). C has the (void *), or superclasses, java uses (lang.Object), objective C (id),… Unfortunately this is not very safe, can make some optimizations more difficult (or impossible), and in Fortran is simply impossible.

The other way is to write a LinkedList<Type> where Type is a parameter. Then you can create a LinkedList<integer> by placing integer wherever there is Type, and obtain a linked list of integers. C++ is the only mainstream language that supports templates (There are other mainly mathematical oriented languages, that sometimes do even better than C++). Fortran has no support for templates, but in fact it is not so difficult to add templates using a script that does global search and replace.

The advantages of Templates are that

• You write the code once, and reuse it in many instances.
• Safe interface (you cannot interpret the blob given back in the wrong way)
• More optimized: the choice to use a LinkedList<integer> is done at compile-time, so the compiler can optimize more.

The drawbacks are that:

• you can do errors by forgetting to put Type somewhere or putting it where not needed
• you add one step to the compilation cycle (template generation)
• it can be difficult to add special cases

Templates can be used to write generic algorithms that are as efficient as specialized ones (decisions done at compile time, no case/if at runtime). This one of the reasons templates are so interesting for numerics: generic algorithms, but well optimized. This also explains why C++ with templates can compete with and even beat Fortran 77.

As I missed templates very much I wrote a simple script to be able to do simple templates in Fortran (/cp2k/tools/instantiateTemplates.py).

• it is a simple replace script, it has no conditionals, it takes a .instatiation file and creates template instances using a .template file.
• The instantiation file is a list of dictionaries that give the correspondence “parameter”:“value”, using the python syntax (multiline strings can be written using “”“).
• to be sure not to have name clashes with variable names,… the template parameters are enclosed in square brackets (i.e. ”[type1]“ is a template parameter)
• file,module, routines,… names should depend on the template parameter, but you cannot, in general, use just [type1] (i.e. calling the module LinkedList_[type1] is not a good idea if [type1]=“type(cp_full_matrix_type), pointer”), so you should also have a [nametype1] parameter
• In the template filename parameter are substitued using _ in place of [ and ] (thus linked_list__nametype_.template becomes linked_list_integer.F if nametype=“integer”).
• a [use] parameter should also be present to be able to insert module dependencies.
• Pointers and normal types are quite different in fortran, thus you should either choose that the type is always a pointer (or always a non pointer) or make your template much more complex to accomodate the differences between pointer and non pointers.
• You should not get intimidated by the presence of many source files, they are all similar: once you understand a linked list you understand all linked lists.

I have created a template for a single linked list, it is somehow complex because I wanted to be able to store pointers and types, order the lists, and give output functions. A posteriori maybe it would have been better (as with fortan arrays) to be able to store only types, if you want to store pointers you just have to define a type that contains the pointer.