C ++ Variadic templates. Currying and partial application
Good day, dear Habrasoobschestvo.
Recently, we had to observe a discussion about currying and partial application. The essence of this controversy was that it is better, for practical purposes, to have in a programming language: embedded partial applications (for example, as in Nemerle ) or embedded curries (as, for example, in Haskell ).
Nemerle:
Haskell:
Personally, I think you need to implement both entities. Especially since enough time has passed since that moment when gcc features appeared from the upcoming C ++ standard, namely Variadic templates. As you understand, the article proposes the implementation of currying and partial application for C ++ using Variadic templates. During the work, MinGW gcc 4.6.1 and Code :: Blocks 10.05 were used.
Let's start with currying, especially since it is intuitive. The goal will be considered a higher order function, which takes a function and returns its curried version. Next, you can pass an arbitrary number of arguments to this function, resulting in another function that takes the remaining arguments and returns the final result.
We need an object that will store the objective function, and will behave as a function itself, which takes an unfixed number of arguments. And the result of the action of this function object on its arguments must be another object, which in addition to the function still saves the passed arguments, because in C ++ the data that is on the stack does not live forever, they need to be copied, that is, for such a case, copyable objects . Addresses, of course, no one forbade. It is possible to philosophize in this direction for a very long time and, I think, for each case to find the optimal solution. You can even, in the future, designate somehow whether you need to copy one or another argument, and maybe the link will suffice.
Further, this object should behave as a simple function and take a specific number of arguments, namely the remaining ones. So, we need a template class that depends on the type of the objective function. Further, to save the passed arguments, their number and types are needed, and the number and types of the remaining arguments are needed to determine the resulting function. Experimentally, it was determined that it is best to pass a type of function and two sets of indices to the pattern: transferred and remaining. The implementation focused on the std :: function wrapper, and the arguments were stored in std :: tuple. A number of auxiliary templates were also used to manipulate numbers and types during compilation — I hope their names will be a good explanation of their essence, since they themselves can claim to be a separate library, and it is not possible to describe them here.
Below is the class code that stores the function and data, as well as the class code that behaves like a function that takes an uncommitted number of arguments. I want to draw attention to the abundant use of pack expansion for templates.
To implement partial application, you can use the approach of rearranging arguments with further currying. It will look like this:
We, as before, need an object that will hold the target function, but it will behave like a normal function that takes a specific number of arguments, or rather, the rearranged arguments of the target function. For this, a template class is needed, which depends on the type of the function and on the sequence of indices - permutations of the arguments. A template will also be necessary to supplement the permutation (explained below) and search for the inverse permutation (inverse index). Direct permutation is needed to form a sequence of types of input parameters, and the inverse to insert arguments during a function call. An internal class is also used to expand the inverse index type. Below is the class code that implements this functionality.
Now a partial application, having the described functionality, becomes trivial - the code below.
And given the possibility of supplementing indices, this can be used to indicate not all indices:
These are the possibilities offered by Variadic templates. Later, if interested, lay out the code.
Actually, the currying was not quite classic, since it is one-step and “mandatory”, that is, passing all the arguments to the curried (in the sense of a realized functional) function, we still get a function that does not accept arguments. Also, the non-classical essence is noticeable during the manipulation of qualifiers. But all of these are C ++ features.
')
UPDATE:
I found that the CarryHolderSpec in Carry :: operator () does not need to be wrapped unnecessarily in the std :: function, since the arguments are being copied again. But, I think, references to temporary objects will help to bypass it.
UPDATE:
Transferred the topic to “Abnormal programming”, I think it will be more comfortable here.
Recently, we had to observe a discussion about currying and partial application. The essence of this controversy was that it is better, for practical purposes, to have in a programming language: embedded partial applications (for example, as in Nemerle ) or embedded curries (as, for example, in 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 xyz = x + y + z -- sum3x = sum3 5 -- sum3xy = sum3x 5 -- sum3xyz = sum3xy 5 -- … , 15 Personally, I think you need to implement both entities. Especially since enough time has passed since that moment when gcc features appeared from the upcoming C ++ standard, namely Variadic templates. As you understand, the article proposes the implementation of currying and partial application for C ++ using Variadic templates. During the work, MinGW gcc 4.6.1 and Code :: Blocks 10.05 were used.
Currying
Let's start with currying, especially since it is intuitive. The goal will be considered a higher order function, which takes a function and returns its curried version. Next, you can pass an arbitrary number of arguments to this function, resulting in another function that takes the remaining arguments and returns the final result.
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); We need an object that will store the objective function, and will behave as a function itself, which takes an unfixed number of arguments. And the result of the action of this function object on its arguments must be another object, which in addition to the function still saves the passed arguments, because in C ++ the data that is on the stack does not live forever, they need to be copied, that is, for such a case, copyable objects . Addresses, of course, no one forbade. It is possible to philosophize in this direction for a very long time and, I think, for each case to find the optimal solution. You can even, in the future, designate somehow whether you need to copy one or another argument, and maybe the link will suffice.
Further, this object should behave as a simple function and take a specific number of arguments, namely the remaining ones. So, we need a template class that depends on the type of the objective function. Further, to save the passed arguments, their number and types are needed, and the number and types of the remaining arguments are needed to determine the resulting function. Experimentally, it was determined that it is best to pass a type of function and two sets of indices to the pattern: transferred and remaining. The implementation focused on the std :: function wrapper, and the arguments were stored in std :: tuple. A number of auxiliary templates were also used to manipulate numbers and types during compilation — I hope their names will be a good explanation of their essence, since they themselves can claim to be a separate library, and it is not possible to describe them here.
Below is the class code that stores the function and data, as well as the class code that behaves like a function that takes an uncommitted number of arguments. I want to draw attention to the abundant use of pack expansion for templates.
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); }; Rearrangement of arguments
To implement partial application, you can use the approach of rearranging arguments with further currying. It will look like this:
std::function< int(int, int, int) > f = [] ( int x, int y, int z ) { return x + y + z; }; auto f1 = permute<2, 1, 0>(f); We, as before, need an object that will hold the target function, but it will behave like a normal function that takes a specific number of arguments, or rather, the rearranged arguments of the target function. For this, a template class is needed, which depends on the type of the function and on the sequence of indices - permutations of the arguments. A template will also be necessary to supplement the permutation (explained below) and search for the inverse permutation (inverse index). Direct permutation is needed to form a sequence of types of input parameters, and the inverse to insert arguments during a function call. An internal class is also used to expand the inverse index type. Below is the class code that implements this functionality.
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); }; Now a partial application, having the described functionality, becomes trivial - the code below.
template< uint32_t... INDEXES, class FUNC_TYPE > auto partApply( FUNC_TYPE const& f ) -> decltype(carry(permute<INDEXES...>(f))) { return carry(permute<INDEXES...>(f)); }; And given the possibility of supplementing indices, this can be used to indicate not all indices:
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> - " " These are the possibilities offered by Variadic templates. Later, if interested, lay out the code.
Actually, the currying was not quite classic, since it is one-step and “mandatory”, that is, passing all the arguments to the curried (in the sense of a realized functional) function, we still get a function that does not accept arguments. Also, the non-classical essence is noticeable during the manipulation of qualifiers. But all of these are C ++ features.
')
UPDATE:
I found that the CarryHolderSpec in Carry :: operator () does not need to be wrapped unnecessarily in the std :: function, since the arguments are being copied again. But, I think, references to temporary objects will help to bypass it.
UPDATE:
Transferred the topic to “Abnormal programming”, I think it will be more comfortable here.
Source: https://habr.com/ru/post/133084/
All Articles