Метапрограммирование шаблона - Template metaprogramming

Парадигмы программирования

Метапрограммирование шаблона (TMP) это метапрограммирование техника, в которой шаблоны используются компилятор создать временный исходный код, который объединяется компилятором с остальной частью исходного кода и затем компилируется. Вывод этих шаблонов включает время компиляции константы, структуры данных, и завершить функции. Использование шаблонов можно рассматривать как полиморфизм времени компиляции. Этот метод используется на нескольких языках, самый известный из которых C ++, но также Завиток, D, и XL.

В некотором смысле метапрограммирование шаблонов было обнаружено случайно.[1][2]

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

Компоненты шаблонного метапрограммирования

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

Метапрограммирование шаблона Полный по Тьюрингу, что означает, что любое вычисление, выражаемое компьютерной программой, может быть вычислено в той или иной форме с помощью метапрограммы шаблона.[3]

Шаблоны отличаются от макросы. Макрос - это фрагмент кода, который выполняется во время компиляции и либо выполняет текстовые манипуляции с кодом, который должен быть скомпилирован (например, C ++ макросов) или манипулирует абстрактное синтаксическое дерево производятся компилятором (например, Ржавчина или Лисп макросы). Текстовые макросы заметно более независимы от синтаксиса манипулируемого языка, поскольку они просто изменяют текст исходного кода в памяти прямо перед компиляцией.

Метапрограммы шаблонов не имеют изменяемые переменные - то есть никакая переменная не может изменить значение после инициализации, поэтому метапрограммирование шаблона можно рассматривать как форму функциональное программирование. Фактически, многие реализации шаблонов реализуют управление потоком только через рекурсия, как показано в примере ниже.

Использование метапрограммирования шаблонов

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

Генерация класса во время компиляции

Что именно означает «программирование во время компиляции», можно проиллюстрировать на примере факториальной функции, которая в нешаблонном C ++ может быть написана с использованием рекурсии следующим образом:

беззнаковый int факториал(беззнаковый int п) {	вернуть п == 0 ? 1 : п * факториал(п - 1); }// Примеры использования:// factorial (0) даст 1;// factorial (4) даст 24.

Приведенный выше код будет выполняться во время выполнения для определения факториала литералов 4 и 0. Используя метапрограммирование шаблона и специализацию шаблона для обеспечения конечного условия рекурсии, факториалы, используемые в программе, игнорируя любой неиспользуемый факториал, могут вычисляться во время компиляции с помощью этого кода:

шаблон <беззнаковый int п>структура факториал {	перечислить { ценить = п * факториал<п - 1>::ценить };};шаблон <>структура факториал<0> {	перечислить { ценить = 1 };};// Примеры использования:// factorial <0> :: value даст 1;// factorial <4> :: value даст 24.

Приведенный выше код вычисляет факториальное значение литералов 4 и 0 во время компиляции и использует результаты, как если бы они были предварительно вычисленными константами. Чтобы иметь возможность использовать шаблоны таким образом, компилятор должен знать значение своих параметров во время компиляции, который имеет естественное предварительное условие, что factorial :: value может использоваться, только если X известен во время компиляции. Другими словами, X должен быть константным литералом или константным выражением.

В C ++ 11 и C ++ 20, constexpr и consteval были введены, чтобы позволить компилятору выполнять код. Используя constexpr и consteval, можно использовать обычное рекурсивное определение факториала с нетрадиционным синтаксисом.[4]

Оптимизация кода во время компиляции

Смотрите также: Выполнение функции времени компиляции

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

В качестве еще одного, более значимого примера времени компиляции разворачивание петли, метапрограммирование шаблона может быть использовано для создания длины-п векторные классы (где п известно во время компиляции). Преимущество по сравнению с более традиционной длинойп vector заключается в том, что циклы могут разворачиваться, что приводит к очень оптимизированному коду. В качестве примера рассмотрим оператор сложения. Длина-п векторное сложение можно записать как

шаблон <int длина>Вектор<длина>& Вектор<длина>::оператор+=(const Вектор<длина>& rhs) {    за (int я = 0; я < длина; ++я)        ценить[я] += rhs.ценить[я];    вернуть *это;}

Когда компилятор создает экземпляр шаблона функции, определенного выше, может быть получен следующий код:[нужна цитата ]

шаблон <>Вектор<2>& Вектор<2>::оператор+=(const Вектор<2>& rhs) {    ценить[0] += rhs.ценить[0];    ценить[1] += rhs.ценить[1];    вернуть *это;}

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

