21 November 2011

C++ Variadic templates. Каррирование и частичное применение

Abnormal programmingC++
Sandbox
Доброго времени суток, уважаемое Хабрасообщество.
Недавно приходилось наблюдать дискуссию о каррировании и частичном применении. Суть этой полемики состояла в том, что лучше, для практических целей, иметь в языке программирования: встроенное частичное применение (например, как в 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, поскольку происходит повторное копирование аргументов. Но, думаю, ссылки на временные объекты помогут это обойти.

UPDATE:
Перенес топик в «Ненормальное программирование», думаю тут ему будет уютней.
Tags:каррингчастичное применениеc plus plusvariadic templates
Hubs: Abnormal programming C++
+21
5.2k 61
Comments 62
Popular right now
C++ Developer. Professional
December 28, 202060,000 ₽OTUS
Программирование на языке C (Си)
December 14, 202022,990 ₽Специалист.ру
C++ Junior Developer
March 3, 202123,990 ₽Level UP
Профессия iOS-разработчик
November 30, 202075,000 ₽SkillFactory
Top of the last 24 hours