Programming in D – Tutorial and Reference
Ali Çehreli

Other D Resources

Templates

Templates are the feature that allows describing the code as a pattern, for the compiler to generate program code automatically. Parts of the source code may be left to the compiler to be filled in until that part is actually used in the program.

Templates are very useful especially in libraries because they enable writing generic algorithms and data structures, instead of tying them to specific types.

Compared to the template supports in other languages, D's templates are very powerful and extensive. I will not get into all of the details of templates in this chapter. I will cover only function, struct, and class templates and only type template parameters. We will see more about templates in the More Templates chapter. For a complete reference on D templates, see Philippe Sigaud's D Templates: A Tutorial.

To see the benefits of templates let's start with a function that prints values in parentheses: 

void printInParens(int value) {
    writefln("(%s)", value);
}

Because the parameter is specified as int, that function can only be used with values of type int, or values that can automatically be converted to int. For example, the compiler would not allow calling it with a floating point type.

Let's assume that the requirements of a program changes and that other types need to be printed in parentheses as well. One of the solutions for this would be to take advantage of function overloading and provide overloads of the function for all of the types that the function is used with: 

// The function that already exists
void printInParens(int value) {
    writefln("(%s)", value);
}

// Overloading the function for 'double'
void printInParens(double value) {
    writefln("(%s)", value);
}

This solution does not scale well because this time the function cannot be used with e.g. real or any user-defined type. Although it is possible to overload the function for other types, the cost of doing this may be prohibitive.

An important observation here is that regardless of the type of the parameter, the contents of the overloads would all be generically the same: a single writefln() expression.

Such genericity is common in algorithms and data structures. For example, the binary search algorithm is independent of the type of the elements: It is about the specific steps and operations of the search. Similarly, the linked list data structure is independent of the type of the elements: Linked list is merely about how the elements are stored in the container, regardless of their type.

Templates are useful in such situations: Once a piece of code is described as a template, the compiler generates overloads of the same code automatically according to the actual uses of that code in the program.

As I have mentioned above, in this chapter I will cover only function, struct, and class templates, and type template parameters.

Function templates

Defining a function as a template is leaving one or more of the types that it uses as unspecified, to be deduced later by the compiler.

The types that are being left unspecified are defined within the template parameter list, which comes between the name of the function and the function parameter list. For that reason, function templates have two parameter lists: the template parameter list and the function parameter list: 

void printInParens(T)(T value) {
    writefln("(%s)", value);
}

The T within the template parameter list above means that T can be any type. Although T is an arbitrary name, it is an acronym for "type" and is very common in templates.

Since T represents any type, the templated definition of printInParens() above is sufficient to use it with almost every type, including the user-defined ones: 

import std.stdio;

void printInParens(T)(T value) {
    writefln("(%s)", value);
}

void main() {
    printInParens(42);           // with int
    printInParens(1.2);          // with double

    auto myValue = MyStruct();
    printInParens(myValue);      // with MyStruct
}

struct MyStruct {
    string toString() const {
        return "hello";
    }
}

The compiler considers all of the uses of printInParens() in the program and generates code to support all those uses. The program is then compiled as if the function has been overloaded explicitly for int, double, and MyStruct: 

/* Note: These functions are not part of the source
 *       code. They are the equivalents of the functions that
 *       the compiler would automatically generate. */

void printInParens(int value) {
    writefln("(%s)", value);
}

void printInParens(double value) {
    writefln("(%s)", value);
}

void printInParens(MyStruct value) {
    writefln("(%s)", value);
}

The output of the program is produced by those different instantiations of the function template: 

(42)
(1.2)
(hello)

Each template parameter can determine more than one function parameter. For example, both the two function parameters and the return type of the following function template are determined by its single template parameter: 

/* Returns a copy of 'slice' except the elements that are
 * equal to 'value'. */
T[] removed(T)(const(T)[] slice, T value) {
    T[] result;

    foreach (element; slice) {
        if (element != value) {
            result ~= element;
        }
    }

    return result;
}
More than one template parameter

Let's change the function template to take the parentheses characters as well: 

void printInParens(T)(T value, char opening, char closing) {
    writeln(opening, value, closing);
}

Now we can call the same function with different sets of parentheses: 

    printInParens(42, '<', '>');

Although being able to specify the parentheses makes the function more usable, specifying the type of the parentheses as char makes it less flexible because it is not possible to call the function with characters of type wchar or dchar: 

    printInParens(42, '→', '←');      // ← compilation ERROR

