Крестики-нолики: компилятор против человека — экстремальный метапрограмминг

[@silvansky]

Человек-маньяк, добавьте Вашу замечательную статью в хаб «Ненормальное программирование»!

[@laphroaig]

Добавил, хотя и не согласен с Вами

[@Door]

Ого! У меня намного проще крестики-нолики, если это можно назвать крестиками-ноликами.
Так автор faslib, это Вы?

Эти пакеты разработаны для поддержки пакета fas/aop (в котором реализованы аспектно-ориентированные сущности), который я активно использую в реальных проектах уже более 8 лет. Если эта тема будет интересна, то я о ней тоже с удовольствием расскажу, но это потребует, возможно, целого цикла статей.

Требую цикл статей!

[@laphroaig]

Да, faslib мой проект.
Я начинал писать статью несколько лет назад, но потом забыл (забил) на это, а Ваша статья побудила реанимировать ее

[@Wyrd]

А почему вы не использовали boost::mpl? на первый взгляд Ваша библиотека реализуют ту же самую функциональность.

[@laphroaig]

faslib быстрее в плане времени компиляции, и многие конструкции можно реализовать компактнее (меньше кода)
В свое время я рассматривал boost::mpl, но т.к. я игрался с оптимизацией времени компиляции нужны были свои решения с которыми можно экспериментировать. Кроме того boost::mpl работает с векторами, а faslib со списками. Много других нюансов. Например boost::mpl::lamba< fun<_1,_2> >::apply — это шаблон с большим числом параметров (не помню сейчас точно), а в fas::lamba< fun<_1,_2> >::apply — это шаблон ровно с двумя параметрами. Да и вся мощь boost::mpl в faslib мне не нужна была. А в общем, то конечно, играть в крестики-нолики можно научить и с помощью boost::mpl

[@Wyrd]

Понятно, спасибо

[@vScherba]

Кроме того boost::mpl работает с векторами, а faslib со списками

Ну почему же? MPL тоже работает со списками и с другими классами и концепциями последовательностей, а также итераторов.

А получилось здорово, конечно.

[@laphroaig]

С векторами это я дал конечно, совсем другое имел ввиду. Проще на примере:

  typedef boost::mpl::list<float,double,long double> floats;
  typedef boost::mpl::push_front<floats,int>::type types;
  /* types: 
         boost::mpl::l_item<mpl_::long_<4l>, int, boost::mpl::list3<float, double, long double> >  */

  typedef fas::type_list_n< float,double,long double>::type floats;
  typedef fas::push_front< int, floats>::type types;
  /* types: 
         fas::type_list<int, fas::type_list<float, fas::type_list<double, fas::type_list<long double, fas::empty_list> > > > */

В faslib результатом операции всегда будет список типов — с ним проще работать, а в бусте непонятно что, результат уже на специализациях не отработаешь. В статье я уже писал, что это сильно сокращает время компиляции. Да и вообще монструозно там все как-то, а про препроцессор я вообще молчу

[@Wyrd]

>> В faslib результатом операции всегда будет список типов — с ним проще работать, а в бусте непонятно что

В бусте это специально сделано, чтоб можно было работать со сложными выражениями не упираясь в ограничение компилятора на максимальную вложенность шаблонов (это проблема для списков типов, но не проблема для «векторов»). Кроме того, насколько я помню «вектора» быстрее компилируются обычно (не уверен, т.к. последний раз я в этом копался очень давно).

>> результат уже на специализациях не отработаешь

ИМХО, это правильно — позволяет менять внутреннее представление данных без изменений клиентского кода.
Буст предоставляет интерфейс доступа аналогичный обычным контейнерав времени выполнения.
В данном случае использование явной специализации — это как попытка «привести» std::vector к int *

Если вам нужна специализация используйте enable_if

1. bool is_empty<Sequence>()
2. {
3.     return false;
4. }
5.  
6. bool is_empty<Sequence>(typename boost::enable_if<boost::mpl::empty<Sequence>>::type * = 0)
7. {
8.     return false;
9. }

>> А про препроцессор я вообще молчу
Это плата за то что оно может работать на куче разных компиляторов, включая древние.
Все новомодные штуки типа variadic templates приходится оборачивать в макросы, которые «эмулируют» новый стандарт тем или иным образом.

p.s.
Все-таки синтаксис С++ меня убивает :(

[@Wyrd]

* вторая функция в примере должна конечно же возвращать тру

[@laphroaig]

Я не спорю, boost::mpl прекрасный инструмент, а вы перечислили различие концепций с faslib:

ИМХО, это правильно — позволяет менять внутреннее представление данных без изменений клиентского кода. Буст предоставляет интерфейс доступа аналогичный обычным контейнерав времени выполнения.

В faslib во главе угла списки типов, могут меняться инструменты, но представление всегда одно. На ранних этапах я пытался скрыть представление, но отказался от этого.

Это плата за то что оно может работать на куче разных компиляторов, включая древние.

Я не готов за это «платить» )

В бусте это специально сделано, чтоб можно было работать со сложными выражениями не упираясь в ограничение компилятора на максимальную вложенность шаблонов

Это не спасает от ограничения. Вы можете сколь угодно сложные конструкции, а в ограничение вы упретесь при обработке таких выражений. Опять же пример, строим «вектор» из 1600 элементов:

template<int I, typename List >
struct push {
  typedef typename boost::mpl::push_front< List, fas::int_<I> >::type result;
  typedef typename push< I-1, result>::type type;
};

template< typename List >
struct push<0, List> {  typedef List type; };

