9. Calculation at compile-time with help of templates Introduction Hi! This is new chapter of my articles about C++. In previous few articles I have mentioned a lot things about templates. All this time I have described templates with type template arguments, but attentive reader could notice interesting thing with std::array in my article "Haters gonna hate or life without pointers in C++11 times". Remind the following code:
std::array<int, 3> array = { 2, -1, 0 };
std::array is template class which has storage type as its first template argument and the second... one minute... *value* of array dimension! Yes, you understand correctly that template argument can be non-type, but value. This topic is about such feature and how it can be used for mathematics calculations at compile time. Value as template argument _or you can do a lot of compile-_time Before happiness there is a restriction: template argument can be non-type only if it is an integer constant (including enumerations) and pointer to an object with external linkage. Other variants are forbidden at the moment. Let's investigate both cases. 1. Pointer to an object with external linkage. Here is an example with such value which is represented as array of characters:
extern char charr[] = "luck"; (1.1)
template<char *str> (1.2)
void PointerTemplateFunc()
{
str[0] = 'd';
}
...
// Currently charr is "luck".
PointerTemplateFunc<charr>(); (1.3)
// Now it has value "duck".
Let's take a look at such lines: (1.1) declaration of external array of characters; (1.2) declaration of template function which template argument is pointer to char; (1.3) call of this template function with external character array as template argument. As you see template argument isn't a type here. It is a pointer to external object. It is not in common practice and probably you won't use it, but the next case has a lot of use cases in real projects. 2. Integer constant. As non-type template argument can also be integer values, such as: char, short, int, long and their versions with unsigned keyword. It is very helpful when you need to generate code with a template which requires some constant value important for the class. Back to std::array<T, N>, T is template argument of item type in array and N is non-type template argument for dimension of array. Besides this such integer template argument can be used for calculation at compile time. My next example with calculation of factorial demonstrates it:
template<int number> (2.1)
class Factorial
{
public:
enum
{
result = number * Factorial<number-1>::result (2.2)
};
};
template<>
class Factorial<1> (2.3)
{
public:
enum
{
result = 1 (2.4)
};
};
...
// It prints: 24
std::cout << Factorial<4>::result << std::endl; (2.5)
In common words here is declaration of template class which has non-type template argument as int value and has specification when this value is 1 what provides calculation of factorial through template generation at compile text. Lets observe all step by step: (2.1) This line is declaration of template argument list which has int value as argument template. (2.2) This is the line which provides all calculations at compile time. As you see it multiplies non-type template argument with result of recursive instantiation of the same template, but its value is reduced by one. Result of calculation is written to enum item. It means expression of Factorial::result holds calculated value. (2.3) Here is specialization for template class Factorial when number value is equal to 1. This is used to stop recursive invocation of template generating on line (2.2). (2.4) 1 is terminal value of multiply series for factorial calculation. (2.5) This is the line where all magic takes place. When compiler gets to this line, it will generate few templates: Factorial, Factorial, Factorial and Factorial. From the last specified template class Factorial to the first Factorial will be calculated sequence of Factorial::result value: 1 in Factorial::result, 2 in Factorial::result, 6 in Factorial::result, 24 in Factorial::result. Actually compile puts just 24 in standard output stream and nothing else. At run-time there aren't any calculations. Thus at run-time this strange code is equal to:
int value = 1;
for(int i = 2; i < 5; ++i)
{
value *= i;
}
std::cout << value << std::endl;
But such calculation is made at compile time and at run time it looks like the following code:
std:: cout << 24 << std::endl;
Isn't it awesome? With help of non-type template argument, recursively instantiation of templates, specialization we can make calculation with loops and conditions. Moreover thanks to such capabilities, templates are full Turing machine. It means that every mathematics function can be calculated. You probably understand that floating point types can't be used here as input non-type argument. But it doesn't have any technical obstacles. In future of C++ it can be provided. As another bad news - it makes building of project slower, but sometimes it is good practice to take some code from run-time and do in at compile time. Extended example of compile-time calculation or on the way to get exponentiation Let's consolidate and increase the new knowledge with another example of calculation at compile time. This time it is calculation of exponentiation. It is a binary operation, so it requires more template arguments for calculations. Let's see implementation and discuss it:
template <int base, int degree, int multiply_adder> (3.1)
class PowerImpl
{
public:
enum
{
result = PowerImpl<base, (3.2)
degree - 1,
multiply_adder * base>
::result
};
};
template <int base, int multiply_adder>
class PowerImpl<base, 0, multiply_adder> (3.3)
{
public:
enum
{
result = multiply_adder
};
};
template <int base, int degree> (3.4)
class Power
{
public:
enum
{
result = PowerImpl<base, degree, 1>::result (3.5)
};
};
...
// It prints: 64
std::cout << Power<4,3>::result << std::endl; (3.6)
So there are: (3.1) Template argument list with three non-type arguments. All of them are integer values. They are: base - base of exponentiation, degree is power of exponentiation, multiply_adder is variable which holds result of multiplying base on itself "degree" times. PowerImpl is implementation of getting exponentiation by itself. (3.2) As in the example with Factorial here we write result of recursive instantiation of template PowerImpl to result enum. As you probably understand we reduce degree by one every time we multiply multiply_adder by base value. (3.3) This is specification for end condition of recursively generation of template classes. You have to catch that this time we specify second argument of template argument list. Specification of templates doesn't have restriction in which order to specify template arguments. This allows to use it for stopping when degree is reduced to zero. It means that multiply_adder stores intermediate value of exponentiation. (3.4) This template class is a wrapper for PowerImpl, because the last one requires value 1 as the third argument and end user might not understand what to pass as the last template argument. (3.5) This line holds what we have hidden from end user of class Power and we save result of calculation to enum item. (3.6) Line shows how end user uses our class for exponentiation calculation. It is the same story as with calculation of Factorial - after compiling in generated assembler code there will be just printing of value 64 to standard output. This is how another simple mathematics entity can be found at compile time. In the next part of the article I will complicate mathematics calculation with already written entities. Get simple mathematics series or increase level of compile-time madness Now we have implemented calculation of factorial and exponentiation. I am proposing to write calculation of such mathematics series at compile time: Let's begin to implement this with Summator class which will make sum of some function from 1 to N. Some function will be set as template class in argument list. It is something new, let's check it out in the following code:
template<
typename TypeData, (4.1)
template<TypeData, TypeData> class T, (4.2)
int value, (4.3)
int i (4.4)
>
class Summator
{
public:
static const double result = T<value, i>::result (4.5)
+
Summator<TypeData, T, value, i-1>::result; (4.6)
};
template<
typename TypeData,
template<TypeData, TypeData> class T,
int value
>
class Summator <TypeData, T, value, 1> (4.7)
{
public:
static const double result = T<value, 1>::result;
};
As usual I will begin with the first marked line: (4.1) TypeData is template argument which is used for setting non-type template argument for template argument. Don't get it? See the next line. (4.2) class T is our template class that calculates some function which is passed as its template argument. This technique is called nesting of templates and it can be unsupported in some compilers that have restriction on level of nesting. TypeData is used for specifying type of arguments in template argument list of class T. The first argument is input value for function and the second one is current index of mathematics series. (4.3) This is input value for mathematics series. (4.4) An index of current calculated item of series. (4.5) There are two new things. The first is that we hold result of sum in constant static variable with double type. Because of division in our mathematics series we need to store result as value with floating point. const and static modifiers provide us to save necessary results at compile time. The second new thing is call of instantiation template argument class, but actually it looks as usual instantiation of template. It is worth noting that when we set this template class at instantiation of Summator, T will be replaced with name of class at compile time. And there will be instantiation of this template class. (4.6) This line must be well known for you. It is another recursively instantiation of our Summator, but with reduced index argument. (4.6) This class must be well acquainted for you - it is end condition for our Summator. It just initiates our template argument class with value and the first index of mathematics series. Now it is easy to implement mathematics series which I have wanted. We need to write template class which calculates our mathematics function [xn / n!] and some wrapper for encapsulating of instantiation our Summator with our mathematics function. Here is the implementation:
template<int x, int n>
class SingleSerie (5.1)
{
public:
static const double result = Power<x,n>::result (5.2)
/
(Factorial<n>::result * 1.0); (5.3)
};
template<int value, int count>
class MathSeries (5.4)
{
public:
static const double result =
Summator<int ,SingleSerie, value, count>::result; (5.5)
(Factorial<n>::result * 1.0); (5.3)
};
(5.1) SignleSerie is class for calculation of n item, generally it is our mathematics function f(x)_n = (x^n / n!) (5.2) There is instantiation of Power<x,n>::result - nothing new. (5.3) There is instantiation of Factorial::result, but probably you will ask why it is necessary to multiply by 1.0. Power<x,n>::result and Factorial::result have enum type which will be cast to integer value, but in this case we will lost fraction part of the number. For preventing this we must cast one of division operand to floating point type. Value 1.0 does it. Thus we get calculated value without losing any information. (5.4) MathSeries is a wrapper of instantiation necessary templates to calculate result of target mathematics series with given "value" "count" times. (5.5) This is what we encapsulate in the wrapper - instantiation of Summator with SignleSerie as target mathematics function. Usage of all this hell looks like an angel, see:
// It prints: 5.33333
std::cout << MathSeries<2, 3>::result << std::endl;
User works just with MathSeries<X, N> template class which encapsulates few entities at the same timee: Factorial, Power<base, degree>, Summator<TypeData, class T, value, i> and SingleSerie<x, n>. All these entities calculate values at compile time. Cool? Indeed. Conclusion This time I have told about such amazing thing with templates as calculation at compile time. Indeed templates have rich means for providing mathematics operations, which proves that templates in C++ are full Turing machine. It is provided by non-type template arguments, specialization and constant static values. On the other hand such implementation can be complicated and increases time for building process. But it helps to move some logic from run-time to compile-time and speed up performance of an application. My previous articles from “.CPP files” series are:
- “Do not muddle pointers and references”;
- “Extended talk about references and pointers”;
- “Haters gonna hate or life without pointers before C++11”;
- “Haters gonna hate or life without pointers in C++11 times”;
- “I have seen incomplete type”;
- “Template as double-edged sword: basic knowledge".
- “Template as double-edged sword: go further with OOP!".
- “Template as double-edged sword: diving with ducks”
