Метапрограммирование на C++: списки типов (typelists)

Классика жанра: книга одного из основоположников современного подхода к метапрограммированию в языке C++

Андрей Александреску
Современное проектирование на С++: Обобщенное программирование и прикладные шаблоны проектирования

Удивительная по простоте реализации и необычности концепция в C++. Списки объектов - это привычно и понятно. Но в языке C++ тип - это сущность, которая имеет только внешние проявления (лексическое - в виде спецификации типа long int или std::list) и внутреннее - специфичное для каждого компилятора и извлекаемое на свет божий только опосредованно с помощью оператора typeid. В среде .Net все проще - типы (их спецификация) с помощью определенных манипуляций могут становиться объектами System.Type, в результате чего задача манипулирования типами сводится к известной задаче манипулирования объектами. В стандартном C++ все гораздо интереснее, так как стандарт не предусматривает, к примеру, возможность создания объекта, тип которого задан строкой. То есть манипулировать типами вроде как и невозможно?

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

Заинтригованы? Поглядываете недоверчиво на текст?

Главное заклинание - шаблоны. С их помощью удается подняться на метауровень языка C++ для магических манипуляций с типами. Причем заклинания для списков типов работают на этапе компиляции программы - как и все, что связано с шаблонами.

Как это можно практически использовать?

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

Кто это придумал?

Как это реализовано?

Внутреннее устройство списков типов

Сам список типов устроен настолько просто, что на первый взгляд даже не верится. Но это - простота колеса, которое применяется тысячью способов.

Head - это голова списка (единственный тип), а Tail - его хвост, который может быть и списком типов, и нулевым типом.

Нулевой тип (null type) - это класс, объявленный в библиотеке Loki так:

Нельзя создать объект этого класса (так как публичного конструктора у него нет), и единственное, для чего он нужен - служить индикатором конца списка типов.

Таким образом, список с одним типом char создается так:

Для списка из двух типов char и int, вопреки вашим ожиданиям, нужен такой синтаксис:

Обратите внимание, что хотя задавать второй параметр шаблона TypeList надо либо как список типов, либо как NullType, но если Вы зададите его как обычный тип - вроде ничего и не произойдет. Но некоторые метафункции работы со списками типов работать откажутся - с выдачей невнятной диагностики. Чтобы явно задать проверку на соответствие параметров шаблонов заданным критериям, необходимо привлекать средства библиотеки Boost.Concept_check, но это мы пока оставим без реализации.

Макросы для удобного создания списков типов

Создавать длинные списки непосредственно рекурсивным конструированием крайне неудобно. Такой стиль создания списков характерен для языка Лисп, но он нынче не в фаворе. В библиотеке Loki предусмотрен набор довольно удобных макросов, позволяющих создавать списки натуральным образом:

Определение макросов достаточно тривиально (см. библиотечный хидер loki/typelist.h:

и так далее. Библиотека Loki содержит макросы для создания списков типов вплоть до 50 элементов, хотя при необходимости легко добавить новые макросы.

Метафункции для списков типов

Библиотека Loki содержит реализацию следующих функций для списков типов:

MostDerived<> - частичная сортировка списка (производные классы переносятся в начало списка)

Метафункция Length - вычисление длины списка типов

Рассмотрим детально самую простую функцию для списков типов - вычисление длины списка. Вместо цикла используется рекурсия (это обычное дело в обобщенном программировании на C++ - см. к примеру статью о вычислении факториала). Критерием выхода из рекурсии служит то факт, что последний элемент списка - это обязательно NullType.

// Для NullType длина списка равна 0
template <> struct Length<NullType>
{
enum { value=0 };
};

// Рекурсивная формула
template <class T,class U>
struct Length< TypeList< T, U> >
{
enum { value = 1 + Length<U>::value };
};

Использовать метафункцию для определения длины списка можно примерно так:

Практический пример использования

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

Разбор примера по винтикам

Печать содержимого списка типов

Прежде всего, чтобы комфортно изучать операции со списками типов, желательно как-то распечатывать их. Вы должны понимать, что все операции со списками типов выполняются на стадии компиляции, к примеру - для доступа к любому элементу надо указать его индекс как константу времени компиляции (а не переменную цикла). Поэтому просто написать функцию, которая в цикле for вызывает Loki::TL::TypeAt<> для каждого элемента не получится. Но ничто не мешает нам написать простой метаалгоритм - с помощью двух рекурсивно вызываемых шаблонных функций можно печатать весь список:

// Вспомогательная функция - печатает символическое представление типа T
template < typename T >
void Print_Type(void) { cout << "(" << typeid( T ).name() << ") "; }

// **********************************************************************
// Две шаблонные функции образуют ЦИКЛ по всем элементам списка типов.
//
// 1------
template < typename TList >
void Print_Type_List( TList x )
{
Print_Type< TList::Head >();
Print_Type_List( TList::Tail() );
}

// 2------
template <>
void Print_Type_List<NullType>( NullType )
{
}

Вызов функции Print_Type<> с явным указанием списка как параметра специализации выполняет печать:

typedef TYPELIST_4(int,double,long,char*) list1;

Print_Type_List<list1>(list1());

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

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

Список знаковых типов

// Список типов, которые могут хранить отрицательные значения.
typedef TYPELIST_7(signed char,int,long,float,double,long double,__int64) signeds;

Определенный в библиотеке Loki макрос TYPELIST_7 делает всю утомительную работу. После этого со списком signeds можно начинать работать.

Как реализован выбор функции в зависимости от принадлежности типа к списку

Вообще говоря, технология подробно описана в другой статье "Выбор кода при компиляции". Вкратце идея такова.

Во-первых создает шаблонный класс, содержащий статический метод для выполнения вычисления:

// Класс, содержащий статический метод для вычисления корня для знаковых типов
template < typename T, bool is_signed >
struct sqrt_resolver
{
static T calc( T arg )
{
// Проверяем (во время компиляции, что тип T не является указателем).
STATIC_CHECK( Loki::TypeTraits<T>::isPointer==false, Pointers_Arent_Allowed );

T res=arg/2;

// ...

return res;
}
};

И специализацию для значения параметра is_signed=false:

// Случай для знаковых типов - надо проверять знак.
template < typename T >
struct sqrt_resolver< T, true >
{
static T calc( T arg )
{
if( arg<0 )
throw std::exception();

T res=arg/2;

// ...

return res;
}
};

Теперь сама функция, которая вызывается пользовательским кодом и направляет компиляцию в одну из двух альтернатив:

template < typename X >
X square_root( X x )
{
return sqrt_resolver<X,Loki::TL::IndexOf<signeds,X>::value!=-1>::calc(x);
}

Как видите, принадлежность типа аргумента функции к подмножеству определяется с помощью метода Loki::TL::IndexOf<>. Слово 'метод' написано курсовом, так как на самом деле это - шаблонный класс, хотя функционально и синтаксически все выглядит как вызов метода.

Внутри одной из двух специализаций класса-вычислителя можно увидеть проверку типа - не указатель ли это (опять-таки с помощью средств библиотеки Loki, хотя в Boost.Type_traits есть аналогичные средства). В этом случае мы вплотную приближаемся к такому интересному вопросу, как concept check - проверка правильности использования шаблона (см. библиотеку Boost.Concept_check).