Недавно приходилось наблюдать дискуссию о каррировании и частичном применении. Суть этой полемики состояла в том, что лучше, для практических целей, иметь в языке программирования: встроенное частичное применение (например, как в Nemerle) или встроенное каррирование (как, например, в Haskell).
Nemerle:
def sum3(x: int, y: int, z: int): int // определяем функцию
{
x + y + z;
};
def sum3y = sum3(_, 5, _); // передаем только второй аргумент
def sum3yz = sum3y(_, 5); // передаем еще третий
def sum3yzx = sum3yz(5); // …и первый, получаем 15
Haskell:
sum3 x y z = x + y + z -- определяем функцию
sum3x = sum3 5 -- передаем только первый аргумент
sum3xy = sum3x 5 -- передаем второй
sum3xyz = sum3xy 5 -- …и третий, получаем 15
Лично я думаю, что нужно реализовать обе сущности. Тем более уже достаточно времени прошло от того момента когда в gcc появились возможности из грядущего стандарта C++, а именно Variadic templates. Как вы поняли, в статье предлагается реализация каррирования и частичного применения для C++ с помощью Variadic templates. В ходе работы использовались MinGW gcc 4.6.1 и Code::Blocks 10.05.
Каррирование
Начнем с каррирования, тем более что это интуитивно понятно. Целью будем считать функцию высшего порядка, которая принимает функцию и возвращает ее каррированный вариант. Далее этой функции можно передать произвольное количество аргументов, получая в результате другую функцию, которая принимает остальные аргументы и выдает окончательный результат.
std::function< int(int, int, int) > f =
[] ( int x, int y, int z )
{
return x + y + z;
};
auto f1 = carry(f);
auto f2 = f1(5, 5);
auto v15 = f2(5);
Нам нужен объект, который будет хранить целевую функцию, и сам будет вести себя как функция, что принимает нефиксированное количество аргументов. А результатом действия этого объекта-функции на свои аргументы должен быть другой объект, который кроме функции еще сохраняет переданные аргументы, поскольку в C++ данные, которые на стеке, живут не вечно, то их нужно именно скопировать, то есть для такого случая нужны копируемые объекты. Адреса, конечно, никто не запрещал. Философствовать в этом направлении можно очень долго и, я думаю, для каждого случая найти оптимальное решение. Можно даже, в перспективе, обозначить как-то, нужно ли копировать тот или иной аргумент, а может ссылки будет достаточно.
Далее этот объект должен вести себя как простая функция и принимать конкретное количество аргументов, а именно оставшиеся. Итак, нам нужен шаблонный класс, который зависит от типа целевой функции. Далее, для сохранения переданных аргументов нужны их количество и типы, а для определения результирующей функции нужны количество и типы оставшихся аргументов. Экспериментальным путем было определено, что лучше всего передавать шаблону тип функции и два набора индексов: переданных и оставшихся. Реализация ориентировалась на обертку std::function, а аргументы сохранялись в std::tuple. Также использовался ряд вспомогательных шаблонов для манипуляции числами и типами во время компиляции - надеюсь, их имена будут хорошим пояснением их сути, поскольку они сами могут претендовать на отдельную библиотеку, и описывать их тут не представляется возможным.
Ниже приведен код класса, который сохраняет функцию и данные, а также код класса, который ведет себя как функция, принимающая нефиксированное количество аргументов. Хочу обратить внимание на обильное использование pack expansion для шаблонов.
template< class, class, class >
class CarryHolder;
template< class OUT_TYPE, class... IN_TYPES, uint32_t... CAP_INDEXES, uint32_t... RES_INDEXES >
class CarryHolder< std::function< OUT_TYPE ( IN_TYPES... ) >,
UintContainer< CAP_INDEXES... >, // индексы захваченных аргументов
UintContainer< RES_INDEXES... > > // индексы оставшихся аргументов
{
public:
typedef std::function< OUT_TYPE ( IN_TYPES... ) > FuncType; // тип целевой функции
typedef std::tuple<
typename UnQualify< // убираем const и &
typename GetNthType< CAP_INDEXES, TypeContainer<IN_TYPES...> >::Result
>::Result...
> CleanCapTupleType; // тип кортежа хранящего захваченные аргументы
typedef std::function< OUT_TYPE
( typename GetNthType< RES_INDEXES, TypeContainer<IN_TYPES...> >::Result... )
> ReturnFuncType; // тип результирующей функции
public:
CarryHolder( FuncType const& f,
typename UnQualify<
typename GetNthType< CAP_INDEXES, TypeContainer<IN_TYPES...> >::Result
>::Result const&... capturedValues ):
_function(f), _capturedData( capturedValues... ) { };
CarryHolder( CarryHolder const& other ):
_function(other._function), _capturedData( other._capturedData ) { };
// принимает оставшиеся аргументы
inline OUT_TYPE operator()( typename GetNthType< RES_INDEXES, TypeContainer<IN_TYPES...> >::Result... other_values )
{
// разворачиваем сохраненные аргументы и только что полученные
return _function( std::get< CAP_INDEXES > (_capturedData)..., other_values ... );
};
private:
CarryHolder();
FuncType _function;
CleanCapTupleType _capturedData;
};
template< class >
class Carry;
template< class OUT_TYPE, class... IN_TYPES >
class Carry< std::function< OUT_TYPE (IN_TYPES...) > >
{
public:
typedef typename std::function< OUT_TYPE (IN_TYPES...) > FuncType;
constexpr static uint32_t ArgsCount = GetTypesLength< TypeContainer<IN_TYPES...> >::Result;
Carry( Carry const& carry ): _function( carry._function ) { };
Carry( FuncType const& f ): _function( f ) { };
template< class... INNER_IN_TYPES >
inline auto operator()( INNER_IN_TYPES const& ... values ) ->
typename CarryHolder<
FuncType,
// генерируем последовательность индексов захваченных аргументов
typename UintRange< GetTypesLength< TypeContainer<INNER_IN_TYPES...> >::Result >::Result,
// генерируем последовательность индексов оставшихся аргументов
typename UintRangeFromTo< GetTypesLength< TypeContainer<INNER_IN_TYPES...> >::Result, ArgsCount >::Result
>::ReturnFuncType // возвращаем CarryHolder завернутый в std::function
{
typedef CarryHolder<
FuncType,
typename UintRange< GetTypesLength< TypeContainer<INNER_IN_TYPES...> >::Result >::Result,
typename UintRangeFromTo< GetTypesLength< TypeContainer<INNER_IN_TYPES...> >::Result, ArgsCount >::Result
> CarryHolderSpec;
return CarryHolderSpec( _function, values... );
};
private:
Carry();
FuncType _function;
};
template< class FUNC_TYPE >
Carry<FUNC_TYPE> carry( FUNC_TYPE const& f ) // функция для удобства
{
return Carry<FUNC_TYPE>(f);
};
Перестановка аргументов
Для реализации частичного применения можно использовать подход, состоящий в перестановке аргументов местами с дальнейшим каррированием. Будет это выглядеть так:
std::function< int(int, int, int) > f =
[] ( int x, int y, int z )
{
return x + y + z;
};
auto f1 = permute<2, 1, 0>(f);
Нам, как и раньше, понадобиться объект, который будет хранить целевую функцию, но вести себя он будет как обычная функция, принимающая конкретное число аргументов, а точнее переставленные аргументы целевой функции. Для этого нужен шаблонный класс, который зависит от типа функции и от последовательности индексов - перестановки аргументов. Также необходимым будет шаблон для дополнения перестановки (пояснения ниже) и поиска обратной перестановки (инверсный индекс). Прямая перестановка нужна для формирования последовательности типов входных параметров, а обратная для вставки аргументов во время вызова функции. Также используется внутренний класс для развертывания типа инверсного индекса. Ниже приведен код класса, который реализует данный функционал.
template< class, class >
class Permutation;
template< class OUT_TYPE, class... IN_TYPES, uint32_t... INDEXES >
class Permutation<
std::function< OUT_TYPE (IN_TYPES...) >, // тип целевой функции
UintContainer< INDEXES... > > // перестановка аргументов
{
public:
typedef std::function< OUT_TYPE (IN_TYPES...) > FuncType;
typedef std::function< OUT_TYPE (typename GetNthType< INDEXES, TypeContainer<IN_TYPES...> >::Result...) > NewFuncType;
Permutation( Permutation const& perm ): _function( perm._function ) { };
Permutation( FuncType const& f ): _function( f ) { };
private:
// вспомогательный метод для развертывания найденной обратной перестановки
template< uint32_t... INVERSE >
inline OUT_TYPE apply( UintContainer< INVERSE... >, // нам нужен только тип, т.е. индексы
typename GetNthType< INDEXES, TypeContainer<IN_TYPES...> >::Result... values )
{
// сохраняем аргументы в std::tuple по индексу перестановки
std::tuple< typename GetNthType< INDEXES, TypeContainer<IN_TYPES...> >::Result... > data( values... );
// извлекаем аргументы из std::tuple по инверсному индексу
return _function( std::get< INVERSE > (data)... );
};
public:
inline OUT_TYPE operator()( typename GetNthType< INDEXES, TypeContainer<IN_TYPES...> >::Result... values )
{
// находим инверсную перестановку
typename InversePermutation< UintContainer<INDEXES...> >::Result inverse;
return apply( inverse, values... );
};
private:
Permutation();
FuncType _function;
};
// функция для удобства; заворачивает Permutation в std::function
template< uint32_t... INDEXES, class FUNC_TYPE >
auto permute( FUNC_TYPE const& f ) ->
typename Permutation<FUNC_TYPE,
// дополняем перестановку, т.е. добавляем в конец недостающие индексы
typename ComplementRange<
GetArgumentsCount<FUNC_TYPE>::Result, UintContainer < INDEXES... >
>::Result
>::NewFuncType
{
typedef Permutation<FUNC_TYPE,
typename ComplementRange<
GetArgumentsCount<FUNC_TYPE>::Result, UintContainer < INDEXES... >
>::Result
> PermutationType;
return PermutationType(f);
};
Теперь частичное применение, имея описанный функционал, становиться тривиальным - ниже код.
template< uint32_t... INDEXES, class FUNC_TYPE >
auto partApply( FUNC_TYPE const& f ) ->
decltype(carry(permute<INDEXES...>(f)))
{
return carry(permute<INDEXES...>(f));
};
А учитывая возможность дополнения индексов, это можно использовать указывая не все индексы:
std::function< int(int, int, int) > f =
[] ( int x, int y, int z )
{
return x + y + z;
};
auto f1 = permute<2>(f); // эквивалентно <2, 0, 1> - значит "ввести третий аргумент первым"
Вот такие возможности открывают Variadic templates. Позже, если будет интересно, выложу код.
На самом деле каррирование вышло не совсем классическим, поскольку является одношаговым и "обязательным", то есть, передав каррированной (в смысле реализованного функционала) функции все аргументы, все равно получим функцию, которая не принимает аргументов. Также неклассическая суть заметна во время манипуляции с квалификаторами. Но все это - особенности C++.
UPDATE:
Обнаружил, что CarryHolderSpec в Carry::operator() не нужно заворачивать без надобности в std::function, поскольку происходит повторное копирование аргументов. Но, думаю, ссылки на временные объекты помогут это обойти.