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

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

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

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

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

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

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

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

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

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

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

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

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

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

unsigned factorial(unsigned n) {
	return n == 0 ? 1 : n * factorial(n - 1); 
}

// Usage examples:
// factorial(0) would yield 1;
// factorial(4) would yield 24.

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

template <unsigned N>
struct factorial {
	static constexpr unsigned value = N * factorial<N - 1>::value;
};

template <>
struct factorial<0> {
	static constexpr unsigned value = 1;
};

// Usage examples:
// factorial<0>::value would yield 1;
// factorial<4>::value would yield 24.

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

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

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

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

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

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

template <int length>
Vector<length>& Vector<length>::operator+=(const Vector<length>& rhs) 
{
    for (int i = 0; i < length; ++i)
        value[i] += rhs.value[i];
    return *this;
}

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

template <>
Vector<2>& Vector<2>::operator+=(const Vector<2>& rhs) 
{
    value[0] += rhs.value[0];
    value[1] += rhs.value[1];
    return *this;
}

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

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

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

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

class Base
{
public:
    virtual void method() { std::cout << "Base"; }
    virtual ~Base() {}
};

class Derived : public Base
{
public:
    virtual void method() { std::cout << "Derived"; }
};

int main()
{
    Base *pBase = new Derived;
    pBase->method(); //outputs "Derived"
    delete pBase;
    return 0;
}

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

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

template <class Derived>
struct base
{
    void interface()
    {
         // ...
         static_cast<Derived*>(this)->implementation();
         // ...
    }
};

struct derived : base<derived>
{
     void implementation()
     {
         // ...
     }
};

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

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

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

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

#include <iostream>
#include <array>

constexpr int TABLE_SIZE = 10;

/**
 * Variadic template for a recursive helper struct.
 */
template<int INDEX = 0, int ...D>
struct Helper : Helper<INDEX + 1, D..., INDEX * INDEX> { };

/**
 * Specialization of the template to end the recursion when the table size reaches TABLE_SIZE.
 */
template<int ...D>
struct Helper<TABLE_SIZE, D...> {
  static constexpr std::array<int, TABLE_SIZE> table = { D... };
};

constexpr std::array<int, TABLE_SIZE> table = Helper<>::table;

enum  {
  FOUR = table[2] // compile time use
};

int main() {
  for(int i=0; i < TABLE_SIZE; i++) {
    std::cout << table[i]  << std::endl; // run time use
  }
  std::cout << "FOUR: " << FOUR << std::endl;
}

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

template <int INDEX = 0, int ...D> struct Helper : Helper<INDEX + 1, D..., INDEX * INDEX> {
};
template<> struct Helper<0, <>> : Helper<0 + 1, 0 * 0> {
};
template<> struct Helper<1, <0>> : Helper<1 + 1, 0, 1 * 1> {
};
template<> struct Helper<2, <0, 1>> : Helper<2 + 1, 0, 1, 2 * 2> {
};
template<> struct Helper<3, <0, 1, 4>> : Helper<3 + 1, 0, 1, 4, 3 * 3> {
};
template<> struct Helper<4, <0, 1, 4, 9>> : Helper<4 + 1, 0, 1, 4, 9, 4 * 4> {
};
template<> struct Helper<5, <0, 1, 4, 9, 16>> : Helper<5 + 1, 0, 1, 4, 9, 16, 5 * 5> {
};
template<> struct Helper<6, <0, 1, 4, 9, 16, 25>> : Helper<6 + 1, 0, 1, 4, 9, 16, 25, 6 * 6> {
};
template<> struct Helper<7, <0, 1, 4, 9, 16, 25, 36>> : Helper<7 + 1, 0, 1, 4, 9, 16, 25, 36, 7 * 7> {
};
template<> struct Helper<8, <0, 1, 4, 9, 16, 25, 36, 49>> : Helper<8 + 1, 0, 1, 4, 9, 16, 25, 36, 49, 8 * 8> {
};
template<> struct Helper<9, <0, 1, 4, 9, 16, 25, 36, 49, 64>> : Helper<9 + 1, 0, 1, 4, 9, 16, 25, 36, 49, 64, 9 * 9> {
};
template<> struct Helper<10, <0, 1, 4, 9, 16, 25, 36, 49, 64, 81>> {
  static constexpr std::array<int, TABLE_SIZE> table = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81};
};

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

 
#include <iostream>
#include <array>

constexpr int TABLE_SIZE = 10;

constexpr std::array<int, TABLE_SIZE> table = [] { // OR: constexpr auto table
  std::array<int, TABLE_SIZE> A = {};
  for (unsigned i = 0; i < TABLE_SIZE; i++) {
    A[i] = i * i;
  }
  return A;
}();

enum  {
  FOUR = table[2] // compile time use
};

int main() {
  for(int i=0; i < TABLE_SIZE; i++) {
    std::cout << table[i]  << std::endl; // run time use
  }
  std::cout << "FOUR: " << FOUR << std::endl;
}

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

                                                                
#include <iostream>
#include <array>

constexpr int TABLE_SIZE = 20;
constexpr int OFFSET = 12;

/**
 * Template to calculate a single table entry
 */
template <typename VALUETYPE, VALUETYPE OFFSET, VALUETYPE INDEX>
struct ValueHelper {
  static constexpr VALUETYPE value = OFFSET + INDEX * INDEX;
};

/**
 * Variadic template for a recursive helper struct.
 */
