Compile life
The article is not about what to do while the project is going.
The phrase “Patterns is a full-fledged, turing-complete, language” is often perceived with distrust. This is just a generalizing possibility of modern programming languages, where does the computational capability come from? I thought so too. Now I want to convince the rest, along the way explaining how templates work for beginners, like me.
My understanding of templates was first shaken after reading the chapter “Metaprogramming” from the book about C ++ from the creator of C ++ - it seemed that they could actually be a full-fledged programming language within the programming language. Anyway, there definitely is a recursion. But the best way to prove yourself is to try and do what we do.
')
There are many implementations of the legendary game "Life" of John Conway, insane and not. But they all have a common fatal flaw: each iteration of Life is calculated directly during the program operation. Let's try to fix it.
This is the mechanism of the language 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 will create the corresponding entity from the template.
The compiler will create two independent classes for the parameters int and double, and one function sum that will accept and return a double value.
Therefore, templates are called templates — you create a class / function, do not fill in some parts, leave labels instead of omissions, list the names of these labels before describing the class, and that's it. Then, when using the template entity, enter the necessary parameters in the corner brackets and the compiler will substitute them into the necessary parts of the code.
"Do not fill in" you can type the variable by specifying before the name of the missing place class \ typename, or some value, indicating its type directly, instead of class \ typename.
Although the typename and class in the template language have exactly the same meaning, the difference in spelling can be used to simplify the understanding of the code — for example, you can use the typename where as a parameter can be not only complex, but also simple data types (plain old data), and class - where extremely complex “adult” classes are expected.
In general, yes, that is 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 with something simple: typedef and using. The latter appeared in C ++ 11 and differs from typedef (which is a remnant of C) with a more understandable syntax and support for templating:
Consequently, using is a more understandable and extended version of typedef. Know about typedef, but use using.
Game Life is a life simulator of cells on the field. There are many variants of the rules of Life, but we use the classic ones. The living cell dies of boredom, if there are less than two neighbors, or hunger, if there are more than three neighbors. In an empty cell, life arises only when there are strictly 3 living cells next to it, i.e. have parents and an obstetrician.
Let us analyze the problem: for Life, cells are needed, the space on which they are located, the way to determine the next state of each cell, based on the number of its neighbors.
This means that the templates in C ++ should allow: setting the initial field, selecting each cell of a 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 need not forget about the output of all iterations of the algorithm.
In the beginning was the cell:
And the binding of the cell type to the value:
It should be clarified that the template language can operate only with data types and constant values that can be calculated at compile time.
The word "constexpr" indicates to the compiler that the function should be able to be executed at the compilation stage. If the compiler seems to be unable to provide this for this function, it will generate an error.
Still here a new feature of the template language is found - specialization. This allows you to create special kinds of entities for specific parameters. In the extreme case, with full specialization, as in the example above, only angle brackets remain from the list of templates.
Specialization is the same opportunity that gives patterns a way out of recursion. About her - a little later.
We will not reinvent the wheel and set the playing field using the tuple from STL, the game parameters - by constants:
tuple - a data structure that can contain various types of data - a kind of heterogeneous array. We will not store anything in it - we are only interested in the tuple type, consisting of the previously defined types O and X. It is important to understand that there are no values that fall into the assembled program, we are only interested in the type and work we are only with type.
We turn to magic. We remember that we need to count the living neighbors of the cell. Let the neighbors of types O and X have already appeared in the tuple and we know their number:
What's going on here? Recursion! Let's take a closer look:
constexpr we have already met - the value is guaranteed to be calculated at the compilation stage and is constant.
tuple_element <N, tuple> - obviously, the selection of the Nth element from the tuple, an option provided in STL.
Why are there typename and :: type? type - a tuple_element structure field, which is a typedef-alias of another type, and typename, roughly speaking, specifically indicates to the compiler that this is exactly the name of the template type.
For more information about typename - here .
And here is the recursion itself. To calculate the value, in the tuple_counter, the value of the same tuple_counter is used, only with the iteration number 1 less. The exit from recursion will occur when N becomes equal to 0. The compiler will come across the tuple_counter pattern specialized for N = 0, in which there is no recursion, and calculate the final value. Is done.
All other calculations in the game, as well as the output of the result, are performed on the same principle - recursively.
Well, suppose we have considered living neighbors - how can we know from this the next state of the cell? It’s very simple if you don’t reinvent the wheel and use conditional from STL:
conditional - a template analogue of the 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 explanations.
Great - we have an initial playing field and a way to determine the next state for any cell on it. Let us ease our life and combine all the main functions of Life in one place:
Try not to make mistakes when calculating the neighbor's index - in case of going beyond the tuple, you will get about 56 incomprehensible compilation errors, depending on the size of the field and the number of iterations.
The further solution is obvious - let's go through all the cells, save the next state of each into an array, display the result, repeat for all iterations ... Array? We do not have an array. It is impossible to simply take and insert individual values in a tuple - we work only with types, and changing the type of an individual element in a tuple is impossible.
What to do? Use tuple_cat - a language mechanism for combining several tuples into one. Unfortunately, tuple_cat accepts tuple values, and we, again, are only interested in types. You can follow the STL sources and find out how tuple_cat determines the type, invent your own tuplesiped, or use existing language tools.
Fortunately, the decltype operator appeared in C ++ 11, which literally means “what type would the function return if we called it”. 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 tuple. Fortunately, in C ++ there is a declval class that allows us to pretend that the value does exist, but it cannot be used anywhere as a value. It's enough.
Done! Now you can recursively collect all the following states in a new state by adding cells one by one:
Strange point indexing is needed for the correct order of the result. Is done. We considered the next state of Life in such 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 cite them under the spoiler.
It remains to set the initial field in the source code, the number of iterations and breathe life into life, fully defined before the beginning of its life.
By creating Life, we proved to ourselves the usefulness of C ++ templates as a language, and also got a way to kill compilers who are too lazy to clean memory after recursive calls to template functions.
Life is in itself a full-fledged language. So, in the game Life, it is theoretically possible to build a C ++ 11 compiler for the source of Life with a C ++ 11 compiler ... I leave this task to bored immortal readers for an independent decision.
The page of the working project on GitHub .
References: The C ++ Programming Language, 4th Edition .
The phrase “Patterns is a full-fledged, turing-complete, language” is often perceived with distrust. This is just a generalizing possibility of modern programming languages, where does the computational capability come from? I thought so too. Now I want to convince the rest, along the way explaining how templates work for beginners, like me.
My understanding of templates was first shaken after reading the chapter “Metaprogramming” from the book about C ++ from the creator of C ++ - it seemed that they could actually be a full-fledged programming language within the programming language. Anyway, there definitely is a recursion. But the best way to prove yourself is to try and do what we do.
')
There are many implementations of the legendary game "Life" of John Conway, insane and not. But they all have a common fatal flaw: each iteration of Life is calculated directly during the program operation. Let's try to fix it.
What are templates?
This is the mechanism of the language 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 will create the corresponding entity from the template.
template <typename T> class SomeClass { T i; }; template <class T> // class — , typename! T sum( T a, T b ) { return a + b; } SomeClass<int> obj_1; SomeClass<double> obj_1; double i = sum<double>( 3.14, 15.9 ); The compiler will create two independent classes for the parameters int and double, and one function sum that will accept and return a double value.
Therefore, templates are called templates — you create a class / function, do not fill in some parts, leave labels instead of omissions, list the names of these labels before describing the class, and that's it. Then, when using the template entity, enter the necessary parameters in the corner brackets and the compiler will substitute them into the necessary parts of the code.
"Do not fill in" you can type the variable by specifying before the name of the missing place class \ typename, or some value, indicating its type directly, instead of class \ typename.
Although the typename and class in the template language have exactly the same meaning, the difference in spelling can be used to simplify the understanding of the code — for example, you can use the typename where as a parameter can be not only complex, but also simple data types (plain old data), and class - where extremely complex “adult” classes are expected.
And all?
In general, yes, that is 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 with something simple: typedef and using. The latter appeared in C ++ 11 and differs from typedef (which is a remnant of C) with a more understandable syntax and support for templating:
// , "" — typedef std::vector<string> Strings; // using Strings = std::vector<string>; // // typedef void (*FunctionType)(double); // using FunctionType = void (*)(double); // FunctionType — , double, void // , — , T template <typename T> typedef Matrix<T, 3> Cube<T>; // template <typename T> using Cube = Matrix<T, 3>; // Consequently, using is a more understandable and extended version of typedef. Know about typedef, but use using.
What is life
Game Life is a life simulator of cells on the field. There are many variants of the rules of Life, but we use the classic ones. The living cell dies of boredom, if there are less than two neighbors, or hunger, if there are more than three neighbors. In an empty cell, life arises only when there are strictly 3 living cells next to it, i.e. have parents and an obstetrician.
Let us analyze the problem: for Life, cells are needed, the space on which they are located, the way to determine the next state of each cell, based on the number of its neighbors.
This means that the templates in C ++ should allow: setting the initial field, selecting each cell of a 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 need not forget about the output of all iterations of the algorithm.
Birth life
In the beginning was the cell:
struct O { }; // dead struct X { }; // alive And the binding of the cell type to the value:
template <typename T> // — constexpr bool is_alive(); template<> // constexpr bool is_alive<O>() { return false; } template<> // X constexpr bool is_alive<X>() { return true; } It should be clarified that the template language can operate only with data types and constant values that can be calculated at compile time.
The word "constexpr" indicates to the compiler that the function should be able to be executed at the compilation stage. If the compiler seems to be unable to provide this for this function, it will generate an error.
Still here a new feature of the template language is found - specialization. This allows you to create special kinds of entities for specific parameters. In the extreme case, with full specialization, as in the example above, only angle brackets remain from the list of templates.
Specialization is the same opportunity that gives patterns a way out of recursion. About her - a little later.
Starting conditions
We will not reinvent the wheel and set the playing field using the tuple from STL, the 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 will not store anything in it - we are only interested in the tuple type, consisting of the previously defined types O and X. It is important to understand that there are no values that fall into the assembled program, we are only interested in the type and work we are only with type.
Recursive counting of living cells
We turn to magic. We remember that we need to count the living neighbors of the cell. Let the neighbors of types O and X have already appeared in the tuple and we know their number:
template <typename tuple, int N> struct tuple_counter { constexpr static int value = is_alive<typename tuple_element<N, tuple>::type>() + tuple_counter<tuple, N-1>::value; }; template <typename tuple> // N = 0 struct tuple_counter<tuple, 0> { constexpr static int value = is_alive<typename tuple_element<0, tuple>::type>(); }; What's going on here? Recursion! Let's take a closer look:
constexpr static int value = is_alive<typename tuple_element<N, tuple>::type>() + // … constexpr we have already met - the value is guaranteed to be calculated at the compilation stage and is constant.
tuple_element <N, tuple> - obviously, the selection of the Nth element from the tuple, an option provided in STL.
Why are there typename and :: type? type - a tuple_element structure field, which is a typedef-alias of another type, and typename, roughly speaking, specifically indicates to the compiler that this is exactly the name of the template type.
For more information about typename - here .
… + tuple_counter<tuple, N-1>::value; And here is the recursion itself. To calculate the value, in the tuple_counter, the value of the same tuple_counter is used, only with the iteration number 1 less. The exit from recursion will occur when N becomes equal to 0. The compiler will come across the tuple_counter pattern specialized for N = 0, in which there is no recursion, and calculate the final value. Is done.
All other calculations in the game, as well as the output of the result, are performed on the same principle - recursively.
Determining the next state of the cell
Well, suppose we have considered living neighbors - how can we know from this the next state of the cell? It’s very simple if you don’t reinvent the wheel and use conditional from STL:
template <typename point, typename neighbors> struct calc_next_point_state { constexpr static int neighbor_cnt = tuple_counter<neighbors, tuple_size<neighbors>() - 1>::value; using type = typename conditional < is_alive<point>(), typename conditional < (neighbor_cnt > 3) || (neighbor_cnt < 2), O, X >::type, typename conditional < (neighbor_cnt == 3), X, O >::type >::type; }; conditional - a template analogue of the 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 explanations.
Playing field
Great - we have an initial playing field and a way to determine the next state for any cell on it. Let us ease our life and combine all the main functions of Life in one place:
template <typename initial_state> struct level { template <int N> // using point = typename tuple_element<N, initial_state>::type; template <int N> // ( ) using neighbors = tuple< point< /* */ >, ... >; template <int N> // using next_point_state = typename calc_next_point_state<point<N>, neighbors<N>>::type; }; Try not to make mistakes when calculating the neighbor's index - in case of going beyond the tuple, you will get about 56 incomprehensible compilation errors, depending on the size of the field and the number of iterations.
Calculating the next field state
The further solution is obvious - let's go through all the cells, save the next state of each into an array, display the result, repeat for all iterations ... Array? We do not have an array. It is impossible to simply take and insert individual values in a tuple - we work only with types, and changing the type of an individual element in a tuple is impossible.
What to do? Use tuple_cat - a language mechanism for combining several tuples into one. Unfortunately, tuple_cat accepts tuple values, and we, again, are only interested in types. You can follow the STL sources and find out how tuple_cat determines the type, invent your own tuplesiped, or use existing language tools.
Fortunately, the decltype operator appeared in C ++ 11, which literally means “what type would the function return if we called it”. 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 tuple. Fortunately, in C ++ there is a declval class that allows us to pretend that the value does exist, but it cannot be used anywhere as a value. It's enough.
template <typename tuple_1, typename tuple_2> struct my_tuple_cat { // tuple_cat, tuple, ? using result = decltype( tuple_cat( declval<tuple_1>(), declval<tuple_2>() ) ); }; Done! Now you can recursively collect all the following states in a new state by adding cells one by one:
template <typename field, int iter> struct next_field_state { template<int N> using point = level<field>::next_point_state<N>; using next_field = typename my_tuple_cat < tuple< point<point_count - iter> >, typename next_field_state<field, iter-1>::next_field >::result; }; template <typename field> struct next_field_state<field, 1> { template<int N> using point = level<field>::next_point_state<N>; using next_field = tuple< point<point_count - 1> >; }; Strange point indexing is needed for the correct order of the result. Is done. We considered the next state of Life in such a form in which it can be sent to the next cycle of calculations. It remains only to display the result.
Output
The output functions do not carry any new knowledge, so I cite them under the spoiler.
Output functions
template <typename Type> void print(); template<> void print<O>() { cout << "O"; } template<> void print<X>() { cout << "X"; } template <typename tuple, int N> struct Printer { static void print_tuple() { Printer<tuple, N-1>::print_tuple(); if( N % width == 0 ) cout << endl; print<typename tuple_element<N, tuple>::type>(); } }; template <typename tuple> struct Printer<tuple, 0> { static void print_tuple() { print<typename tuple_element<0, tuple>::type>(); } }; template <typename field, int iters> struct game_process { static void print() { Printer< field, point_count - 1 >::print_tuple(); cout << endl << endl; game_process< typename next_field_state<field, point_count>::next_field, iters-1 >::print(); } }; template <typename field> struct game_process<field, 0> { static void print() { Printer< field, point_count - 1 >::print_tuple(); cout << endl; } }; In conclusion
It remains to set the initial field in the source code, the number of iterations and breathe life into life, fully defined before the beginning of its life.
int main() { game_process< start, iterations >::print(); return 0; } By creating Life, we proved to ourselves the usefulness of C ++ templates as a language, and also got a way to kill compilers who are too lazy to clean memory after recursive calls to template functions.
Life is in itself a full-fledged language. So, in the game Life, it is theoretically possible to build a C ++ 11 compiler for the source of Life with a C ++ 11 compiler ... I leave this task to bored immortal readers for an independent decision.
The page of the working project on GitHub .
References: The C ++ Programming Language, 4th Edition .
Source: https://habr.com/ru/post/218229/
All Articles