Метапрограммирование — это «программирование программ», то есть написание некой промежуточной программы, результатом которой будет некая часть другой программы. Самый простой пример метапрограммирования — это шаблоны C++. Вместо написания десяти одинаковых функций для разных типов, мы пишем шаблон, и компилятор сам соберет нам эти десять функций.
Другой неявный пример метапрограммирования — это precomputing, вычисления, которые проводятся на этапе компиляции. Если в коде вы напишете
компилятор (вернее, прекомпилятор), вычислит это значение и передаст компилятору уже готовое
Прекомпилятор пытается вычислить все возможное на этапе компиляции, чтобы разгрузить ран-тайм, в том числе и раскрыть шаблоны. Именно это его свойство позволяет писать очень интересные precomputing штучки, которые будут вычислены на этапе компиляции.
Конкретный пример — это реализация CRC32. Не вдаваясь в детали, приведу ее алгоритм:
Для этого алгоритма нужна таблица из 256 чисел. Логично было бы не вычислять ее при каждом вызове функции, да и вообще, так как таблица определена заранее, записать ее в виде
Но это как-то неслишком круто. Посему было решено вынести ее вычисление в compile-time средствами метапрограммирования.
Рассмотрим функцию вычисления таблицы поближе. Она состоит из четырех составляющих:
Будем создавать наше вычисление по шагам.
Первый шаг — создание шаблона, который по данному t вычислит значение полинома. Это неслишком сложно:
Данный шаблон принимает на вход unsigned long параметр и превращает его в структуру с определенной внутри константой value.
Следющий шаг — выполнение этого кода в цикле. Для этого определим такой шаблон:
Здесь начинается магия.
Мы определили шаблон, который получает два параметра — t, собственно вычисляемое значение, и i — счетчик. Этот шаблон создает структуру с единственной константой value внутри, которая вычисляется… через значение этого же шаблона! Мы получаем рекурсию — шаблон определеятся через самого себя. Для завершения рекурсии, мы воспользуемся частичной специализацией шаблона:
И, наконец, само вычисление — вызов шаблона For с определенным количество итераций:
Что же происходит в этих строчках.
Прекомпилятор пытается вычислить все значения констант. Если выражение задано через другие константы — это выражение также является константным и будет вычислено на этапе компиляции. С другой стороны, компилятору от прекомпилятора необходимы полностью специализированные шаблоны, поэтому прекомпилятор будет последовательно раскрывать все шаблоны, попутно вычисляя константы, определенные в них.
Все это очень напоминает вычисление рекурсивных функций в функциональном программировании:
(Не уверен в точности написания, но суть, думаю, понята)
Третий и четвертый шаги — создать таблицу вычисленных значений. Опять-таки воспользуемся шаблоном со счетчиком:
Здесь происходит переход от препроцессора собственно к коду. Первый шаблон создает рекурсивную иеррахию наследников структур Table, каждый из которых добавляет занчение в таблицу values, соотвествующую своему номеру. Второй шаблон определяет конец рекурсии, собственно саму таблицу values и идексатор для более простого использования этой таблицы.
Последний шаг — это, собственно, объявление самой таблицы
Теперь у нас есть структура, которая ведет себя в точности как необходимая нам таблица. Так как все вычисления известны во время компиляции, прекомпилятор раскроет все шаблоны и в конце концов соберет нужную нам таблицу.
Вот так это все выглядит в собранном виде
Для заинтересовавшихся — советую почитать Андрей Александреску «Современное проектирование на С++» ISBN: 5-8459-0351-3
Другой неявный пример метапрограммирования — это precomputing, вычисления, которые проводятся на этапе компиляции. Если в коде вы напишете
int i = 2+2*2;
компилятор (вернее, прекомпилятор), вычислит это значение и передаст компилятору уже готовое
int i = 6;
Прекомпилятор пытается вычислить все возможное на этапе компиляции, чтобы разгрузить ран-тайм, в том числе и раскрыть шаблоны. Именно это его свойство позволяет писать очень интересные precomputing штучки, которые будут вычислены на этапе компиляции.
Конкретный пример — это реализация CRC32. Не вдаваясь в детали, приведу ее алгоритм:
unsigned long Crc32(unsigned char *buf, unsigned long len)
{
unsigned long crc_table[256];
unsigned long crc;
for (int i = 0; i < 256; i++)
{
crc = i;
for (int j = 0; j < 8; j++)
crc = crc & 1 ? (crc >> 1) ^ 0xEDB88320UL : crc >> 1;
crc_table[i] = crc;
}
crc = 0xFFFFFFFFUL;
while (len--)
crc = crc_table[(crc ^ *buf++) & 0xFF] ^ (crc >> 8);
return crc ^ 0xFFFFFFFFUL;
};
Для этого алгоритма нужна таблица из 256 чисел. Логично было бы не вычислять ее при каждом вызове функции, да и вообще, так как таблица определена заранее, записать ее в виде
long crc_table[256] = {"0x12345678", ... }
Но это как-то неслишком круто. Посему было решено вынести ее вычисление в compile-time средствами метапрограммирования.
Рассмотрим функцию вычисления таблицы поближе. Она состоит из четырех составляющих:
- вычисления значения полинома:
crc = crc & 1 ? (crc >> 1) ^ 0xEDB88320UL : crc >> 1;
- цикла, повторяющего вычисления «рекурсивно» 8 раз, то есть применяющего первое выражение последовательно для одного и того же алгортима:
for (int j = 0; j < 8; j++)
- сохранения вычисленного значения в таблице:
crc_table[i] = crc
- и цикла для всей таблицы:
for (int i = 0; i < 256; i++)
Будем создавать наше вычисление по шагам.
Первый шаг — создание шаблона, который по данному t вычислит значение полинома. Это неслишком сложно:
template <unsigned long t> struct Polynome { static const unsigned long value = t&1 ? (t>>1)^0xedb88320 : t>>1 }; };
Данный шаблон принимает на вход unsigned long параметр и превращает его в структуру с определенной внутри константой value.
Следющий шаг — выполнение этого кода в цикле. Для этого определим такой шаблон:
template <unsigned long t, int i> struct For { static const unsigned long value = For<Polynome<t>::value, i-1 >::value; };
Здесь начинается магия.
Мы определили шаблон, который получает два параметра — t, собственно вычисляемое значение, и i — счетчик. Этот шаблон создает структуру с единственной константой value внутри, которая вычисляется… через значение этого же шаблона! Мы получаем рекурсию — шаблон определеятся через самого себя. Для завершения рекурсии, мы воспользуемся частичной специализацией шаблона:
template <unsigned long t> struct For<t,0> { static const unsigned long value = Polynome<t>::value; };
И, наконец, само вычисление — вызов шаблона For с определенным количество итераций:
template < unsigned long t> struct Hash { static const unsigned long value = For<t,7>::value; };
Что же происходит в этих строчках.
Прекомпилятор пытается вычислить все значения констант. Если выражение задано через другие константы — это выражение также является константным и будет вычислено на этапе компиляции. С другой стороны, компилятору от прекомпилятора необходимы полностью специализированные шаблоны, поэтому прекомпилятор будет последовательно раскрывать все шаблоны, попутно вычисляя константы, определенные в них.
Все это очень напоминает вычисление рекурсивных функций в функциональном программировании:
polynom x = x & 1 ? (x >> 1) ^ 0xEDB88320UL : x >> 1
for x t = polynom(for x t-1)
for x 0 = polynom(x)
hash x = for x 7
(Не уверен в точности написания, но суть, думаю, понята)
Третий и четвертый шаги — создать таблицу вычисленных значений. Опять-таки воспользуемся шаблоном со счетчиком:
template<int r, int t> struct Table : Table<r+1, t-1>
{
Table() { values[t]=Hash<t>::value; }
};
template<int r> struct Table<r,0>
{
unsigned long values[r+1];
Table() { values[0]=Hash<0>::value; }
unsigned long operator[](int i) { return values[i];}
};* This source code was highlighted with Source Code Highlighter.
Здесь происходит переход от препроцессора собственно к коду. Первый шаблон создает рекурсивную иеррахию наследников структур Table, каждый из которых добавляет занчение в таблицу values, соотвествующую своему номеру. Второй шаблон определяет конец рекурсии, собственно саму таблицу values и идексатор для более простого использования этой таблицы.
Последний шаг — это, собственно, объявление самой таблицы
typedef Table<0,255> CRC_TABLE;
Теперь у нас есть структура, которая ведет себя в точности как необходимая нам таблица. Так как все вычисления известны во время компиляции, прекомпилятор раскроет все шаблоны и в конце концов соберет нужную нам таблицу.
Вот так это все выглядит в собранном виде
template <unsigned long t> struct Polynome { static const unsigned long value = t&1 ? (t>>1)^0xedb88320 : t>>1; };
template <unsigned long t, int i> struct For { static const unsigned long value = For<Polynome<t>::value,i-1 >::value; };
template <unsigned long t> struct For<t,0> { static const unsigned long value = Polynome<t>::value; };
template <unsigned long t> struct Hash { static const unsigned long value = For<t,7>::value; };
template<int r, int t> struct Table : Table<r+1, t-1>
{
Table() { values[t]=Hash<t>::value; }
};
template<int r> struct Table<r,0>
{
int values[r+1];
Table() { values[0]=Hash<0>::value; }
int operator[](int i) { return values[i];}
};
typedef Table<0,255> CRC_TABLE;
class Crc32Hasher
{
CRC_TABLE crc_table;
public:
unsigned long GetHashCode(const void* pObj, size_t length){
const char* buf = (const char*)pObj;
unsigned long crc32=0xffffffff;
for (size_t i=0; i<length; i++)
crc32=crc_table[(crc32^(*buf++))&0xff]^(crc32>>8);
crc32=crc32^0xffffffff;
return crc32;
}
};* This source code was highlighted with Source Code Highlighter.
Для заинтересовавшихся — советую почитать Андрей Александреску «Современное проектирование на С++» ISBN: 5-8459-0351-3