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

Although it's large (2000loc) I made a reflexive class system within c++ that is compiler independant and includes object marshalling and metadata but has no storage overhead or access time penalties. It's hardcore metaprogramming, and being used in a very big online game for mapping game objects for network transmission and database-mapping (ORM).

Anyways it takes a while to compile, about 5 minutes, but has the benefit of being as fast as hand tuned code for each object. So it saves lots of money by reducing significant CPU time on our servers (CPU usage is 5% of what it used to be).

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

  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 ++ . Все больше и больше я чувствую, что это очень похоже на введение «типов» в качестве переменных в том виде, в каком это есть в функциональном программировании. Это делает декларативное программирование возможным на 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;
}

Следующий пример взят из прекрасной книги Шаблоны 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 происходит во время компиляции, а не во время выполнения. Таким образом, он чрезвычайно эффективен с точки зрения производительности во время выполнения за счет более медленной компиляции.

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

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

Идея полностью исходит из названия Мета- означает абстрагироваться от того, на чем стоит префикс.
В более «разговорном стиле» делать что-то с вещью, а не с самой вещью.

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

Система шаблонов 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 для построения указателей -to-указатели:

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

На такого рода вопросы собеседования нет "правильного ответа". Есть несколько способов сделать это (справочные таблицы, кто угодно?), И нужно будет обсудить компромиссы между каждым из них (удобочитаемость, производительность, переносимость и ремонтопригодность).

Вопрос - это всего лишь вводный гамбит, чтобы заставить вас обсудить некоторые из вышеперечисленных вопросов и определить, насколько «глубоко» вы можете обсуждать такие проблемы.