4 апреля 2014 в 11:38

Жизнь во время компиляции из песочницы

Статья не о том, чем заняться, пока собирается проект.

Фраза «Шаблоны — полноценный, тьюринг-полный, язык» часто воспринимается с недоверием. Это же просто обобщающая возможность современных языков программирования, откуда там вычислительные возможности? Так думал и я. Теперь хочу переубедить остальных, попутно объясняя принципы работы шаблонов для начинающих, вроде меня.

Мое понимание шаблонов впервые пошатнулось после прочтения главы «Метапрограммирование» из книги о С++ от создателя С++ — показалось, что они действительно могут быть полноценным языком программирования внутри языка программирования. Во всяком случае, там точно есть рекурсия. Но лучший способ доказать себе что-то — попытаться сделать, что мы и сделаем.

Существует множество реализаций легендарной игры «Жизнь» Джона Конвея, безумных и не очень. Но все они имеют общий фатальный недостаток: каждая итерация Жизни вычисляется непосредственно во время работы программы. Попробуем это исправить.

Что такое шаблоны


Это механизм языка, который создает конкретные функции\типы данных за вас, позволяя писать обобщенные алгоритмы, структуры данных и тому подобное — программист сам подставит нужный параметр, и компилятор, по шаблону, создаст соответствующую сущность.

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.
Поэтому шаблоны и называются шаблонами — вы создаете класс\функцию, некоторые участки не заполняете, оставляете вместо пропусков метки, перечисляете названия этих меток перед описанием класса и все. Потом, при использовании шаблонной сущности, вписываете нужные параметры в угловых скобочках и компилятор подставит их в нужные участки кода.

«Не заполнить» можно тип переменной, указав перед названием пропущенного места class\typename, или некую величину, указав ее тип напрямую, вместо class\typename.

Хотя 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
карма
62,0
рейтинг 0,2
Похожие публикации
Самое читаемое Разработка

