Что такое метапрограммирование?

До сих пор большинство примеров оперировали значениями (вычисление цифр числа пи, факториала N и т. п.), и это практически примеры из учебника, но в целом они не очень полезны. Просто сложно представить ситуацию, когда вам действительно нужен компилятор для вычисления 17-й цифры числа пи. Либо вы жестко кодируете его сами, либо вычисляете во время выполнения.

Пример, который может быть более уместным для реального мира, может быть таким:

Допустим, у нас есть класс массива, где размер является параметром шаблона (так что это будет объявлять массив из 10 целых чисел: array<int, 10>)

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

template <typename T, int lhs_size, int rhs_size>
array<T, lhs_size + rhs_size> concat(const array<T, lhs_size>& lhs, const array<T, rhs_size>& rhs){

  array<T, lhs_size + rhs_size> result;
  // copy values from lhs and rhs to result
  return result;

}

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

Однако чаще вы склонны использовать метапрограммирование для типов, а не для значений.

Хороший пример можно найти в стандартной библиотеке. Каждый тип контейнера определяет свой собственный тип итератора, но простые старые указатели также могут использоваться в качестве итераторов. Технически итератор требуется для предоставления ряда членов typedef, таких как value_type, а указатели, очевидно, этого не делают. Поэтому мы используем немного метапрограммирования, чтобы сказать: «О, но если тип итератора оказывается указателем, его value_type вместо этого следует использовать это определение».

Есть две вещи, которые следует отметить по этому поводу. Во-первых, мы манипулируем типами, а не значениями. Мы не говорим, что «факториал N такой-то и такой-то», а скорее «value_type типа T определяется как...»

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

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

Несмотря на то, что он большой (2000loc), я создал рефлексивную систему классов в C++, которая независима от компилятора и включает в себя сортировку объектов и метаданные, но не имеет накладных расходов на хранение или штрафов за время доступа. Это хардкорное метапрограммирование, которое используется в очень крупной онлайн-игре для отображения игровых объектов для передачи по сети и отображения базы данных (ORM).

В любом случае, для компиляции требуется некоторое время, около 5 минут, но преимущество заключается в том, что он выполняется так же быстро, как код, настроенный вручную для каждого объекта. Таким образом, это экономит много денег за счет значительного сокращения времени ЦП на наших серверах (использование ЦП составляет 5% от того, что было раньше).

Эта концепция полностью исходит из названия Meta-, что означает абстрагирование от того, к чему оно предшествует.< br> В более «разговорном стиле» делать что-то с вещью, а не с самой вещью.

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

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

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

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

Глядя на код QT MetaObjects, я бы не стал (при беглом осмотре) называть его метапрограммированием в том смысле, который обычно используется для таких вещей, как система шаблонов C++ или макросы Lisp. Похоже, это просто форма генерации кода, которая внедряет некоторые функции в существующие классы на этапе компиляции (его можно рассматривать как предшественника модного в настоящее время стиля аспектно-ориентированного программирования или объектных систем на основе прототипов в таких языках, как JavaScripts).

В качестве примера экстремальной длины вы можете взять это в C++: Boost MPL, чей руководство показывает, как получить:

Размерные типы (единицы Мера)

quantity<float,length> l( 1.0f );
quantity<float,mass> m( 2.0f );
m = l;    // compile-time type error

Метафункции высшего порядка

дважды (f, x): = f (f (x))

template <class F, class X>
struct twice
  : apply1<F, typename apply1<F,X>::type>
{};

struct add_pointer_f
{
    template <class T>
    struct apply : boost::add_pointer<T> {};
};

Теперь мы можем дважды использовать add_pointer_f для создания указателей на указатели:

BOOST_STATIC_ASSERT((
    boost::is_same<
         twice<add_pointer_f, int>::type
       , int**
    >::value
));

Вот типичный пример:

  template <int N>
  struct fact {
      enum { value = N * fact<N-1>::value };
  };

  template <>
  struct fact<1> {
      enum { value = 1 };
  }; 

  std::cout << "5! = " << fact<5>::value << std::endl; 

