Template Primer, In D

Published 2012-03-22 23:21 by Abscissa in Coding

While generics have become fairly common in many languages, the similar (but more general) concept of templates are fairly uncommon among languages. As such, many people have only a passing familiarity with them. It doesn't help that the most well-known example of templates, those in C++, have...well...they're earned a reputation for being an advanced concept.

This is unfortunate, because at their core, templates are really both very simple and very powerful. Especially if you use D.

Here's a little template primer I initially wrote in response to a newsgroup post:

A template is just a clean way of generating code instead of manually copy-pasting a bunch of times (which would end up being a maintenance nightmare).

Suppose you have this:

int add(int a, int b) { return a + b; }

That's called, of course, like this:

add(7, 42);

Suppose you then want another version of the same function, but with double instead of int:

double add(double a, double b) { return a + b; }

Called like this:

add(3.14, 5.73);

Now you have two functions that are exactly the same, just with one little thing changed. If you need to modify one function, you'll have to remember to modify the other, too. God help you if it's a really big function and you accidentally make a mistake copying it. It just gets to be a big problem. It violates what we call DRY: "Don't Repeat Yourself".

Some languages, like Java or C#, try to solve this issue by making everything an object (or in dynamic languages, a variant). Then they pass around those "boxed" versions instead. This might be done manually, or it may be automatic via autoboxing or generics. Either way, there's a problem: performance. These boxed types, whether objects or variants, are not free: They require extra time and memory. In same cases, the difference is negligible, but in critical sections it can easily add up. So you have to be careful about where and when you use this form of generic code.

Let's step back into first grade for a minute: Have you ever drawn or painted with stencils? You make one design, once, by cutting it out of paper. Then you can easily draw and redraw the same design with different colors: Just place the stencil on a new piece of paper, choose a color, fill it in, lift the stencil, and boom! Suddenly there's another copy of your design, no matter how intricate, in whatever color variation you want.

Templates are stencils for code. Heck, even outside of code this is true, too: "Template" is just another word for "stencil".

So here's how you make a stencil for an add() function. Just "punch out" whatever you want to change, by making it a template parameter:

// Make a "stencil" template myTemplate(T) { // This is what's inside the "stencil" T add(T a, T b) { return a + b; } }

Notice how the add() function is exactly the same as before, but the ints were changed to T (for "Type").

Now let's stamp down some add() prints:

// The dot in between is because "add" is *inside* the template "myTemplate" myTemplate!(int).add(7, 42); myTemplate!(double).add(3.14, 5.73);

That too, is almost exactly the same as before. I've only added that myTemplate!(int) and the similar myTemplate!(float). The compiler turns those into:

int add(int a, int b) { return a + b; } double add(double a, double b) { return a + b; }

And then calls them:

add(7, 42); add(3.14, 5.73);

Those are exactly the functions we were manually writing before! Not only that, but unlike generics or dynamic types, there's no time or memory overhead, so it's perfectly safe to use this in performance-critical sections!

A technical side-note: Truthfully, there is a small amount of extra memory used simply because we're generating code for another whole function. But that's much less of an issue than it may seem. First of all, a Java-style or dynamic-style "generics" version of the function would involve extra code being generated, too - the extra code to detect and handle the types of the variables at runtime. Secondly, the extra memory here is "per function generated", not "per variable". You could juggle millions of variables in template version, and it still wouldn't increase memory usage. But that's not necessarily true of a non-template "generics" version.

Suppose now we want to use add() with ulong and BigInt, too. Instead of manually copying the function and changing the type, we can just let the compiler copy the function and change the type:

myTemplate!(ulong).add(7, 42); myTemplate!(BigInt).add(BigInt(7), BigInt(42));

The compiler, of course, automatically generates:

ulong add(ulong a, ulong b) { return a + b; } BigInt add(BigInt a, BigInt b) { return a + b; }

And then calls them:

add(7, 42); add(BigInt(7), BigInt(42));

You can also add more stuff to the template:

// A bigger "stencil" template myTemplate(T) { T add(T a, T b) { return a + b; } T mult(T a, T b) { return a * b; } }

So now the compiler will turn this:

myTemplate!(int) myTemplate!(double)

Into this:

int add(int a, int b) { return a + b; } int mult(int a, int b) { return a * b; } double add(double a, double b) { return a + b; } double mult(double a, double b) { return a * b; }

And you can use them like this:

