Metaprogramming is the writing of computer programs that write or manipulate other programs as their data, or that do part of the work at compile time that would otherwise be done at runtime...
In a broad definition, generic programming is a style of computer programming in which algorithms are written in terms of to-be-specified-later types that are then instantiated when needed for specific types provided as parameters...
A compiler is a computer program that transforms source code written in a programming language into another computer language...
to generate temporary source code, which is merged by the compiler with the rest of the source code and then compiled. The output of these templates include compile-time
Compile time
In computer science, compile time refers to either the operations performed by a compiler , programming language requirements that must be met by source code for it to be successfully compiled , or properties of the program that can be reasoned about at compile time.The operations performed at...
constants, data structures, and complete functions. The use of templates can be thought of as compile-time execution
Compile time function execution
Compile time function execution is the ability of a compiler, that would normally compile a function to machine code and execute it at run-time, to execute the function at compile-time...
. The technique is used by a number of languages, the best-known being C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
Curl is a reflective object-oriented programming language for interactive web applications whose goal is to provide a smoother transition between formatting and programming...
XL stands for eXtensible Language. It is a computer programming language designed to support concept programming.XL features programmer-reconfigurable syntax and semantics. Compiler plug-ins can be used to add new features to the language. A base set of plug-ins implements a relatively standard...
.
Template metaprogramming was, in a sense, discovered accidentally: see History of TMP.
Some other languages support similar, if not more powerful compile-time facilities (such as Lisp macros), but those are outside the scope of this article.
Components of template metaprogramming
The use of templates as a metaprogramming technique requires two distinct operations: a template must be defined, and a defined template must be instantiated. The template definition describes the generic form of the generated source code, and the instantiation causes a specific set of source code to be generated from the generic form in the template.
Template metaprogramming is generally Turing-complete, meaning that any computation expressible by a computer program can be computed, in some form, by a template metaprogram.
Templates are different from macros. A macro, which is also a compile-time language feature, generates code in-line using text manipulation and substitution. Macro systems often have limited compile-time process flow abilities and usually lack awareness of the semantics and type system of their companion language (an exception should be made with Lisp's macros, which are written in Lisp itself and involve manipulation and substitution of Lisp code represented as data structures as opposed to text).
In object-oriented and functional programming, an immutable object is an object whose state cannot be modified after it is created. This is in contrast to a mutable object, which can be modified after it is created...
— that is, no variable can change value once it has been initialized, therefore template metaprogramming can be seen as a form of functional programming
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
. In fact many template implementations only implement flow control through recursion, as seen in the example below.
Using template metaprogramming
Though the syntax of template metaprogramming is usually very different from the programming language it is used with, it has practical uses. Some common reasons to use templates are to implement generic programming
Generic programming
In a broad definition, generic programming is a style of computer programming in which algorithms are written in terms of to-be-specified-later types that are then instantiated when needed for specific types provided as parameters...
(avoiding sections of code which are similar except for some minor variations) or to perform automatic compile-time optimization such as doing something once at compile time rather than every time the program is run — for instance, by having the compiler unroll loops to eliminate jumps and loop count decrements whenever the program is executed.
Compile-time class generation
What exactly "programming at compile-time" means can be illustrated with an example of a factorial
Factorial
In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...
function, which in non-template C++ can be written using recursion as follows:
unsigned int factorial(unsigned int n)
{
if (n
0)
return 1;
return n * factorial(n - 1);
}
void foo
{
int x = factorial(4); //
(4 * 3 * 2 * 1 * 1)
24
int y = factorial(0); //
0! 1
}
The code above will execute when the program is run to determine the factorial value of the literals 4 and 0.
Instead, by using template metaprogramming and template specialization to provide the ending condition for the recursion, the factorials used in the program, ignoring any factorial not used, can be calculated at compile-time by this code:
template
struct Factorial
{
enum { value = N * Factorial::value };
};
The code above calculates the factorial value of the literals 4 and 0 at compile time and uses the result as if they were precalculated constants.
While the two versions are similar from the point of view of the program's functionality, the first example calculates the factorials at run time, while the second calculates them at compile time
Compile time
In computer science, compile time refers to either the operations performed by a compiler , programming language requirements that must be met by source code for it to be successfully compiled , or properties of the program that can be reasoned about at compile time.The operations performed at...
. However, to be able to use templates in this manner, the compiler must know the value of its parameters at compile time, which has the natural precondition that Factorial<X>::value can only be used if X is known at compile time. In other words, X must be a constant literal or a constant expression.
The difference between the two approaches is a conceptual one: optimizers may evaluate the first example's factorial(X) at compile time, too, if X is known at compile time. However, this kind of optimization is neither guaranteed nor achieved through programming, as it is in the case of template metaprogramming. The first example also has the effect of producing code of a function definition for computing factorials regardless of its being called or not, unlike the second example whose intention is to avoid producing a factorial function's code.
Compile-time code optimization
The factorial example above is one example of compile-time code optimization in that all factorials used by the program are pre-compiled and injected as numeric constants at compilation, saving both run-time overhead and memory footprint. It is, however, a relatively minor optimization.
As another, more significant, example of compile-time loop-unrolling, template metaprogramming can be used to create length-n vector classes (where n is known at compile time). The benefit over a more traditional length-n vector is that the loops can be unrolled, resulting in very optimized code. As an example, consider the addition operator. An length-n vector addition might be written as
template
Vector& Vector::operator+=(const Vector& rhs)
{
for (int i = 0; i < length; ++i)
value[i] += rhs.value[i];
return *this;
}
When the compiler instantiates the function template defined above, the following code may be produced:
In computer science, polymorphism is a programming language feature that allows values of different data types to be handled using a uniform interface. The concept of parametric polymorphism applies to both data types and functions...
is a common standard programming facility where derived objects can be used as instances of their base object but where the derived objects' methods will be invoked, as in this code
class Base
{
public:
virtual void method { std::cout << "Base"; }
virtual ~Base {}
};
class Derived : public Base
{
public:
virtual void method { std::cout << "Derived"; }
};
int main
{
Base *pBase = new Derived;
pBase->method; //outputs "Derived"
delete pBase;
return 0;
}
where all invocations of virtual methods will be those of the most-derived class. This dynamically polymorphic behaviour is (typically) obtained by the creation of virtual look-up tables for classes with virtual methods, tables that are traversed at run time to identify the method to be invoked. Thus, run-time polymorphism necessarily entails execution overhead (though on modern architectures the overhead is negligible).
However, in many cases the polymorphic behaviour needed is invariant and can be determined at compile time. Then the Curiously Recurring Template Pattern
Curiously Recurring Template Pattern
The curiously recurring template pattern is a C++ idiom in which a class X derives from a class template instantiation using X itself as template argument...
(CRTP) can be used to achieve static polymorphism, which is an imitation of polymorphism in programming code but which is resolved at compile time and thus does away with run-time virtual-table lookups. For example:
template
struct base
{
void interface
{
// ...
static_cast(this)->implementation;
// ...
}
};
struct derived : base
{
void implementation;
};
Here the base class template will take advantage of the fact that member function bodies are not instantiated until after their declarations, and it will use members of the derived class within its own member functions, via the use of a static_cast, thus at compilation generating an object composition with polymorphic characteristics. As an example of real-world usage, the CRTP is used in the Boost
Boost library
Boost is a set of free software libraries that extend the functionality of C++.-Overview:Most of the Boost libraries are licensed under the Boost Software License, designed to allow Boost to be used with both free and proprietary software projects...
In computer programming, an iterator is an object that enables a programmer to traverse a container. Various types of iterators are often provided via a container's interface...
Another similar use is the "Barton–Nackman trick", sometimes referred to as "restricted template expansion", where common functionality can be placed in a base class that is used not as a contract but as a necessary component to enforce conformant behaviour while minimising code redundancy.
Benefits and drawbacks of template metaprogramming
Compile-time versus execution-time tradeoff: If a great deal of template metaprogramming is used, compilation may become slow; section 14.7.1 [temp.inst] of the current standard defines the circumstances under which templates are implicitly instantiated. As with most aspects of C++, you pay only for what you use: defining a template does not imply that it will be instantiated, and instantiating a class template does not cause its member definitions to be instantiated. Depending on the style of use, templates may compile either faster or slower than hand-rolled code.
Generic programming: Template metaprogramming allows the programmer to focus on architecture and delegate to the compiler the generation of any implementation required by client code. Thus, template metaprogramming can accomplish truly generic code, facilitating code minimization and better maintainability.
Readability: With respect to C++, the syntax and idioms of template metaprogramming are esoteric compared to conventional C++ programming, and template metaprograms can be very difficult to understand. Metaprograms can thus be difficult to maintain by programmers inexperienced in template metaprogramming (though this may vary with the language's implementation of template metaprogramming syntax). On the other hand, template metaprogramming can often be used to make programs much shorter and simpler, and thus more readable. An experienced programmer will also be able to tweak the program and use the compiler error messages to understand the program flow much more easily than could have been achieved by any non-metaprogramming approach.
Portability: With respect to C++, due to differences in compilers, code relying heavily on template metaprogramming (especially the newest forms of metaprogramming) might have portability issues.
Metaprogramming is the writing of computer programs that write or manipulate other programs as their data, or that do part of the work at compile time that would otherwise be done at runtime...
In computer science, a preprocessor is a program that processes its input data to produce output that is used as input to another program. The output is said to be a preprocessed form of the input data, which is often used by some subsequent programs like compilers...
In programming languages and type theory, parametric polymorphism is a way to make a language more expressive, while still maintaining full static type-safety. Using parametric polymorphism, a function or a data type can be written generically so that it can handle values identically without...
In computer programming, variadic templates are templates that take a variable number of arguments.Variadic templates are supported by the D programming language, and the newest version of C++, formalized in the C++11 standard.-C++11:...
Compile time function execution is the ability of a compiler, that would normally compile a function to machine code and execute it at run-time, to execute the function at compile-time...
Walter Bright is a computer programmer known for being the designer of the D programming language. He was also the main developer of the first C++ compiler that translated directly to object without going via C, Zortech C++ . Before the C++ compiler, he developed the Datalight C compiler, also...
, "Templates Revisited", an article on template metaprogramming in the D programming language.
