Life at compilation time
The article is not about what to do while the project is going.
The phrase "Templates - full, turing-complete, language" is often perceived with disbelief. This is just a generalizing feature of modern programming languages, where does the computing power come from? So I thought. Now I want to convince the rest, along with explaining the principles of the work of templates for beginners, like me.
My understanding of templates was shaken for the first time after reading the chapter “Metaprogramming” from a book about C ++ from the creator of C ++ - it seemed that they really can be a full-fledged programming language inside a programming language. In any case, there definitely is recursion. But the best way to prove something to yourself is to try to do what we will do.
There are many realizations of the legendary game "Life" by John Conway, crazy and not so. But all of them have a common fatal flaw: each iteration of Life is calculated directly during program operation. Let's try to fix it.
This is a language mechanism that creates specific functions \ data types for you, allowing you to write generalized algorithms, data structures, and the like - the programmer will substitute the desired parameter, and the compiler, by template, will create the corresponding entity.
The compiler will create two independent classes for the int and double parameters, and one sum function that accepts and returns a double value.
Therefore, templates are called templates - you create a class \ function, do not fill in some sections, leave labels instead of blanks, list the names of these labels before the class description and that’s it. Then, when using a template entity, enter the necessary parameters in angle brackets and the compiler will substitute them in the necessary sections of the code.
You can “not fill out” the type of the variable by specifying class \ typename in front of the name of the missing place, or by specifying a type directly, instead of class \ typename.
Although typename and class in the template language have exactly the same meaning, you can use the difference in writing to simplify the understanding of the code - for example, use typename where not only complex, but also simple data types can be used as parameters (plain old data), and class - where extremely complex "adult" classes are expected.
In general, yes, that’s enough.
It is also desirable that the compiler complies with the C ++ 11 standard and is able to calculate the results of constant expressions containing simple functions at the compilation stage.
But to simplify the code, we need aliases for types. C ++ provides 2 mechanisms for calling something complicated something simple: typedef and using. The latter appeared in C ++ 11 and differs from typedef (which is a relic of C) with a more understandable syntax and template support:
Therefore, using is a more understandable and extended version of typedef. Know about typedef, but use using.
Game Life - a simulator of the life of cells on the field. There are many variations of the rules of Life, but we use the classic ones. A living cell dies of boredom if there are less than two neighbors, or starvation if there are more than three neighbors. In an empty cell, life begins only when there are strictly 3 living cells next to it, i.e. there are parents and an obstetrician.
Let us analyze the problem: for Life, cells are needed, the space on which they are located, a way to determine the next state of each cell, based on the number of its neighbors.
Therefore, templates in C ++ should allow: setting the initial field, selecting each cell in the field, determining its neighbors, counting their number, determining the future state, forming the next field and looping the algorithm a certain number of times. In addition, you must not forget about the conclusion of all iterations of the algorithm.
In the beginning there was a cell:
And the binding of the cell type to the value:
It should be clarified that the template language can only operate with data types and constant values that can be calculated at compile time.
The word "constexpr" tells the compiler that the function should be able to execute at the compilation stage. If it seems to the compiler that this cannot be provided for this function, it will throw an error.
Still here a new feature of the template language is discovered - specialization. This allows you to create special types of entities for specific parameters. In extreme cases, with full specialization, as in the example above, only angle brackets remain from the list of templates.
Specialization is the very opportunity that gives templates a way to exit recursion. About her - a little later.
We will not reinvent the wheel and set the playing field using tuple from STL, game parameters - by constants:
tuple - a data structure that can contain various types of data - a kind of heterogeneous array. We, in fact, will not store anything in it - we are only interested in the tuple type, which consists of the previously defined types O and X. It is important to understand that there are no values that get into the assembled program, we are only interested in the type and work we are only with type.
Let's move on to magic. We remember that we need to count the living neighbors of the cell. Let the neighbors of types O and X already be in tuple and we know their number:
What's going on here? Recursion! Let's take a closer look:
we have already met constexpr - the value is guaranteed to be calculated at the compilation stage and is constant.
tuple_element- obviously, the selection of the Nth element from tuple, an opportunity provided in the STL.
Why is there typename and :: type? type is the field of the tuple_element structure, which is a typedef alias of another type, and typename, roughly speaking, specifically tells the compiler that this is the name of the template type.
More about typename here .
And here is the recursion itself. To calculate value, tuple_counter uses the value of the same tuple_counter, only with an iteration number 1 less. The exit from the recursion will occur when N becomes 0. The compiler will stumble upon the tuple_counter template specialized for N = 0, in which there is no recursion, and calculate the final value. Done.
All other calculations in the game, as well as the output of the result, are performed according to the same principle - recursively.
Well, suppose we counted living neighbors - how can we find out the next state of a cell based on this? Very simple if you do not reinvent the wheel and use conditional from STL:
conditional analogue of ternary operator X? Y: Z. If the condition in the first parameter is true, then the second parameter, otherwise the third. The rest of the code, I think, no longer needs explanation.
Great - we have an initial playing field and a way to determine the next state for any cell on it. Make life easier and combine all the basic functions of Life in one place:
Try not to make mistakes when calculating the neighbor index - if you go beyond tuple, you will find about 56 obscure compilation errors, it depends on the size of the field and the number of iterations.
The further solution is obvious - we will go through all the cells, save the next state of each in an array, print the result, repeat for all iterations ... Array? We do not have an array. You can’t just take and insert individual values in tuple - we only work with types, and changing the type of an individual element in tuple is not possible.
What to do? Use tuple_cat - a language mechanism for combining several tuple into one. Unfortunately, tuple_cat takes on tuple values, and again, we are only interested in types. You can peek at the STL sources and find out how tuple_cat determines the type, invent your own tupleciped, or use the available language tools.
Fortunately, the decltype operator appeared in C ++ 11, which literally means “what type the function would return if we called it”. We apply it to tuple_cat and ... make sure that tuple_cat still accepts not the bare type “tuple” with which we operate everywhere, but the value of tuple. Fortunately, C ++ has a declval class that allows us to pretend that a value does exist, but it cannot be used anywhere else as a value. It's enough.
Done! Now you can recursively collect all of the following states into a new state, adding cells one at a time:
Strange point indexing is needed for the correct order of the result. Done. We calculated the next state of Life in a form in which it can be sent to the next cycle of calculations. It remains only to display the result.
The output functions do not carry any new knowledge, so I bring them under the spoiler.
It remains to set the initial field, the number of iterations in the source, and breathe life into Life, which was completely determined even before its life began.
Having created Life, we proved to ourselves the usefulness of C ++ templates as a language, and also got a way to kill compilers that are too lazy to clean memory after recursive calls to template functions.
Life itself is a full-fledged language. So, in the game Life, it is theoretically possible to build a C ++ 11 compiler for Life source with a C ++ 11 compiler ... I leave this task to bored immortal readers for an independent solution.
The page of the working project on GitHub .
References: The C ++ Programming Language, 4th Edition .
The phrase "Templates - full, turing-complete, language" is often perceived with disbelief. This is just a generalizing feature of modern programming languages, where does the computing power come from? So I thought. Now I want to convince the rest, along with explaining the principles of the work of templates for beginners, like me.
My understanding of templates was shaken for the first time after reading the chapter “Metaprogramming” from a book about C ++ from the creator of C ++ - it seemed that they really can be a full-fledged programming language inside a programming language. In any case, there definitely is recursion. But the best way to prove something to yourself is to try to do what we will do.
There are many realizations of the legendary game "Life" by John Conway, crazy and not so. But all of them have a common fatal flaw: each iteration of Life is calculated directly during program operation. Let's try to fix it.
What are patterns
This is a language mechanism that creates specific functions \ data types for you, allowing you to write generalized algorithms, data structures, and the like - the programmer will substitute the desired parameter, and the compiler, by template, will create the corresponding entity.
template
class SomeClass
{
T i;
};
template // class тут — то же самое, что и typename!
T sum( T a, T b )
{
return a + b;
}
SomeClass obj_1;
SomeClass obj_1;
double i = sum( 3.14, 15.9 ); The compiler will create two independent classes for the int and double parameters, and one sum function that accepts and returns a double value.
Therefore, templates are called templates - you create a class \ function, do not fill in some sections, leave labels instead of blanks, list the names of these labels before the class description and that’s it. Then, when using a template entity, enter the necessary parameters in angle brackets and the compiler will substitute them in the necessary sections of the code.
You can “not fill out” the type of the variable by specifying class \ typename in front of the name of the missing place, or by specifying a type directly, instead of class \ typename.
Although typename and class in the template language have exactly the same meaning, you can use the difference in writing to simplify the understanding of the code - for example, use typename where not only complex, but also simple data types can be used as parameters (plain old data), and class - where extremely complex "adult" classes are expected.
Is that all?
In general, yes, that’s enough.
It is also desirable that the compiler complies with the C ++ 11 standard and is able to calculate the results of constant expressions containing simple functions at the compilation stage.
But to simplify the code, we need aliases for types. C ++ provides 2 mechanisms for calling something complicated something simple: typedef and using. The latter appeared in C ++ 11 and differs from typedef (which is a relic of C) with a more understandable syntax and template support:
// укажем, что "строки" — другое название вектора из строк
typedef std::vector Strings; // ок
using Strings = std::vector; // ок
// пример взят из Википедии
typedef void (*FunctionType)(double); // черт ногу сломит
using FunctionType = void (*)(double); // FunctionType — указатель на функцию, принимающую double, возвращающую void
// укажем, что куб — некая трехмерная матрица, содержащая значения типа T
template
typedef Matrix Cube; // ошибка компиляции
template
using Cube = Matrix; // ок Therefore, using is a more understandable and extended version of typedef. Know about typedef, but use using.
What is life
Game Life - a simulator of the life of cells on the field. There are many variations of the rules of Life, but we use the classic ones. A living cell dies of boredom if there are less than two neighbors, or starvation if there are more than three neighbors. In an empty cell, life begins only when there are strictly 3 living cells next to it, i.e. there are parents and an obstetrician.
Let us analyze the problem: for Life, cells are needed, the space on which they are located, a way to determine the next state of each cell, based on the number of its neighbors.
Therefore, templates in C ++ should allow: setting the initial field, selecting each cell in the field, determining its neighbors, counting their number, determining the future state, forming the next field and looping the algorithm a certain number of times. In addition, you must not forget about the conclusion of all iterations of the algorithm.
We give birth to life
In the beginning there was a cell:
struct O { }; // dead
struct X { }; // alive
And the binding of the cell type to the value:
template // базовый вид — неопределенная функция
constexpr bool is_alive();
template<> // специальный вид для типа О
constexpr bool is_alive()
{ return false; }
template<> // специальный вид для типа X
constexpr bool is_alive()
{ return true; } It should be clarified that the template language can only operate with data types and constant values that can be calculated at compile time.
The word "constexpr" tells the compiler that the function should be able to execute at the compilation stage. If it seems to the compiler that this cannot be provided for this function, it will throw an error.
Still here a new feature of the template language is discovered - specialization. This allows you to create special types of entities for specific parameters. In extreme cases, with full specialization, as in the example above, only angle brackets remain from the list of templates.
Specialization is the very opportunity that gives templates a way to exit recursion. About her - a little later.
Starting conditions
We will not reinvent the wheel and set the playing field using tuple from STL, game parameters - by constants:
using start = tuple<
O, O, O, O, O,
O, O, X, O, O,
O, O, O, X, O,
O, X, X, X, O,
O, O, O, O, O
>;
// параметры игры
const int width = 5;
const int height = 5;
const int iterations = 20;tuple - a data structure that can contain various types of data - a kind of heterogeneous array. We, in fact, will not store anything in it - we are only interested in the tuple type, which consists of the previously defined types O and X. It is important to understand that there are no values that get into the assembled program, we are only interested in the type and work we are only with type.
Recursive counting of living cells
Let's move on to magic. We remember that we need to count the living neighbors of the cell. Let the neighbors of types O and X already be in tuple and we know their number:
template
struct tuple_counter
{
constexpr static int value = is_alive::type>()
+ tuple_counter::value;
};
template // выход из рекурсии при указанном N = 0
struct tuple_counter
{
constexpr static int value = is_alive::type>();
}; What's going on here? Recursion! Let's take a closer look:
constexpr static int value = is_alive::type>() + // … we have already met constexpr - the value is guaranteed to be calculated at the compilation stage and is constant.
tuple_element
Why is there typename and :: type? type is the field of the tuple_element structure, which is a typedef alias of another type, and typename, roughly speaking, specifically tells the compiler that this is the name of the template type.
More about typename here .
… + tuple_counter::value; And here is the recursion itself. To calculate value, tuple_counter uses the value of the same tuple_counter, only with an iteration number 1 less. The exit from the recursion will occur when N becomes 0. The compiler will stumble upon the tuple_counter template specialized for N = 0, in which there is no recursion, and calculate the final value. Done.
All other calculations in the game, as well as the output of the result, are performed according to the same principle - recursively.
Determination of the next state of the cell
Well, suppose we counted living neighbors - how can we find out the next state of a cell based on this? Very simple if you do not reinvent the wheel and use conditional from STL:
template
struct calc_next_point_state
{
constexpr static int neighbor_cnt =
tuple_counter() - 1>::value;
using type =
typename conditional <
is_alive(),
typename conditional <
(neighbor_cnt > 3) || (neighbor_cnt < 2),
O,
X
>::type,
typename conditional <
(neighbor_cnt == 3),
X,
O
>::type
>::type;
}; conditional analogue of ternary operator X? Y: Z. If the condition in the first parameter is true, then the second parameter, otherwise the third. The rest of the code, I think, no longer needs explanation.
Playing field
Great - we have an initial playing field and a way to determine the next state for any cell on it. Make life easier and combine all the basic functions of Life in one place:
template
struct level
{
template // определить тип конкретной клетки
using point = typename tuple_element::type;
template // (занимает много места) определение типов соседей клетки
using neighbors = tuple< point< /*индекс соседа*/ >, ... >;
template // определение следующего типа клетки
using next_point_state = typename calc_next_point_state, neighbors>::type;
}; Try not to make mistakes when calculating the neighbor index - if you go beyond tuple, you will find about 56 obscure compilation errors, it depends on the size of the field and the number of iterations.
Calculation of the next field state
The further solution is obvious - we will go through all the cells, save the next state of each in an array, print the result, repeat for all iterations ... Array? We do not have an array. You can’t just take and insert individual values in tuple - we only work with types, and changing the type of an individual element in tuple is not possible.
What to do? Use tuple_cat - a language mechanism for combining several tuple into one. Unfortunately, tuple_cat takes on tuple values, and again, we are only interested in types. You can peek at the STL sources and find out how tuple_cat determines the type, invent your own tupleciped, or use the available language tools.
Fortunately, the decltype operator appeared in C ++ 11, which literally means “what type the function would return if we called it”. We apply it to tuple_cat and ... make sure that tuple_cat still accepts not the bare type “tuple” with which we operate everywhere, but the value of tuple. Fortunately, C ++ has a declval class that allows us to pretend that a value does exist, but it cannot be used anywhere else as a value. It's enough.
template
struct my_tuple_cat
{
// какой тип вернула бы tuple_cat, если бы мы вызвали ее с такими tuple, будь они у нас?
using result = decltype( tuple_cat( declval(), declval() ) );
}; Done! Now you can recursively collect all of the following states into a new state, adding cells one at a time:
template
struct next_field_state
{
template
using point = level::next_point_state;
using next_field = typename my_tuple_cat <
tuple< point >,
typename next_field_state::next_field
>::result;
};
template
struct next_field_state
{
template
using point = level::next_point_state;
using next_field = tuple< point >;
}; Strange point indexing is needed for the correct order of the result. Done. We calculated the next state of Life in a form in which it can be sent to the next cycle of calculations. It remains only to display the result.
Output result
The output functions do not carry any new knowledge, so I bring them under the spoiler.
Output functions
template
void print();
template<>
void print()
{ cout << "O"; }
template<>
void print()
{ cout << "X"; }
template
struct Printer {
static void print_tuple()
{
Printer::print_tuple();
if( N % width == 0 ) cout << endl;
print::type>();
}
};
template
struct Printer {
static void print_tuple()
{
print::type>();
}
};
template
struct game_process
{
static void print()
{
Printer< field, point_count - 1 >::print_tuple();
cout << endl << endl;
game_process< typename next_field_state::next_field, iters-1 >::print();
}
};
template
struct game_process
{
static void print()
{
Printer< field, point_count - 1 >::print_tuple();
cout << endl;
}
}; In conclusion
It remains to set the initial field, the number of iterations in the source, and breathe life into Life, which was completely determined even before its life began.
int main()
{
game_process< start, iterations >::print();
return 0;
}Having created Life, we proved to ourselves the usefulness of C ++ templates as a language, and also got a way to kill compilers that are too lazy to clean memory after recursive calls to template functions.
Life itself is a full-fledged language. So, in the game Life, it is theoretically possible to build a C ++ 11 compiler for Life source with a C ++ 11 compiler ... I leave this task to bored immortal readers for an independent solution.
The page of the working project on GitHub .
References: The C ++ Programming Language, 4th Edition .