Вы в основном используете шаблоны для вычисления факториала.

Более практичный пример, который я недавно видел, — это объектная модель, основанная на таблицах БД, в которой использовались классы-шаблоны для моделирования отношений внешних ключей в базовых таблицах.

Другой пример: в этом случае метод метапрограммирования используется для получения значения PI произвольной точности во время компиляции с использованием алгоритма Гаусса-Лежандра.

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

Лично я люблю метапрограммирование, потому что ненавижу повторяться и потому что могу настраивать константы, используя ограничения архитектуры.

Надеюсь, вам это нравится.

Просто мои 2 цента.

/**
 *  FILE     : MetaPI.cpp
 *  COMPILE  : g++ -Wall -Winline -pedantic -O1 MetaPI.cpp -o MetaPI
 *  CHECK    : g++ -Wall -Winline -pedantic -O1 -S -c MetaPI.cpp [read file MetaPI.s]
 *  PURPOSE  : simple example template metaprogramming to compute the
 *             value of PI using [1,2].
 *
 *  TESTED ON:
 *  - Windows XP, x86 32-bit, G++ 4.3.3
 *
 *  REFERENCES:
 *  [1]: http://en.wikipedia.org/wiki/Gauss%E2%80%93Legendre_algorithm
 *  [2]: http://www.geocities.com/hjsmithh/Pi/Gauss_L.html
 *  [3]: http://ubiety.uwaterloo.ca/~tveldhui/papers/Template-Metaprograms/meta-art.html
 *
 *  NOTE: to make assembly code more human-readable, we'll avoid using
 *        C++ standard includes/libraries. Instead we'll use C's ones.
 */

#include <cmath>
#include <cstdio>

template <int maxIterations>
inline static double compute(double &a, double &b, double &t, double &p)
{
    double y = a;
    a = (a + b) / 2;
    b = sqrt(b * y);
    t = t - p * ((y - a) * (y - a));
    p = 2 * p;

    return compute<maxIterations - 1>(a, b, t, p);
}

// template specialization: used to stop the template instantiation
// recursion and to return the final value (pi) computed by Gauss-Legendre algorithm
template <>
inline double compute<0>(double &a, double &b, double &t, double &p)
{
    return ((a + b) * (a + b)) / (4 * t);
}

template <int maxIterations>
inline static double compute()
{
    double a = 1;
    double b = (double)1 / sqrt(2.0);
    double t = (double)1 / 4;
    double p = 1;

    return compute<maxIterations>(a, b, t, p); // call the overloaded function
}

int main(int argc, char **argv)
{
    printf("\nTEMPLATE METAPROGRAMMING EXAMPLE:\n");
    printf("Compile-time PI computation based on\n");
    printf("Gauss-Legendre algorithm (C++)\n\n");

    printf("Pi=%.16f\n\n", compute<5>());

    return 0;
}

Следующий пример взят из превосходной книги Шаблоны C++ — полное руководство.

#include <iostream>
using namespace std;

template <int N> struct Pow3 {
   enum { pow = 3 * Pow3<N-1>::pow };
}

template <> struct Pow3<0> {
   enum { pow = 1 };
}

int main() {
   cout << "3 to the 7 is " << Pow<7>::pow << "\n";
}

Смысл этого кода в том, что рекурсивное вычисление 7-й степени числа 3 происходит во время компиляции, а не во время выполнения. Таким образом, он чрезвычайно эффективен с точки зрения производительности во время выполнения за счет более медленной компиляции.

Это полезно? В этом примере, наверное, нет. Но есть проблемы, когда выполнение вычислений во время компиляции может быть преимуществом.

Трудно сказать, что такое метапрограммирование C++. Я все больше и больше чувствую, что это очень похоже на введение «типов» в качестве переменных, как это делается в функциональном программировании. Это делает возможным декларативное программирование на C++.

Намного проще показать примеры.

Одним из моих любимых является «трюк» (или паттерн:)) для сглаживания многократно вложенных блоков switch/case:

#include <iostream>
using namespace std;

enum CCountry { Belgium, Japan };
enum CEra     { ancient, medieval, future };