int main()
{
  typedef boost::mpl::vector<> lst;
  typedef push<800, lst>::type lst800;
  typedef push<800, lst800>::type lst1600;
  std::cout << boost::mpl::size<lst800>::value << std::endl;
  std::cout << boost::mpl::size<lst1600>::value << std::endl;
}

Используя этот способ мы не можем построить за раз вектор больше чем 900 элементов (у меня такое ограничение по умолчанию), потому что именно в push мы упремся в это ограничение. Аналогично мы и список типов можем построить такой же длинны:

template<int I, typename List >
struct push2 {
  typedef typename fas::push_front< fas::int_<I>, List >::type result;
  typedef typename push2< I-1, result>::type type;
};

template< typename List >
struct push2<0, List> {  typedef List type; };

int main()
{
  typedef fas::empty_list lst;
  typedef push2<800, lst>::type lst800;
  typedef push2<800, lst800>::type lst1600;
  std::cout << fas::length<lst800>::value << std::endl;
  std::cout << fas::length<lst1600>::value << std::endl;
}

Кроме того, насколько я помню «вектора» быстрее компилируются обычно (не уверен, т.к. последний раз я в этом копался очень давно).

Время компиляции примера на faslib:
0m1.027s
На boost::mpl:
2m16.836s
Да-да я сам в шоке (от буста, конечно-же)
Дальше, больше 3200 элементов:
faslib: 0m1.400s
boost: 16m58.397s
Вот она сила специализаций. Хотел попробовать сделать крестики-нолики на бусте, чтобы изучить матчасть, но уже больше не хочу

[@vScherba]

Да, помню, как я раздосадовался, когда хотел красиво специализацией раздиспатчить что-то типа:

template <typename V>
class C{};

template <>
class C<mpl::vector<int> >{};

Не специфицировано, что может получиться после манимуляций с вектором (получится, конечно, тот же вектор как концепт, но имя у него может быть vector0, vector1 и т.д.). По факту у меня мог прийти mpl::vector1<int> или mpl::vector<int>

Пришлось извращаться менее красиво.

[@Wyrd]

deleted

[@Wyrd]

Для такой задачи есть стандартный механизм:

1. template <class V, class Enable = void> 
2. class C {};
3.  
4. template <class C>
5. class A<C, typename boost::enable_if<boost::mpl::equal<V, boost::mpl::vector<int> > >::type> {};

Делает имеенно то, что вы хотели.

Справедливости ради, вместо вектора там вообще может быть все что угодно, например вы можете простенький враппер который позволит boost::mpl принимать конкретно ваши (fas::) списки типов. Все что вам нужно, это привести их к виду www.boost.org/doc/libs/1_55_0/libs/mpl/doc/refmanual/forward-sequence.html

[@laphroaig]

Для такой задачи есть стандартный механизм:

Примерно так и работают операции со списками типов (в статье есть пример fas::lenght ), но плюс всегда есть специализация, для ускорения компиляции.
Как это реально влияет можно посмотреть в этом ответе выше. А посему я лучше напишу простенький враппер приводящий бустовые последовательности в списки типов

[@vScherba]

Именно такой подход сразу и пришел мне в голову: через mpl::equal выражать. Это менее красиво, в разы тормознее, но формально правильно по спецификации mpl, ничего тут не поделаешь.

Справедливости ради, вместо вектора там вообще может быть все что угодно

Я о том же выше и написал, что неспецифицировано. Например, для операции mpl::erase гарантируется лишь, что результат будет «concept-identical» источнику. То есть, с сохранением набора концепций, но фиг знает каким классом.

A sequence s1 is said to be concept-identical to a sequence s2 if s1 and s2 model the exact same set of concepts.

На практике из mpl::vector[N] будет получаться mpl::vectorN-1, я бы мог забить вторую спецификацию mpl::vector1<int> и, уверен, 100 лет бы проработало, но формально — это ошибка.

принимать конкретно ваши (fas::) списки типов

К сожалению, fas — не моя, это laphroaig :)
Ни сколько не умаляю достоинств mpl. Сам пользуюсь. Ее возможности более широкие. Широченные. А за высокий уровень абстрагирования приходится платить временем компиляции.

[@denisshevchenko]

Когда я вижу вот такое:

fas::switch_< fas::case_< fas::false_, fas::int_<24> >, fas::case_c< 1, fas::int_<42> >, fas::default_< fas::int_<44> > >::type::value 

я понимаю, что значит НЕНОРМАЛЬНОЕ программирование…

[@Nomad1]

На калькуляторе БЗ-21 как-то попроще эта игра делалась. Наверное я отстал от жизни :)

[@Fil]

Здравствуй, компилятор, я хочу хочу сыграть с тобой в игру…

[@sl4mmer]

Более яркие эмоции можно испытать очнувшись прикованным к офисному креслу и услышав это предложение от компилятора

[@laphroaig]

После многочасового писка глупой ошибки в программе, достаточно сказать ему «Зато хрен ты у меня в крестики-нолики выиграешь» и сразу легче на душе

[@sl4mmer]

Главное чтобы он не предложил посоревноватmся в пересборке мира с -O3

[@kriokamera]

Постойте, но ведь на офисном кресле можно просто уехать.

[@AraneusAdoro]

До первой лестницы.

[@Coderik]

А дальше бобслей

[@AraneusAdoro]

Скелетон тогда уж.

[@uvelichitel]

Полными по Тьюрингу также являются typecheckers Haskell и D. Видел академические доказательства этому, но вот такое прагматичное впервые. Спасибо, интересная статья. Полнота по Тьюрингу кстати означает, что время компиляции теоретически не ограничено.