#include <iostream>


template <typename org, int x, int y>
struct neighbors
{
	static const int count =
		(org::template cell<x-1, y-1>::alive ? 1 : 0) +
		(org::template cell<x-1, y  >::alive ? 1 : 0) +
		(org::template cell<x-1, y+1>::alive ? 1 : 0) +
		(org::template cell<x  , y-1>::alive ? 1 : 0) +
		(org::template cell<x  , y+1>::alive ? 1 : 0) +
		(org::template cell<x+1, y-1>::alive ? 1 : 0) +
		(org::template cell<x+1, y  >::alive ? 1 : 0) +
		(org::template cell<x+1, y+1>::alive ? 1 : 0);

	template <int x1, int y1>
	struct with
	{
		static const int dx = x - x1;
		static const int dy = y - y1;

		static const bool are =
			(dx || dy) &&
			(dx >= -1 && dx <= 1) &&
			(dy >= -1 && dy <= 1);
	};
};


template <typename org>
struct evolved
{
	template <int x, int y>
	struct cell
	{
		static const bool alive =
			(neighbors<org, x, y>::count == 3) ||
			(org::template cell<x, y>::alive && neighbors<org, x, y>::count == 2);
	};
};


template <typename org, int x, int y>
struct cell_printer
{
	static void print(std::ostream& out)
	{
		out << (org::template cell<x, y>::alive ? "()" : "--");
	}
};


template <typename org, int x1, int y1, int x2, int y2, int x = x1, int y = y1>
struct org_printer
{
	static void print(std::ostream& out)
	{
		cell_printer<org, x, y>::print(out);
		org_printer<org, x1, y1, x2, y2, x+1, y>::print(out);
	}
};


template <typename org, int x1, int y1, int x2, int y2, int y>
struct org_printer<org, x1, y1, x2, y2, x2, y>
{
	static void print(std::ostream& out)
	{
		cell_printer<org, x2, y>::print(out);
		out << std::endl;
		org_printer<org, x1, y1, x2, y2, x1, y+1>::print(out);
	}
};


template <typename org, int x1, int y1, int x2, int y2>
struct org_printer<org, x1, y1, x2, y2, x2, y2>
{
	static void print(std::ostream& out)
	{
		cell_printer<org, x2, y2>::print(out);
		out << std::endl;
	}
};


template <typename org, int x1, int y1, int x2, int y2, int steps, int n = 0>
struct life_printer
{
	static void print(std::ostream& out)
	{
		org_printer<org, x1, y1, x2, y2>::print(out);
		out << std::endl;
		life_printer<evolved<org>, x1, y1, x2, y2, steps, n+1>::print(out);
	}
};


template <typename org, int x1, int y1, int x2, int y2, int steps>
struct life_printer<org, x1, y1, x2, y2, steps, steps>
{
	static void print(std::ostream& out)
	{
	}
};


namespace glider
{
	template <int x, int y>
	struct cell { const static bool alive = false; };

	template <> struct cell<0, 0> { const static bool alive = true; };
	template <> struct cell<1, 0> { const static bool alive = true; };
	template <> struct cell<2, 0> { const static bool alive = true; };
	template <> struct cell<2, 1> { const static bool alive = true; };
	template <> struct cell<1, 2> { const static bool alive = true; };

	struct org
	{
		template <int x, int y>
		struct cell: glider::cell<x, y> {  };
	};
};



int main()
{
	life_printer<glider::org, -2, -2, +4, +4, 5>::print(std::cout);
	return 0;
}

Рекомендуется также собрать это с опциями -S -O3, и посмотреть на ассемблерный листинг функции main =)

Зачот :)

А меня поразило время компиляции такой вроде бы небольшой программки...

> поразило время компиляции такой вроде бы небольшой программки...

Время компиляции идёт лесом. Зато работает быстро :)

На самом деле, очень завуалирован принцип действия даже для C++ с его шаблонами.

> Время компиляции идёт лесом. Зато работает быстро :)
Да, уж кому как.. А представляете если бы ядро было в таком же стиле написано? Кхе-кхе.. Мне бы не хотелось тратить сутки на компиляцию только ядра.
Шаблоны, конечно, полезны иногда, но.. ключевое слово _иногда_ - по-моему, нельзя всё на них преводить..

Дяденьки, вы меня пугаете 8))))))))

дык, если бы ядро занимало бы пару килобайт, пусть и компилировалось бы пару недель и при этом быстро работало то цены бы ему не было.

> Мне бы не хотелось тратить сутки на компиляцию только ядра.

Если бы оно работало раза в два, скажем, быстрее, то это был бы много бОльший выигрыш в производительности, чем после перекомпиляции под архитектуру. Я был бы только за. Не каждый же день я ядра собираю.

> А меня поразило время компиляции такой вроде бы небольшой программки...

