Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Парадигмы программирования
  • v
  • т
  • е

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приведенный выше код вычисляет факториальное значение литералов 4 и 0 во время компиляции и использует результаты, как если бы они были предварительно вычисленными константами. Чтобы иметь возможность использовать шаблоны таким образом, компилятор должен знать значение своих параметров во время компиляции, что имеет естественное предварительное условие, что 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 > :: operator + = ( const  Vector < length > &  rhs )  {  for  ( int  i  =  0 ;  i  <  length ;  ++ i )  value [ i ]  + =  шк . значение [ i ];  return  * this ; }

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

template  <> Vector < 2 > &  Vector < 2 > :: operator + = ( const  Vector < 2 > &  rhs )  {  value [ 0 ]  + =  rhs . значение [ 0 ];  значение [ 1 ]  + =  прав . значение [ 1 ];  return  * this ; }

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

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

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

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

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

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

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

template  < class  Derived > struct  base {  void  interface ()  {  // ...  static_cast < Derived *> ( this ) -> implementation ();  // ...  } }; производная  структура :  база < производная > {  недействительная  реализация ()  {  // ...  } };

Здесь шаблон базового класса воспользуется преимуществом того факта, что тела функций-членов не создаются до тех пор, пока не будут объявлены их экземпляры, и он будет использовать члены производного класса в своих собственных функциях-членах посредством использования a 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 ()  {  для ( int  i = 0 ;  i  <  TABLE_SIZE ;  i ++ )  {  std :: cout  <<  table [ i ]  <<  std :: endl ;  // использование во время выполнения  }  std :: cout  <<  "FOUR:"  <<  FOUR  <<  std :: endl ; }

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

шаблон  < int  INDEX  =  0 ,  int  ... D >  struct  Helper  :  Helper < INDEX  +  1 ,  D ...,  INDEX  *  INDEX >  { }; шаблон <>  struct  Helper < 0 ,  <>>  :  Helper < 0  +  1 ,  0  *  0 >  { }; шаблон <>  struct  Helper <1 ,  < 0 >>  :  Помощник < 1  +  1 ,  0 ,  1  *  1 >  { }; template <>  struct  Helper < 2 ,  < 0 ,  1 >>  :  Helper < 2  +  1 ,  0 ,  1 ,  2  *  2 >  { }; шаблон <>  struct  Helper < 3 ,  <0 ,  1 ,  4 >>  :  Помощник < 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 >  { }; шаблон <>  struct  Helper < 6 ,  < 0 ,  1 ,  4 , 9 ,  16 ,  25 >>  :  Помощник < 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  <массив>constexpr  int  TABLE_SIZE  =  10 ;constexpr  std :: array < int ,  TABLE_SIZE >  table  =  []  {  // ИЛИ: constexpr auto table  std :: array < int ,  TABLE_SIZE >  A  =  {};  for  ( без знака  я  =  0 ;  я  <  РАЗМЕР ТАБЛИЦЫ ;  я ++ )  {  A [ я ]  =  я  *  я ;  }  return  A ; } ();enum  {  FOUR  =  table [ 2 ]  // время компиляции };int  main ()  {  для ( int  i = 0 ;  i  <  TABLE_SIZE ;  i ++ )  {  std :: cout  <<  table [ i ]  <<  std :: endl ;  // использование во время выполнения  }  std :: cout  <<  "FOUR:"  <<  FOUR  <<  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 ()  {  для ( 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 ,  VALUETYPE  OFFSET > constexpr  std :: array < VALUETYPE ,  TABLE_SIZE >  table  =  []  {  // OR: constexpr auto table  std :: array < VALUETYPE ,  TABLE_SIZE >  A  =  {};  for  ( без знака  i  =  0 ;  i  <  TABLE_SIZE ;  i ++ )  {  A [ i]  =  СМЕЩЕНИЕ  +  i  *  i ;  }  return  A ; } ();int  main ()  {  for ( int  i  =  0 ;  i  <  TABLE_SIZE ;  i ++ )  {  std :: cout  <<  table < uint16_t ,  OFFSET > [ i ]  <<  std :: endl ;  } }

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

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

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

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

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

  1. ↑ Скотт Мейерс (12 мая 2005 г.). Эффективный C ++: 55 конкретных способов улучшить ваши программы и дизайн . Pearson Education. ISBN 978-0-13-270206-5.
  2. ^ См. Историю TMP в Викиучебниках.
  3. ^ Велдхуизен, Тодд Л. «Шаблоны C ++ завершены по Тьюрингу». CiteSeerX 10.1.1.14.3670 .  Цитировать журнал требует |journal=( помощь )
  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 ++ страдает от ряда ограничений, включая проблемы с переносимостью из-за ограничений компилятора (хотя за последние несколько лет ситуация значительно улучшилась), отсутствие поддержки отладки или ввода-вывода во время создания экземпляра шаблона, длительное время компиляции, длинные и непонятные ошибки, плохое читаемость кода и плохое сообщение об ошибках. Цитировать журнал требует |journal=( помощь )
  7. ^ Шеард, Тим; Джонс, Саймон Пейтон (2002). «Шаблонное метапрограммирование для Haskell» (PDF) . АСМ 1-58113-415-0 / 01/0009. В провокационной статье Робинсона шаблоны C ++ называются главным, хотя и случайным, успехом дизайна языка C ++. Несмотря на чрезвычайно барочную природу метапрограммирования шаблонов, шаблоны используются увлекательными способами, которые выходят за рамки самых смелых мечтаний разработчиков языка. Возможно, это удивительно, учитывая тот факт, что шаблоны являются функциональными программами, функциональные программисты не спешат извлекать выгоду из успеха C ++. Цитировать журнал требует |journal=( помощь )
  • Эйзенекер, Ульрих В. (2000). Генеративное программирование: методы, инструменты и приложения . Эддисон-Уэсли. ISBN 0-201-30977-7.
  • Александреску, Андрей (2003). Современный дизайн C ++: применение общих шаблонов программирования и проектирования . Эддисон-Уэсли. ISBN 3-8266-1347-3.
  • Авраамс, Давид ; Гуртовой, Алексей (январь 2005 г.). Метапрограммирование шаблонов C ++: концепции, инструменты и методы от Boost и не только . Эддисон-Уэсли. ISBN 0-321-22725-5.
  • Вандевурде, Дэвид ; Йосуттис, Николай М. (2003). Шаблоны C ++: полное руководство . Эддисон-Уэсли. ISBN 0-201-73484-2.
  • Клавель, Мануэль (2000-10-16). Отражение в переписывании логики: металогические основы и приложения для метапрограммирования . ISBN 1-57586-238-7.

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

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