Error: template deneme.printInParens(T) cannot deduce
template function from argument types !()(int,wchar,wchar)

One solution would be to specify the type of the parentheses as dchar but this would still be insufficient as this time the function could not be called e.g. with string or user-defined types.

Another solution is to leave the type of the parentheses to the compiler as well. Defining an additional template parameter instead of the specific char is sufficient: 

void printInParens(T, ParensType)(T value,
                                  ParensType opening,
                                  ParensType closing) {
    writeln(opening, value, closing);
}

The meaning of the new template parameter is similar to T's: ParensType can be any type.

It is now possible to use many different types of parentheses. The following are with wchar and string: 

    printInParens(42, '→', '←');
    printInParens(1.2, "-=", "=-");

→42←
-=1.2=-

The flexibility of printInParens() has been increased, as it now works correctly for any combination of T and ParensType as long as those types are printable with writeln().

Type deduction

The compiler's deciding on what type to use for a template parameter is called type deduction.

Continuing from the last example above, the compiler decides on the following types according to the two uses of the function template:

The compiler can deduce types only from the types of the parameter values that are passed to function templates. Although the compiler can usually deduce the types without any ambiguity, there are times when the types must be specified explicitly by the programmer.

Explicit type specification

Sometimes it is not possible for the compiler to deduce the template parameters. A situation that this can happen is when the types do not appear in the function parameter list. When template parameters are not related to function parameters, the compiler cannot deduce the template parameter types.

To see an example of this, let's design a function that asks a question to the user, reads a value as a response, and returns that value. Additionally, let's make this a function template so that it can be used to read any type of response: 

T getResponse(T)(string question) {
    writef("%s (%s): ", question, T.stringof);

    T response;
    readf(" %s", &response);

    return response;
}

That function template would be very useful in programs to read different types of values from the input. For example, to read some user information, we can imagine calling it as in the following line: 

    getResponse("What is your age?");

Unfortunately, that call does not give the compiler any clue as to what the template parameter T should be. What is known is that the question is passed to the function as a string, but the type of the return value cannot be deduced: 

Error: template deneme.getResponse(T) cannot deduce template
function from argument types !()(string)

In such cases, the template parameters must be specified explicitly by the programmer. Template parameters are specified in parentheses after an exclamation mark: 

    getResponse!(int)("What is your age?");

The code above can now be accepted by the compiler and the function template is compiled as T being an alias of int within the definition of the template.

When there is only one template parameter specified, the parentheses around it are optional: 

    getResponse!int("What is your age?");    // same as above

You may recognize that syntax from to!string, which we have been using in earlier programs. to() is a function template, which takes the target type of the conversion as a template parameter. Since it has only one template parameter that needs to be specified, it is commonly written as to!string instead of to!(string).

Template instantiation

Automatic generation of code for a specific set of template parameter values is called an instantiation of that template for that specific set of parameter values. For example, to!string and to!int are two different instantiations of the to function template.

As I will mention again in a separate section below, distinct instantiations of templates produce distinct and incompatible types.

Template specializations

Although the getResponse() function template can in theory be used for any template type, the code that the compiler generates may not be suitable for every type. Let's assume that we have the following type that represents points on a two dimensional space: 

struct Point {
    int x;
    int y;
}

Although the instantiation of getResponse() for the Point type itself would be fine, the generated readf() call for Point cannot be compiled. This is because the standard library function readf() does not know how to read a Point object. The two lines that actually read the response would look like the following in the Point instantiation of the getResponse() function template: 

    Point response;
    readf(" %s", &response);    // ← compilation ERROR

One way of reading a Point object would be to read the values of the x and y members separately and then to construct a Point object from those values.

Providing a special definition of a template for a specific template parameter value is called a template specialization. The specialization is defined by the type name after a : character in the template parameter list. A Point specialization of the getResponse() function template can be defined as in the following code: 

// The general definition of the function template (same as before)
T getResponse(T)(string question) {
    writef("%s (%s): ", question, T.stringof);

    T response;
    readf(" %s", &response);

    return response;
}

// The specialization of the function template for Point
T getResponse(T : Point)(string question) {
    writefln("%s (Point)", question);

    auto x = getResponse!int("  x");
    auto y = getResponse!int("  y");

    return Point(x, y);
}

Note that the specialization takes advantage of the general definition of getResponse() to read two int values to be used as the values of the x and y members.

Instead of instantiating the template itself, now the compiler uses the specialization above whenever getResponse() is called for the Point type: 

    auto center = getResponse!Point("Where is the center?");

