- PVSM.RU - https://www.pvsm.ru -
"- После Мятежа Галактическое Содружество наложило строгие ограничения на метафункции высшего порядка. И не только из соображений этики; их власти опасаются вообще всякого проявления мании величия..."
(из поисковой выдачи google)
Предлагаю Вам сыграть в крестики-нолики с компилятором. Для игры знания c++ не потребуются, достаточно наличия cmake, python и собственно компилятора c++ ( потянет даже такой древний как gcc-3.3 ). Python используется только для ввода данных пользователя, запуска компилятора после каждого хода, и скомпилированной программы для получения результата. Все вычисления (следующий ход, определение победителя или констатации ничьей) производятся на этапе компиляции, в run-time только вывод результата.
Для тех, у кого возникнет желание разобраться, как это работает: будет все по-честному, никаких хитрых трюков, хаков и генерации кода скриптом (ну почти). На выходе скрипта два файла, один с исходной позицией — это строка вида e,x,e,o,e,e,e,e,x, где e — пустое поле, а во втором файле число 0,1 или 2 — это уровень сложности. Будет 3 уровня сложности, и ходы компилятора будут случайны в зависимости от этого уровня. Также научим компилятор играть с самим собой на разных уровнях сложности.
Кода будет немного — воспользуемся тем, что уже реализовано в библиотеке faslib [1]. Эта библиотека разработана для реализации aспектно-ориентированных концепций с использованием шаблонов на базе списков типов. Темы АОП, в этот раз касаться не будем, а воспользуемся пакетами для работы со списками типов и мета-алгоритмами.
Для того, чтобы сыграть, загружаем проект с github (faslib подключена как субмодуль):
git clone https://github.com/migashko/tictactoe.git
cd tictactoe/
git submodule init
git submodule update
Убеждаемся, что cmake и c++ доступны, и запускаем игру:
./tictactoe.py
При первом запуске скрипт сам создаст директорию сборки и запустит cmake. Если что-то пошло не так, делаем это вручную:
mkdir build
cd ./build
cmake ..
make tictactoe
Level [0,1,2]: 2
Figure [X,x,1,O,o,0]: o
compiling...
- - -
- X -
- - -
Move [0..8, a1..c3]: a2
compiling...
- O -
- X -
X - -
Move [0..8, a1..c3]: a3
compiling...
X O O
- X -
X - -
Move [0..8, a1..c3]: b2
BUSSY
Move [0..8, a1..c3]: b1
compiling...
X O O
O X -
X - X
X winner (compiler)
Скрипт в начале игры записывает в файл level.inl число, введенное пользователем, которое задает уровень сложности, а после каждого хода в файл board.inl новую расстановку фигур (крестиков или ноликов), анализируя которую, компилятор делает ход. Эти действия можно сделать вручную, запустить компилятор и посмотреть результат. В качестве примера запишите в level.inl второй уровень сложности:
echo 2 > level.inl
а в board.inl задайте исходные позиции с помощью текстового редактора (можно вставлять переносы строк):
e,e,e,
x,o,e,
e,e,e
или так:
echo "e,e,e,x,o,e,e,e,e" > board.inl
перейдите в build и запустите make, затем ./tictactoe.
$> make
$> ./tictactoe
- - -
X O -
- - X
$> make
$> ./tictactoe
- - X
X O -
- - -
$> make
$> ./tictactoe
X - -
X O -
- - -
Помимо tictactoe, есть программа tictactoe_its, которая проигрывает партию до конца (также на этапе компиляции). Для исходного расположения фигур используется board.inl. Если нужно проиграть партию с начала, то просто удалите этот файл.
$> ./tictactoe_its
- - -
X O -
- - -
X - -
X O -
- - -
X - -
X O -
O - -
X - X
X O -
O - -
X O X
X O -
O - -
X O X
X O -
O X -
Draw
Алгоритм, который использует компилятор, не идеален, поэтому для данного расположения даже для второго уровня сложности не гарантируется ничейная смерть.
Беспроигрышный алгоритм:
В текущей реализации, на втором уровне сложности, компилятор игнорирует пункты 3 и 5. Если вы сами будете следовать этому алгоритму, даже с учетом пунктов 3 и 5, то компилятор сведет игру к ничьей. На первом уровне не учитывается четвертый пункт, а на самом простом, нулевом, шестой.
Чтобы получить шанс выиграть у компилятора на втором уровне сложности, нужно сделать первый ход в самую “неправильную” позицию — в боковую клетку. Ход компилятора ноликами будет в центр. Ваш следующий ход должен быть в один из противоположных углов, относительно вашего первого хода. Компилятор, следуя алгоритму, сделает ход в любой из свободных углов, и, если он выберет угол не рядом с вашим первым ходом, то вы гарантированно можете поставить вилку и выиграть.
e> ./tictactoe.py
Level [0,1,2]: 2
Figure [X,x,1,O,o,0]: x
Move [0..8, a1..c3]: b1
compiling…
- - -
X O -
- - -
Move [0..8, a1..c3]: c3
compiling...
- - O
X O -
- - X
Move [0..8, a1..c3]: c1
compiling...
- - O
X O -
X O X
Move [0..8, a1..c3]: a1
compiling...
X - O
X O -
X O X
X winner (you)
На этом игры заканчиваем и приступаем к самому интересному. Далее вам потребуются неплохие знания C++, особенно всего того, что касается шаблонов. В начале я дам краткий обзор faslib (только те пакеты, которые нам потребуются для реализации игры), далее научим компилятор делать один ход, выявлять победителя и определять ничью. И, наконец, научим его играть всю партию с самим собой.
Ориентироваться в библиотеке просто — каждая конструкция (даже самая простая) в отдельном файле. Достаточно просмотреть список файлов, чтобы определить доступный функционал. faslib — это мета-библиотека, run-time кода там практически нет, поэтому под функциями и алгоритмами будем понимать мета-функции и мета-алгоритмы.
На дизайн faslib оказали влияние несколько библиотек. Списки типов (fas/type_list [2]), а также всевозможные операции над типами (fas/typemanip [3]) — это, разумеется, Loki [4]. Многие конструкции из typemanip могут быть заменены аналогами <type_traits> в c++11. Идеи для пакета fas/mp [5] (placeholder expressions и лямбда мета-функции) и fas/integral [6](обертки над интегральными типами и операции над ними) взяты из boost::mpl. Интерфейсы для мета-алгоритмов [7] я постарался сделать похожими на алгоритмы STL.
Начнем с интегральных типов. При работе с шаблонами не всегда удобно использовать числа, для этих целей удобнее специальные обёртки, например:
typedef fas::int_<2> level;
Определение этой конструкции, а также для других интегральных типов в пакете fas/integral. Там же можно найти и базовые операции, например, сложения:
std::cout << fas::int_<1>::value << std::endl; // 1
std::cout << fas::plus< fas::int_<1>, fas::int_<2> >::value
<< std::endl; // 3
Пример, как найти наименьшее общее кратное на этапе компиляции, можно изучить здесь [8].
В пакете fas/typemanip набор конструкций для работы с различными типами данных. Нам потребуются same_type для определения того, совпадают ли два типа:
std::cout << fas::same_type<int, long>::value; // 0
std::cout << fas::same_type<int, int>::value; // 1
Пары и кортежи типов и функции получения типа из определенной позиции:
typedef fas::pair< fas::int_<1>, fas::int_<2> > pair;
typedef fas::tuple< fas::int_<3>, fas::int_<4>, fas::int_<5> > tuple;
std::cout << fas::first<pair>::type::value << std::endl; // 1
std::cout << fas::second<tuple>::type::value << std::endl; // 4
std::cout << fas::third<tuple>::type::value << std::endl; // 5
Кортеж может принимать до пяти типов. Если нужно больше, то удобнее использовать списки типов. Функции для получения четвертого и пятого типов: fourth и fifth.
Условные операции:
std::cout <<
fas::if_<
fas::true_,
fas::int_<42>,
fas::int_<24>
>::type::value
<< std::endl; // 42
std::cout <<
fas::switch_<
fas::case_< fas::false_, fas::int_<24> >,
fas::case_c< 1, fas::int_<42> >,
fas::default_< fas::int_<44> >
>::type::value
<< std::endl; // 42
Списки типов. Не буду подробно описывать концепцию, укажу лишь особенности реализации. Итак, базовые конструкции:
struct empty_list
{
typedef metalist::empty_list metatype;
};
template< typename L, typename R = empty_list >
struct type_list
{
typedef metalist::type_list metatype;
typedef L left_type;
typedef R right_type;
};
Список из четырех типов:
typedef fas::type_list<A,
fas::type_list<B,
fas::type_list<C,
fas::type_list<D
> > > > list_abcd; // [A,B,C,D,empty_list]
Неправильный список:
typedef fas::type_list<A, B > list2_ab_invalid;
В faslib, в отличии от Loki, список типов всегда должен оканчиваться типом fas::empty_list. Если это правило не соблюдается, то такой список называется неорганизованным. Исправить ситуацию поможет функция fas::organize, например вот так:
typedef fas::type_list< A, B > list_ab_invalid; // [A,B]
typedef fas::type_list< C, D > list_cd_invalid; // [C,D]
typedef fas::type_list< list_ab_invalid, list_cd_invalid> list_abcd_invalid; // [[C,D],[C,D]]
typedef fas::organize<list2_abcd_invalid>::type list_abcd; // [A,B,C,D,empty_list]
Искренне не понимаю, почему Александреску и последователи используют #define для формирования списка типов, можно гораздо элегантнее, например:
typedef fas::type_list_n<A,B,C>::type list; // [A,B,C,empty_list]
До c++11 type_list_n принимает до 26 параметров, после не ограничено (variadic templates).
typedef fas::type_list_n<
fas::type_list_n<A,B>::type, // [A,B,empty_list]
fas::type_list_n<C,D>::type // [C,D,empty_list]
>::type list; // [A,B,C,D,empty_list]
Следующая замечательная особенность списков типов в faslib — это возможность их экранирования структурами, например, так:
struct list_bc: fas::type_list<B, fas::type_list<C> > {}; // [B,C,empty_list]
struct list_abc: fas::type_list<B, list_bc > {}; // [A,list_bc]
Все операции и алгоритмы, работающие со списками типов, разработаны так, чтобы детектировать экранирование и, по возможности, не перестраивать их. Поясню на примере объединения списков:
typedef fas::merge<
list_bc, // [B,C,empty_list]
list_abc // [A,list_bc]
>::type list; // [B,C,A,list_bc]
Тривиальная реализация этой операции перестроила бы список в [B,C,A,B,C,empty_list]. Реализация в faslib не намного сложнее, но и реального профита она не дает в плане оптимизации времени компиляции и практического уменьшения лога в случае ошибок при экранировании хвоста списка. Но сама возможность экранирования может быть полезна для формирования списка, например, так:
template<int A, int B, int C>
struct list123: fas::type_list_n<
fas::int_<A>, fas::int_<B>, fas::int_<C>
>::type {};
Кроме того, экранированный список при передаче в качестве шаблонного параметра какому-либо классу позволяет сделать более читабельным лог ошибок:
#include <fas/integral.hpp>
#include <fas/type_list.hpp>
typedef fas::type_list_n<
fas::int_<1>, fas::int_<2> , fas::int_<2>
>::type list1;
struct list2: list1 {};
template<typename L>
class test {};
int main()
{
// test<list2> tst;
test<list1> tst;
tst.doit();
}
В этом варианте компилятор выдаст что-то типа этого:
error: ‘class test<fas::type_list<fas::int_<1>, fas::type_list<fas::int_<2>, fas::type_list<fas::int_<2>, fas::empty_list> > > >’ has no member named ‘doit’
а для list2:
error: ‘class test<list2>’ has no member named ‘doit’
Вы почувствуете разницу, если в списке с десяток или больше элементов. Итак, раскроем тайну, как работает экранирование, на примере определения функции определяющей длину списка. Реализация без учета экранирования:
template<typename L, typename R>
struct length;
template<typename L, typename R>
struct length< type_list<L, R> >
{
enum { value = 1 + length<R>::value };
};
template<>
struct length< empty_list >
{
enum { value = 0 };
};
Если на вход функции length, в этой реализации, придет экранированный список, то получим ошибку на этапе компиляции. Для того, чтобы отличить список типов от прочих конструкций, используем волшебный metatype, определенный в структурах fas::type_list и fas::empty_list, объявив дополнительно:
template<typename L>
struct length
: length_impl<typename L::metatype, L>
{};
template<typename L>
struct length_impl<metalist::type_list, L>
{
typedef typename L::right_type tail;
enum { value = 1 + length< tail>::value };
};
template<typename L>
struct length_impl<metalist::empty_list, L>
{
enum { value = 0 };
};
Идея в том, что если не сработают специализации length по fas::type_list или fas::empty_list, то будут задействованы специализации на базе типа metatype, который определен во входном параметре. Если он не определен или не является типом fas::metalist::type_list или fas::metalist::empty_list, то получим ошибку компиляции. Если удалить специализации length< type_list<L, R> > и length< empty_list >, то код будет работоспособным, но компилироваться он будет медленнее. Компилятору (в данном случае g++) гораздо проще отработать специализации без “вскрытия” входных типов.
Кроме того, все операции умеют проверять входные списки типов на валидность. Эта опция по умолчанию отключена, т.к. она увеличивает время компиляции. Если у вас появится желание поэкспериментировать со списками типов, то рекомендую включить FASLIB_TYPE_LIST_CHECK, для этого достаточно раскомментировать строку в CMakeLists.txt:
#add_definitions(-DFASLIB_TYPE_LIST_CHECK)
Там же можно отключить специализации операций и алгоритмов по type_list, оставив только специализации по метатипу, и оценить эффект в плане времени компиляции:
#add_definitions(-DDISABLE_TYPE_LIST_SPEC)
Далее, в комментариях, при описании списка типов, для краткости, указывать empty_list я не буду. Будем работать только с правильными списками типов.
template< typename T1 = empty_list, typename T2 = empty_list,
typename T3 = empty_list, typename T4 = empty_list,
typename T5 = empty_list, typename T6 = empty_list,
typename T7 = empty_list, typename T8 = empty_list,
typename T9 = empty_list, typename T10 = empty_list,
typename T11 = empty_list, typename T12 = empty_list,
typename T13 = empty_list, typename T14 = empty_list,
typename T15 = empty_list, typename T16 = empty_list,
typename T17 = empty_list, typename T18 = empty_list,
typename T19 = empty_list, typename T20 = empty_list,
typename T21 = empty_list, typename T22 = empty_list,
typename T23 = empty_list, typename T24 = empty_list,
typename T25 = empty_list, typename T26 = empty_list
>
struct type_list_n
{
typedef
type_list< T1, type_list< T2, type_list< T3, type_list< T4,
type_list< T5, type_list< T6, type_list< T7, type_list< T8,
type_list< T9, type_list< T10, type_list< T11, type_list< T12,
type_list< T13, type_list< T14, type_list< T15, type_list< T16,
type_list< T17, type_list< T18, type_list< T19, type_list< T20,
type_list< T21, type_list< T22, type_list< T23, type_list< T24,
type_list< T25, type_list< T26
> >
> > > >
> > > > > >
> >
> > > > > >
> > > >
> >
bar;
typedef typename organize<bar>::type type;
};
Формируем список типов из всех 26 шаблонных параметров, в голове списка будут явно заданные параметры, а хвост списка будет состоять из множества fas::empty_list — это неправильный список типов в контексте faslib. Операция fas::organize удаляет лишние fas::empty_list и в результате получаем список типов из нужного количества элементов.
Вариант для с++11:
template<typename Head = fas::empty_list, typename ...Args >
struct type_list_n
{
typedef typename fas::organize<
fas::type_list<
Head,
typename type_list_n<Args...>::type
>
>::type type;
};
template<>
struct type_list_n<>
{
typedef fas::empty_list type;
};
Также упрощенная реализация — fas::organize применяется к списку на каждом этапе его формирования. По-хорошему, сначала нужно создать список и потом один раз его организовать. Здесь fas::organize нужен для того, чтобы была возможность передавать списки типов в параметрах fas::type_list_n.
Для манипуляций со списками типов есть набор операций, которые помимо списка типов L, могут принимать тип T и индекс I — интегральный тип. Для операций с индексом есть альтернатива с суффиксом _c, в котором индекс задается числом, например:
typedef fas::erase< fas::int_<0>, fas::type_list<char> >::type empty;
typedef fas::erase_c< 0, fas::type_list<char> >::type empty;
Список всех доступных операций для списков типов:
erase<I,L>::type
erase_c<int,L>::type
head<L>::type
index_of<T,L>::value
length<L>::value
merge<L1,L2>::type
organize<L>::type
normalize<L>::type
push_back<T,L>::type
push_front<T,L>::type
reverse<L>::type
split<I,L>::left_list
split<I,L>::right_list
split_c<int,L>::left_list
split_c<int,L>::right_list
tail<L>::type
type_at<I,L>::type
type_at_c<int,L>::type
type_count<T,L>::value
unique<L>::type
unique_first<L>::type
В этом списке нет таких очевидных операций, как замена типа в заданной позиции set_at (она нам потребуется для того, чтобы сделать ход) и получения последнего элемента списка типов last. Это связано тем, что рассматриваемые в этой статье пакеты faslib разрабатывались в основном для поддержки пакета fas/aop — основного пакета faslib. А операции типа set_at просто-напросто не потребовались для этого. Ну что-же, исправим это недоразумение.
Для получения последнего элемента необходимо вычислить длину списка типов (fas::length) и получить тип в предпоследней позиции (fas::type_at):
template<typename L>
struct last
{
typedef typename fas::type_at_c<
fas::length< L >::value-1,
L
>::type type;
};
Операция set_at будет устанавливать тип в заданной позиции списка типов. Также разработаем set_at_с которая принимает в качестве позиции число. Для минимизации времени компиляции эффективней реализовать эту операцию на специализациях, но мы сделаем проще — используем имеющиеся операции. Для этого:
template<int Pos, typename T, typename L>
struct set_at_c
{
typedef fas::split_c<Pos, L> splitter;
typedef typename splitter::left_list left_list;
typedef typename splitter::right_list right_list;
typedef typename fas::tail< right_list >::type headless;
typedef typename fas::push_front< T, headless >::type pollywog;
typedef typename fas::merge< left_list, pollywog >::type type;
};
template<typename Pos, typename T, typename L>
struct set_at
: set_at_c< Pos::value, T, L>
{
};
Помимо операций над списками типов, в faslib реализован ряд compile-time алгоритмов, по аналогии с алгоритмами stl. В отличие от операций, алгоритм — это всегда мета-функция ( структура, в которой определен тип type — результирующий тип). Многие алгоритмы принимают на вход, помимо списка типов, унарную или бинарную операцию — это шаблонная мета-функция с одним или двумя параметрами. Если алгоритм с условием, то необходим унарный или бинарный предикат (также мета-функция). В качестве предиката могут использоваться операции сравнения интегральных типов, функции из пакета fas/typemanip (например, same_type, super_subclass) или классы stl <type_traits> (например, std::is_base_of, если вы используете c++11).
Все алгоритмы, использующие операции и/или предикаты, имеют версию с суффиксом _t, которая принимает операции и предикаты в виде шаблонных-шаблонных параметров, например:
template<typename L, template<typename> class F >
struct transform_t;
которая для каждого элемента списка типов L применяет операцию F, например:
typedef fas::type_list_n< fas::int_<1>, fas::int_<2>,
fas::int_<3>, fas::int_<4> >::type lst;
typedef fas::transform_t<lst2, fas::inc >::type res; // [2,3,4,5]
В результате получим список интегральных типов, где каждый элемент списка инкрементирован на единицу. Вариант без суффикса предполагает использование placeholder expressions:
template<typename L, typename F >
struct transform;
Например:
typedef fas::transform<lst, fas::inc< fas::_ > >::type res2;
Пример | Альтернатива |
---|---|
foo<_> | foo<_1> |
foo<_,_> | foo<_1,_2> |
foo<_1,_,_2> | foo<_1,_1,_2> |
foo<_1,_,_2,_,_> | foo<_1,_1,_2,_2,_3> |
Иными словами, первый _ в выражении эквивалентен _1, второй — _2 и т.д. Если в выражении используются плейсхолдеры отличные от _, то лучше от последних вообще отказаться, иначе выражение становится сложным для понимания. В то же время в простых вариантах они очень даже удобны.
В примере с fas::transform мы использовали функцию fas::inc, для получения интегрального типа увеличенного на единицу. Однако результат этой функции является тип вида fas::integral_c<int, 4> который является семантически эквивалентным fas::int_<4>, но это другой тип. Для преобразования fas::integral_c в fas::int_ можно использовать функцию fas::make_int:
typedef fas::transform<
lst,
fas::make_int< fas::inc< fas::_ > >
>::type res2;
Список доступных алгоритмов:
accumulate<L, I, F<_,_>=plus >
count<T, L>
count_if<L, С<_> >
erase_if<L, C<_> >
find_if<L, C<_> >
for_<I, C<_>, F<_> >
generator< T, F<_> >
generate< N, F >
index_of_if<L, C<_> >
is_sorted<L, С<_,_>=less >
random_shuffle<R, L>
select< L, С<_> >
shuffle< L, RL>
sort<L, С<_,_>=less >
transform<L, F<_> >
transform2<L1, L2, F<_,_> >
transform_if< L, F<_>, C<_> >
transform_tail<L, F<_> >
transform_tail_if< L, F<_>, C<_> >
unique_if<L, С<_,_>=same_type >
unique_first_if<L, С<_,_>=same_type >
Пример использования алгоритма compile-time сортировки:
typedef fas::type_list_n<
fas::int_<3>, fas::int_<2>,
fas::int_<3>, fas::int_<1>
>::type list1; //[3,2,3,1]
typedef fas::sort_t<list1>::type res1; //[1,2,3,3]
typedef fas::sort<list1>::type res2; //[1,2,3,3]
typedef fas::sort_t<list1, fas::greater>::type res3; //[3,3,2,1]
typedef fas::sort<
list1,
fas::greater< fas::_1, fas::_2>
>::type res4; //[3,3,2,1]
typedef fas::sort<
list1,
fas::greater< fas::_2, fas::_1>
>::type res5; //[1,2,3,3]
Сортировать можно не только интегральные типы. Например, можно отсортировать типы в порядке наследования:
struct A{};
struct B:A{};
struct C:B{};
struct D:C{};
typedef fas::type_list_n< C, B, A, A, D >::type list2;
typedef fas::sort<
list2,
fas::f< fas::super_subclass< fas::_1, fas::_2> >
>::type res5; // [A,A,B,C,D]
Конструкция super_subclass из пакета typemanip не является мета-функцией в контексте алгоритмов faslib, т.к. в ней не определен тип type, а только value, которое принимает значение 1, если первый тип является наследником второго, и ноль в противном случае. А конструкция fas::f исправляет это недоразумение. Если ваш компилятор поддерживает c++11, то в качестве альтернативы fas::super_subclass, вы можете использовать std::is_base_of, в котором определен и type и value. Более того, т.к. преобразований для него не требуется, вы можете передавать его как шаблонный-шаблонный параметр:
typedef fas::sort<
list2,
std::is_base_of< fas::_1, fas::_2>
>::type res5; // [A,A,B,C,D]
typedef fas::sort_t<list2, std::is_base_of >::type res5; // [A,A,B,C,D]
Да, сортировка выполняется методом пузырька — одним из самых неэффективных алгоритмов времени выполнения. На сколько неэффективным он является с точки зрения времени компиляции — я эту тему глубоко не исследовал. Поэтому этот алгоритм, а также fas::for_, fas::shuffle и fas::random_shuffle я отношу к разряду экспериментальных, и в реальных проектах стараюсь не использовать. Эти алгоритмы разработаны для оптимизации времени компиляции прочих конструкций faslib.
Еще один пример — реверс списка типов с использованием алгоритма fas::accumulate
struct A; struct B; struct C;
typedef fas::type_list_n< A, B, C >::type list4;
typedef fas::accumulate<
list4,
empty_list,
push_front<_2, _1>
>::type res4; // [C,B,A]
Мы рассмотрели далеко не все возможности faslib, но этих конструкций вполне достаточно, чтобы научить компилятор играть в крестики-нолики.
Сначала определим типы крестиков, ноликов и пустое поле:
struct e {};
struct x {};
struct o {};
Подключим уровень доступа и игровую доску, которую генерирует python скрипт:
typedef fas::int_<
#include "level.inl"
> level;
typedef fas::type_list_n<
#include "board.inl"
>::type board;
Если файлы *.lnl отсутствуют, то система сборки создаст их (см. CMakeLists.txt). По умолчанию это второй уровень сложности и пустая доска. Так же при каждой компиляции система сборки создает файл rand.inl со случайным числом — его мы будем использовать для рандомизации ходов компилятором. Подключаем аналогичным образом:
typedef fas::int_<
#include "rand.inl"
> initial_rand;
Пустая доска будет выглядеть так:
typedef fas::type_list_n<
e, e, e,
e, e, e,
e, e, e
>::type empty_board;
Далее научимся выводить игровую позицию на экран. Вывод конкретной позиции:
std::ostream& operator<<(std::ostream& s, e)
{
s << "-";
}
std::ostream& operator<<(std::ostream& s, o)
{
s << "O";
}
std::ostream& operator<<(std::ostream& s, x)
{
s << "X";
}
Для наглядности разделим каждую позицию пробелом, а каждую линию с новой строки:
template<typename L, typename R>
std::ostream& operator<<(std::ostream& s, fas::type_list<L, R>)
{
s << L(); // текущая позиция
int len = fas::length<R>::value; // длина хвоста списка
if ( len%3 == 0 ) // если длина хвоста кратна трем, то с новой строки
s << std::endl;
else if (len != 0) // остальные, если не последний элемент, то пробел
s << " ";
s << R(); // “рекурсивно” выводим хвост списка
}
std::ostream& operator<<(std::ostream& s, fas::empty_list)
{
// Конец списка. Ничего не делаем
}
Результатом “хода” компилятора будет кортеж из трех типов:
Для вывода результата “хода” компилятора следующая специализация:
template<typename Pos, typename Fig, typename Board>
std::ostream& operator<< ( std::ostream& s, fas::tuple< Pos, Fig, Board> )
{
s << Board(); // если Board пустой список, то вывода не будет
enum {
// нет хода
nopos = fas::same_type< Pos, fas::int_<-1> >::value,
// нет победителя
nofig = fas::same_type< e, Fig>::value,
};
if ( nopos )
{
// Если ход невозможен, то ничья или победа игрока
if (nofig)
s << "Draw" << std::endl;
else
s << Fig() << " winner (you)" << std::endl;
}
else if ( !nofig )
{
// Есть ход и победная фигура - компилятор победил
s << Fig() << " winner (compiler)" << std::endl;
}
}
При проигрывании партии компилятором без участия человека, результатом будет список кортежей (специализация для конца списка fas::empty_list у нас уже есть ):
template<typename Pos, typename F, typename S, typename Tail>
std::ostream& operator<<(std::ostream& s
,fas::type_list<fas::tuple< Pos, F, S>, Tail>)
{
s << fas::tuple<Pos, F, S>() << std::endl;
s << Tail();
}
Ну а теперь самое интересное. Каждый ход будет делать функция game:
template<typename R, typename Level, typename Board>
struct game;
Здесь R — интегральный тип со случайным числом, которое генерирует система сборки, Level — уровень сложности, Board — исходная доска — список типов из девяти элементов (фигур). Результатом игры, как было отмечено выше, кортеж из трех типов: позиция, если ход возможен ( -1 в противном случае), фигура победителя (e — если нет), новая доска с ходом компилятора (empty_list если ход невозможен).
Алгоритм следующий:
template<typename R, typename Level, typename Board>
struct game
{
typedef typename figure<Board>::type fig;
typedef typename available_moves<R, Level, fig, Board>::type moves;
typedef typename fas::head<moves>::type result_move;
typedef typename fas::first<result_move>::type position;
typedef typename fas::second<result_move>::type win_fig;
typedef typename do_move<position, fig, Board>::type board;
typedef fas::tuple< position, win_fig, board > type;
};
Определить, чей ход на текущей доске, просто: если пустых клеток нечетное количество, то ход крестиков, в противном случае — ноликов:
template<typename Board>
struct figure
{
typedef typename fas::if_c<
fas::type_count< e, Board>::value % 2 == 1,
x,
o
>::type type;
};
При заполненной доске получим, что ход ноликов, но это не важно, т.к. функция определения списка доступных ходов в этом случае проигнорирует этот тип.
Функция определения списка доступных ходов (available_moves) возвращает список пар: [позиция, победитель], причем имеющим значение является только голова списка — по которому и определяется следующий ход. Если ход невозможен, то в голове списка будет пара с позицией -1. Возможные комбинации:
Функция available_moves формирует список, используя ряд вспомогательных функций, каждая возвращает список типов из одного или нескольких пар или пустой список:
Объединив эти списки, в том порядке, в котором они перечислены, получим список ходов в порядке приоритета:
template<
typename R,
typename Level,
typename Fig,
typename Board
>
struct available_moves
{
typedef typename fas::type_list_n<
typename winner_list< Fig, Board >::type,
typename winning_moves< Fig, Board >::type,
typename blocking_moves< Fig, Board >::type,
typename draw_list< Board >::type,
typename free_moves<R, Level, Board >::type
>::type type;
};
Рассмотрим подробнее первые три функции: winner_list, winning_moves и blocking_moves. Каждая из этих функций использует вспомогательные функции, которые принимают на вход список из трех пар [позиция, фигура]. Таких списков восемь: три по горизонтали, три по вертикали и два по диагонали. Например, для доски:
x - -
0 x -
- - 0
Получим следующие списки:
[[0,e],[1,e],[2,e]]
[[3,e],[4,e],[5,e]]
[[6,e],[7,e],[8,e]]
[[0,e],[3,e],[6,e]]
[[1,e],[4,e],[7,e]]
[[2,e],[5,e],[8,e]]
[[0,e],[4,e],[8,e]]
[[2,e],[4,e],[6,e]]
Начнем с функции, которая определяет, что на линии уже есть победитель:
template<typename, typename PairList3>
struct winner_line
{
typedef typename fas::switch_<
fas::case_c<
is_win_line<x, PairList3>::value,
fas::pair< fas::int_<-1>, x>
>,
fas::case_c<
is_win_line<o, PairList3>::value,
fas::pair< fas::int_<-1>, o>
>,
fas::default_< fas::empty_list >
>::type type;
};
Если линия из крестиков (is_win_line<x, PairList3>), то возвращаем [-1,x] — ход невозможен, т.к. крестики победили, если линия из ноликов, то [-1,o]. В противном случае — пустой список.
Для того, чтобы определить, что линия состоит из одних и тех же фигур, достаточно их посчитать:
template<typename Fig, typename PairList3>
struct is_win_line
{
enum {
value = fas::count_if<
PairList3 ,
fas::same_type< Fig, fas::second<fas::_1> >
>::value == 3
};
};
С определением победной или блокирующей позиции (куда можно сделать ход, чтобы победить или предотвратить победу противника) немного сложнее. Для начала научимся определять, есть ли такая позиция:
template<typename Fig, typename PairList3>
struct has_win_pos
{
enum {
value =
fas::count_if<
PairList3 ,
fas::same_type< e, fas::second<fas::_1> >
>::value == 1
&& fas::count_if<
PairList3 ,
fas::same_type< Fig, fas::second<fas::_1> >
>::value == 2
};
};
В этой функции value примет значение 1, если на линии ровно одна пустая клетка, а остальные две заняты заданной фигурой.
Далее разработаем еще одну вспомогательную функцию, которая из входного списка извлекает пары, у которых вторым типом будет e, при условии, если на данной линии возможен победный ход — это всегда список из одного элемента, и пустой список в противном случае:
template<typename Fig, typename PairList3 >
struct win_helper
{
typedef typename fas::if_c<
has_win_pos< Fig, PairList3 >::value,
typename fas::select<
PairList3,
fas::same_type< fas::second<fas::_1>, e>
>::type,
fas::empty_list
>::type type;
};
Для того, чтобы определить блокирующую позицию на линии, нужно обратить фигуру (превратить крестик в нолик и наоборот) и воспользоваться win_helper:
template<typename Fig, typename PairList3 >
struct blocking_move
{
typedef typename fas::if_<
fas::same_type<Fig, x>,
o,
x
>::type rev_fig;
typedef typename win_helper< rev_fig, PairList3 >::type type;
};
Для определения победного хода обращать фигуру не надо, но нужно второй тип из пары (если это не пустой список, то это всегда список из одного элемента с позицией и типом e, например [8,e]) преобразовать в текущую фигуру. Для этого воспользуемся алгоритмом transform:
template<typename Fig, typename PairList3>
struct winning_move
{
typedef typename fas::transform<
typename win_helper< Fig, PairList3 >::type,
fas::pair< fas::first<fas::_1>, Fig >
>::type type;
};
Если результатом win_helper пустой список, то на выходе также пустой список. В противном случае win_helper вернет список из одного элемента, например [[4,e]] и, в этом случае, нужно заменить тип e на текущую фигуру (Fig). Именно по причине того, что win_helper может вернуть пустой список, мы не можем воспользоваться условной конструкцией fas::if_.
Итак, с линиями разобрались, далее нам потребуются функции, для конкретной линии. Сделаем одну, но универсальную:
template<
template<typename, typename> class Move,
typename Fig,
typename Board,
int P0, int P1, int P2
>
struct move_t
{
typedef typename fas::type_list_n<
fas::pair< fas::int_<P0>, typename fas::type_at_c<P0, Board>::type >,
fas::pair< fas::int_<P1>, typename fas::type_at_c<P1, Board>::type >,
fas::pair< fas::int_<P2>, typename fas::type_at_c<P2, Board>::type >
>::type pos_list;
typedef typename Move<Fig, pos_list>::type type;
};
Параметром Move может передаваться одна из наших вспомогательных функций (winner_line, blocking_move или winning_move). Функция move_t формирует список из трех пар [позиция, фигура], на основе трех целочисленных параметров P0, P1 и P2 и передает их в Move.
Всевозможные комбинации зададим явно:
template<
template<typename, typename> class Move,
typename Fig,
typename Board
>
struct moves_list_t
{
typedef typename fas::type_list_n <
typename move_t< Move, Fig, Board, 0, 1, 2 >::type,
typename move_t< Move, Fig, Board, 3, 4, 5 >::type,
typename move_t< Move, Fig, Board, 6, 7, 8 >::type,
typename move_t< Move, Fig, Board, 0, 3, 6 >::type,
typename move_t< Move, Fig, Board, 1, 4, 7 >::type,
typename move_t< Move, Fig, Board, 2, 5, 8 >::type,
typename move_t< Move, Fig, Board, 0, 4, 8 >::type,
typename move_t< Move, Fig, Board, 2, 4, 6 >::type
>::type type;
};
В результате функции для определения доступных ходов (победных или блокирующих) получаются тривиальными.
Уже есть победитель:
template<typename Fig, typename Board>
struct winner_list
: moves_list_t< winner_line, Fig, Board>
{};
Список победных ходов:
template<typename Fig, typename Board>
struct winning_moves
: moves_list_t< winning_move, Fig, Board>
{};
Список блокирующих ходов:
template<typename Fig, typename Board>
struct blocking_moves
: moves_list_t< blocking_move, Fig, Board>
{};
Итак, мы разобрали три вспомогательные функции для определения доступных ходов (winner_line, blocking_move или winning_move), осталось еще две. Следующая по списку — определение ничьей. Определяем ничью просто — если свободных клеток меньше трех, то это ничья. В общем случае это, конечно же, не верно, однако мы договорились, что используем только голову списка из списка возможных ходов. Поэтому если все предыдущие функции (winner_line, blocking_move или winning_move) вернули пустые списки, то этого достаточно. Разумеется, так мы можем пропустить ничью, которую можно было определить несколько раньше, но этого вполне достаточно, чтобы не делать игру утомительной.
template<typename Board>
struct draw_list
{
typedef typename fas::if_c<
fas::type_count< e, Board >::value < 3,
fas::pair< fas::int_<-1>, e >,
fas::empty_list
>::type type;
};
Здесь все очевидно, если пустых полей меньше трех, то возвращаем пару [-1,e] — ход невозможен, ничья.
Ну а теперь, как это ни странно, самое сложное — ход в любую свободную позицию. Сложность заключается в том, что именно на этом этапе мы учитываем уровень сложности (уж простите за каламбур) и при этом делаем “случайные ходы”, в зависимости от этого уровня сложности.
Для этого функцию free_moves разобьем на два этапа. На первом, без учета занятых полей, выдаем список позиций всевозможных ходов, причем приоритетные ходы в голове списка. На втором этапе формируем список пар [позиция, фигура] и удаляем из списка те пары, у которых фигура не равна e (занятые позиции).
Для функции, которая возвращает список ходов на пустой доске в порядке приоритета в зависимости от уровня сложности, потребуется псевдослучайное число ® и уровень сложности:
template<typename R, typename Level>
struct priority_positions;
Нам потребуются три типа:
typedef fas::int_<4> center;
typedef fas::type_list_n<
fas::int_<0>, fas::int_<2>,
fas::int_<6>, fas::int_<8>
>::type corner_list;
typedef fas::type_list_n<
fas::int_<1>, fas::int_<3>,
fas::int_<5>, fas::int_<7>
>::type edge_list;
Для второго уровня сложности нужно случайно перемешать списки corner_list и edge_list и объединить с центром:
typedef typename fas::merge<
center,
typename fas::merge<
typename fas::random_shuffle< R, corner_list>::type,
typename fas::random_shuffle< R, side_list>::type
>::type
>::type level2_list;
Таким образом на втором уровне сложности приоритеты ходов: центр, угол, крайние позиции. Вместо вложенного fas::merge можно использовать “плоский” fas::type_list_n.
[A,B,C,D]
Для того, чтобы его перемешать, нужно сгенерировать список такой-же длины из произвольных интегральных типов, например:
[10,2,44,7]
Затем объединить эти два списка в список пар:
[[10,A],[2,B],[44,C],[7,D]]
Отсортировать его по первому типу каждой пары:
[[2,B],[7,D],[10,A],[44,C]]
И извлечь второй тип из каждой пары:
[B,D,A,C]
Для генерации псевдослучайной последовательности нам потребуется генератор, который преобразует исходный тип в некоторый другой. Пример инкрементального генератора:
typedef fas::generator<
fas::int_<1>,
fas::inc< fas::_ >
>::next_type result; // fas::int_<2>
Для генерации случайного числа:
typedef fas::generator<
fas::int_<1>,
fas::rand< fas::_>
>::next_type result; // fas::int_<12461757>
Алгоритм fas::generate генерирует последовательность заданной длины используя заданный генератор. Далее fas::random_shuffle использует алгоритм fas::shuffle, который сначала трансформирует список случайных интегральных типов и исходный список типов в список пар (используя fas::transform2), сортирует его, и извлекает второй тип из каждой пары (fas::transform).
Собственно алгоритм fas::random_shuffle, генерирует псевдослучайную последовательность по заданному зерну и применяет fas::shuffle — все просто. Упрощенная реализация fas::random_shuffle:
template<typename R, typename L>
struct random_shuffle
{
typedef typename generate_c<
length<L>::value,
generator_t<rand<R>, rand >
>::type rand_list;
typedef typename shuffle< L, rand_list>::type type;
};
И fas::shuffle:
template<typename L, typename RL>
struct shuffle
{
typedef typename transform2_t< RL, L, make_pair >::type pair_list;
typedef typename sort<
pair_list,
less<
first<_1>,
first<_2>
>
>::type sorted_list;
typedef typename transform_t< sorted_list, second >::type type;
};
Для нулевого уровня сложности просто перемешиваем то, что получили для второго уровня:
typedef typename fas::random_shuffle< R, level2_list >::type level0_list;
Для первого уровня сложности нужно объединить списки углов и крайних позиций в один список, перемешать его, и в голову поместить центральную позицию:
typedef typename fas::merge< corner_list, edge_list >::type side_list;
typedef typename fas::merge<
center,
typename fas::random_shuffle< R, side_list>::type
>::type level1_list;
Итак мы получили три списка возможных ходов, для каждого уровня сложности, осталось выбрать нужный список:
typedef typename fas::switch_<
fas::case_c< Level::value == 0, level0_list >,
fas::case_c< Level::value == 1, level1_list >,
fas::default_< level2_list >
>::type type;
Итого:
template<typename R, typename Level>
struct priority_positions
{
typedef fas::int_<4> center;
typedef fas::type_list_n<
fas::int_<0>, fas::int_<2>,
fas::int_<6>, fas::int_<8>
>::type corner_list;
typedef fas::type_list_n<
fas::int_<1>, fas::int_<3>,
fas::int_<5>, fas::int_<7>
>::type edge_list;
typedef typename fas::merge< corner_list, edge_list >::type side_list;
typedef typename fas::merge<
center,
typename fas::merge<
typename fas::random_shuffle< R, corner_list>::type,
typename fas::random_shuffle< R, side_list>::type
>::type
>::type level2_list;
typedef typename fas::merge<
center,
typename fas::random_shuffle< R, side_list>::type
>::type level1_list;
typedef typename fas::random_shuffle< R, level2_list >::type level0_list;
typedef typename fas::switch_<
fas::case_c< Level::value == 0, level0_list >,
fas::case_c< Level::value == 1, level1_list >,
fas::default_< level2_list >
>::type type;
};
На выходе priority_positions список интегральных типов — позиции в порядке приоритета в зависимости от уровня сложности. Но на выходе free_moves должен быть список пар, в виде [N,e], а для этого нужно трансформировать список:
typedef typename fas::transform <
typename priority_positions< R, Level >::type,
fas::pair<
fas::_1,
fas::type_at< fas::_1, Board>
>
>::type pair_list;
И извлечь свободные позиции:
typedef typename fas::select<
pair_list,
fas::same_type<
e,
fas::second<fas::_>
>
>::type type;
Итак, функция, которая делает ход в случайную свободную позицию в зависимости от уровня сложности:
template<typename R, typename Level, typename Board>
struct free_moves
{
typedef typename fas::transform<
typename priority_positions< R, Level >::type,
fas::pair<
fas::_1,
fas::type_at< fas::_1, Board>
>
>::type pair_list;
typedef typename fas::select<
pair_list,
fas::same_type<
e,
fas::second<fas::_>
>
>::type type;
};
Последний пункт в алгоритме game — сделать ход. Если ход возможен, то замещаем тип e, в заданной позиции фигурой, которой сделал ход компилятор. В противном случае возвращаем пустой список (если компилятор не может сделать ход, то доску на экран не выводим):
template<typename Pos, typename Fig, typename Board>
struct do_move
{
typedef typename set_at< Pos, Fig, Board >::type type;
};
template<typename Fig, typename Board>
struct do_move< fas::int_<-1>, Fig, Board>
{
typedef fas::empty_list type;
};
Уффф. Вроде, все. Основная программа:
#include "tictactoe.hpp"
#include "types.hpp"
#include "show_board.hpp"
#include <iostream>
int main()
{
typedef game< initial_rand, level, board >::type result;
std::cout << result() ;
return 0;
}
Итак, мы научили компилятор делать один ход на заданной доске. А если можно сделать один ход, то научить играть партию до конца с самим собой — дело техники.
Для этого нам понадобится цикл, который будет применять game, до тех пор, пока не выявится победитель или будет ничья. Изучать циклы будем на примере факториала. Рекурсивная реализация (без проверок):
int factorial(int n)
{
return n > 0 ? n * factorial(n - 1) : 1;
}
Аналог на этапе компиляции:
template<int N>
struct factorial { enum { value = N * factorial<N-1>::value }; };
template<>
struct factorial<1> { enum { value = 1 };};
В цикле:
int factorial(int i)
{
int result = 1;
for ( ; i > 0; result*=i, --i);
return result;
}
Но для начала совсем простой пример:
int i=0;
for (; i<10;i++);
std::cout << i << std::endl;
С использованием fas::for_:
typedef fas::for_<
fas::int_<0>,
fas::less<fas::_, fas::int_<10> >,
fas::inc<fas::_>
>::type result;
std::cout << result::value << std::endl;
Аналогично классическому оператору for у fas::for_ три элемента: исходный тип, условие и действие. На первой итерации исходный тип передается, как есть, условному выражению, и, если оно истинно, то операции. Далее, результат операции, на вход условию, после опять операции и т.д. до тех пор пока срабатывает условие. Если условие не сработало ни разу, то результатом будет исходный тип. Результатом операции должен быть тип, который корректно обработает условие и который можно заново передать операции.
Для вычисления факториала с использованием цикла нам потребуется пара типов — счетчик и текущее значение:
template<int I>
struct factorial
{
typedef typename fas::for_<
// исходный тип
fas::pair<
fas::int_<I>, // счетчик
fas::int_<1> // текущее значение
>,
// условие (пока счетчик больше нуля)
fas::greater< fas::first< _1 >, int_<0> >,
// действие (декримент счетчика и умножение текущего значения на счетчик)
fas::pair<
fas::dec< fas::first< _1 > >,
fas::times< fas::second< _1 >, fas::first< _1 > >
>
>::type result;
// результат пара: счетчик (всегда равен нулю) и факториал
typedef typename fas::second<result>::type type; // int_< I! >
enum { value = type::value};
};
Приступим к разработке цикла, который проигрывает партию начиная с заданной позиции и до конца (ничья или победитель). Результатом выполнения цикла будет список кортежей, которые вернет game на каждой итерации. Соответственно все элементы fas::for_ будут манипулировать этим списком. В качестве исходного типа будет список из одного кортежа, в который будет добавляться результат каждого раунда игры до тех пор, позиция очередного хода не будет равна fas::int_<-1>, что будет означать конец игры и условием выхода из цикла. Итак, исходный тип:
fas::type_list<
fas::tuple<
fas::empty_type, // ход игрока
e, // фигура победителя
board // исходная доска
>
>
Особенность цикла будет в том, что в любом случае он выполнится хотя бы один раз, даже на доске, где нет хода. Поэтому голова списка, в который попадает исходный кортеж, не важна — мы ее отрежем.
Условием выхода из цикла будет первый тип кортежа, который расположен в хвосте списка типов результатов ходов, равный fas::int_<-1> (ход невозможен) или фигура, не равная e (есть победитель):
fas::and_<
fas::not_<
fas::same_type<
fas::int_<-1>,
fas::first< last< fas::_1> >
>
>,
fas::same_type<
e,
fas::second< last< fas::_1> >
>
>
Действием будет добавление в хвост списка типов результата очередного раунда игры:
fas::push_back<
game<
initial_rand, // “случайное” число
level, // уровень сложности
fas::third< last< fas::_1> > // Результат предыдущего раунда
// (третий элемент последнего кортежа)
>,
fas::_1 // Список результатов предыдущих игр
>
Далее остается только отрезать голову списка, вывести исходную доску и результаты всех раундов игры (соответствующая специализация << для вывода списка результатов раундов у нас уже есть):
#include "show_board.hpp"
#include "tictactoe.hpp"
#include "types.hpp"
int main()
{
typedef fas::for_<
fas::type_list<
fas::tuple<
fas::empty_type,
e,
board
>
>,
fas::and_<
fas::not_<
fas::same_type<
fas::int_<-1>,
fas::first< last< fas::_1> >
>
>,
fas::same_type<
e,
fas::second< last< fas::_1> >
>
>,
fas::push_back<
game<
initial_rand,
level,
fas::third< last< fas::_1> >
>,
fas::_1
>
>::type result_list;
typedef fas::tail<result_list>::type game_list;
std::cout << board() << std::endl;
std::cout << game_list() << std::endl;
return 0;
}
Мы научили компилятор играть в крестики-нолики, не идеально, но вполне сносно. Для идеальной игры нужно научить компилятор ходить в противоположный угол предыдущего хода противника (если ход был сделан в угол), а также научить ставить вилку. Для первого случая знать предыдущий ход противника не обязательно, достаточно делать ход в любой угол, если в противоположном фигура противника. С вилкой немного сложнее, но вполне реализуемо.
Если эта тема вызовет некоторый интерес, я опишу ее в следующей статье. А также познакомлю с мета-функциями высшего порядка — они нам понадобятся для того, чтобы научить компилятор проиграть несколько партий подряд с использованием вложенного цикла fas::for_ одной конструкцией. В отличии от обычных мета-функций, результатом мета-функции высшего порядка будет мета-функция (в том числе и мета-функции высшего порядка).
Так же не раскрыта тема экстремального мета-программинга в моей интерпретации. Здесь речь не идет об XP. Это программирование на пределе возможностей, но не человека (хотя и не без этого), а компилятора. Суть достаточно проста. Нужно заставить компилятор разворачивать относительно простую внешне шаблонную конструкцию достаточно долго, так, чтобы можно замерить время компиляции (чем дольше, тем лучше), не сваливаясь в
error: template instantiation depth exceeds maximum of 900
Сделать это не так просто, но очень увлекательно, и позволяет наглядно увидеть эффект от оптимизации тех или иных конструкций, с точки зрения времени компиляции. Побочный эффект от подобных экспериментов, это безумные логи ошибок (десятки, а иногда и сотни мегабайт), сваливание компилятора в глубокий своп (зависание системы) и Internal Compiler Error. Например, если в цикле fas::for_, который проигрывает партию крестиков-ноликов, заменить board на, например, fas::empty_type, получите 128 мегабайтный лог ошибок (для gcc-4.8).
В повседневной практике рассмотренные пакеты в явном виде я использую редко, за исключением fas::type_list_n для формирования списка типов. Эти пакеты разработаны для поддержки пакета fas/aop (в котором реализованы аспектно-ориентированные сущности), который я активно использую в реальных проектах уже более 8 лет. Если эта тема будет интересна, то я о ней тоже с удовольствием расскажу, но это потребует, возможно, целого цикла статей.
Автор: laphroaig
Источник [9]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/news/63904
Ссылки в тексте:
[1] faslib: http://faslib.com
[2] fas/type_list: https://github.com/migashko/faslib/tree/master/fas/type_list
[3] fas/typemanip: https://github.com/migashko/faslib/tree/master/fas/typemanip
[4] Loki: http://ru.wikipedia.org/wiki/Loki
[5] fas/mp: https://github.com/migashko/faslib/tree/master/fas/mp
[6] fas/integral: https://github.com/migashko/faslib/tree/master/fas/integral
[7] мета-алгоритмов: https://github.com/migashko/faslib/tree/master/fas/algorithm
[8] здесь: https://github.com/migashko/faslib/blob/master/tutorial/algorithm/algorithm4.cpp
[9] Источник: http://habrahabr.ru/post/228367/
Нажмите здесь для печати.