Generic Programming with Templates

Reusable code is a constant goal in programming. A function that adds two numbers is useful, but a programmer often wants the same logic to work for many kinds of data without rewriting it each time. Templates are a feature designed to address this need. They let a single piece of code serve many situations, and they do so by moving certain decisions out of the running program and into the process that turns source code into an executable.

A useful way to understand templates is to ask what they make possible that ordinary functions and ordinary values do not. The answer is that templates give a program three distinct capabilities. Each one addresses a different limit a programmer would otherwise run into. The first is that templates can accept types, values, and other templates as arguments. The second is that type checking in a template is delayed until the template is instantiated. The third is that constant values passed as arguments allow computation to happen at compile time.

All three capabilities share a common theme: each one moves decisions out of the running program and into the compilation process. The diagram below shows how the three ideas relate to one another and to the broader goal of generic programming.

The source describes the three ideas as reinforcing one another. Types carry exact information, checking waits for concrete use, and constants can be evaluated early. Combined, these produce a mechanism that can be very compact and efficient, which is why the source calls it a powerful one.

The first capability is that a template can accept a type as an argument, in the same way a function accepts a value. The important phrase is without loss of information. When a type is handed to a template, the template receives the type itself, not a stand-in or a simplified description of it. Because of this, the code that is produced can be built around that exact type.

The same passing mechanism works for values and for templates. The source emphasizes that the ability extends to types as well as values and templates. Keeping all of this information intact is what gives the compiler the chance to optimize, and that opportunity is the subject of the next idea.

Because the exact type survives the trip into the template, the compiler can make its generated code specific to that type. Inlining is the practice of placing the body of a called routine at the point where it is called. The source connects the preserved type information directly to this practice, noting that it creates excellent opportunities for inlining and that current implementations take great advantage of them.

The reasoning can be followed step by step. A template receives a type argument. The type is kept whole. The compiler therefore has a version of the code that is built for that specific type. A routine that exists in a version written for exactly that type is a natural candidate for having its body placed directly at the call site. The source does not go into further detail about the particular optimizations involved, so the key idea to hold on to is simply that exact type information is what makes the specialized code possible.

The second capability concerns when a template's types are checked. The source states that type checking in templates is delayed until instantiation. Instantiation is the point at which a template is used with concrete arguments and a version of it is actually produced. Until that point, the template is a pattern that has not yet been filled in, so the checking that depends on specific types waits for those specific types to arrive.

The source describes the benefit as an opportunity to weave together information from different contexts. The template itself does not need to know every situation in which it will be used. Each use supplies its own context, and the checking that happens at that moment draws on the information that context provides. A single template can therefore serve many callers, each bringing different information with them.

The third capability is the ability to pass constant values as arguments. The source draws the conclusion that this implies the ability to do computation at compile time. The reasoning is direct. If the value handed to a template is a constant, the compiler already knows it when the template is instantiated. Any work that depends only on that constant can therefore be carried out before the program runs.

A small illustrative example makes this concrete. Suppose a template named factorial takes a constant n and is defined so that factorial of n equals n multiplied by factorial of n minus 1, with factorial of 0 equal to 1. The example below is generated for teaching purposes and is not taken from the source. It shows how a constant argument drives a chain of steps that the compiler can finish before execution.