✖


Jump to content

Template metaprogramming

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

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

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

Components of template metaprogramming [ edit ]

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

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

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

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

Using template metaprogramming [ edit ]

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

Генерация классов во время компиляции [ править ]

Что именно означает «программирование во время компиляции», можно проиллюстрировать на примере функции факториала, которую на нешаблоном 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 во время компиляции и использует результаты, как если бы они были предварительно рассчитанными константами. Чтобы иметь возможность использовать шаблоны таким образом, компилятор должен знать значение своих параметров во время компиляции, что имеет естественное предварительное условие: факториал<X>::value может использоваться только в том случае, если X известен во время компиляции. Другими словами, X должен быть константным литералом или константным выражением.

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

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

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

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

во время компиляции В качестве еще одного, более значимого примера развертывания цикла можно использовать метапрограммирование шаблонов для создания длиной 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()
     {
         // ...
     }
};

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

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

Генерация статической таблицы [ править ]

Преимущество статических таблиц — замена «дорогих» вычислений простой операцией индексации массива (примеры см. в справочной таблице ). В 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, int 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++ новый инструмент для программирования меташаблонов — концепции. [6]

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

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

#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 instantiation 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 concatenator
 */
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++, и метапрограммы шаблонов могли быть очень трудными для понимания. [7] [8] Но начиная с C++11 синтаксис метапрограммирования вычислений значений становится все более и более похожим на «нормальный» C++, с все меньшим и меньшим ухудшением читаемости.

См. также [ править ]

Ссылки [ править ]

  1. ^ Скотт Мейерс (12 мая 2005 г.). Эффективный C++: 55 конкретных способов улучшить ваши программы и проекты . Пирсон Образование. ISBN  978-0-13-270206-5 .
  2. ^ См . Историю TMP в Wikibooks.
  3. ^ Вельдхуизен, Тодд Л. (2003). «Шаблоны C++ полны по Тьюрингу». CiteSeerX   10.1.1.14.3670 .
  4. ^ «Constexpr — Обобщенные константные выражения в C++11 — Cprogramming.com» . www.cprogramming.com .
  5. ^ «Фасад Итератора — 1.79.0» .
  6. ^ «Ограничения и концепции (начиная с C++20) — cppreference.com» . ru.cppreference.com .
  7. ^ Чарнецкий, К.; О'Доннелл, Дж.; Стригниц, Дж.; Таха, Валид Мохамед (2004). «Реализация DSL в метаокамле, шаблоне Haskell и C++» (PDF) . Университет Ватерлоо, Университет Глазго, Исследовательский центр Юлиха, Университет Райса. Метапрограммирование шаблонов C++ страдает от ряда ограничений, в том числе проблем с переносимостью из-за ограничений компилятора (хотя за последние несколько лет ситуация значительно улучшилась), отсутствия поддержки отладки или ввода-вывода во время создания экземпляра шаблона, длительного времени компиляции, длинных и непонятных ошибок, плохой читаемость кода и плохая отчетность об ошибках.
  8. ^ Шеард, Тим; Джонс, Саймон Пейтон (2002). «Шаблон метапрограммирования для Haskell» (PDF) . АСМ 1-58113-415-0/01/0009. В провокационной статье Робинсона шаблоны C++ названы главным, хотя и случайным, успехом разработки языка C++. Несмотря на чрезвычайно причудливую природу метапрограммирования шаблонов, шаблоны используются удивительными способами, выходящими за рамки самых смелых мечтаний разработчиков языка. Возможно, это удивительно, но, учитывая тот факт, что шаблоны являются функциональными программами, функциональные программисты не спешат извлекать выгоду из успеха C++.

Внешние ссылки [ править ]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Template_metaprogramming&oldid=1226317186"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 6f78ee2381c6a6317d586830cd6e5a0c__1717008000
URL1:https://arc.ask3.ru/arc/aa/6f/0c/6f78ee2381c6a6317d586830cd6e5a0c.html
Заголовок, (Title) документа по адресу, URL1:
Template metaprogramming - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)