template<typename VALUETYPE, VALUETYPE OFFSET, int N = 0, VALUETYPE ...D>
struct Helper : Helper<VALUETYPE, OFFSET, N+1, D..., ValueHelper<VALUETYPE, OFFSET, N>::value> { };

/**
 * Specialization of the template to end the recursion when the table size reaches TABLE_SIZE.
 */
template<typename VALUETYPE, VALUETYPE OFFSET, VALUETYPE ...D>
struct Helper<VALUETYPE, OFFSET, TABLE_SIZE, D...> {
  static constexpr std::array<VALUETYPE, TABLE_SIZE> table = { D... };
};

constexpr std::array<uint16_t, TABLE_SIZE> table = Helper<uint16_t, OFFSET>::table;

int main() {
  for(int i = 0; i < TABLE_SIZE; i++) {
    std::cout << table[i] << std::endl;
  }
}

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

#include <iostream>
#include <array>

constexpr int TABLE_SIZE = 20;
constexpr int OFFSET = 12;

template<typename VALUETYPE, VALUETYPE OFFSET>
constexpr std::array<VALUETYPE, TABLE_SIZE> table = [] { // OR: constexpr auto table
  std::array<VALUETYPE, TABLE_SIZE> A = {};
  for (unsigned i = 0; i < TABLE_SIZE; i++) {
    A[i] = OFFSET + i * i;
  }
  return A;
}();

int main() {
  for(int i = 0; i < TABLE_SIZE; i++) {
    std::cout << table<uint16_t, OFFSET>[i] << std::endl;
  }
}

Концепции

Стандарт C ++ 20 предоставил программистам на C ++ новый инструмент для программирования мета-шаблонов, концепций.

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

Вот пример известной проблемы с шумом Fizz, решенной с помощью шаблонного метапрограммирования. 

#include <boost/type_index.hpp> // for pretty printing of types
#include <iostream>
#include <tuple>

/**
 * Type representation of words to print
 */
struct Fizz {};
struct Buzz {};
struct FizzBuzz {};
template<size_t _N> struct number { constexpr static size_t N = _N; };

/**
 * Concepts used to define condition for specializations
 */
template<typename Any> concept has_N = requires{ requires Any::N - Any::N == 0; };
template<typename A> concept fizz_c = has_N<A> && requires{ requires A::N % 3 == 0; };
template<typename A> concept buzz_c = has_N<A> && requires{ requires A::N % 5 == 0;};
template<typename A> concept fizzbuzz_c = fizz_c<A> && buzz_c<A>;

/**
 * By specializing `res` structure, with concepts requirements, proper instantation is performed
 */
template<typename X> struct res;
template<fizzbuzz_c X> struct res<X> { using result = FizzBuzz; };
template<fizz_c X> struct res<X> { using result = Fizz; };
template<buzz_c X> struct res<X> { using result = Buzz; };
template<has_N X> struct res<X> { using result = X; };

/**
 * Predeclaration of concentrator
 */
template <size_t cnt, typename... Args> 
struct concatenator;

/**
 * Recursive way of concatenating next types
 */
template <size_t cnt, typename ... Args>
struct concatenator<cnt, std::tuple<Args...>> 
{ using type = typename concatenator<cnt - 1, std::tuple< typename res< number<cnt> >::result, Args... >>::type;};

/**
 * Base case
 */
template <typename... Args> struct concatenator<0, std::tuple<Args...>> { using type = std::tuple<Args...>;};

/**
 * Final result getter
 */
template<size_t Amount>
using fizz_buzz_full_template = typename concatenator<Amount - 1, std::tuple<typename res<number<Amount>>::result>>::type;

int main()
{
	// printing result with boost, so it's clear
	std::cout << boost::typeindex::type_id<fizz_buzz_full_template<100>>().pretty_name() << std::endl;
/*
Result:
	std::tuple<number<1ul>, number<2ul>, Fizz, number<4ul>, Buzz, Fizz, number<7ul>, number<8ul>, Fizz, Buzz, number<11ul>, Fizz, number<13ul>, number<14ul>, FizzBuzz, number<16ul>, number<17ul>, Fizz, number<19ul>, Buzz, Fizz, number<22ul>, number<23ul>, Fizz, Buzz, number<26ul>, Fizz, number<28ul>, number<29ul>, FizzBuzz, number<31ul>, number<32ul>, Fizz, number<34ul>, Buzz, Fizz, number<37ul>, number<38ul>, Fizz, Buzz, number<41ul>, Fizz, number<43ul>, number<44ul>, FizzBuzz, number<46ul>, number<47ul>, Fizz, number<49ul>, Buzz, Fizz, number<52ul>, number<53ul>, Fizz, Buzz, number<56ul>, Fizz, number<58ul>, number<59ul>, FizzBuzz, number<61ul>, number<62ul>, Fizz, number<64ul>, Buzz, Fizz, number<67ul>, number<68ul>, Fizz, Buzz, number<71ul>, Fizz, number<73ul>, number<74ul>, FizzBuzz, number<76ul>, number<77ul>, Fizz, number<79ul>, Buzz, Fizz, number<82ul>, number<83ul>, Fizz, Buzz, number<86ul>, Fizz, number<88ul>, number<89ul>, FizzBuzz, number<91ul>, number<92ul>, Fizz, number<94ul>, Buzz, Fizz, number<97ul>, number<98ul>, Fizz, Buzz>
*/
}

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

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

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

использованная литература

внешние ссылки