Рекурсивные вычисления на шаблонах C++

struct NullEnv;

Тег ты объявил, а почему не дал хотя бы пустого определения?

/cast anonymous

Бесполезной действие.

Y = λf.(λx.f (x x)) (λx.f (x x))

попробуй

Y = λf.(λx.(f λy.((x x) y)) λx.(f λy.((x x) y)))

У нас с коллегами недавно была идея дописать в какой-нибудь компилятор C++ поддержку хвостовой рекурсии в шаблонах, и писать код чисто на них. Пришлось бы, правда, везде с собой таскать компилятор (вернее теперь уже интерпретатор темплейтов), и всё это чудовищно тормозило бы, но разве это не истинный C++ way?

попробуй
Y = λf.(λx.(f λy.((x x) y)) λx.(f λy.((x x) y)))

Пробовал же (это Z-комбинатор).

Тег ты объявил, а почему не дал хотя бы пустого определения?

Спасибо, что напомнил. Уберу определения и с Lam, Ref и App. Идея в том, чтобы оставить интерпретатор в пределах системы типов языка. Отсутствие определений — намёк на то, что всё должно происходить в пределах тайпдефов.

Бесполезной действие.

Я в курсе :3

Раскуривание стандарта ни к чему конкретному не привело. Медитация над кодом дала догадку, что typename Temp<A, B, C>::dependent_type приводит к обязательному раскрытию всех A, B, C. Это, видимо, и мешает реализовать рекурсию. Хотя, конкретный пункт стандарта, требующий такого «энергичного» поведения, (пока) не найден.

Рекурсию по идее можно будет вшить в язык вместе с новой конструкцией Rec, определяющей рекурсивные абстракции. Её с горем пополам можно реализовать без зацикливания, введя «ленивые окружения».

Однако, вдобавок к этому необходимо реализовать ленивый If, который вычисляет только одну из веток, а вторую вообще не трогает. С ним пока затык.

Уии, работает. С ленивым If и Z-комбинатором. Код закоммичу днём уже.

ilammy@ferocity ~/dev/tlc $ time g++ -std=c++11 fact.cpp -DARG=6 

real    0m12.661s
user    0m12.245s
sys     0m0.341s

ilammy@ferocity ~/dev/tlc $ ./a.out
720

Contrary to popular belief, язык шаблонов C++ не является тьюринг-полным. Ибо глубина раскрытия шаблонов ограничена, причём чем-то маленьким, по крайней мере, если не крутить настройки.

приводит к обязательному раскрытию всех A, B, C.

Естественно. Потому что сгенерированный код будет содержать что-то вроде Temp_A_B_C, которое не имеет никакого отношения к Temp_D_E_F. То есть, ему надо точно знать эти A, B и C.

Contrary to popular belief, тьюринг-полных языков вообще не существует, если пользоваться твоей логикой. Ведь память ограничена.

Temp<A, B, C>::dependent_type

Как же вы заебали. Нету в плюсах никаких dependent_type и даже ничего похожего на них нету.

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

Contrary to popular belief, язык шаблонов C++ не является тьюринг-полным. Ибо глубина раскрытия шаблонов ограничена, причём чем-то маленьким, по крайней мере, если не крутить настройки.

Рекомендация: Recursively nested template instantiations [1 024]. Реально implementation defined, т.е. может и не быть лимитировано вообще.

Contrary to popular belief, язык шаблонов C++ не является тьюринг-полным. Ибо глубина раскрытия шаблонов ограничена, причём чем-то маленьким, по крайней мере, если не крутить настройки.

Афаик, для C++03 — 17, для C++11 — 1024. Тем не менее, даже машина Тьюринга исходит из предположения, что бесконечная лента всё же «существует». Поэтому, думаю, и Тьюринг полноту шаблонов следует доказывать, исходя из предположения, что память у компилятора не заканчивается и раскрывать шаблоны он может неограниченно.

Как же вы заебали. Нету в плюсах никаких dependent_type и даже ничего похожего на них нету.

Иди... скажи это комитету по стандартизации. Я знаю, что в C++ нет dependent types в том самом смысле. Но в стандарте типы, объявляемые внутри шаблонов, называются именно так.

Мне кажется, это диверсия. «Функтор» уже засрали своим дебильным ООП, теперь вот за «зависимые типы» взялись.

Расслабься. Просто нежизнеспособное ФП отмирает и заменяется более практичными вещами.

Компиль сlang++'ом там нет километров ошибок - проще будет разобраться в ошибках компиляции

Афаик, для C++03 — 17, для C++11 — 1024

Да, верно. My bad, не знал.

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

Так и запишем: свора быдла затравила благородного пуриста.

C++ compile-time Prolog interpreter