Assuming that the user enters 11 and 22: 

Where is the center? (Point)
  x (int): 11
  y (int): 22

The getResponse!int() calls are directed to the general definition of the template and the getResponse!Point() calls are directed to the Point specialization of it.

As another example, let's consider using the same template with string. As you would remember from the Strings chapter, readf() would read all of the characters from the input as part of a single string until the end of the input. For that reason, the default definition of getResponse() would not be useful when reading string responses: 

    // Reads the entire input, not only the name!
    auto name = getResponse!string("What is your name?");

We can provide a template specialization for string as well. The following specialization reads just the line instead: 

T getResponse(T : string)(string question) {
    writef("%s (string): ", question);

    // Read and ignore whitespace characters which have
    // presumably been left over from the previous user input
    string response;
    do {
        response = strip(readln());
    } while (response.length == 0);

    return response;
}
Struct and class templates

The Point struct may be seen as having a limitation: Because its two members are defined specifically as int, it cannot represent fractional coordinate values. This limitation can be removed if the Point struct is defined as a template.

Let's first add a member function that returns the distance to another Point object: 

import std.math;

// ...

struct Point {
    int x;
    int y;

    int distanceTo(Point that) const {
        immutable real xDistance = x - that.x;
        immutable real yDistance = y - that.y;

        immutable distance = sqrt((xDistance * xDistance) +
                                  (yDistance * yDistance));

        return cast(int)distance;
    }
}

That definition of Point is suitable when the required precision is relatively low: It can calculate the distance between two points at kilometer precision, e.g. between the center and branch offices of an organization: 

    auto center = getResponse!Point("Where is the center?");
    auto branch = getResponse!Point("Where is the branch?");

    writeln("Distance: ", center.distanceTo(branch));

Unfortunately, Point is inadequate at higher precisions than int can provide.

Structs and classes can be defined as templates as well, by specifying a template parameter list after their names. For example, Point can be defined as a struct template by providing a template parameter and replacing the ints by that parameter: 

struct Point(T) {
    T x;
    T y;

    T distanceTo(Point that) const {
        immutable real xDistance = x - that.x;
        immutable real yDistance = y - that.y;

        immutable distance = sqrt((xDistance * xDistance) +
                                  (yDistance * yDistance));

        return cast(T)distance;
    }
}

Since structs and classes are not functions, they cannot be called with parameters. This makes it impossible for the compiler to deduce their template parameters. The template parameter list must always be specified for struct and class templates: 

    auto center = Point!int(0, 0);
    auto branch = Point!int(100, 100);

    writeln("Distance: ", center.distanceTo(branch));

The definitions above make the compiler generate code for the int instantiation of the Point template, which is the equivalent of its earlier non-template definition. However, now it can be used with any type. For example, when more precision is needed, with double: 

    auto point1 = Point!double(1.2, 3.4);
    auto point2 = Point!double(5.6, 7.8);

    writeln(point1.distanceTo(point2));

Although the template itself has been defined independently of any specific type, its single definition makes it possible to represent points of various precisions.

Simply converting Point to a template would cause compilation errors in code that has already been written according to its non-template definition. For example, now the Point specialization of getResponse() cannot be compiled: 

T getResponse(T : Point)(string question) {  // ← compilation ERROR
    writefln("%s (Point)", question);

    auto x = getResponse!int("  x");
    auto y = getResponse!int("  y");

    return Point(x, y);
}

The reason for the compilation error is that Point itself is not a type anymore: Point is now a struct template. Only instantiations of that template would be considered as types. The following changes are required to correctly specialize getResponse() for any instantiation of Point: 

Point!T getResponse(T : Point!T)(string question) {  // 2, 1
    writefln("%s (Point!%s)", question, T.stringof); // 5

    auto x = getResponse!T("  x");                   // 3a
    auto y = getResponse!T("  y");                   // 3b

    return Point!T(x, y);                            // 4
}
  1. In order for this template specialization to support all instantiations of Point, the template parameter list must mention Point!T. This simply means that the getResponse() specialization is for Point!T, regardless of T. This specialization would match Point!int, Point!double, etc.
  2. Similarly, to return the correct type as the response, the return type must be specified as Point!T as well.
  3. Since the types of x and y members of Point!T are now T, as opposed to int, the members must be read by calling getResponse!T(), not getResponse!int(), as the latter would be correct only for Point!int.
  4. Similar to items 1 and 2, the type of the return value is Point!T.
  5. To print the name of the type accurately for every type, as in Point!int, Point!double, etc., T.stringof is used.