А ты замени там первую строчку в main на:

life_printer<glider::org, -10, -10, +10, +10, 5>::print(std::cout);

И потом можешь помедитировать, глядя на то, как gcc потихоньку жрет память... =)

> Да, уж кому как.. А представляете если бы ядро было в таком же стиле написано? Кхе-кхе..

Это как? Расчитывало на шаблонах в compile-time сегфаулт (все равно все там будем ;), и при запуске сразу делало dump и вываливалось? =)

> На самом деле, очень завуалирован принцип действия даже для C++ с его шаблонами.

Что там завуалированного? Собственно сами правила игры целиком описаны в первых двух структурах (причем neighbors::with - не нужен, я его просто забыл выкинуть). А там - типичный (для ФП) pattern matching.

Вы не забывайте, что кроме время компиляции при этом бы ещё увеличился дико сам бинарник...

> И потом можешь помедитировать, глядя на то, как gcc потихоньку жрет память... =
Нет, спасибо, не охота.. Я конечно, понимаю так ещё будет дольше :-))

> Вы не забывайте, что кроме время компиляции при этом бы ещё увеличился дико сам бинарник...

Да, но зато в нем вообще нет условных переходов - рай для оптимизатора переходов =)

> Нет, спасибо, не охота.. Я конечно, понимаю так ещё будет дольше :-))

Я у себя так запускал. Компилилось около восьми минут, выжрав под конец 150 метров памяти. Но заработало =)

> Это как? Расчитывало на шаблонах в compile-time сегфаулт (все равно все там будем ;), и при запуске сразу делало dump и вываливалось? =)
Когда ехал на учёбу понял о чём вы говорите :-))
Ведь попытка реализации на шаблонах любой рекурсии или бесконечного цикла (без чего не обойтись в ОС) вызовет зацикливание уже компилятора (пока он не съест всё место на диске или в ОП) :-))

Вот это меня и смешит в C++ более всего - вроде бы, простой функциональный язык в этих темплейтах - так ведь фигушки, даже такой отстой не смогли реализовать эффективно... За столько лет разработчики быдловских недоязыков так ничему и не научились - и ведь столько примеров вокруг было, откуда можно идеи целиком тянуть. Не смогли, уродцы, мозгов не хватило.

P.S. Страуса из AT&T с работы выгнали. Наконец-то. Возрадуемся!

Ничего ты не понял. А если шаблон создаст ЛЕНИВЫЙ код?

Ты, похоже, не на ту учёбу ездишь, деточка. Не тому, чему следует, тебя там учат...

> Ведь попытка реализации на шаблонах любой рекурсии или бесконечного цикла (без чего не обойтись в ОС) вызовет зацикливание уже компилятора (пока он не съест всё место на диске или в ОП) :-))

Гм... ты бы посмотрел на код еще раз, что ли. Там как раз одна сплошная рекурсия. Больше того, с ее помощью создается _бесконечная_ матрица поля игры - т.е. для _любой_ клетки (x,y) задано правило определения ее состояния на данном шаге. Другой вопрос, что, поскольку обращения идут только к видимым клеткам, а область видимости ограничена, реально рассчитывается только необходимое подмножество (т.е. по сути имеем lazy evaluation). Но сама по себе структура, заданная первыми двумя классами в коде - неограниченна.

> Вот это меня и смешит в C++ более всего - вроде бы, простой функциональный язык в этих темплейтах - так ведь фигушки, даже такой отстой не смогли реализовать эффективно...

Имхо дело просто в том, что темплейты изначально задумывались для простых целей - типизированные контейнеры etc - а не для полноценного метапрограммирования. А потом в процессе развития языка накрутили всяких фич, и постфактум получили Тьюринг-полный, но жутко кривой метаязык =/ Иными словами: "мы не хотели, оно само так получилось". А потом появился STL, и поехало...

Дык я об то и говорю - даже скоммуниздить идею как следует Страус не может...

Весь C++ такой - большая, пованивающая кучка нелепостей.

> Дык я об то и говорю - даже скоммуниздить идею как следует Страус не может...

Дык и я о том же =) не коммуниздил он идею. Он вообще о другом думал =) а оно само взяло и получилось...

Вывод: срочно нужно начинать массовое производство презервативов для мозгов

> Гм... ты бы посмотрел на код еще раз, что ли. Там как раз одна сплошная рекурсия.
Я имел ввиду бесконечную рекурсию...

А она там бесконечная и есть.

Хорошо, конечно, когда компилятор умный, но зачем тогда template'ы, если компилятор их вдруг всё равно "завернёт" как функцию?

Да ну? Программа оканчивает работу? Оканчивает - значит конечный.

Для полноты логики, надо, конечно, же заметить что программа заканчивает работу совершенно не зависимо от действий пользователя или ещё каких-то непредсказуемых обстоятельств.