Комментарии (35)

  • +24
    Слишком быстро компилируется программа и нету времени почитать хабр?
    Добавь в исходники жизни.
    • 0
      А потом можно даже заставить её эволюционировать средствами компилятора, а точнее оптимизатора, особо хорошо это получается у компилятора Intel, тогда времени будет ещё больше :)
      • +2
        Программисты С++ — самые читающие программисты в мире! )
        • 0
          Самые чиТающие :-)
        • 0
          И свободного времени всегда гораздо больше, агу :)

          xkcd.ru/i/303_v1.png
  • +3
    Создав Жизнь, мы доказали сами себе полноценность шаблонов С++ как языка

    Звучит классно :)

    Собственно говоря, никто не сомневается в полноте по Тьюрингу шаблонов С++ и возможности написать на них хоть чёрта лысого. Беда в том, что код получается сложным и трудно поддерживаемым (взять хотя бы отладку). Нет практического коммерческого профита писать на них что-то сложнее разных разновидностей контейнеров и пары паттернов из числа классических.
    • 0
      Собственно говоря, никто не сомневается в полноте по Тьюрингу шаблонов С++ и возможности написать на них хоть чёрта лысого.
      Я вроде бы написал на них рекурсивную функцию вычисления факториала, но порядок раскрытия и редукции шаблонов не позволяет вычислить результат её применения :(

      Ну, хотя да. Шаблоны настолько круты, что на них можно выразить даже бесконечный цикл.
      • 0
        Закостылил рекурсию, теперь всё считает. Факториал шести — за 10 секунд. Факториал семи — падает с переполнением стека. Пойду дописывать статью.
        • 0
          Извините, возможно, я что-то не так понял, но что сложного в факториале на шаблонах С++?

          template <int N>
          struct fact {
              static const int value = N * fact<N-1>::value;
          };
          
          template <>
          struct fact<1> {
              static const int value = 1;
          };
          
          int fact_5 = fact<5>::value; // = 120
          
          • 0
            Я более извращён. Там именно что функция, вычисляющая факториал. И интерпретатор (времени компиляции), который вычисляет результат применения этой функции.
    • 0
      Я где-то видел примеры статически конфигурируемых связей listener'ов на этапе компиляции.
      Вот это было круто — все само связывается, и на этапе компиляции проверяет, что все связи действительно есть.
      :-)
      Жаль, не могу указать источник.
  • +19
    С каждым новым релизом количество способов нетривиально вывихнуть себе мозг при помощи С++ продолжает увеличиваться)
    • +3
      Жизнь на шаблонах можно написать и с использованием предыдущих стандартов С++, но как раз это сделало бы код более мозговывихивающим :)
      Особенно, если не менять подход к реализации игрового поля и продолжать пытаться все вычисления выполнять не над константами, а над типами.
    • +2
      Хотите решить головоломку?
      Напишите компилятор C++ на шаблонах C++. :-)
  • +10
    Дык используйте boost::spirit, вам обеспечены долгие часы чтения хабра :-D
  • +4
    >Еще тут обнаруживается новая возможность языка шаблонов — спецификация
    Не спецификация, а специализация.
    • +1
      Я жажду слышать аргументы того, кто минусанул комментарий.
  • +5
    Как же, помню… Через тернии темлейтного метапрограммирования, boost, интервальная арифметика и символьное дифференцирование, сообщения об ошибках на 40 страниц, потом попытки реализовать доморощенный reflection и прочие плюшки для C++ на основе gccxml (это были ~2002-2003 годы)… Желание управлять процессом компиляции… Потом Scheme, hygienic macros… Мой долгий путь к Common Lisp'у. Здравствуй, defmacro :)
    • +1
      Очень красивый и емкий язык, для работы с которым нужно перевернуть мышление.
      :-)
      Вот закончу разбираться с 3D-графикой, и перейду на темную сторону силы — практиковаться в Lisp или Closure.
  • +4
    мсьє знает толк в извращениях :)
    плюсанул
  • 0
    Для дальнейших извращений рекомендую А.Александреску «Modern C++ Design», а если этого будет мало, то можно обратить взор на D (в который и ушел автор этой книги), в нем не проблема сделать compile-time raytracer, да и скорость компиляции на порядок выше C++.
    • 0
      Эти идеи отлично применяются на практике. Например, NS-3 симулятор сети, который активно используется в научных исследованиях, сделан с использованием многих идей из этой книги. Там, например, Garbage Collector реализован через метапрограммирование в С++.
  • –1
    А вот замедлить вывод на экран не сможите.
    • 0
      Вывод на экран выполняется обычным cout, если после него вставить задержку — вывод можно будет замедлить. Но зачем?
      • 0
        Ну я эт к тому что шаблоны не всемогущи :) Хотя как то глупо получилось :(
  • –3
    Есть тьюринг-полные языки, а есть тьюринг-полный-пиз.ец языки.
    • +2
      Ну зачем же так грубо? Это обычная Тьюринговская трясина.
      • +2
        Это лингвистическая конструкция вокруг слова «полный».
  • +1
    К счастью, в С++11 появился оператор decltype, который буквально означает «какой тип вернула бы функция, если бы мы ее вызвали». Применим его к tuple_cat и… убедимся, что tuple_cat все-таки принимает не голый тип «tuple», которым мы везде оперируем, а значение tuple. К счастью, в С++ имеется класс declval, который позволяет нам сделать вид, что значение все же существует, но его нельзя нигде использовать именно как значение. Этого достаточно.

    Вот за это я и люблю С++. Чтобы костыль не падал, подопрем его другим, побольше, чтоб тот поддержал первый :D

    И все же генерики шарпа мне нравятся больше. Да, нету возможности писать a + b и затем подставлять любые типы, но это же является и плюсом — строгая типизация, можно явно указать, что ожидается на вход функции, а ошибка имеет достаточно понятное описание, а темплейт-ошибка всегдав мне напоминает «выр-выр-выр» из Темного Рыцаря.

    Но статья очень интересная, спасибо. Плюсанул.
  • +4
    А в openttd на поездах и семафорах счетчики и цифровые индикаторы реализовать можно…
  • +2
    Скажите, у меня одного clang 3.4 не может скомпилировать исходник? Только gcc справляется…
  • +2
    Как меня расстроила первая строка =(
  • 0
    А вот меня лично интересует другие два вопроса — сколько весит бинарник, и сколько памяти в runtime жрет все это дело :-)
    :-)

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.