Здравствуйте, eao197, Вы писали:

E>Добрый день.

E>Навеяно Re[2]: Compile-time template library

Автор: Юрий Жмеренецкий
Дата: 25.10.05

.

E>Хотелось бы поговорить о наболевшем, о шаблонных наворотах. На примере compile-time вычислений в частности.

E>Вот мне и интересно, есть ли не академические примеры использования compile-time вычислений? И если есть, то что это за примеры, и оправдали ли себя compile-time вычисления в плане сопровождаемости?

Эх, чувствовал что придется это написать.

Только начну я немного издалека (что бы была понятна моя точка зрения), а именно с тех сущностей, которые начинаются с приставки 'мета'. Например, метапрограммирование. Что это такое? Часто применяемое определение этого термина гласит, что это всего лишь программирование на метаязыке. Метаязык это язык более высокого уровня чем 'объектный' язык, понятиями которого и оперирует метаязык. Зачем оно надо? Согласно теореме Геделя, как бы не стройна и логична была некая формальная система, найдется утверждение(выраженное терминами этой ФС) об истинности которого невозможно ничего сказать. Кстати существование многих парадоксов обусловлено именно существованием таких утверждений. Чтобы можно было делать выводы об истиности таких утверждений приходится приходится вводить новый уровень формализации(или метаязык в рассматриваемом контексте). Здесь можно вспомнить Тарского (который и ввел понятие 'метаязык') с его 'белым снегом':

"Снег белый" — утверждение на объектном языке,
"Утверждение "Снег белый" истинно" — утверждение на метаязыке.

Отсюда следует заключение, что на метаязыке можно _доказывать_ утверждения, выраженные в терминах объектного языка (можно поднять еще на ступеньку выше и 'доказывать' метязык и т.д).

Это было небольшое отступление. Теперь про метапрограммирование.

Метапрограммы оперируют 'объектными программами' либо их фрагментами. Существует две (основных и местами перекрывающихся) категории метапрограмм — генераторы и анализаторы. К первым можно отнести различные DSL, генераторы компиляторов и т.п. Анализирующие метапрограммы используют информацию об объектном языке для получения некого результата. Результатом может являться, например оптимизированный вариант исходной программы, набор некой статистики и т.п.

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

В первую очередь это производительность, которую можно рассматривать с двух точек зрения:
1)Удобство и скорость написания программ.
Например boost::spirit, и тому подобные domain-oriented средства заметно упрощают процесс написания программ. Также упрощается модификация и дальнейшие сопровождение.

1)Производительность как таковая. Для достижения максимального роста производительности необходимо идентифицировать и выполнить как можно больше вычислений в течении компиляции (это утверждение спорно — разумеется нужно соблюдать какие-либо ограничения, но в данном контесте, смысл, я думаю понятен). Таким образом, процесс оптимизации распадается на две фазы – анализа и специализации. Анализ (Binding-Time Analysis) – это процесс определения вычислений, выполнение которых возможно до времени выполнения. Фаза специализации использует результаты BTA для порождения оптимизированных вариантов участков кода. Хорошим примером для С++ является возможность определения POD классов (фаза анализа) с дальнейшим применением к ним bitwise копирования (специализация).

Доказательство правильности программ. Так как программы пишут на неком формальном языке, то анализируя эту программу можно обнаружить ее свойства. Эти свойства могут быть использованы для оптимизации (см.выше), выявления ошибок и доказательства правильности. Более того, при модификации участков объектного кода необходимо гарантировать что оптимизированная программа по функциональности будет идентична исходной (особенно актуально для оптимизирующих компиляторов).

Это основные (ИМХО) плюсы, которые дает метапрограммирование. Еще можно добавить получение различных метрик, графов зависимостей и т.п.

О сложности метапрограммирования.
Чем обусловлена сложность метапрограммирования? Как не странно ответ банален – сложностью программ. Для управления сложностью программных систем программисты используют множество механизмов встроенных в язык, например систему типов, области видимости, разнообразные механизмы абстракции. При применении метапрограмм эта сложность возрастает дважды, поскольку используется фактически два языка. Хорошая система метапрограммирования имеет дело непосредственно со сложностями объектного языка(опять же boost::spirit). В противном случае необходимо явно описать специфику объектного языка(yacc/cocor, etc.), что в свою очередь еще больше увеличивает сложность метапрограммирования (когда метаязык и целевой язык не совпадают, иногда пользуются термином 'гетерогенное метапрограммирование').

Все вышесказанное является моим пониманием метапрограммирования.

О cttl.

Во-первых cttl это _экспериментальная_ бибилиотека. Писалась (и пишется) для построения сложных анализаторов кода(то что выложено — это далеко не все) и КА. Не заточена для обработки чисел. Основное назначение cttl::recursion предоставить максимально обощенный интерфейс для рекурсии. Первоначальные параметры — исходный тип, функция перехода к следующему(next), критерий остановки(stop) и тело рекурсии(body). Причем основной фичей является то что в этих функциях можно использовать данные о: текущем значении, номере итерации и обрабатываемом элементе. Функции next_list для перехода к следующему списку типа(как и plus в приведенных примерах) является _очень_ примитивной для перехода к следующему элементу. В реальности там сильно ветвящийся алгоритм. Попросили показать как считать простые числа используя cttl::recursion — показал, и это говорит о том что даже такие вещи можно выразить, хотя и выглядит как стрельба из пушки по воробьям. Пример с факториалам я привел для сравнения, поскольку это наверное самый первый пример с которого начинают глубоко изучать шаблоны.

О compile-time(CT) вычислениях.

Работа с числами в CT действительно не часто требуется(ИМХО). Мне например, вряд ли понадобится считать простые числа. Числа можно рассматривать как некие аттрибуты типов(размер, позиция), в этом случае несложные алгоритмы вполне оправданы. Про дробные числа здесь:"Floating point arithmetic in C++ templates" . Цитата оттуда: "The code to generate the convolution kernel takes 7 minutes to compile on a Xeon 2.4". Красиво, но реальное использование, IMHO сомнительное.

На мой взгляд гораздо более востребованы алгоритмы оперирующие типами(и их списками)
для последующей генерации классов/функций/учасков кода.