Тебе же сказали - иди, учись в другое место, туда, где научат.

Ещё раз: в ленивой семантике бесконечная рекурсия вполне может завершиться за конечное время.

> Да ну? Программа оканчивает работу? Оканчивает - значит конечный.

Кусок кода на Haskell:

fibs@(_:rest) = 0 : 1 : (zipWith (+) fibs rest)

Какой глубины здесь рекурсия, по-твоему? При всем при том, эта строчка компилится и работает ...

И вот еще, почитай на досуге: http://en.wikipedia.org/wiki/Lazy_evaluation

Умный, да?
Вот вам "бесконечный цикл":
---
int i=0;
while (true)
{
    fprintf(stdout,"%d\n",i);
    if (++i>=10) break;
}
---
Так, вот, по-моему, определение это не бесконечный цикл, хотя и выглядит как бесконечный.

А вот уже "бесконечный цикл", который, по-моему, определению действительно
бесконечный - и тут уже ни один компилятор не поможет:
---
time_t t;
time (&t);
srand (t);
while (true)
{
    int i=rand();
    fprintf(stdout,"%d\n",i);
    if (++i>=(RAND_MAX/2)) break;
}
---

> Какой глубины здесь рекурсия, по-твоему?
Понятия не имею - я Haskell'я не знаю (пока)

То есть - понятия не имеешь, но мнение иметь (и высказывать) считаешь для себя допустимым. И кто ты после этого?

> Что там завуалированного?

Слишком много непонятных сущностей :) На самом деле, программа состоит
из описания игрового поля и "принтера". Вот и надо так писать :)


#include <iostream>

template < typename game, int x1, int y1, int x2, int y2, int n, int g=0, int x=x1, int y=y1 >
struct printer
{
    static void print( std::ostream& out )
    {
        out << (game::template cell< x, y, g >::alive ? "()" : "--");
        printer< game, x1, y1, x2, y2, n, g, x+1, y >::print( out );
    };
};

template < typename game, int x1, int y1, int x2, int y2, int n, int g, int y >
struct printer< game, x1, y1, x2, y2, n, g, x2, y >
{
    static void print( std::ostream& out )
    {
        out << std::endl;
        printer< game, x1, y1, x2, y2, n, g, x1, y+1 >::print( out );
    };
};

template < typename game, int x1, int y1, int x2, int y2, int n, int g, int x >
struct printer< game, x1, y1, x2, y2, n, g, x, y2 >
{
    static void print( std::ostream& out )
    {
        out << std::endl;
        printer< game, x1, y1, x2, y2, n, g+1, x1, y1 >::print( out );
    };
};

template < typename game, int x1, int y1, int x2, int y2, int n, int x, int y >
struct printer< game, x1, y1, x2, y2, n, n, x, y >
{
    static void print( std::ostream& out )
    {
        out << std::endl;
    };
};

template < int x, int y, int g >
struct cell
{
    static const int score = (
                              cell< x-1, y-1, g-1 >::alive +
                              cell< x  , y-1, g-1 >::alive +
                              cell< x+1, y-1, g-1 >::alive +
                              cell< x-1,   y, g-1 >::alive +
                              cell< x+1,   y, g-1 >::alive +
                              cell< x-1, y+1, g-1 >::alive +
                              cell< x  , y+1, g-1 >::alive +
                              cell< x+1, y+1, g-1 >::alive
                              );
                                    
    static const int alive = (score==2) ? cell< x, y, g-1 >::alive : (score==3) ? 1 : 0;

};

template < int x, int y > struct cell<  x,  y, 0 > { const static int alive = 0; };
template <> struct cell< -1, 0, 0 > { const static int alive = 1; };
template <> struct cell<  0, 0, 0 > { const static int alive = 1; };
template <> struct cell<  1, 0, 0 > { const static int alive = 1; };
template <> struct cell<  1, 1, 0 > { const static int alive = 1; };
template <> struct cell<  0, 2, 0 > { const static int alive = 1; };

struct game
{
    template < int x, int y, int g >
    struct cell : ::cell< x, y, g >
    {};
};

int main()
{
    printer< game, -3, -2, 4, 5, 5 >::print( std::cout );
    return 0;
};

Дык, я ж не о Haskell'е говорил всё это время!

Я вот подумал - может вам потренироваться и на IOCCC программы посылать? :-)
Всё же template'ы что не говори а добавляют неразберихи (также как и #define'ы)

Ах, да там же только C.. А так можно было бы поизвращаться :-))

> Так, вот, по-моему, определение это не бесконечный цикл, хотя и выглядит как бесконечный.

Вообще-то, речь шла о бесконечной рекурсии.

> Понятия не имею - я Haskell'я не знаю (пока)

Узнай. Правда, хорошо мозги прочищает =) Плюс к тому - просто красивый (чисто эстетически) язык.