Default template parameters

Sometimes it is cumbersome to provide template parameter types every time a template is used, especially when that type is almost always a particular type. For example, getResponse() may almost always be called for the int type in the program, and only in a few places for the double type.

It is possible to specify default types for template parameters, which are assumed when the types are not explicitly provided. Default parameter types are specified after the = character: 

T getResponse(T = int)(string question) {
    // ...
}

// ...

    auto age = getResponse("What is your age?");

As no type has been specified when calling getResponse() above, T becomes the default type int and the call ends up being the equivalent of getResponse!int().

Default template parameters can be specified for struct and class templates as well, but in their case the template parameter list must always be written even when empty: 

struct Point(T = int) {
    // ...
}

// ...

    Point!() center;

Similar to default function parameter values as we have seen in the Variable Number of Parameters chapter, default template parameters can be specified for all of the template parameters or for the last ones: 

void myTemplate(T0, T1 = int, T2 = char)() {
    // ...
}

The last two template parameters of that function may be left unspecified but the first one is required: 

    myTemplate!string();

In that usage, the second and third parameters are int and char, respectively.

Every template instantiation yields a distinct type

Every instantiation of a template for a given set of types is considered to be a distinct type. For example, Point!int and Point!double are separate types: 

Point!int point3 = Point!double(0.25, 0.75); // ← compilation ERROR

Those different types cannot be used in the assignment operation above: 

Error: cannot implicitly convert expression (Point(0.25,0.75))
of type Point!(double) to Point!(int)
A compile-time feature

Templates are entirely a compile-time feature. The instances of templates are generated by the compiler at compile time.

Class template example: stack data structure

Struct and class templates are commonly used in the implementations of data structures. Let's design a stack container that will be able to contain any type.

Stack is one of the simplest data structures. It represents a container where elements are placed conceptually on top of each other as would be in a stack of papers. New elements go on top, and only the topmost element is accessed. When an element is removed, it is always the topmost one.

If we also define a property that returns the total number of elements in the stack, all of the operations of this data structure would be the following:

An array can be used to store the elements such that the last element of the array would be representing the topmost element of the stack. Finally, it can be defined as a class template to be able to contain elements of any type: 

class Stack(T) {
private:

    T[] elements;

public:

    void push(T element) {
        elements ~= element;
    }

    void pop() {
        --elements.length;
    }

    T top() const {
        return elements[$ - 1];
    }

    size_t length() const {
        return elements.length;
    }
}

Here is a unittest block for this class that uses its int instantiation: 

unittest {
    auto stack = new Stack!int;

    // The newly added element must appear on top
    stack.push(42);
    assert(stack.top == 42);
    assert(stack.length == 1);

    // .top and .length should not affect the elements
    assert(stack.top == 42);
    assert(stack.length == 1);

    // The newly added element must appear on top
    stack.push(100);
    assert(stack.top == 100);
    assert(stack.length == 2);

    // Removing the last element must expose the previous one
    stack.pop();
    assert(stack.top == 42);
    assert(stack.length == 1);

    // The stack must become empty when the last element is
    // removed
    stack.pop();
    assert(stack.length == 0);
}

To take advantage of this class template, let's try using it this time with a user-defined type. As an example, here is a modified version of Point: 

struct Point(T) {
    T x;
    T y;

    string toString() const {
        return format("(%s,%s)", x, y);
    }
}

A Stack that contains elements of type Point!double can be defined as follows: 

    auto points = new Stack!(Point!double);

Here is a test program that first adds ten elements to this stack and then removes them one by one: 

import std.string;
import std.stdio;
import std.random;

struct Point(T) {
    T x;
    T y;

    string toString() const {
        return format("(%s,%s)", x, y);
    }
}

// Returns a random value between -0.50 and 0.50.
double random_double()
out (result) {
    assert((result >= -0.50) && (result < 0.50));

} do {
    return (double(uniform(0, 100)) - 50) / 100;
}

// Returns a Stack that contains 'count' number of random
// Point!double elements.
Stack!(Point!double) randomPoints(size_t count)
out (result) {
    assert(result.length == count);

} do {
    auto points = new Stack!(Point!double);

    foreach (i; 0 .. count) {
        immutable point = Point!double(random_double(),
                                       random_double());
        writeln("adding  : ", point);
        points.push(point);
    }

    return points;
}