// nested switch
void historic( CCountry country, CEra era ) {
  switch( country ) {
        case( Belgium ):
          switch( era ) {
            case( ancient ): cout << "Ambiorix"; break;
            case( medieval ): cout << "Keizer Karel"; break;
          }
          break;
        case( Japan ):
          switch( era ) {
            case( future ): cout << "another Ruby?"; break;
            case( medieval ): cout << "Musashi Mijamoto"; break;
          }
          break;
  }
}


// the flattened, metaprogramming way
// define the conversion from 'runtime arguments' to compile-time arguments (if needed...)
// or use just as is.
template< CCountry country, CEra era > void thistoric();


template<> void thistoric<Belgium, ancient> () { cout << "Ambiorix"; }
template<> void thistoric<Belgium, medieval>() { cout << "Keizer Karel"; }
template<> void thistoric<Belgium, future  >() { cout << "Beer, lots of it"; }

template<> void thistoric<Japan, ancient> () { cout << "wikipedia"; }
template<> void thistoric<Japan, medieval>() { cout << "Musashi"; }
template<> void thistoric<Japan, future  >() { cout << "another Ruby?"; }


// optional: conversion from runtime to compile-time
//
template< CCountry country > struct SelectCountry {
  static void select( CEra era ) {
    switch (era) {
          case( medieval ): thistoric<country, medieval>(); break;
          case( ancient  ): thistoric<country, ancient >(); break;
          case( future   ): thistoric<country, future  >(); break;

    }
  }
};

void Thistoric ( CCountry country, CEra era ) {
    switch( country ) {
          case( Belgium ): SelectCountry<Belgium>::select( era ); break;
          case( Japan   ): SelectCountry<Japan  >::select( era ); break;
    }
  } 



int main() {   
  historic( Belgium, medieval ); // plain, nested switch
  thistoric<Belgium,medieval>(); // direct compile time switch
  Thistoric( Belgium, medieval );// flattened nested switch
  return 0;
}

Единственный раз, когда мне нужно было использовать Boost.MPL в моей повседневной работе, это когда мне нужно было преобразовать boost::variant в и из QVariant.

Поскольку boost::variant имеет механизм посещения O(1), направление от boost::variant к QVariant почти тривиально.

Однако QVariant не имеет механизма посещения, поэтому, чтобы преобразовать его в boost::variant, вам нужно перебрать mpl::list типов, которые может содержать конкретная реализация boost::variant, и для каждого типа спросить QVariant, содержит ли он этот тип. , и если это так, извлеките значение и верните его в файле boost::variant. Это довольно весело, вы должны попробовать это :)

QtMetaObject в основном реализует отражение (Reflection) и ЯВЛЯЕТСЯ одним из них. одной из основных форм метапрограммирования, на самом деле весьма мощной. Он похож на отражение в Java и также широко используется в динамических языках (Python, Ruby, PHP...). Это более читабельно, чем шаблоны, но у обоих есть свои плюсы и минусы.

Это простое «вычисление стоимости» в духе Факториала. Тем не менее, вы, скорее всего, будете использовать его в своем коде.

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

template<long long int POW2VAL> class NextPow2Helper
{
    enum { c_ValueMinusOneBit     = (POW2VAL&(POW2VAL-1)) };
public:
    enum {
        c_TopBit                      = (c_ValueMinusOneBit) ?
            NextPow2Helper<c_ValueMinusOneBit>::c_TopBit : POW2VAL,
        c_Pow2ThatIsGreaterOrEqual    = (c_ValueMinusOneBit) ?
            (c_TopBit<<1) : c_TopBit
    };
};
template<> class NextPow2Helper<1>
{ public: enum { c_TopBit = 1, c_Pow2ThatIsGreaterOrEqual = 1 }; };
template<> class NextPow2Helper<0>
{ public: enum { c_TopBit = 0, c_Pow2ThatIsGreaterOrEqual = 0 }; };
// This only works for values known at Compile Time (CT)
#define CT_NEXTPOWEROFTWO2(VAL) NextPow2Helper<VAL>::c_Pow2ThatIsGreaterOrEqual