Spiiin's blog

C++ Metaprogramming - ссылки

Список книг и ресурсов по метапрограммированию в C++. Грубая карта небольшой части огромной территории.

Желание разобраться с очередным трюком с шаблонами в C++ приходит после обнаружения какой-либо библиотеки или кода, который непонятно как работает, но вроде что-то ловко делает. И заканчивается мыслью “это ж ебануться можно, так писать”.

Такие мысли приходят в голову всем практикующим и работающим в командах программистам. Пара примеров лютых исходников — cppcoro, range-v3 (“Modern” C++ Lamenations).

Заметки о языках программирования — про использование различных языков для решения задач различных уровней, а также подходы к борьбе с возрастающей сложностью при масштабируемости.
С++ в геймдеве — “высокоуровневый” С++ - часть задач решаемых метапрограммированием.

Общий обзор возможностей шаблонов и списки примеров использования:

Vandervoorde D. Josuttis N. Gregor D. - C++ Templates: The Complete Guide - полный обзор возможностей языка, второе издание — по C++17
Александреску А. - Современное проектирование на C++ - pre-C++11, но классические идеи
Di Genaro D. - Advanced Metaprogramming in Classic C++ - много небольших примеров
More C++ idioms - еще больше примеров, не только с шаблонами
Boost - лучший учебник

Generic-типы

Часто первое столкновение с шаблонами — обобщенные контейнеры, итераторы и умные указатели из stl
Более продвинутые примеры — стратегии Александреску, задание отношений между типами, CRTP, template template параметры

EnTT dense set - пример кода контейнера и итератора не из stl
libnest2d - небольшая библиотека для паковки многоугольников, использующая стратегии для выбора вариантов оптимизации, паковки и математического бекэнда

Задание ограничений и свойств для типов

Контракты, распознавание свойств типов (std::is_XXX), частичная специализация

Stepanov A. - Elements of programming - математическое описание типов и структур, контракты
Lecture and presentation Sean Parent - и другие лекции Шона Парента, про value-oriented programming

Пример из daScript — частичная специализация с захватом новых шаблонных параметров
Templated class specialization where template argument is a template - описание возможных подходов к созданию связи между шаблонными параметрами

Работа с типами как с данными

Типы не являются объектами первого класса, поэтому работы с ними, поэтому все действия выполняются во время компиляции. Один из ключевых приёмов — выбор того, или иного типа в зависимости от статически известного условия. При этом не определяется новый тип, а создаётся псевдоним для существуюшего, “слот”, в который можно сохранить любой тип (typedef). Типы используются не для создания экземпляров, а для вообще чего угодно, от управляющих конструкций и отправки сигналов в рантайм, до операций группировки других типов.

Abrahams D. Gurtovoy A. - C++ Template Metaprogramming - одна из наиболее замороченных книг, pre-C++11. Частично описывает Boost.MPL
Boost.Mp11 - C++11-версия библиотеки для манипуляции с типами, несколько статей сравнения новых подходов со старыми

Domain Specific Language

Следующая идея — пойти еще дальше: построить на специальных типах свой язык, с управляющими конструкциями. Примеры задач — парсинг команд и создание деревьев выражений для последующего вычисления в рантайме.

Hana Dusíková — A state of сompile time regular expressions — регулярные выражения в compile-time (compile-time.re)
Ben Deane & Jason Turner “constexpr ALL the Things!” — парсинг json в compile-time

Runtime-полиморфизм в C++ - пост со ссылками на серию видео про построение в compile-time кастомных версий динамического полиморфизма. dyno - библиотека Louis Dionne, автора Boost.Hana

Выполнение кода в compile-time

Изначально возможность выполнения кода во время компиляции в С++ была артефактом шаблонов (первая “программа” - вывод простых чисел в сообщении об ошибке). Со временем добавляются более серьёзные возможности, однако код времени компиляции серьёзно ограничен и отличается от среды выполнения.

Примеры задач в compile-time:

  • заранее предпосчитать значение выражение, все части которого известны на момент компиляции
  • построить таблицу значений чистой функции, которая долго вычисляется

Основная возможность в pre-C++11 - SFINAE и рекурсивные+терминальные пары функций, и дополнительно const-expr/if/eval в более поздних стандартах.

Don’t constexpr All the Things - David Sankel CppNow 2021 - обзор ограничений подъязыка времени выполнения
Circle - wip компилятор C++ Шона Бакстера, с возможностью выполнение кода на этапе компиляции без ограничений
Ideas for a Programming Language Part 3: No Shadow Worlds - похожие рассуждения на тему того, что не полностью интегрированные в основной язык подмножества создают “теневые миры”, в которых приходится переизобреть заново возможности основного языка

В Circle меня настораживает, что код, кажется, должен компилироваться дважды, особенно с учетом того, что скорее всего выполнение кода в compile-time будет медленнее, чем в рантайм. Для nim выполнение кода в compile-time — раз в 10 медленее

Доступ к данным о типах в рантайм

Отсутствует в C, и не zero-cost абстракция, так что в стандарте языка отсутствует механизм неявной передачи информации о типах в рантайм (можно откопать пачку предложений для будущих улучшений).

Поэтому задачи типа рефлексии/инстроспекции решаются либо явной декларацией полей и методов класса (как при создании врапперов для других языков), либо предварительным внешним парсингом кода — либо кастомной метаинформации, которую пропускает компилятор C++ (в комментариях), либо полноценным разбором кода (clang), с последующей генерацией по этой информации кода.

Аналогично, без явной интроспекции и вещи вроде сериализации или описания RPC не могут быть неявными — необходимо явно аннотировать типы.

Кодогенерация выражений на C++ в рантайме также отсутствует в стандарте, и заменяется генерации во время компиляции — текста, либо бинарного кода (или промежуточного кода, вроде IR для LLVM).

LLVM - обзор — обзор тулзов из набора LLVM, для парсинга и генерации кода, в настоящий момент state-of-art для генерации кода на C++
Automatic C++ source code generation with clang - Sergei Sadovnikov ACCU 2017 - доклад с обзором подходов, и способа генерации с помощью clang
Reflection in C++ Next - Anton Bikineev - Meeting C++ 2017 - обзор пропозалов в стандарт, связанных с рефлексией
Boost.Serialization - сериализация в Boost

Функциональное программирование

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

Чукич И. - Функциональное программирование на языке С++ — книга о том, как использовать элементы функционального программирования на C++, ссылки на библиотеки буста, реализующие концепции
Milewski B. - Category Theory For Programmers - серия статей (собранная в книгу), по теории категорий для программистов, с примерами на C++ и хаскелл. Видеолекции на ту же тему
In-depth: Functional programming in C++ - статья Кармака про бонусы, которые можно получить, если использовать функциональный подход, в частности, бонусы от чистоты функций