void main() {
    auto stackedPoints = randomPoints(10);

    while (stackedPoints.length) {
        writeln("removing: ", stackedPoints.top);
        stackedPoints.pop();
    }
}

As the output of the program shows, the elements are removed in the reverse order as they have been added: 

adding  : (-0.02,-0.01)
adding  : (0.17,-0.5)
adding  : (0.12,0.23)
adding  : (-0.05,-0.47)
adding  : (-0.19,-0.11)
adding  : (0.42,-0.32)
adding  : (0.48,-0.49)
adding  : (0.35,0.38)
adding  : (-0.2,-0.32)
adding  : (0.34,0.27)
removing: (0.34,0.27)
removing: (-0.2,-0.32)
removing: (0.35,0.38)
removing: (0.48,-0.49)
removing: (0.42,-0.32)
removing: (-0.19,-0.11)
removing: (-0.05,-0.47)
removing: (0.12,0.23)
removing: (0.17,-0.5)
removing: (-0.02,-0.01)
Function template example: binary search algorithm

Binary search is the fastest algorithm to search for an element among the elements of an already sorted array. It is a very simple algorithm: The element in the middle is considered; if that element is the one that has been sought, then the search is over. If not, then the algorithm is repeated on the elements that are either on the left-hand side or on the right-hand side of the middle element, depending on whether the sought element is greater or less than the middle element.

Algorithms that repeat themselves on a smaller range of the initial elements are recursive. Let's write the binary search algorithm recursively by calling itself.

Before converting it to a template, let's first write this function to support only arrays of int. We can easily convert it to a template later, by adding a template parameter list and replacing appropriate ints in its definition by Ts. Here is a binary search algorithm that works on arrays of int: 

/* This function returns the index of the value if it exists
 * in the array, size_t.max otherwise. */
size_t binarySearch(const int[] values, int value) {
    // The value is not in the array if the array is empty.
    if (values.length == 0) {
        return size_t.max;
    }

    immutable midPoint = values.length / 2;

    if (value == values[midPoint]) {
        // Found.
        return midPoint;

    } else if (value < values[midPoint]) {
        // The value can only be in the left-hand side; let's
        // search in a slice that represents that half.
        return binarySearch(values[0 .. midPoint], value);

    } else {
        // The value can only be in the right-hand side; let's
        // search in the right-hand side.
        auto index =
            binarySearch(values[midPoint + 1 .. $], value);

        if (index != size_t.max) {
            // Adjust the index; it is 0-based in the
            // right-hand side slice.
            index += midPoint + 1;
        }

        return index;
    }

    assert(false, "We should have never gotten to this line");
}

The function above implements this simple algorithm in four steps:

Here is a unittest block that tests the function: 

unittest {
    auto array = [ 1, 2, 3, 5 ];
    assert(binarySearch(array, 0) == size_t.max);
    assert(binarySearch(array, 1) == 0);
    assert(binarySearch(array, 4) == size_t.max);
    assert(binarySearch(array, 5) == 3);
    assert(binarySearch(array, 6) == size_t.max);
}

Now that the function has been implemented and tested for int, we can convert it to a template. int appears only in two places in the definition of the template: 

size_t binarySearch(const int[] values, int value) {
    // ... int does not appear here ...
}

The ints that appear in the parameter list are the types of the elements and the value. Specifying those as template parameters is sufficient to make this algorithm a template and to be usable with other types as well: 

size_t binarySearch(T)(const T[] values, T value) {
    // ...
}

That function template can be used with any type that matches the operations that are applied to that type in the template. In binarySearch(), the elements are used only with comparison operators == and <: 

    if (value == values[midPoint]) {
        // ...

    } else if (value < values[midPoint]) {

        // ...

For that reason, Point is not ready to be used with binarySearch() yet: 

import std.string;

struct Point(T) {
    T x;
    T y;

    string toString() const {
        return format("(%s,%s)", x, y);
    }
}

void main() {
    Point!int[] points;

    foreach (i; 0 .. 15) {
        points ~= Point!int(i, i);
    }

    assert(binarySearch(points, Point!int(10, 10)) == 10);
}

The program above would cause a compilation error: 

Error: need member function opCmp() for struct
const(Point!(int)) to compare

According to the error message, opCmp() needs to be defined for Point. opCmp() has been covered in the Operator Overloading chapter: 

struct Point(T) {
// ...

    int opCmp(const ref Point that) const {
        return (x == that.x
                ? y - that.y
                : x - that.x);
    }
}
Summary

We will see other features of templates in a later chapter. The following are what we have covered in this chapter: