Статья не о том, чем заняться, пока собирается проект.
Фраза «Шаблоны — полноценный, тьюринг-полный, язык» часто воспринимается с недоверием. Это же просто обобщающая возможность современных языков программирования, откуда там вычислительные возможности? Так думал и я. Теперь хочу переубедить остальных, попутно объясняя принципы работы шаблонов для начинающих, вроде меня.
Мое понимание шаблонов впервые пошатнулось после прочтения главы «Метапрограммирование» из книги о С++ от создателя С++ — показалось, что они действительно могут быть полноценным языком программирования внутри языка программирования. Во всяком случае, там точно есть рекурсия. Но лучший способ доказать себе что-то — попытаться сделать, что мы и сделаем.
Существует множество реализаций легендарной игры «Жизнь» Джона Конвея, безумных и не очень. Но все они имеют общий фатальный недостаток: каждая итерация Жизни вычисляется непосредственно во время работы программы. Попробуем это исправить.
Что такое шаблоны
Это механизм языка, который создает конкретные функциитипы данных за вас, позволяя писать обобщенные алгоритмы, структуры данных и тому подобное — программист сам подставит нужный параметр, и компилятор, по шаблону, создаст соответствующую сущность.
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 );
Компилятор создаст два независимых класса для параметров int и double, и одну функцию sum, принимающую и возвращающую величину типа double.
Поэтому шаблоны и называются шаблонами — вы создаете классфункцию, некоторые участки не заполняете, оставляете вместо пропусков метки, перечисляете названия этих меток перед описанием класса и все. Потом, при использовании шаблонной сущности, вписываете нужные параметры в угловых скобочках и компилятор подставит их в нужные участки кода.
«Не заполнить» можно тип переменной, указав перед названием пропущенного места classtypename, или некую величину, указав ее тип напрямую, вместо classtypename.
Хотя typename и class в языке шаблонов имеют абсолютно одно и то же значение, разницей в написании можно воспользоваться для упрощения понимания кода — к примеру, использовать typename там, где в качестве параметра могут оказаться не только сложные, но и простые типы данных (plain old data), а class — там, где ожидаются исключительно сложные «взрослые» классы.
И все?
В общем-то, да, этого достаточно.
Еще желательно, чтобы компилятор соответствовал стандарту С++11 и умел вычислять результаты константных выражений, содержащих простые функции, на этапе компиляции.
Но для упрощения кода нам понадобятся псевдонимы для типов. С++ предоставляет 2 механизма для обзывания чего-то сложного чем-то простым: typedef и using. Последний появился в С++11 и отличается от typedef'а (являющегося пережитком С) более понятным синтаксисом и поддержкой шаблонизации:
// укажем, что "строки" — другое название вектора из строк
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>; // ок Следовательно, using – более понятная и расширенная версия typedef. Знайте про typedef, но используйте using.
Что такое Жизнь
Игра Жизнь — симулятор жизни клеточек на поле. Существует много вариантов правил Жизни, но используем классические. Живая клеточка умирает от скуки, если соседей меньше двух, или голода, если соседей больше трех. В пустой клеточке зарождается жизнь только когда рядом с ней строго 3 живые клеточки, т.е. есть родители и акушер.
Проанализируем задачу: для Жизни нужны клеточки, пространство, на котором они находятся, способ определения следующего состояния каждой клеточки, на основании количества ее соседей.
Значит, шаблоны в С++ должны позволять: задание начального поля, выделение каждой клетки поля, определение ее соседей, подсчет их количества, определение будущего состояния, формирование следующего поля и зацикливание алгоритма на определенное количество раз. К тому же, нужно не забыть о выводе всех итераций алгоритма.
Зарождаем жизнь
В начале была клетка:
struct O { }; // dead
struct X { }; // alive
И привязка типа клетки к значению:
template <typename T> // базовый вид — неопределенная функция
constexpr bool is_alive();
template<> // специальный вид для типа О
constexpr bool is_alive<O>()
{ return false; }
template<> // специальный вид для типа X
constexpr bool is_alive<X>()
{ return true; }Стоит уточнить, что язык шаблонов может оперировать только типами данных и константными значениями, которые можно вычислить во время компиляции.
Слово «constexpr» указывает компилятору, что функция должна иметь возможность выполняться на этапе компиляции. Если компилятору покажется, что для этой функции такое обеспечить нельзя — он выдаст ошибку.
Еще тут обнаруживается новая возможность языка шаблонов — спецификация. Это позволяет создавать специальные виды сущностей для конкретных параметров. В крайнем случае, при полной спецификации, как в примере выше, от списка шаблонов остаются только угловые скобки.
Спецификация — та самая возможность, которая наделяет шаблоны способом выхода из рекурсии. О ней — чуть позже.
Стартовые условия
Не будем изобретать велосипед и зададим игровое поле с помощью tuple из STL, игровые параметры — константами:
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 – структура данных, которая может содержать различные типы данных — своеобразный гетерогенный массив. Хранить мы в ней, по сути, ничего не будем — нас интересует только тип tuple, состоящий из ранее заданных типов О и Х. Важно понять, что никаких значений, которые попадут в собранную программу, тут не существует, нас интересует только тип и работаем мы только с типом.
Рекурсивный подсчет живых клеток
Перейдем к магии. Мы помним, что нам нужно считать живых соседей клетки. Пусть соседи типов О и Х уже оказались в tuple и мы знаем их количество:
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>();
};Что тут происходит? Рекурсия! Посмотрим поближе:
constexpr static int value = is_alive<typename tuple_element<N, tuple>::type>() + // …
constexpr мы уже встречали — значение гарантированно вычисляется на этапе компиляции и является константным.
tuple_element<N, tuple> — очевидно, выделение N-го элемента из tuple, возможность, предоставленная в STL.
Зачем тут typename и ::type? type – поле структуры tuple_element, являющееся typedef-псевдонимом другого типа, а typename, грубо говоря, конкретно указывает компилятору, что это именно название шаблонизированного типа.
Более подробно о typename — тут.
… + tuple_counter<tuple, N-1>::value;А вот и сама рекурсия. Для вычисления value, в tuple_counter используется value такого же tuple_counter, только с номером итерации на 1 меньше. Выход из рекурсии произойдет, когда N станет равно 0. Компилятор наткнется на специфицированный для N = 0 шаблон tuple_counter, в котором рекурсии нет, и вычислит окончательное значение. Готово.
Все остальные вычисления в игре, а также вывод результата, выполняются по тому же принципу — рекурсивно.
Определение следующего состояния клетки
Хорошо, предположим, живых соседей мы посчитали — как на основании этого узнать следующее состояние клеточки? Очень просто, если не изобретать велосипед и использовать conditional из 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 – шаблонный аналог тернарного оператора X? Y: Z. Если условие в первом параметре истинно — то второй параметр, иначе — третий. Остальной код, думаю, в пояснениях уже не нуждается.
Игровое поле
Замечательно — у нас есть начальное игровое поле и способ определения следующего состояния для любой клеточки на нем. Облегчим себе жизнь и объединим все основные функции Жизни в одном месте:
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;
};Постарайтесь не совершать ошибок при вычислении индекса соседа — в случае выхода за пределы tuple, вас ждет около 56 малопонятных ошибок компиляции, зависит от размеров поля и количества итераций.
Вычисление следующего состояния поля
Дальнейшее решение очевидно — пройдемся по всем клеткам, сохраним следующее состояние каждой в массив, выведем результат, повторим для всех итераций… Массив? У нас нет массива. Нельзя просто взять и вставить отдельные значения в tuple – мы работаем только с типами, и измение типа отдельного элемента в tuple невозможно.
Что делать? Использовать tuple_cat – механизм языка для объединения нескольких tuple в одну. К сожалению, tuple_cat принимает значения tuple, а мы, опять же, интересуемся только типами. Можно подсмотреть исходники STL и узнать, как tuple_cat определяет тип, изобрести свой tupleсипед или использовать имеющиеся средства языка.
К счастью, в С++11 появился оператор decltype, который буквально означает «какой тип вернула бы функция, если бы мы ее вызвали». Применим его к tuple_cat и… убедимся, что tuple_cat все-таки принимает не голый тип «tuple», которым мы везде оперируем, а значение tuple. К счастью, в С++ имеется класс declval, который позволяет нам сделать вид, что значение все же существует, но его нельзя нигде использовать именно как значение. Этого достаточно.
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>() ) );
};Готово! Теперь можно рекурсивно собрать все следующие состояния в новое состояние, добавляя клетки по одной:
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> >;
};Странная индексация point нужна для правильного порядка результата. Готово. Мы посчитали следующее состояние Жизни в таком виде, в котором его можно отправить на следующий цикл вычислений. Осталось только вывести результат.
Вывод результата
Функции вывода никаких новых знаний не несут, поэтому привожу их под спойлером.
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;
}
};
В завершение
Остается задать в исходнике начальное поле, количество итераций и вдохнуть жизнь в Жизнь, полностью определенную еще до начала ее жизни.
int main()
{
game_process< start, iterations >::print();
return 0;
}Создав Жизнь, мы доказали сами себе полноценность шаблонов С++ как языка, а также получили способ убивать компиляторы, которые ленятся чистить память после рекурсивных вызовов шаблонных функций.
Жизнь — сама по себе полноценный язык. А значит, в игре Жизнь теоретически возможно построить компилятор С++11 для исходника Жизни с компилятором С++11… Оставляю эту задачу скучающим бессмертным читателям на самостоятельное решение.
Страничка работающего проекта на GitHub.
Использованная литература: The C++ Programming Language, 4th Edition.
Автор: HurrTheDurr
