Шаблонное метапрограммирование

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

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

Шаблонное метапрограммирование было, в некотором смысле, открыто случайно. ^{[1] [2]}

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

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

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

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

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

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

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

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

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

шаблон < беззнаковое N > struct factorial { static constexpr беззнаковое значение = N * factorial < N - 1 >:: значение ; };             шаблон <> struct factorial < 0 > { static constexpr беззнаковое значение = 1 ; };        // Примеры использования: // factorial<0>::value вернет 1; // factorial<4>::value вернет 24.

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

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

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

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

template < int length > Vector < length >& Vector < length >:: оператор += ( const Vector < length >& rhs ) { for ( int i = 0 ; i < length ; ++ i ) value [ i ] += rhs . value [ i ]; return * this ; }                    

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

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

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

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

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

class Base { public : virtual void method () { std :: cout << "Base" ; } virtual ~ Base () {} };            класс Производный : общедоступный Базовый { общедоступный : виртуальный метод void () { std :: cout << "Производный" ; } };            int main () { Base * pBase = new Derived ; pBase -> method (); //выводит "Derived" delete pBase ; return 0 ; }            

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

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

template < класс 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 <массив>  constexpr int TABLE_SIZE = 10 ;    /** * Вариативный шаблон для рекурсивной вспомогательной структуры. */ template < int INDEX = 0 , int ... D > struct Helper : Helper < INDEX + 1 , D ..., INDEX * INDEX > { };                /** * Специализация шаблона для завершения рекурсии, когда размер таблицы достигает 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 ] // использование во время компиляции };     int main () { for ( int i = 0 ; i < TABLE_SIZE ; i ++ ) { std :: cout << table [ i ] << std :: endl ; // использование во время выполнения } std :: cout << "ЧЕТЫРЕ: " << ЧЕТЫРЕ << std :: endl ; }                        

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

template < int INDEX = 0 , int ... D > структура Helper : Helper < INDEX + 1 , D ..., INDEX * INDEX > { }; template <> структура Helper < 0 , <>> : Helper < 0 + 1 , 0 * 0 > { }; template <> структура Helper < 1 , < 0 >> : Helper < 1 + 1 , 0 , 1 * 1 > { }; template <> структура Helper < 2 , < 0 , 1 >> : Helper < 2 + 1 , 0 , 1 , 2 * 2 > { }; template <> структура Helper < 3 , < 0 , 1 , 4 >> : Helper < 3 + 1 , 0 , 1 , 4 , 3 * 3 > { }; шаблон <> структура Helper < 4 , < 0 , 1 , 4 , 9 >> : Helper < 4 + 1 , 0 , 1 , 4 , 9 , 4 * 4 > { }; шаблон <> структура Helper < 5 , < 0 , 1 , 4 , 9 , 16 >> :Помощник < 5 + 1 , 0 ,                                                                                                     1 , 4 , 9 , 16 , 5 * 5 > { }; шаблон <> структура Helper < 6 , < 0 , 1 , 4 , 9 , 16 , 25 >> : Helper < 6 + 1 , 0 , 1 , 4 , 9 , 16 , 25 , 6 * 6 > { }; шаблон <> структура Helper < 7 , < 0 , 1 , 4 , 9 , 16 , 25 , 36 >> : Helper < 7 + 1 , 0 , 1 , 4 , 9 , 16 , 25 , 36 , 7 * 7 > { }; шаблон <> структура Helper < 8 , < 0 , 1 , 4 , 9 , 16 , 25 , 36 , 49 >> : Helper < 8 + 1 , 0 , 1 , 4 , 9 , 16 , 25 , 36 , 49 , 8 * 8 > { }; шаблон <> структура 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 > { }; шаблон <> структура Helper < 10 , < 0 , 1 , 4 , 9 , 16 , 25 , 36 , 49 , 64 , 81 >> { static constexpr std :: array < int , TABLE_SIZE > таблица = { 0 , 1 , 4 , 9 , 16 , 25 , 36 , 49 , 64 , 81 }; };                                    

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

 #include <iostream> #include <массив>  constexpr int TABLE_SIZE = 10 ;    constexpr std :: array < int , TABLE_SIZE > table = [] { // ИЛИ: 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 ] // использование во время компиляции };     int main () { for ( int i = 0 ; i < TABLE_SIZE ; i ++ ) { std :: cout << table [ i ] << std :: endl ; // использование во время выполнения } std :: cout << "ЧЕТЫРЕ: " << ЧЕТЫРЕ << std :: endl ; }                        

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

 #include <iostream> #include <массив>  constexpr int TABLE_SIZE = 20 ; constexpr int OFFSET = 12 ;        /** * Шаблон для вычисления одной записи таблицы */ template < typename VALUETYPE , VALUETYPE OFFSET , VALUETYPE INDEX > struct ValueHelper { static constexpr VALUETYPE value = OFFSET + INDEX * INDEX ; };                  /** * Вариативный шаблон для рекурсивной вспомогательной структуры. */ template < typename VALUETYPE , VALUETYPE OFFSET , int N = 0 , VALUETYPE ... D > struct Helper : Helper < VALUETYPE , OFFSET , N + 1 , D ..., ValueHelper < VALUETYPE , OFFSET , N >:: value > { };                    /** * Специализация шаблона для завершения рекурсии, когда размер таблицы достигает 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 <массив>  constexpr int TABLE_SIZE = 20 ; constexpr int OFFSET = 12 ;        template < typename VALUETYPE , int OFFSET > constexpr std :: array < VALUETYPE , TABLE_SIZE > table = [] { // ИЛИ: 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> // для красивой печати типов #include <iostream> #include <tuple>   /** * Тип представления слов для печати */ struct Fizz {}; struct Buzz {}; struct FizzBuzz {}; template < size_t _N > struct number { constexpr static size_t N = _N ; };                 /** * Концепции, используемые для определения условий для специализаций */ template < typename Any > concept has_N = required { required Any :: N - Any :: N == 0 ; }; template < typename A > concept fizz_c = has_N < A > && required { required A :: N % 3 == 0 ; }; template < typename A > concept buzz_c = has_N < A > && required { required A :: N % 5 == 0 ;}; template < typename A > concept fizzbuzz_c = fizz_c < A > && buzz_c < A > ;                                              /** * За счет специализации структуры `res` с учетом требований концепций выполняется правильная конкретизация */ 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 ; };                                       /** * Предварительное объявление конкатенатора */ template < size_t cnt , typename ... Args > struct concatenator ;      /** * Рекурсивный способ конкатенации следующих типов */ 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 ;};                      /** * Базовый случай */ template < typename ... Args > struct concatenator < 0 , std :: tuple < Args ... >> { using type = std :: tuple < Args ... > ;};          /** * Получатель конечного результата */ template < size_t Amount > using fizz_buzz_full_template = typename concatenator < Amount - 1 , std :: tuple < typename res < number < Amount >>:: result >>:: type ;         int main () { // выводим результат с boost, чтобы было понятно std :: cout << boost :: typeindex :: type_id < fizz_buzz_full_template < 100 >> (). pretty_name () << std :: endl ; /* Результат: std::tuple<число<1ul>, число<2ul>, Fizz, число<4ul>, Buzz, Fizz, число<7ul>, число<8ul>, Fizz, Buzz, число<11ul>, Fizz, число<13ul>, число<14ul>, FizzBuzz, число<16ul>, число<17ul>, Fizz, число<19ul>, Buzz, Fizz, число<22ul>, число<23ul>, Fizz, Buzz, число<26ul>, Fizz, число<28ul>, число<29ul>, FizzBuzz, число<31ul>, число<32ul>, Fizz, число<34ul>, Buzz, Fizz, число<37ul>, число<38ul>, Fizz, Buzz, число<41ul>, Fizz, число<43ul>, число<44ul>, FizzBuzz, номер<46ul>, номер<47ul>, Fizz, номер<49ul>, Buzz, Fizz, номер<52ul>, номер<53ul>, Fizz, Buzz, номер<56ul>, Fizz, номер<58ul>, номер<59ul>, FizzBuzz, номер<61ul>, номер<62ul>, Fizz, номер<64ul>, Buzz, Fizz, номер<67ul>, номер<68ul>, Fizz, Buzz, номер<71ul>, Fizz, номер<73ul>, номер<74ul>, FizzBuzz, номер<76ul>, номер<77ul>, Fizz, номер<79ul>, Buzz, Fizz, номер<82ul>, номер<83ul>, Fizz, Buzz, номер<86ul>, Fizz, номер<88ul>, номер<89ul>, FizzBuzz, номер<91ul>, номер<92ul>, Шипение, номер<94ul>, Жужжание, Шипение, номер<97ul>, номер<98ul>, Шипение, Шипение> */ }     

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

• Шаблонное метапрограммирование позволяет программисту сосредоточиться на архитектуре и делегировать компилятору генерацию любой реализации, требуемой клиентским кодом. Таким образом, шаблонное метапрограммирование может достичь действительно универсального кода , способствуя минимизации кода и лучшей поддерживаемости ^{[ требуется цитата ]} .
• Что касается C++ до версии C++11 , синтаксис и идиомы метапрограммирования шаблонов были эзотерическими по сравнению с обычным программированием на C++, и метапрограммы шаблонов могли быть очень трудными для понимания. ^{[7] [8]} Но начиная с C++11 синтаксис метапрограммирования вычисления значений становится все более и более похожим на «обычный» C++, с меньшими потерями в читабельности.

• Неудача при замене не является ошибкой (SFINAE)
• Метапрограммирование
• Препроцессор
• Параметрический полиморфизм
• Шаблоны выражений
• Вариативный шаблон
• Выполнение функции во время компиляции

• Айзенекер, Ульрих В. (2000). Генеративное программирование: методы, инструменты и приложения . Addison-Wesley. ISBN 0-201-30977-7.
• Александреску, Андрей (2003). Современный дизайн C++: применение шаблонов обобщенного программирования и проектирования . Addison-Wesley. ISBN 3-8266-1347-3.
• Абрахамс, Дэвид ; Гуртовой, Алексей (январь 2005 г.). Метапрограммирование шаблонов C++: концепции, инструменты и методы из Boost и далее . Addison-Wesley. ISBN 0-321-22725-5.
• Вандевурде, Дэвид; Джосуттис, Николай М. (2003). Шаблоны C++: Полное руководство . Аддисон-Уэсли. ISBN 0-201-73484-2.
• Клавель, Мануэль (16.10.2000). Размышления о переписывании логики: металогические основы и приложения метапрограммирования . Cambridge University Press. ISBN 1-57586-238-7.

• «Библиотека метапрограммирования Boost (Boost MPL)».
• «Библиотека Духа».(построено с использованием шаблонного метапрограммирования)
• «Библиотека Boost Lambda».(легко использовать алгоритмы STL)
• Вельдхёйзен, Тодд (май 1995 г.). «Использование метапрограмм шаблонов C++». C++ Report . 7 (4): 36–43 . Архивировано из оригинала 2009-03-04.
• «Шаблон Хаскелл».(типобезопасное метапрограммирование в Haskell)
• Брайт, Уолтер . «Повторный взгляд на шаблоны».(шаблон метапрограммирования на языке программирования D )
• Коскинен, Йоханнес . «Метапрограммирование в C++» (PDF) .
• Аттарди, Джузеппе; Чистернино, Антонио. «Поддержка рефлексии посредством шаблонного метапрограммирования» (PDF) .
• Бертон, Майкл К.; Грисволд, Уильям Г.; Маккалок, Эндрю Д.; Хубер, Гэри А. (2002). "Статические структуры данных". CiteSeerX  10.1.1.14.5881 .
• Амджад, Зишан (13 августа 2007 г.). «Шаблонная метапрограмма и теория чисел».
• Амджад, Зишан (24 августа 2007 г.). «Шаблонное метапрограммирование и теория чисел: Часть 2».
• «Библиотека для программирования в стиле LISP на C++».