Комментарии 63
Допустим, сформировали «дерево типов», вида int->«int», double->«double» и т.д. Тогда можно будет по типу получать его строковое название на этапе компиляции. ОК, метапрограммирование как бы работает. (другого примера с практическим применением пока что не могу придумать). Однако это будет гораздо сложнее для написания, чем просто структуры вида ToString::name, создание которых будет обёрнуто в макрос и не потребует никаких деревьев и чего-то ещё и будет поддерживаться любым старым компилятором…
В общем, хочу какой-то реалистичный пример использования того, чего вы тут натворили.)
UPD: Перечитал предпоследний абзац. Это что-то типа boost::spirit получилось что ли?
В общем, хочу какой-то реалистичный пример использования того, чего вы тут натворили.)
UPD: Перечитал предпоследний абзац. Это что-то типа boost::spirit получилось что ли?
сформировали «дерево типов»
И сразу вопрос — а зачем? Ответ в вопросе: если в задаче требуется создание дерева и операции с ним на этапе компиляции, то вот и пример) Описан инструментарий, о более реальном(ых) же примерах его применения сказано несколько слов в соответствующем разделе. Вы правы, для описаной вами задачи макроса действительно будет достаточно. Одной из целей статьи, однако, было показать, как можно обходиться без макросов в довольно нетривиальных ситуациях.
Про Spirit — да, в каком-то смысле, вы правы: упрощенно, финальная задача — получить (но на этапе компиляции) некоторый предметно-ориентированный автомат.
Существует несколько алгоритмов прямой конвертации регулярного выражения в ДКА (детерминированный конечный автомат), его распознающий, часть которых оперирует т.н. синтаксическим деревом, которое по своей природе «не более чем» бинарное. Таким образом, бинарное дерево поиска времени компиляции — составная часть
Если под «синтаксическим деревом» вы имеете ввиду АСД представляющее выражение регулярное выражение, то это очень странное утверждение. Потому как АСД не является деревом поиска (даже если оно оказалось бинарным). Так что не очень понятно, каким образом у вас получается, что бинарное дерево поиска — это составная часть?
И другой вопрос, вы пробовали замерять время компиляции на разных примерах использования все этого «чуда»? Если да, то, пожалуйста, поделитесь результатами.
Речь не об АСД, в эпилоге имеется в виду конкретный алгоритм типа «first/last/follow pos» (пример описания, самое простое, что сразу нашёл).
Нет, готовых измерений производительности нет, но вопрос интересный, доп. флагами компилятора можно включить вывод времени фаз компиляции. Сделаю замеры и обновлю комментарий/эпилог статьи.
Нет, готовых измерений производительности нет, но вопрос интересный, доп. флагами компилятора можно включить вывод времени фаз компиляции. Сделаю замеры и обновлю комментарий/эпилог статьи.
То что описано по ссылке ничто иное как АСД, и оно не является деревом поиска.
Каюсь, согласен, это частный случай АСД, однако данное конкретное дерево имеет узлы степени не более 2 и может быть построено рекусивным спуском особым сравнителем и типами-ключами. Вообще, описанное дерево имеет косвенное отношение к указанной задаче, и было, можно сказать, тренировкой и проверкой выразительных возможностей.
То, что надо, для взрыва мозга и практики в C++, но не в субботу:(
Давно не пишу на плюсах и надеюсь больше не буду, поэтому абсолютно всё равно про что статья и какой смысл она несёт, но большое спасибо за интересный С++, а не С с классами.
Не понравилось изложение материала. Сумбурно, неточно, неполно.
Сложность такой реализации search — опять-таки O(n) инстанцирований, глубина — h (высота дерева). «Стоп!» — воскликнет удивленный читатель, — «а как же логарифмическая сложность поиска и всё такое?»
Во-первых, для логарифмической сложности требуется сбалансированность дерева. Здесь про это нет ни слова.
Во-вторых, остановка ненужных конкретизаций шаблонов чрезвычайно важна.
камни в сторону std::conditional
Летят совершенно напрасно.
std::conditional недостаточно для остановки рекурсии
Это не так. std::conditional здесь не при чём.
Просто нужно конкретизировать шаблон не внутри, а снаружи.
Неверно:
std::conditional
<
condition,
expression1::type,
expression2::type
>
::type;Верно:
std::conditional
<
condition,
expression1,
expression2
>
::type::type;это задача для более глубокого исследования и в данном случае будет являться преждевременной оптимизацией
Это не вопрос для исследования, и это не оптимизация. Это необходимое условие.
Без остановки прохода по ненужным веткам и без сбалансированности такое "дерево поиска" — внимание — хуже простого линейного поиска.
Заголовок спойлера
в стандарте C++14 планируется ввести
Так 17-й же уже на подходе.
Спасибо за замечания. Это была, так сказать, проба пера*, и некоторый сумбур, безусловно, присутствует.
По пунктам:
Во-первых, для логарифмической сложности требуется сбалансированность дереваСтатья не претендует на звание исчерпывающего руководства по алгоритмам и структурам данных (она и так получилась весьма объёмной даже со спойлерами), поэтому я намеренно опускал некоторые моменты: сведующий читатель поймёт, о чём речь, остальные же получат повод загуглить, если эти моменты действительно им интересны. И да, корень «логарифм» встречается только в одном месте в тексте, а сырое бинарное дерево не имеет балансировки (и необходимость в ней, вообще говоря, зависит от решаемой задачи*).
Просто нужно конкретизировать шаблон не внутри, а снаружиВот это очень интересное замечание, спасибо, я обращу на конкретизацию особое внимание. Вы хотите сказать, что такой подход автоматически отключит инстанцирование
search или insert на неверном пути? Пока я в этом сомневаюсь.Без остановки прохода по ненужным веткам и без сбалансированности такое «дерево поиска» хуже простого линейного поиска.О сбалансированности было сказано ранее, об отключениях — согласитесь, без сбалансированности оно не имеет особого смысла :) Надо сказать, слово «поиска» в определении немного сбивает с толку: кому-то может показаться, что описанная структура — это готовый мета-
std::map, однако это именно бинарное дерево (не более) с минимально необходимым интерфейсом.Так 17-й же уже на подходе.Справедливо. У меня до сих пор присутствует некоторая инертность относительно новых и грядущих стандартов — политика партии требует стабильности компиляции.
Наблюдая такие статьи, каждый раз думаю: как же плюсам не хватает адекватного, встроенного в стандарт языка редактирования AST на этапе компиляции…
Можете привести пример. когда редактирования AST на этапе компиляции может быть полезно или необходимо? Правда не понимаю.
Я думаю, автор (@semenyakinVS) скорее хотел обратить внимание на более общий вопрос рефлексии в C++ (см. его цикл статей, рассказывающий о разработке библиотеки поддержки рефлексии).
А так да, действительно, каждый день просто сажусь и описываю AST в compile-time. Вот скоро порт
А так да, действительно, каждый день просто сажусь и описываю AST в compile-time. Вот скоро порт
boost::spirit на язык шаблонов закончу, вот тесты на static_assert дописываю, жаль, компилируются по две недели…Да. Вы правы. Однако я имел в виду не только рефлексию. Рефлексия — это лишь доступ к AST. Я же подразумевал нечто большее. Полноценное изменение AST во время прохода по коду парсера/компилятора.
Возможность редактирования AST, де факто, уже есть в С++. Очевидно, шаблоны позволяют подменять узлы синтаксического дерева. В описании шаблонного типа мы помечаем узлы для подмены с помощью аргументов, после чего выполняем подстановку типов или констант в указанные места. Однако когда речь заходит о том, чтобы выполнять подобную подмену на основании каких-нибудь свойств существующего дерева (то есть работа на стыке рефлексии и шаблонов) — начинаются костыли с type traits, рекурсивными списками типов и, в сложных случаях, с макросами.
От этого плохо всем. Плохо компилятору — он мучается с рекурсивными шаблонами и затягивает время сборки кода. Плохо парсеру — мы теряем возможность использования фишек IDE (автоподстановка, индексы типов). Плохо программисту — он вынужден ковыряться в жутких функциональных конструкциях без получения внятных сообщений об ошибках. Плохо экосистеме в целом — функционально-ориентированные шаблоны вызывают оторопь у неофитов С++.
Редактирование AST позволило бы навести порядок, вынеся кодогенерацию из кода основной программы в отдельную категорию «поведения времени компиляции» программы.
Я не думал пока о конкретных языковых конструкциях, с помощью которых можно было бы редактировать AST. Однако в процессе написания комментария набросал некоторые имеющиеся сумасшедшие мысли:
P.S.: Просьба не сильно пинать. Возможно, тут я написал далеко не самые умные вещи. Однако, во-первых, иногда неумные вещи могут порождать осмысленные дискуссии. Во-вторых, мысль о необходимости доступа к AST завладела моим сознанием не на ровном месте. Будучи не оформленной окончательно, она сформировалась после прочтения интервью Эрика Ниблера, а также мыслей некоторых других умных людей (ссылка на мой комментарий к статье о судьбах С++: в комментарии приведена целевая цитата Гора Нишанова из статьи).
P.P.S.: Ещё раз приношу извинение за большой объём комментария.
Возможность редактирования AST, де факто, уже есть в С++. Очевидно, шаблоны позволяют подменять узлы синтаксического дерева. В описании шаблонного типа мы помечаем узлы для подмены с помощью аргументов, после чего выполняем подстановку типов или констант в указанные места. Однако когда речь заходит о том, чтобы выполнять подобную подмену на основании каких-нибудь свойств существующего дерева (то есть работа на стыке рефлексии и шаблонов) — начинаются костыли с type traits, рекурсивными списками типов и, в сложных случаях, с макросами.
От этого плохо всем. Плохо компилятору — он мучается с рекурсивными шаблонами и затягивает время сборки кода. Плохо парсеру — мы теряем возможность использования фишек IDE (автоподстановка, индексы типов). Плохо программисту — он вынужден ковыряться в жутких функциональных конструкциях без получения внятных сообщений об ошибках. Плохо экосистеме в целом — функционально-ориентированные шаблоны вызывают оторопь у неофитов С++.
Редактирование AST позволило бы навести порядок, вынеся кодогенерацию из кода основной программы в отдельную категорию «поведения времени компиляции» программы.
Я не думал пока о конкретных языковых конструкциях, с помощью которых можно было бы редактировать AST. Однако в процессе написания комментария набросал некоторые имеющиеся сумасшедшие мысли:
Предупреждаю - много текста... Я не шучу - действительно много
1. Реализация шаблонов.
Любители ФП могут меня запинать — но я не устану повторять: людям неудобно мыслить рекурсивными категориями. Мы с детства читаем текст последовательно, не сохраняя в голове точки возврата (например, текст в скобках (даже если он выстроен логично (в рамках выбранной области) и без рекурсивных отсылок (хотя сложно представить себе рекурсию в тексте)) воспринимается тяжело).
Если бы логика генерации шаблонных классов описывались аналогично макросным проверкам — имхо, шаблоны воспринимались бы проще. Например:
2. Обработка списков типов.
Обращаю внимание противников RTII — генерация специализаций подобной функции не подразумевает использование RTII. Рефлексийные сведения нужны исключительно на этапе парсинга/компиляции кода. И, опять-таки, мы не засоряем код утилитными типами-специализациями type_traits.
3. Генерация имён типов.
Подобное использование кодогенерации заменило бы собой лексически/синтаксически нейтральные макросы.
4. Напоследок — несколько сумбурных мыслей по поводу кодогенерации:
Сейчас всё это выглядит очень неуклюже. Как я указал с самого начала — данные мысли формулировались на ходу, в процессе написания комментария (извиняюсь, кстати, за его размер). Чтобы язык редактирования AST стал лучше — нужны усилия умных людей, намного умнее меня.
Заканчивая, перечислю почему мне кажется, что не-функционально-ориентированная кодогенерация была бы хороша:
0. Она сделала бы написание и чтение кода, требующего кодогенерации, проще.
1. Она вытеснила бы лексически/синтаксически нейтральные макросы.
2. Описанная кодогенерация могла бы упростить оптимизацию кода. На замену утилитным типам type_traits (которые регистрируются компилятором как типы, со всеми вытекающими последствиями) пришли бы инструкции, априори существующие лишь на этапе кодогенерации и созданные исключительно для решения задач котогенерации.
3. Описанная кодогенерация могла пригодиться при введении концепции модулей в С++. Код модулей с элементами кодогенерации мог бы сохраняться в виде «промежуточное AST + логика кодогенерации для формирования кода на этапе сборки приложения/динамической библиотеки».
Любители ФП могут меня запинать — но я не устану повторять: людям неудобно мыслить рекурсивными категориями. Мы с детства читаем текст последовательно, не сохраняя в голове точки возврата (например, текст в скобках (даже если он выстроен логично (в рамках выбранной области) и без рекурсивных отсылок (хотя сложно представить себе рекурсию в тексте)) воспринимается тяжело).
Если бы логика генерации шаблонных классов описывались аналогично макросным проверкам — имхо, шаблоны воспринимались бы проще. Например:
Странный псевдокод
Примечание: Проверки кодогенерации, описанные здесь, выполняются на этапе парсинга/компиляции кода; по-умолчанию после выполнения кодогенерации никакие необходимые для кодогенерации данные не сохраняются.
template< typename T_Type >
class Array {
private:
@if (T_Type is bool) [[ char *_bitarray; ]]
@else [[T_Type *_array; ]]
public:
@if (T_Type.isScalar) [[ T_Type ]] @else [[T_Type &]]
operator [](size_t inIndex) {
@if(T_Type is bool) [[
return _bitarray[inIndex/8*sizeof(char)] & (1 << (inIndex%8*sizeof(char)));
]]
@else [[
return _array[inIndex];
]]
}
}
Примечание: Проверки кодогенерации, описанные здесь, выполняются на этапе парсинга/компиляции кода; по-умолчанию после выполнения кодогенерации никакие необходимые для кодогенерации данные не сохраняются.
2. Обработка списков типов.
Странный псевдокод
template< typename ... T_List >
void print(T_List ... inArgs) {
@for (Variable : inArgs) [[
std::cout << Variable.name;
std::cout << Variable.type.name;
@if (Variable.type.isScalar) [[
std::cout << Varuable.value;
]] @else [[
std::cout << Varuable.value@.toString();
]]
std::cout << std::endl;
]]
}
Обращаю внимание противников RTII — генерация специализаций подобной функции не подразумевает использование RTII. Рефлексийные сведения нужны исключительно на этапе парсинга/компиляции кода. И, опять-таки, мы не засоряем код утилитными типами-специализациями type_traits.
3. Генерация имён типов.
Странный псевдокод
@function VectorsGenerator(Type inType, Int inArgumentsCount) [[
struct Vector##inType.name.capitalized##inArgumentsCount {
@if (inArgumentsCount == 1) [[
Type x;
]] @elseif (inArgumentsCount == 2) [[
Type y;
]] @elseif (inArgumentsCount == 3) [[
Type z;
]] @else [[
@COMPILE_ERROR("Incorrect vector generating arguments count")
]]
};
]]
@decl VectorsGenerator(int, 2);
@decl VectorsGenerator(float, 3);
int main() {
VectorInt2 theIntVector;
VectorFloat3 theFloatVector;
@decl VectorsGenerator(double, 1) theDoubleOneDementional;
}
Подобное использование кодогенерации заменило бы собой лексически/синтаксически нейтральные макросы.
4. Напоследок — несколько сумбурных мыслей по поводу кодогенерации:
Не очень много текста под катом
1. В рамках кодогенерации можно ввести ввести функции (выше уже описана такая функция), а также переменные (для сохранения типов, например… можно сделать возможность «собирать» классы из методов и полей — прямо как это делается в динамических языках, но на этапе компиляции).
2. С описанным подходом достаточно неплохо совместились бы концепты. Фактически, они описывают что-то вроде интерфейса типа, описывают тип типа.
2. С описанным подходом достаточно неплохо совместились бы концепты. Фактически, они описывают что-то вроде интерфейса типа, описывают тип типа.
Сейчас всё это выглядит очень неуклюже. Как я указал с самого начала — данные мысли формулировались на ходу, в процессе написания комментария (извиняюсь, кстати, за его размер). Чтобы язык редактирования AST стал лучше — нужны усилия умных людей, намного умнее меня.
Заканчивая, перечислю почему мне кажется, что не-функционально-ориентированная кодогенерация была бы хороша:
0. Она сделала бы написание и чтение кода, требующего кодогенерации, проще.
1. Она вытеснила бы лексически/синтаксически нейтральные макросы.
2. Описанная кодогенерация могла бы упростить оптимизацию кода. На замену утилитным типам type_traits (которые регистрируются компилятором как типы, со всеми вытекающими последствиями) пришли бы инструкции, априори существующие лишь на этапе кодогенерации и созданные исключительно для решения задач котогенерации.
3. Описанная кодогенерация могла пригодиться при введении концепции модулей в С++. Код модулей с элементами кодогенерации мог бы сохраняться в виде «промежуточное AST + логика кодогенерации для формирования кода на этапе сборки приложения/динамической библиотеки».
P.S.: Просьба не сильно пинать. Возможно, тут я написал далеко не самые умные вещи. Однако, во-первых, иногда неумные вещи могут порождать осмысленные дискуссии. Во-вторых, мысль о необходимости доступа к AST завладела моим сознанием не на ровном месте. Будучи не оформленной окончательно, она сформировалась после прочтения интервью Эрика Ниблера, а также мыслей некоторых других умных людей (ссылка на мой комментарий к статье о судьбах С++: в комментарии приведена целевая цитата Гора Нишанова из статьи).
P.P.S.: Ещё раз приношу извинение за большой объём комментария.
Спасибо за развернутый ответ. Ещё такой еретический вопрос: если мы пытаемся реализовать на языке конценцепцию, которая, судя по синтаксису и удобочитаемости, чужда этому языку, то почему не добавить кодогенератор на скриптовом языке как pre-build? А про сборку типов из классов и методов… это похожа на гибрид виртуальной таблицы и описания железа с помощью баз данных
почему не добавить кодогенератор на скриптовом языке как pre-build
Подозреваю, что это был сарказм — однако подобная реализация тоже возможна.
По поводу чуждости языку — я согласен с тем, что текущий вариант кодогенерации выглядит уродливо. Однако если показать некоторые многоэтажные шаблонные конструкции программисту Java или C# — они также воспримут это как извращение. Я проверял. На мой взгляд, их реакция обоснована — причём не только непривычкой создания кода на языке С++.
это похожа на гибрид виртуальной таблицы
Отчасти. В динамических языках в классы можно включать как поля (ivars), так и методы (например, первая ссылка для java). В С++ это может происходить на этапе компиляции. И, следует заметить, данную фичу я описал как возможную — далеко не факт что она будет реально нужна.
описани[е] железа с помощью баз данных
Как я понял, к кодогенерации статья относится в том смысле, что в случае с кодогенерацией мы описываем некий каркас для класса, который потом расширяем определённым образом. Если так — это несколько отдалённая ассоциация, но да. В чём-то похоже.
Оффтоп
Статья, которую вы привели, несколько родственна одной моей давней идее. Она заключалась в создании пакетного менеджер для С++, в рамках экосистемы которого выделялся бы слой системных пакетов. Фактически, прокси над драйверами устройств компьютера (RAM, CPU, HDD, и т.д.), объектно-ориентированное API которых с разной степенью точности описывал бы поведение соответствующих устройств. Прикладные пакеты жили над этим API (например, подключая RAM как зависимость и аллоцируя память исключительно через методы класса-абстракции RAM), а пакетный менеджер выступал в качестве такой себе тонкой виртуальной машины, выбирающей пакеты под ориентировочную конфигурацию целевого компьютера (как выяснилось позже, эта архитектура чем-то напоминала архитектуру игры doom).
Эх… Вспомнил весь этот мой код — аж ностальгия взяла. Спасибо за ссылку.
Эх… Вспомнил весь этот мой код — аж ностальгия взяла. Спасибо за ссылку.
Насколько я понял, цель описанной кодогенерации — автоматическое создание сущностей типов по описанию свойств (полей) и умений (методов) и последующее использование этого boilerplate code в обычном ООП, т.е. пишем код в уверенности, что всё необходимое уже задекларировано/описано, а в определенных случаях создано и инициализировано. Вы эту мысль пытались донести, или я опять нафантазировал?
Подозреваю, что это был сарказм — однако подобная реализация тоже возможна.
Нет, я серьёзно. Пытался понять, как писать одновременно переносимый и быстрый код для разных микроконтроллеров. варианты: жуткие макросы и внешний кодогенератор на скриптоязыке. Что так, что так получается уродливо и тяжко в поддержке
объектно-ориентированное API которых с разной степенью точности описывал бы поведение соответствующих устройств.
Да, удобно, я такое решение тоже видел: описание устройств в micro-manager
Вы эту мысль пытались донести, или я опять нафантазировал?
Не совсем. Цель описанной кодогенерации — иметь возможность использовать нефункциональные подходы при описании сложных, зависящих от контекста шаблонных типов.
Что так, что так получается уродливо и тяжко в поддержке
Да. Я сразу признал что сейчас это выглядит нелепо. Однако моя мысль заключалась в том, что кодогенераторы могут быть ближе к выражению семантики, которая сейчас описывается с помощью шаблонов… Собственно, если почитать существующие в данный момент статьи о рефлексии — достаточно часто люди приходят к идее использования third party кодогенераторов на базе всяких clang-ов.
Да, удобно, я такое решение тоже видел
Спасибо за ссылку. Интересно почитать… На мой взгляд, подход с описанием железа через дешёвые абстракции очень естественен для такого системного языка как С++.
Спасибо за кулуарный диалог. Как обещал, пишу комментарий к статье.
Пожалуй, одно из основных преимуществ нефункциональной кодогенерации, которое я забыл упомянуть — такую кодогенерацию легче отлаживать. Можно ставить компайл-брейкпоинты на логику кодогенерации и пошагово отслеживать процесс модификации AST. Конечно, важно разумно определить точки входа в блоки кодогенерации и порядок их исполнения — но, в целом, это будет всяко лучше чем ломать глаза о десятистраничные скобочные сообщения об ошибке.
P.S.: На одной плюсовой тусовке, помню, кто-то хвастался тем, что дампил шаблонные ошибки компиляции в файл и парсил файл дополнительной тулзой. Подчеркну — хвастался. На мой взгляд, это говорит о достаточно нездоровой атмосфере в сообществе языка.
Пожалуй, одно из основных преимуществ нефункциональной кодогенерации, которое я забыл упомянуть — такую кодогенерацию легче отлаживать. Можно ставить компайл-брейкпоинты на логику кодогенерации и пошагово отслеживать процесс модификации AST. Конечно, важно разумно определить точки входа в блоки кодогенерации и порядок их исполнения — но, в целом, это будет всяко лучше чем ломать глаза о десятистраничные скобочные сообщения об ошибке.
P.S.: На одной плюсовой тусовке, помню, кто-то хвастался тем, что дампил шаблонные ошибки компиляции в файл и парсил файл дополнительной тулзой. Подчеркну — хвастался. На мой взгляд, это говорит о достаточно нездоровой атмосфере в сообществе языка.
я вас обрадую: концепты, constexpr if и decltype вкупе друг с другом как раз таки позволяют сделать всё вами предложенное. Кроме автоматической генерации имен классов. К черту её, имо.
О, интересно. Думал, эти штуки будут двигать язык в сторону всё того же шаблонного ФП… Значит будем ждать и надеяться на то, что всё будет хорошо.
Спрошу ещё — вы не встречали, случайно, каких-нибудь хороших статей/обзоров с примерами описанного использования этих новых фич языка? Любопытно было бы почитать. Если прям сходу нет — то ладно. Сам нагуглю.
Пожалуй, соглашусь. Variatic template отменяют необходимость в данной фиче для, например, функторов под разное количество аргументов (как это было в старом fastdelegate, созданном без поддержки С++11), а предложенный мною кейс — это вообще пережиток С, где для имитации перегрузки функций нужно было выполнять их декорирование вручную.
Спрошу ещё — вы не встречали, случайно, каких-нибудь хороших статей/обзоров с примерами описанного использования этих новых фич языка? Любопытно было бы почитать. Если прям сходу нет — то ладно. Сам нагуглю.
Кроме автоматической генерации имен классов. К черту её, им[х]о
Пожалуй, соглашусь. Variatic template отменяют необходимость в данной фиче для, например, функторов под разное количество аргументов (как это было в старом fastdelegate, созданном без поддержки С++11), а предложенный мною кейс — это вообще пережиток С, где для имитации перегрузки функций нужно было выполнять их декорирование вручную.
Энтузиасты пилят совершенно нереальные вещи. Например, паттерн матчинг на C++, даже синтаксис приемлемый, и без макросов (!).
Ещё посмотрите на
Ещё посмотрите на
constexpr if — фича C++17. Вообще, по мощности C++17 должен получиться тортом. Ждём и желаем удачи (и душевных сил) разработчикам компиляторов!Пожалуй, скажу ещё пару слов о
constexpr if. В описании есть несколько важных моментов, и самыми вкусными являются эти:The return statements in a discarded statement do not participate in function return type deduction.
...if condition is not value-dependent after instantiation, the discarded statement is not instantiated when the enclosing template is instantiated.т.е.
constexpr функции отныне действительно смогут «конструировать» типы и останавливать рекурсию по типам (с некоторыми оговорками). Рис возвращается в плов.там еще вкуснота в правилах подавления ветки: подавленный код проверяется на семантическую корректность не полностью. Например, SFINAE печать значения:
void func (auto arg) {
if constexpr(requires { cout << arg; })
cout << arg << endl;
else
cout << "(obj of type " << typeid(arg).name() << ")" << endl;
}
Вы ограничены C++11? Если да, то почему? В C++14 многое можно сделать без шаблонов в constexpr.
Не совсем корректно:
Все алгоритмы в статье возвращают именно типы, о наделении же узлов данными-членами сказано несколько слов в Применении.
constexpr-функции всё-таки не способны создавать новые типы (в зависимости от значений аргументов), а если применять вывод возвращаемого типа из типов аргументов через auto a la C++14, то задача скатывается к старым добрым шаблонам.Все алгоритмы в статье возвращают именно типы, о наделении же узлов данными-членами сказано несколько слов в Применении.
Всякие сложности (например, операции с числами) можно выполнить в контексте функции, а возвращаемое значение — использовать в качестве аргумента шаблона (пример).
Понял замечание, согласен, такой подход был бы хорош в случае, если бы узлы хранились в плоском кортеже, а структура дерева описывалась бы последовательностями индексов. В случае же, когда навигация осуществляется непосредственно по вложенным псевдонимам (т.е. так, как дерево описано в статье), «считать» как бы ничего и не остаётся, нужно просто явно применять рекурсивные алгоритмы навигации. В статье есть упоминание о неединственности представления дерева.
Спасибо! Хотя я и считаю, что на практике желание шаблонно пометапрограмировать нужно строго контролировать, но грамотные погружения в эту тему всегда вызывают интерес и уважение! Это одна из возможностей, которая редко требуется, но в этих случаях без нее никуда и она творит чудеса!
Не согласен с предыдущим комментатором. Такого качественного материала, который будет понятен даже минимально сведущему в шаблонах C++ и метапрограммированию человеку, давненько уже не было на просторах Хабра. Особенно порадовала внимательность к «мелочам», как то: адекватное форматирование кода и последовательность изложения.
Если настоящая статья вызовет интерес и найдёт своего читателя, я с удовольствием продолжу тему метапрограммирования (и, возможно, не только) в следующих публикациях.
O(nn) шаблонов этому человеку!
Большое спасибо за статью!
Очень грамотно и интересно написано, буду ждать продолжения
Очень грамотно и интересно написано, буду ждать продолжения
Блин, чувак, ты офигенен! Надо будет на досуге форкнуть и попытаться реализовать балансировку.
Форки и импрувы только приветствуются!
Рад, что задача вызвала интерес: варка в собственном соку в перспективе не приносит ничего хорошего, всегда важен взгляд со стороны заинтересованного сообщества.
Если даже разработанная реализация никогда явно никому не пригодится (кроме инсайдеров нашей команды), но идеи и подходы заинтересуют энтузиастов и помогут в изучении темы или реализации собственных инструментов и идей, то задача статьи будет выполнена.
Если даже разработанная реализация никогда явно никому не пригодится (кроме инсайдеров нашей команды), но идеи и подходы заинтересуют энтузиастов и помогут в изучении темы или реализации собственных инструментов и идей, то задача статьи будет выполнена.
Балансировка — интересная задача, и, в принципе, вполне решаемая уже на описанном уровне абстракций, реализация вращений будет похожа идеей на
insert. Не знаю, насколько оправдана она будет (как упражнение — вполне): там, где важна балансировка, нужно смотреть уже в сторону АВЛ или красно-чёрных деревьев, реализацию которых пока оставим как домашнее упражнение заинтересованным читателям :)Ну, AVL и RB — это здорово, конечно, но я попробую реализовать Treap, думаю, будет сильно проще. Да и, насколько я помню по опыту олимпиад, оно не сильно проигрывает по скорости std::set/std::map, а там, где это важно, лучше уже смотреть в сторону 2-3- или 2-3-4-деревьев.
Только в отличие от AVL и RB, для Treap нужен генератор случайных чисел (причем если он плохой, то и от балансировки ничего хорошего ждать не приходиться), а для AVL и RB нет.
Действительно, нужен. Но, думаю, для вычислений во время компиляции что-нибудь вроде std::hash от значения вполне подойдет.
В общем случае у вас там хранятся проивзольные типы, как вы предлагаете в общем случае брать hash от типа? Единственный разумный вариант, который я вижу, это вынести эту функциональность в еще один шаблонный параметр, но это просто переложит ответственность на пользователя, которому все еще придется озадачиваться тем, как брать хеш от типа.
Более перспективный вариант, ИМХО, просто взять чисто функциональное красно-черное дерево, так как чисто функциональные реализации деревьев поиска имеют больше шансов на удачное переложение на шаблоны C++ и не требуют кроме сравнения никаких дополнительных параметров.
Более перспективный вариант, ИМХО, просто взять чисто функциональное красно-черное дерево, так как чисто функциональные реализации деревьев поиска имеют больше шансов на удачное переложение на шаблоны C++ и не требуют кроме сравнения никаких дополнительных параметров.
Да, для общей реализации это не подойдет, но я не супермен и мне нужно с чего-то начинать.
Ок, вы начали с Treap, как вы собираетесь продолжать? Выкинуть Treap и взять нормальный алгоритм? Если так, то зачем брать Treap с самого начала, если в мире функционального программирования с такой задачей уже сталкивались и решили ее, а шаблоны C++ — это просто функциональный язык, и можно воспользоваться их решением? Или начало у вас сразу и конец?
Да, выкинуть и взять нормальный алгоритм (а еще провести исследование на тему того, какой алгоритм лучше взять — возможно, это будет 2-3-дерево). Я сомневаюсь в своем умении реализовать нормальный алгоритм сразу, без этой подготовки.
И как реализация Treap поможет вам подготовится к реализации другого алгоритма?
Точно так же, как решение любой более простой задачи в какой-либо области помогает набраться опыта для решения более сложной.
PS: я сомневаюсь в конструктивности нашей дискуссии
PS: я сомневаюсь в конструктивности нашей дискуссии
То что вы говорите — это абстрактная демагогия (которая, конечно, не может быть конструктивной), а я задал вам вполне конкретный вопрос, как реализация одного вполне конкретного дерева поиска поможет вам в реализации другого, о котором вы еще ничего даже не знаете? Ответа на вопрос я не получил.
ОК, надеюсь, вам действительно не понятны мои слова, и вы не тролль.
Это общий принцип обучения: «сначала изучи что-то более простое, а потом уже более сложное в той же области», и именно из этого общего принципа я и вывожу необходимость для себя сначала потренироваться на куда более простом в реализации для compile-time Treap (да что там писать-то, merge и split, вот и все), и уже потом реализовывать более сложный алгоритм.
Вы могли заметить, что этот же принцип используется повсеместно в технологиях обучения, как в рамках computer science (например, знание стека не нужно для реализации кучи, но его все равно дают раньше), так и вне его.
Да, если бы я уже имел большой опыт реализации compile-time алгоритмов, не было бы ни малейшего смысла в предварительной реализации Treap, но у меня такого опыта почти нет.
Ну это, конечно, если копать глубже, чем очевидный ответ «все равно в стол пишу, вот и выбрал алгоритм, который мне больше нравится»
Точно так же, как решение любой более простой задачи в какой-либо области помогает набраться опыта для решения более сложной.
Это общий принцип обучения: «сначала изучи что-то более простое, а потом уже более сложное в той же области», и именно из этого общего принципа я и вывожу необходимость для себя сначала потренироваться на куда более простом в реализации для compile-time Treap (да что там писать-то, merge и split, вот и все), и уже потом реализовывать более сложный алгоритм.
Вы могли заметить, что этот же принцип используется повсеместно в технологиях обучения, как в рамках computer science (например, знание стека не нужно для реализации кучи, но его все равно дают раньше), так и вне его.
Да, если бы я уже имел большой опыт реализации compile-time алгоритмов, не было бы ни малейшего смысла в предварительной реализации Treap, но у меня такого опыта почти нет.
Ну это, конечно, если копать глубже, чем очевидный ответ «все равно в стол пишу, вот и выбрал алгоритм, который мне больше нравится»
Они мне не не понятны, я вам явно выше написал, что ваши слова просто демагогия, а принцип в том виде в каком вы его описываете просто не существует.
То что в курсах по алгоритмам раньше дают стек чем кучу, не значит, что стек чем-то полезен для изучения кучи. В противном случае получится, что алфавит, который дают еще раньше, полезен для изучения стека.
А вот то, что в курсах рассказывают про дерево поиска раньше чем про сбалансированные деревья поиска, вот это уже логичный пример. Очевидно, чтобы сделать сбалансированное дерево поиска нужно знать, что такое дерево поиска впринципе — более простая вещь, необходимая для понимая, дается раньше. Аналогично про массивы и свзные списки рассказывают раньше чем про стек и очередь, потому что первые являются средствами реализации последних. Обратите внимание, в моих примерах польза конкретна, в ваших нет.
Касательно более простого в compile-time Treap-а, то вы не имея опыта реализации алгоритмов в compille-time утверждаете это на каком основании? На основании того, что не в compile-time Treap реализовать легче? Так связный список реализовать будет еще легче.
То что в курсах по алгоритмам раньше дают стек чем кучу, не значит, что стек чем-то полезен для изучения кучи. В противном случае получится, что алфавит, который дают еще раньше, полезен для изучения стека.
А вот то, что в курсах рассказывают про дерево поиска раньше чем про сбалансированные деревья поиска, вот это уже логичный пример. Очевидно, чтобы сделать сбалансированное дерево поиска нужно знать, что такое дерево поиска впринципе — более простая вещь, необходимая для понимая, дается раньше. Аналогично про массивы и свзные списки рассказывают раньше чем про стек и очередь, потому что первые являются средствами реализации последних. Обратите внимание, в моих примерах польза конкретна, в ваших нет.
Касательно более простого в compile-time Treap-а, то вы не имея опыта реализации алгоритмов в compille-time утверждаете это на каком основании? На основании того, что не в compile-time Treap реализовать легче? Так связный список реализовать будет еще легче.
Оуоу, давайте жить дружно! Практика как самоцель тоже имеет право на существование, и ничего плохого в попытке «с нуля» по аналогии соорудить мета-контейнер нет (набить руку, так сказать).
По теме беседы:
- Описанное в статье дерево может быть сбалансировано очень простым приёмом (однако сложность O(n2) при конструировании с пустого): добавляем элементы «как попало» => делаем симметричный обход (сортируем) => сортированный кортеж разбираем делением пополам (в новое дерево кладём серединный элемент, далее середины середин и т.д.)
- Генератор псевдослучайных чисел можно соорудить и на этапе компиляции (только надо пробрасывать seed для всех последующих «вызовов»). Есть ещё крайне интересная идея: использовать этот подход для генерации псевдослучайной последовательности (ОПАСНОСТЕ: по ссылке разрыв шаблонов во всех смыслах).
Нет никакой агресии, так что призывы к дружбе излишни.
Касательно вашего первого варианта балансировки — то он вряд ли может считаться за балансировку дерева. Зачем строить дерево, потом отсортированный список, потом опять дерево, если можно изначально построить список и посортировать его и сделать из него дерево (строить список легко, сортировать тоже, плюс не нужна операция вставки в дерево).
Если под генератором вы имеете ввиду что-то подобного вида:
Или вроде:
То вам нужно хранить новую версию генератора после того как он «сгенерирует» значение.
Касательно статьи, которую вы привели, то не очень понятно как из этого сделать генератор. По сути, функция из статьи возвращает только последовательность вида false, true, true, true, ...., и так далее. Как заставить значение поменяться обратно с true на false не понятно (и мы еще не рассматриваем вопрос о том, когда нужно поменять значение назад). Т. е. не понятно как из этого получить хотя бы что-то напоминающее случайную последовательность бит.
Касательно вашего первого варианта балансировки — то он вряд ли может считаться за балансировку дерева. Зачем строить дерево, потом отсортированный список, потом опять дерево, если можно изначально построить список и посортировать его и сделать из него дерево (строить список легко, сортировать тоже, плюс не нужна операция вставки в дерево).
Если под генератором вы имеете ввиду что-то подобного вида:
static const int M = ...;
static const int C = ...;
template <int N, int seed>
struct Random {
static const int value = Random<N - 1, seed>::value * M + C;
};
template <int seed>
struct Random<0, seed> {
static const int value = seed * M + C;
};
Или вроде:
template <int V>
struct Random {
static const int M = ...;
static const int C = ...;
static const int value = V * M + C;
typedef struct Random<value> next;
};
То вам нужно хранить новую версию генератора после того как он «сгенерирует» значение.
Касательно статьи, которую вы привели, то не очень понятно как из этого сделать генератор. По сути, функция из статьи возвращает только последовательность вида false, true, true, true, ...., и так далее. Как заставить значение поменяться обратно с true на false не понятно (и мы еще не рассматриваем вопрос о том, когда нужно поменять значение назад). Т. е. не понятно как из этого получить хотя бы что-то напоминающее случайную последовательность бит.
У вас есть готовая функция сортировки кортежей в рукаве? Замечание о балансировке было сказано только как пример: мол, на основе уже существующего API можно это же дерево и сбалансировать.
Касательно статьи, которую я привел: ознакомьтесь с ней, пожалуйста, прежде, чем делать выводы (+ещё лучше сразу с источником перевода, это цикл из 3-х статей). Техника, описанная в них, позволяет реализовать глобальный счётчик времени компиляции как минимум. Применение его (несть числа способам) — дело техники.
Касательно статьи, которую я привел: ознакомьтесь с ней, пожалуйста, прежде, чем делать выводы (+ещё лучше сразу с источником перевода, это цикл из 3-х статей). Техника, описанная в них, позволяет реализовать глобальный счётчик времени компиляции как минимум. Применение его (несть числа способам) — дело техники.
Касательно сортировки списка типов (не кортежей), то вообще-то есть. Конкретно я для этого делал сортировку выбором. Не пробовал лично, но кажется, что сортировка слиянием тоже может неплохо лечь на шаблоны.
Касательно статьи, не надо тыкать в меня пальцами и говорить, что я с ней не ознакомился. Вообще я ее прочитал от начала и до конца и не один раз. Конкретно в той статье, на которую вы дали ссылку, описывается «переменная», которую можно изменить только один раз (вы можете сами попробовать код и убедиться в этом). Заглянув в следующую статью цикла, вы можете заметить, что автор сам пишет ровно то же самое, так что вы поторопились с выводами.
Но да не будем на этом останавливаться, посмотрим что происходит далее. Автор для того, чтобы сделать счетчик с N значениями использует N-1 такую «переменную». Т. е. фактически счетчик построенный с помощью такой идеи не отличается по «сложности» (мы же в данном случае измеряем сложность количеством инстанцирований) от генераторов, которые я привел вам выше, а коли так, то не понятно, зачем вообще это делать используя constexpr функции, если генераторы выше просто проще?
Касательно статьи, не надо тыкать в меня пальцами и говорить, что я с ней не ознакомился. Вообще я ее прочитал от начала и до конца и не один раз. Конкретно в той статье, на которую вы дали ссылку, описывается «переменная», которую можно изменить только один раз (вы можете сами попробовать код и убедиться в этом). Заглянув в следующую статью цикла, вы можете заметить, что автор сам пишет ровно то же самое, так что вы поторопились с выводами.
Но да не будем на этом останавливаться, посмотрим что происходит далее. Автор для того, чтобы сделать счетчик с N значениями использует N-1 такую «переменную». Т. е. фактически счетчик построенный с помощью такой идеи не отличается по «сложности» (мы же в данном случае измеряем сложность количеством инстанцирований) от генераторов, которые я привел вам выше, а коли так, то не понятно, зачем вообще это делать используя constexpr функции, если генераторы выше просто проще?
Хорошо, сортировка у вас есть, но не из коробки: вы сами её реализовывали, а основная мысль была об использовании готового инструментария.
По сложности не отличается, но отличается в удобстве применения. Написать
Добавлю в TODO мини-задачу реализации compile-time генератора псевдослучайных чисел. Challenge accepted. Закончу — оставлю здесь ссылку.
По сложности не отличается, но отличается в удобстве применения. Написать
template<..., counter::next()> func{...}; проще (и логичнее), чем помнить пробрасываемый генератор. Следуя вашей логике вообще можно заранее руками написать всю последовательность «случайных» чисел.Добавлю в TODO мини-задачу реализации compile-time генератора псевдослучайных чисел. Challenge accepted. Закончу — оставлю здесь ссылку.
Вы спросили про готовую функцию — я вам ответил, что у меня есть готовая функция. Какой вопрос такой и ответ. Если вас интересует функция реализованная в каокй-нибудь популярной библиотеке, то в boost mpl есть сортировка. В стандартной библиотеке такого нет, на сколько я знаю.
Касательно сложности и логичности, я, лично, не вижу большой разницы между числом в качестве шаблонного параметра и типом, который хранит число, как не вижу большой разницы между counter::next() и Random::next. Что-то вам все равно придется хранить и передавать.
Не знаю какой моей логике вы следуете, но я нигде не утвеждал, что можно заранее написать всю последовательность. Более того я привел пример того как ее можно сгенерировать, а не описывать руками заранее.
Не понял где вы в моем сообщении увидели какой-то challenge, но удачно вам поразвлекаться.
Касательно сложности и логичности, я, лично, не вижу большой разницы между числом в качестве шаблонного параметра и типом, который хранит число, как не вижу большой разницы между counter::next() и Random::next. Что-то вам все равно придется хранить и передавать.
Не знаю какой моей логике вы следуете, но я нигде не утвеждал, что можно заранее написать всю последовательность. Более того я привел пример того как ее можно сгенерировать, а не описывать руками заранее.
Не понял где вы в моем сообщении увидели какой-то challenge, но удачно вам поразвлекаться.
не вижу большой разницы между counter::next() и Random::next. Что-то вам все равно придется хранить и передавать
Более того я привел пример того как ее можно сгенерироватьКак раз не придётся. То, что вы описали, просто не будет работать: вам либо придётся руками считать вызовы
Random<...>, либо подсовывать предыдущие псевдонимы в параметр шаблона. Упомянутые статьи как раз и описывают реализацию счётчика, способного инкрементироваться без посторонней помощи.удачно вам поразвлекатьсяСпасибо! Задача действительно интересная.
Число вам все равно придется хранить в каждом узле, в противном случае как вы собираетесь использовать что-то к чему у вас нет доступа при балансировке?
Естественно, кроме числа/типа в каждом узле, нужно будет еще сохранить Random::next, но в единственном экземпляре на все дерево. Нельзя это назвать такой уж существенной сложностью, особенно если учесть реализацию альтернативы (здесь я имею ввиду проблемы с некоторыми компиляторами, переносимость на разные версии C++, плюс некоторое легкое допиливание, чтобы можно было создавать несколько независимых счетчиков/генераторов + удобство использоввания допиленной версии под вопросом).
Естественно, кроме числа/типа в каждом узле, нужно будет еще сохранить Random::next, но в единственном экземпляре на все дерево. Нельзя это назвать такой уж существенной сложностью, особенно если учесть реализацию альтернативы (здесь я имею ввиду проблемы с некоторыми компиляторами, переносимость на разные версии C++, плюс некоторое легкое допиливание, чтобы можно было создавать несколько независимых счетчиков/генераторов + удобство использоввания допиленной версии под вопросом).
«ученые были так озадачены поиском ответа на вопрос „а это возможно?“, что забыли ответить на вопрос „а это нужно?“»
Не так страшен Александреску, как тот кто его начитался :)
Часто встречал подобное мнение и не считаю его справедливым и конструктивным: всё-таки А.А. сыграл значительную роль в развитии языка (см. спойлер «Лирическое отступление»). В конце концов, никто не заставляет программистов городить воздушные замки из шаблонов: они, как и любой инструмент, имеют свою область применения, а большинство задач может быть решено разными способами (и с разным соотношением время/универсальность/расширяемость/производительность).
ИМХО, гораздо более «страшным» мне видится виртуально-интерфейсный фарш, бездонные иерархии и километровые определения приезжих в C++ из C#/Java, обычно и пышущих ненавистью к углоскобочному миру.
ИМХО, гораздо более «страшным» мне видится виртуально-интерфейсный фарш, бездонные иерархии и километровые определения приезжих в C++ из C#/Java, обычно и пышущих ненавистью к углоскобочному миру.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Практика метапрограммирования на C++: бинарное дерево поиска на этапе компиляции