(495) 925-0049, ITShop интернет-магазин 229-0436, Учебный Центр 925-0049
  Главная страница Карта сайта Контакты
Поиск
Вход
Регистрация
Рассылки сайта
 
 
 
 
 

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

Источник: habrahabr

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

 UPD: Обнаружил, что CarryHolderSpec в Carry::operator() не нужно заворачивать без надобности в std::function, поскольку происходит повторное копирование аргументов. Но, думаю, ссылки на временные объекты помогут это обойти.

Ссылки по теме


 Распечатать »
 Правила публикации »
  Обсудить материал в конференции Embarcadero »
Написать редактору 
 Рекомендовать » Дата публикации: 23.11.2011 
 

Магазин программного обеспечения   WWW.ITSHOP.RU
Delphi Professional Named User
Enterprise Connectors (1 Year term)
ARCHICAD 21, локальная лицензия на 12 месяцев
IBM Domino Enterprise Server Processor Value Unit (PVU) License + SW Subscription & Support 12 Months
Microsoft Office 365 Бизнес. Подписка на 1 рабочее место на 1 год
 
Другие предложения...
 
Курсы обучения   WWW.ITSHOP.RU
 
Другие предложения...
 
Магазин сертификационных экзаменов   WWW.ITSHOP.RU
 
Другие предложения...
 
3D Принтеры | 3D Печать   WWW.ITSHOP.RU
 
Другие предложения...
 
Новости по теме
 
Рассылки Subscribe.ru
Информационные технологии: CASE, RAD, ERP, OLAP
Новости ITShop.ru - ПО, книги, документация, курсы обучения
Программирование на Microsoft Access
CASE-технологии
Программирование в AutoCAD
СУБД Oracle "с нуля"
Компьютерные книги. Рецензии и отзывы
 
Статьи по теме
 
Новинки каталога Download
 
Исходники
 
Документация
 
Обсуждения в форумах
Разработка программ базы данных (63)
Написание прикладных компьютерных программ (базы данных) на заказ. Разработка корпоративных...
 
Кухня (4)
Хочу сделать ремонт на кухне. Где приобрести кухонную плиту? Какой фирмы стоит её рассматривать?
 
Как в IBM Rational DOORS сделать заголовки не жирным шрифтом? (2)
Измучился уже, когда идет иерархия уровнем ниже, чем Х.Х., мне нужно, чтобы заголовки не...
 
Ищу программиста для написания программы (62)
Ищу программиста ,владеющего Вижуал Бэйсик и программированием в Экселе, для написания...
 
Отличается ли ДрифтКазино от беттинга? (18)
Друзья, давно заметил, что на Дрифте уже несколько месяцев во всю рекламируется и предлагается...
 
 
 



    
rambler's top100 Rambler's Top100