myTemplate!(int).add(7, 42); myTemplate!(double).add(3.14, 5.73); myTemplate!(int).mult(7, 42); myTemplate!(double).mult(3.14, 5.73);

You can put other things inside the template, too, like structs and classes, or even variables:

template anotherTemplate(T, int initialValue) { struct Foo { T value; int someInt = initialValue; } T[] myArray; } // Use the array: anotherTemplate!(string, 5).myArray = ["abc", "def", "g"]; // Declare a variable "myFoo" of type "Foo": // Foo's "value" should be a string // And Foo's "someInt" should start out as 5 anotherTemplate!(string, 5).Foo myFoo; if(myFoo.someInt == 5) myFoo.value = "Hello";

Notice that we've added another parameter to the template this time. But this one's an int, rather than a type! Templates can take any type as a parameter like that. You also use alias (as in template(alias foo) ... ) which will accept any symbol: The name of a type, a variable of any type, a literal, or even another template!

Admittedly, this all gets rather wordy, so D offers some convenient tricks:

Using that myTemplate and anotherTemplate all over is a bit of a bother. Why should we have to? D has a shortcut for making and using templates:

T add(T)(T a, T b) { return a + b; }

That's nothing more than a convenient shortcut for:

template add(T) { T add(T a, T b) { return a + b; } }

Or we can define the struct like:

struct Foo(T, int initialValue) { T value; int someInt = initialValue; }

Which is a convenient shortcut for:

template Foo(T, int initialValue) { struct Foo { T value; int someInt = initialValue; } }

The same trick doesn't work for variables like myArray though (but that will likely get fixed in the future). For now, you'll have to manually write them as:

template myArray(T) { T[] myArray; }

Note that (as was true before) each instance of this template is a different array. So myArray!(int).myArray and myArray!(double).myArray are two different arrays. (If you want a single array that can hold anything, you can just simply make an array of Variants: Variant[] variantArray;)

Here's an even handier trick: Since the name of the template and the "thing" inside the template is the same, you don't have to repeat their names (The technical term for this is an "eponymous template"). To use them, all you have to write is:

add!int(7, 42); add!double(3.14, 5.73); add!BigInt(BigInt(7), BigInt(42)); mult!int(7, 42); mult!double(3.14, 5.73); mult!BigInt(BigInt(7), BigInt(42)); myArray!string = ["abc", "def", "g"]; myArray!int = [1, 2, 3]; myArray!double = [1.5, 2.70, 3.14]; Foo!(string, 5) myFoo; if(myFoo.someInt == 5) myFoo.value = "Hello"; Foo!(float, 1) bar; if(bar.someInt == 1) bar.value = 3.14;

This, in fact, is how templates are usually used in D. Looks pretty simple, doesn't it? Barely any different from the non-template versions. That's because it really is simple, as it should be. After all, they're just stamps.

And there's yet one more frequently used convenience: A special thing D has called IFTI: Implicit Function Template Instantiation. It sounds intimidating, but again, it's really very simple. It just means D lets you call the functions above like this:

add(7, 42); add(3.14, 5.73); add(BigInt(7), BigInt(42)); mult(7, 42); mult(3.14, 5.73); mult(BigInt(7), BigInt(42));

Look ma! No types!

• D already knows that 7 and 43 are int, so it automatically uses the add!int version.
• D already knows that 3.14 and 5.73 are double, so it automatically uses the add!double version.
• D already knows that BigInt(7) and BigInt(42) are BigInt, so it automatically uses the add!BigInt version.

Now these really are identical to using the old non-template versions!

So ultimately, if we start with this copy-paste mess:

int add(int a, int b) { return a + b; } double add(double a, double b) { return a + b; } add(7, 42); add(3.14, 5.73); add(BigInt(7), BigInt(42)); // ERROR! You have to write a BigInt version *manually*!

We can turn it into a convenient "stencil" with just a trivial little change:

T add(T)(T a, T b) { return a + b; } add(7, 42); add(3.14, 5.73); add(BigInt(7), BigInt(42)); add( /+ anything else! +/ );

That will automatically stamp out any add() function you need, when you need it. And we can do the same for structs, classes and variables!

For more details on templates and D, check out:

• Philippe Sigaud's "D Templates: A Tutorial"
• Ali Çehreli's "Programming in D"
• The official D website
• The official D book: The D Programming Language

UPDATE (2012-05-12): Added a couple paragraphs about the non-template approaches used in most languages, basic syntax highlighting, and a few minor updates and wording tweaks.