Understanding Templates: why can't anybody do it?

[Sean Kelly]

On Mar 17, 2012, at 10:14 AM, Entity325 wrote:

> (Sorry if this is the wrong place for this, or if there's already a thread in existence which would be better.  If either of these is the case, simply point me in the right direction, and I'll be on my way.)
> 
> My first interaction with Templates was about 5 years ago, in a C++ class at my university.  I immediately thought "A general type?  This would be great for my logger!" and tried to implement them into the small library I had been developing to save time on the class assignments.
> 
> Naturally, I didn't understand them, so after a couple of half-hearted attempts, I gave up and went back to doing things the way I had before.  I've avoided Templates since then, because they don't make any sense!

I see this a lot, and it's why I wrote the chapter on templates for Learn to Tango with D.  I don't think I can sort out releasing the chapter though.  One approach is to think of templates as compile-time polymorphism.  In Java, you might create a linked-list as:

class List {
    void insert(Object e) {
        head = new Node(e, head);
    }

    static class Node {
        Object elem;
        Node next;

        this(Object e, Node n) {
            elem = e; 
            next = n;
        }
    }
}


This works fine so long as everything you store in the list derives from Object, and you have to remember what the list holds so when you examine an element you cast it to Integer or whatever.  But both of these are problems.  First, you can't store concrete types (int, float, etc) in the list, and second, the compiler can't help you make sure you only store instances of Integer or whatever in the list (for the record, Java does have auto-boxing and generics now to deal with these issues).  In D, we can address these problems by converting List to a template class.

Templates are really just a means of telling the compiler to generate code according to some simple rules.  So looking at the List class above, if we want it to hold anything instead of just Objects, we replace instances of "Object" above with a type signifier.  The long form is easiest to understand:

template (T) {
    class List {
        void insert(T e) {
            head = new Node(e, head);
        }

        static class Node {
            T elem;
            Node next;
            
            this(T e, Node n) {
                elem = e;
                next = n;
            }
        }
    }
}


Notice that all we did to create this template was replace "Object" with an arbitrarily chosen name "T", then enclose the whole thing in a "template" block with one parameter, T.  This tells the compiler that what's contained is a template with a variable type T.  Let's say you declare one instance of this container:

auto list = new List!(int);


The compiler sees "int" as the parameter for template argument "T" and generates code for the list above with "int" written wherever "T" is, so:

class List {
    void insert(int e) {
        head = new Node(e, head);
    }

    static class Node {
        int elem;
        Node next;
            
        this(int e, Node n) {
            elem = e;
            next = n;
        }
    }
}


This is done early enough during compilation that it's as if you wrote the code by hand, so you'll get a compile error if you try to insert something that isn't an int, etc.

The declaration of template types that introduce their own scope (ie. structs and classes) can eliminate the enclosing "template" scope and move the template list down to after the type name, so the original template declaration above is equivalent to:

class List (T) {
    ...
}


Template functions work exactly the same way, except that the compiler can infer the types of template parameters based on the function argument list, so:

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


which can be written in a more compact form as:

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


Note how the template list moved after the function name, just like with the List class above.  Now, you can call this as:

auto result = add!(int)(1, 2);
assert(result == 3);


Or let the compiler determine T for you.  The arguments above are both of type int, so if you write:

auto result = add(1, 2);
assert(result == 3);


The compiler sees that the arguments for add() are type int and does the replacement automatically.

Now fast-forward from the original conception of templates to today.  D also allows you to pass data as template arguments, so this also works:

template (int x) {
    int add(int y) {
        return x + y;
    }
}


or again:

int add(int x)(int y) {
    return x + y;
}


And calling:

int val = 7;
auto result = add!(5)(val);


Generates the function:


int add!(5)(int y) {
    return 5 + y;
}


The more advanced template stuff is just riffs on these ideas.  It all works by having the compiler generate code, replacing type and variable symbols in the template list with whatever was specified when the template was called.  And back to the original motivation above, this gives you the performance and safety of hand-written code with the ease of maintenance of polymorphic code, since you only have to maintain a single copy.

I dunno if any of that helped, but if not, maybe some more directed questions in D.learn?  The basic idea behind templates is very straightforward.  The biggest problem seems to be that most people talk about them like they're some sort of black magic, so finding a straightforward explanation can be surprisingly hard.