Однако будьте осторожны и соблюдайте осторожность, так как это может вызвать раздувание кода, поскольку для каждого N (размер вектора), который вы создаете, будет создаваться отдельный развернутый код.

Статический полиморфизм

Полиморфизм - это обычное стандартное средство программирования, в котором производные объекты могут использоваться как экземпляры своего базового объекта, но при этом будут вызываться методы производных объектов, как в этом коде

класс База{общественный:    виртуальный пустота метод() { стандартное::cout << "Основание"; }    виртуальный ~База() {}};класс Получено : общественный База{общественный:    виртуальный пустота метод() { стандартное::cout << "Полученный"; }};int основной(){    База *pBase = новый Получено;    pBase->метод(); // выводит "Derived"    Удалить pBase;    вернуть 0;}

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

Однако во многих случаях необходимое полиморфное поведение инвариантно и может быть определено во время компиляции. Тогда Любопытно повторяющийся шаблон шаблона (CRTP) можно использовать для достижения статический полиморфизм, который является имитацией полиморфизма в программном коде, но разрешается во время компиляции и, таким образом, устраняет поиск в виртуальной таблице во время выполнения. Например: 

шаблон <класс Получено>структура основание{    пустота интерфейс()    {         // ...         static_cast<Получено*>(это)->реализация();         // ...    }};структура полученный : основание<полученный>{     пустота реализация()     {         // ...     }};

Здесь шаблон базового класса будет использовать тот факт, что тела функций-членов не создаются до тех пор, пока не будут объявлены их объявления, и он будет использовать члены производного класса в своих собственных функциях-членах посредством использования static_cast, при этом при компиляции генерируется объектная композиция с полиморфными характеристиками. В качестве примера реального использования CRTP используется в Способствовать росту итератор библиотека.[5]

Другое подобное использование - "Уловка Бартона – Накмана ", иногда называемый" ограниченным расширением шаблона ", где общие функциональные возможности могут быть помещены в базовый класс, который используется не в качестве контракта, а в качестве необходимого компонента для обеспечения согласованного поведения при минимизации избыточности кода.

Создание статической таблицы

Преимуществом статических таблиц является замена «дорогостоящих» вычислений простой операцией индексации массива (примеры см. Справочная таблица ). В C ++ существует более одного способа создания статической таблицы во время компиляции. В следующем листинге показан пример создания очень простой таблицы с использованием рекурсивных структур и вариативные шаблоны Таблица имеет размер десять. Каждое значение - это квадрат индекса.

#включают <iostream>#включают <array>constexpr int TABLE_SIZE = 10;/** * Вариативный шаблон для рекурсивной вспомогательной структуры. */шаблон<int ПОКАЗАТЕЛЬ = 0, int ...D>структура Помощник : Помощник<ПОКАЗАТЕЛЬ + 1, D..., ПОКАЗАТЕЛЬ * ПОКАЗАТЕЛЬ> { };/** * Специализация шаблона для завершения рекурсии, когда размер таблицы достигает TABLE_SIZE. */шаблон<int ...D>структура Помощник<TABLE_SIZE, D...> {  статический constexpr стандартное::множество<int, TABLE_SIZE> Таблица = { D... };};constexpr стандартное::множество<int, TABLE_SIZE> Таблица = Помощник<>::Таблица;перечислить  {  ЧЕТЫРЕ = Таблица[2] // использование времени компиляции};int основной() {  за(int я=0; я < TABLE_SIZE; я++) {    стандартное::cout << Таблица[я]  << стандартное::конец; // использование во время выполнения  }  стандартное::cout << "ЧЕТЫРЕ:" << ЧЕТЫРЕ << стандартное::конец;}

Идея заключается в том, что struct Helper рекурсивно наследуется от структуры с еще одним аргументом шаблона (в этом примере вычисленным как INDEX * INDEX) до тех пор, пока специализация шаблона не завершит рекурсию с размером 10 элементов. Специализация просто использует список переменных аргументов в качестве элементов массива. Компилятор создаст код, подобный следующему (взятый из clang, вызываемого с помощью -Xclang -ast-print -fsyntax-only).

шаблон <int ПОКАЗАТЕЛЬ = 0, int ...D> структура Помощник : Помощник<ПОКАЗАТЕЛЬ + 1, D..., ПОКАЗАТЕЛЬ * ПОКАЗАТЕЛЬ> {};шаблон<> структура Помощник<0, <>> : Помощник<0 + 1, 0 * 0> {};шаблон<> структура Помощник<1, <0>> : Помощник<1 + 1, 0, 1 * 1> {};шаблон<> структура Помощник<2, <0, 1>> : Помощник<2 + 1, 0, 1, 2 * 2> {};шаблон<> структура Помощник<3, <0, 1, 4>> : Помощник<3 + 1, 0, 1, 4, 3 * 3> {};шаблон<> структура Помощник<4, <0, 1, 4, 9>> : Помощник<4 + 1, 0, 1, 4, 9, 4 * 4> {};шаблон<> структура Помощник<5, <0, 1, 4, 9, 16>> : Помощник<5 + 1, 0, 1, 4, 9, 16, 5 * 5> {};шаблон<> структура Помощник<6, <0, 1, 4, 9, 16, 25>> : Помощник<6 + 1, 0, 1, 4, 9, 16, 25, 6 * 6> {};шаблон<> структура Помощник<7, <0, 1, 4, 9, 16, 25, 36>> : Помощник<7 + 1, 0, 1, 4, 9, 16, 25, 36, 7 * 7> {};шаблон<> структура Помощник<8, <0, 1, 4, 9, 16, 25, 36, 49>> : Помощник<8 + 1, 0, 1, 4, 9, 16, 25, 36, 49, 8 * 8> {};шаблон<> структура Помощник<9, <0, 1, 4, 9, 16, 25, 36, 49, 64>> : Помощник<9 + 1, 0, 1, 4, 9, 16, 25, 36, 49, 64, 9 * 9> {};шаблон<> структура Помощник<10, <0, 1, 4, 9, 16, 25, 36, 49, 64, 81>> {  статический constexpr стандартное::множество<int, TABLE_SIZE> Таблица = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81};};

Начиная с C ++ 17, это можно более удобно записать как:

 #включают <iostream>#включают <array>constexpr int TABLE_SIZE = 10;constexpr стандартное::множество<int, TABLE_SIZE> Таблица = [] { // ИЛИ: автоматическая таблица constexpr  стандартное::множество<int, TABLE_SIZE> А = {};  за (беззнаковый я = 0; я < TABLE_SIZE; я++) {    А[я] = я * я;  }  вернуть А;}();перечислить  {  ЧЕТЫРЕ = Таблица[2] // использование времени компиляции};int основной() {  за(int я=0; я < TABLE_SIZE; я++) {    стандартное::cout << Таблица[я]  << стандартное::конец; // использование во время выполнения  }  стандартное::cout << "ЧЕТЫРЕ:" << ЧЕТЫРЕ << стандартное::конец;}

Чтобы показать более сложный пример, код в следующем листинге был расширен, чтобы иметь помощник для вычисления значений (при подготовке к более сложным вычислениям), смещение для конкретной таблицы и аргумент шаблона для типа значений таблицы (например, uint8_t, uint16_t, ...). 

                                                                #включают <iostream>#включают <array>constexpr int TABLE_SIZE = 20;constexpr int КОМПЕНСИРОВАТЬ = 12;/** * Шаблон для расчета одной записи в таблице */шаблон <typename ТИП ЦЕННОСТИ, ТИП ЦЕННОСТИ КОМПЕНСИРОВАТЬ, ТИП ЦЕННОСТИ ПОКАЗАТЕЛЬ>структура ValueHelper {  статический constexpr ТИП ЦЕННОСТИ ценить = КОМПЕНСИРОВАТЬ + ПОКАЗАТЕЛЬ * ПОКАЗАТЕЛЬ;};/** * Вариативный шаблон для рекурсивной вспомогательной структуры. */шаблон<typename ТИП ЦЕННОСТИ, ТИП ЦЕННОСТИ КОМПЕНСИРОВАТЬ, int N = 0, ТИП ЦЕННОСТИ ...D>структура Помощник : Помощник<ТИП ЦЕННОСТИ, КОМПЕНСИРОВАТЬ, N+1, D..., ValueHelper<ТИП ЦЕННОСТИ, КОМПЕНСИРОВАТЬ, N>::ценить> { };/** * Специализация шаблона для завершения рекурсии, когда размер таблицы достигает TABLE_SIZE. */шаблон<typename ТИП ЦЕННОСТИ, ТИП ЦЕННОСТИ КОМПЕНСИРОВАТЬ, ТИП ЦЕННОСТИ ...D>структура Помощник<ТИП ЦЕННОСТИ, КОМПЕНСИРОВАТЬ, TABLE_SIZE, D...> {  статический constexpr стандартное::множество<ТИП ЦЕННОСТИ, TABLE_SIZE> Таблица = { D... };};constexpr стандартное::множество<uint16_t, TABLE_SIZE> Таблица = Помощник<uint16_t, КОМПЕНСИРОВАТЬ>::Таблица;int основной() {  за(int я = 0; я < TABLE_SIZE; я++) {    стандартное::cout << Таблица[я] << стандартное::конец;  }}

Это можно было бы записать на C ++ 17 следующим образом:

#включают <iostream>#включают <array>constexpr int TABLE_SIZE = 20;constexpr int КОМПЕНСИРОВАТЬ = 12;шаблон<typename ТИП ЦЕННОСТИ, ТИП ЦЕННОСТИ КОМПЕНСИРОВАТЬ>constexpr стандартное::множество<ТИП ЦЕННОСТИ, TABLE_SIZE> Таблица = [] { // ИЛИ: автоматическая таблица constexpr  стандартное::множество<ТИП ЦЕННОСТИ, TABLE_SIZE> А = {};  за (беззнаковый я = 0; я < TABLE_SIZE; я++) {    А[я] = КОМПЕНСИРОВАТЬ + я * я;  }  вернуть А;}();int основной() {  за(int я = 0; я < TABLE_SIZE; я++) {    стандартное::cout << Таблица<uint16_t, КОМПЕНСИРОВАТЬ>[я] << стандартное::конец;  }}

Преимущества и недостатки метапрограммирования шаблонов

Компромисс между временем компиляции и временем выполнения
Если используется много шаблонного метапрограммирования.
Общее программирование
Метапрограммирование шаблонов позволяет программисту сосредоточиться на архитектуре и делегировать компилятору создание любой реализации, требуемой клиентским кодом. Таким образом, с помощью метапрограммирования шаблонов можно создать действительно общий код, облегчая минимизацию кода и улучшая ремонтопригодность.[нужна цитата ].
Читаемость
Что касается C ++, синтаксис и идиомы метапрограммирования шаблонов эзотеричны по сравнению с обычным программированием на C ++, а метапрограммы шаблонов могут быть очень трудными для понимания.[6][7]

Смотрите также

Рекомендации

  1. ^ Скотт Мейерс (12 мая 2005 г.). Эффективный C ++: 55 конкретных способов улучшить ваши программы и дизайн. Pearson Education. ISBN  978-0-13-270206-5.
  2. ^ Видеть История ТМП в Викиучебниках
  3. ^ Велдхёйзен, Тодд Л. «Шаблоны C ++ завершены по Тьюрингу». CiteSeerX  10.1.1.14.3670. Цитировать журнал требует | журнал = (Помогите)
  4. ^ http://www.cprogramming.com/c++11/c++11-compile-time-processing-with-constexpr.html
  5. ^ http://www.boost.org/libs/iterator/doc/iterator_facade.html
  6. ^ Czarnecki, K .; О'Доннелл, Дж .; Striegnitz, J .; Таха, Валид Мохамед (2004). «Реализация DSL в метаокамере, шаблоне haskell и C ++» (PDF). Университет Ватерлоо, Университет Глазго, Исследовательский центр Джулих, Университет Райса. Метапрограммирование шаблонов C ++ страдает рядом ограничений, включая проблемы с переносимостью из-за ограничений компилятора (хотя за последние несколько лет ситуация значительно улучшилась), отсутствие поддержки отладки или ввода-вывода во время создания экземпляра шаблона, длительное время компиляции, длинные и непонятные ошибки, плохой читаемость кода и плохое сообщение об ошибках. Цитировать журнал требует | журнал = (Помогите)
  7. ^ Шеард, Тим; Джонс, Саймон Пейтон (2002). «Шаблонное метапрограммирование для Haskell» (PDF). АСМ 1-58113-415-0 / 01/0009. В провокационной статье Робинсона шаблоны C ++ называются главным, хотя и случайным, успехом дизайна языка C ++. Несмотря на чрезвычайно барочную природу метапрограммирования шаблонов, шаблоны используются увлекательными способами, которые выходят за рамки самых смелых мечтаний разработчиков языка. Возможно, это удивительно, учитывая тот факт, что шаблоны являются функциональными программами, функциональные программисты не спешат извлекать выгоду из успеха C ++. Цитировать журнал требует | журнал = (Помогите)

внешняя ссылка