Доброго времени суток, уважаемое Хабрасообщество.
Недавно приходилось наблюдать дискуссию о каррировании и частичном применении. Суть этой полемики состояла в том, что лучше, для практических целей, иметь в языке программирования: встроенное частичное применение (например, как в Nemerle) или встроенное каррирование (как, например, в Haskell).
Nemerle:
Haskell:
Лично я думаю, что нужно реализовать обе сущности. Тем более уже достаточно времени прошло от того момента когда в gcc появились возможности из грядущего стандарта C++, а именно Variadic templates. Как вы поняли, в статье предлагается реализация каррирования и частичного применения для C++ с помощью Variadic templates. В ходе работы использовались MinGW gcc 4.6.1 и Code::Blocks 10.05.
Начнем с каррирования, тем более что это интуитивно понятно. Целью будем считать функцию высшего порядка, которая принимает функцию и возвращает ее каррированный вариант. Далее этой функции можно передать произвольное количество аргументов, получая в результате другую функцию, которая принимает остальные аргументы и выдает окончательный результат.
Нам нужен объект, который будет хранить целевую функцию, и сам будет вести себя как функция, что принимает нефиксированное количество аргументов. А результатом действия этого объекта-функции на свои аргументы должен быть другой объект, который кроме функции еще сохраняет переданные аргументы, поскольку в C++ данные, которые на стеке, живут не вечно, то их нужно именно скопировать, то есть для такого случая нужны копируемые объекты. Адреса, конечно, никто не запрещал. Философствовать в этом направлении можно очень долго и, я думаю, для каждого случая найти оптимальное решение. Можно даже, в перспективе, обозначить как-то, нужно ли копировать тот или иной аргумент, а может ссылки будет достаточно.
Далее этот объект должен вести себя как простая функция и принимать конкретное количество аргументов, а именно оставшиеся. Итак, нам нужен шаблонный класс, который зависит от типа целевой функции. Далее, для сохранения переданных аргументов нужны их количество и типы, а для определения результирующей функции нужны количество и типы оставшихся аргументов. Экспериментальным путем было определено, что лучше всего передавать шаблону тип функции и два набора индексов: переданных и оставшихся. Реализация ориентировалась на обертку std::function, а аргументы сохранялись в std::tuple. Также использовался ряд вспомогательных шаблонов для манипуляции числами и типами во время компиляции – надеюсь, их имена будут хорошим пояснением их сути, поскольку они сами могут претендовать на отдельную библиотеку, и описывать их тут не представляется возможным.
Ниже приведен код класса, который сохраняет функцию и данные, а также код класса, который ведет себя как функция, принимающая нефиксированное количество аргументов. Хочу обратить внимание на обильное использование pack expansion для шаблонов.
Для реализации частичного применения можно использовать подход, состоящий в перестановке аргументов местами с дальнейшим каррированием. Будет это выглядеть так:
Нам, как и раньше, понадобиться объект, который будет хранить целевую функцию, но вести себя он будет как обычная функция, принимающая конкретное число аргументов, а точнее переставленные аргументы целевой функции. Для этого нужен шаблонный класс, который зависит от типа функции и от последовательности индексов – перестановки аргументов. Также необходимым будет шаблон для дополнения перестановки (пояснения ниже) и поиска обратной перестановки (инверсный индекс). Прямая перестановка нужна для формирования последовательности типов входных параметров, а обратная для вставки аргументов во время вызова функции. Также используется внутренний класс для развертывания типа инверсного индекса. Ниже приведен код класса, который реализует данный функционал.
Теперь частичное применение, имея описанный функционал, становиться тривиальным – ниже код.
А учитывая возможность дополнения индексов, это можно использовать указывая не все индексы:
Вот такие возможности открывают Variadic templates. Позже, если будет интересно, выложу код.
На самом деле каррирование вышло не совсем классическим, поскольку является одношаговым и «обязательным», то есть, передав каррированной (в смысле реализованного функционала) функции все аргументы, все равно получим функцию, которая не принимает аргументов. Также неклассическая суть заметна во время манипуляции с квалификаторами. Но все это — особенности C++.
UPDATE:
Обнаружил, что CarryHolderSpec в Carry::operator() не нужно заворачивать без надобности в std::function, поскольку происходит повторное копирование аргументов. Но, думаю, ссылки на временные объекты помогут это обойти.
UPDATE:
Перенес топик в «Ненормальное программирование», думаю тут ему будет уютней.
Недавно приходилось наблюдать дискуссию о каррировании и частичном применении. Суть этой полемики состояла в том, что лучше, для практических целей, иметь в языке программирования: встроенное частичное применение (например, как в 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); // …и первый, получаем 15Haskell:
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:
Перенес топик в «Ненормальное программирование», думаю тут ему будет уютней.