2Луговский: кстати говоря, не знаешь, где можно было бы найти внятное описание хаскеллевских монад? Мне очень не нравится пользоваться тем, чего я не понимаю; а в имеющихся у меня книгах etc объяснения из разряда "это те самые монады, которые вы изучали на третьем году Math". Не изучали мы их =/

> Слишком много непонятных сущностей :) На самом деле, программа состоит из описания игрового поля и "принтера". Вот и надо так писать :)

Я специально хотел разнести рассчет следующего состояния и рекурсивную итерацию до N-го шага - имхо так логичней =) А клетки были запиханы в отдельный namespace, чтобы можно было кроме планера задать еще несколько фигур.

> Дык, я ж не о Haskell'е говорил всё это время!

Так и он говорил не о паскале. Я просто привел пример кода на языке, в котором изначально есть lazy evaluation - как наглядную демонстрацию (вычисление бесконечного списка за конечное время). Но дело в том, что на плюсовых шаблонах тоже можно это сделать - о чем и шла речь.

А уменя даже не скомпилилась

> Вообще-то, речь шла о бесконечной рекурсии.
Как бы не выглядела эта рекурсия, всё равно она преобразуется к конечной компилятором, а следовательно является "псевдобесконечной" :-)

>Как бы не выглядела эта рекурсия, всё равно она преобразуется к 
>конечной компилятором, а следовательно является "псевдобесконечной" :-)

Ты уверен? Практика - критерий истины:

$ cat Zz.hs
module Zz where
fibs@(_:rest) = 0 : 1 : (zipWith (+) fibs rest)
$ ghc -c Zz.hs && rm Zz.hs #Компилятор свое дело сделал, исходников больше нет
$ cat Xx.hs
import Zz
main = print $ fibs !! 10000
$ ghc Xx.hs Zz.o && ./a.out
336447 ... 66875 , всего больше 2000 цифр
$ cat Cc.hs
import Zz
main = print $ length fibs
$ ghc Cc.hs && ./a.out
Висим-с.

И как компилятор догадался при компиляции Zz, как я буду использовать массив fibs?

Ps: в догонку

Конечно, "список fibs" вместо "массив fibs". И вместо 10000 можно что угодно поставить. Естественно число получится другое;-)

> И как компилятор догадался при компиляции Zz, как я буду использовать массив fibs?
Никак не узнавал - скомпилировала как обыкновенный рукурсивный вызов и всё.
А template'ы они всегда компилируются без использования переходов в функцию - они именно "вставляются" в код (так же как и #define'ы). Доказательством думаю послужит то, что размер a.out после компиляции оригинального кода приведённого вначале этой темы составляет ~86 Кб, а если заменить
life_printer<glider::org, -2, -2, +4, +4, 5>::print(std::cout);
на
life_printer<glider::org, -2, -2, +4, +4, 2>::print(std::cout);
то уже ~37 Кб

> А template'ы они всегда компилируются без использования переходов в функцию -
> они именно "вставляются" в код (так же как и #define'ы).
Чёрт!!
Как я ошибался :-(
По-крайней мере gcc точно компилирует template'ы не как макросы, а как обычные функции.
Просто из-за того, что всюду написано, что template'ы это как бы расширенные макросы, я сделал вывод (преждевременный как оказалось), что они и компилируются также.. А оказалось, что нет :-//
Но почему же тогда размер бинарника от количества шагов в этой программке меняется?

> По-крайней мере gcc точно компилирует template'ы не как макросы, а как обычные функции.

Это ты откуда взял? Посмотрел на исходник?

Ты не прав =) Это он вызовы operator<< иногда забывает inline'ить. А собственно цифири там уже все подсчитаны и запиханы в код в виде констант, QED.

> Никак не узнавал - скомпилировала как обыкновенный рукурсивный вызов и всё.

Так ты все-таки скажи - там рекурсия конечная или бесконечная? =) А то у тебя получается, что когда на _уже скомпилированный_ код вызывается !! (получить N-й элемент), то она конечная - т.к. завершается. А когда вызывается функция length (длина списка), то рекурсия бесконечная - прога виснет. Ты все-таки определись =)

> Это ты откуда взял? Посмотрел на исходник?
Написал "подставную" прогу:
---
#include<stdlib.h>
#include<stdio.h>
#include<time.h>

template <class T>
T f (T a)
{
    fprintf (stdout, "%d\n", a);
    if (a>(RAND_MAX/2)) return a;
    else f<T>(rand());
    return 0;
}

main()
{
    time_t t;
    time (&t);
    srand (t);
    f<int>(rand());
}
---
Ну и разумеется ожидал что g++ зависнет. Ан нет!
Посмотрел после "g++ -S" и убедился, что call'ы есть (соответственно 2 штуки)