Geekly Articles each Day
📜 ⬆️ ⬇️

Currying and partial application in C ++ 14

In this article I will talk about one of the variants of currying and partial application of functions in my favorite C ++, I will show my experimental implementation of this action and explain without mathematics, on my fingers, what currying is all about and what’s under the hood of kari.hpp we will curry the function. Well and as here it is accepted: interested - I ask under kat.


Currying


What is currying? It seems to me that this is one of the most popular words that Haskell programmers love to throw at (after the monads , of course). And the essence of the term is simple as a stick, and anyone who is aware of its meaning or wrote in languages ​​like ML or Haskell can safely skip this section.


Currying is the operation of converting a function of N arguments to a function of one argument, which returns a function of the next argument, etc. until we return the function from the last argument, which does not apply them all. We drove with examples:


int sum2(int lhs, int rhs) { return lhs + rhs; }

We have binary addition function. How to turn it into a function from a single argument? Very simple:


 auto curried_sum2(int lhs) { return [=](int rhs) { return sum2(lhs, rhs); }; }

What have we done? Captured by value our only argument in lambda, which takes the second remaining argument and performs, ultimately, the addition operation. As a result, we can apply our curried_sum2 function in turn to our arguments:


 // output: 42 std::cout << sum2(40, 2) << std::endl; std::cout << curried_sum2(40)(2) << std::endl;

Everything, this is the meaning of the operation of currying. All this, of course, can be turned on the functions of any arity - the essence will remain the same, you will need to return a curried function of N-1 arguments with each use of the function on the argument:


 auto sum3(int v1, int v2, int v3) { return v1 + v2 + v3; } auto curried_sum3(int v1) { return [=](int v2){ return [=](int v3){ return sum3(v1, v2, v3); }; }; } // output: 42 std::cout << sum3(38, 3, 1) << std::endl; std::cout << curried_sum3(38)(3)(1) << std::endl;

Partial application


Partial application is the ability to call functions of N arguments by passing only a portion of these arguments to them, the result of such a call will be another function from the remaining arguments.


Here it is worth making a reservation that in languages ​​like Haskell it all works in automatic mode behind the programmer’s back. This is what we will try to depict, that is, ideally, we need the ability to call our function sum3 like this: sum3(38,3)(1) or like this: sum3(38)(3,1) . On top of that, if the function returns another curried function, it can also be called with the argument list to the first in the same way. For example:


 int boo(int v1, int v2) { return v1 + v2; } auto foo(int v1, int v2) { return kari::curry(boo, v1 + v2); } // output: 42 std::cout << kari::curry(foo)(38,3,1) << std::endl; std::cout << kari::curry(foo)(38,3)(1) << std::endl; std::cout << kari::curry(foo)(38)(3,1) << std::endl;

I had to run a little ahead and show the use of kari.hpp and yes, she knows it.


Goal setting


To write something - you need (preferably?) To understand what we want to get at the output. And at the output, we want to be able to curry and partially apply everything that can be invoked in C ++. Namely:



Functions with a variable number of arguments can be curried through a specific indication of the number of arguments that we want to curry. Normal interaction with std :: bind and its results is also desirable. And of course, you need to be able to use functions for several arguments and be able to call nested functions so that it seems that we are interacting with one curried function.


Naturally, we must not forget about performance. It is necessary to minimize the costs of various wrappers, passing arguments and storing them. To transfer instead of copying, to store only what is really needed and to give (preferably by transfer) as soon as possible.


Author, you're trying to invent std::bind !


Yes and no. std::bind no doubt a powerful and proven tool, I am not going to write its killer or alternative implementation. Yes, it can be used as a tool for currying and explicit partial use (with indication of what we use, on what place and how much). But this is inconvenient for such cases and is not always applicable, because you need to know the specific arity of the function and, depending on it, write specific binding (binding?). Example:


 int foo(int v1, int v2, int v3, int v4) { return v1 + v2 + v3 + v4; } // std::bind auto c0 = std::bind(foo, _1, _2, _3, _4); auto c1 = std::bind(c0, 15, _1, _2, _3); auto c2 = std::bind(c1, 20, 2, _1); auto rr = c2(5); std::cout << rr << std::endl; // output: 42 // kari.hpp auto c0 = kari::curry(foo); auto c1 = c0(15); auto c2 = c1(20, 2); auto rr = c2(5); std::cout << rr << std::endl; // output: 42

API


 namespace kari { template < typename F, typename... Args > constexpr decltype(auto) curry(F&& f, Args&&... args) const; template < typename F, typename... Args > constexpr decltype(auto) curryV(F&& f, Args&&... args) const; template < std::size_t N, typename F, typename... Args > constexpr decltype(auto) curryN(F&& f, Args&&... args) const; template < typename F > struct is_curried; template < typename F > constexpr bool is_curried_v = is_curried<F>::value; template < std::size_t N, typename F, typename... Args > struct curry_t { template < typename... As > constexpr decltype(auto) operator()(As&&... as) const; }; }


kari::curry(F&& f, Args&&... args)


Returns a functional object of type curry_t (a curry_t function) with optional args arguments applied or the result of applying arguments to the passed function f (if the function is null or the arguments passed are enough to call it).


When passing the f parameter to an already curried function, it returns a copy of it with args arguments applied to it.



kari::curryV(F&& f, Args&&... args)


Allows currying functions with a variable number of arguments. Such functions can be called further by the () operator without arguments. Example:


 auto c0 = kari::curryV(std::printf, "%d + %d = %d"); auto c1 = c0(37, 5); auto c2 = c1(42); c2(); // output: 37 + 5 = 42

When the f parameter is already transferred to a curried function, it returns a copy of it with a modified application type for a variable number of arguments with args arguments applied.



kari::curryN(F&& f, Args&&... args)


It allows currying functions with a variable number of arguments with an indication of the specific number of arguments N that we want to apply (besides those that were passed as args ). Example:


 char buffer[256] = {'\0'}; auto c = kari::curryN<3>(std::snprintf, buffer, 256, "%d + %d = %d"); c(37, 5, 42); std::cout << buffer << std::endl; // output: 37 + 5 = 42

When the f parameter is already transferred to a curried function, it returns a copy of it with a modified application type for N arguments with args arguments applied.



kari::is_curried<F>, kari::is_curried_v<F>


Auxiliary structures to check the function for its curry. Example:


 const auto l = [](int v1, int v2){ return v1 + v2; }; const auto c = curry(l); // output: is `l` curried? no std::cout << "is `l` curried? " << (is_curried<decltype(l)>::value ? "yes" : "no") << std::endl; // output: is `c` curried? yes std::cout << "is `c` curried? " << (is_curried_v<decltype(c)> ? "yes" : "no") << std::endl;


kari::curry_t::operator()(As&&... as)


Operator partial or full use of the curried function. The result of the call is the curried function of the remaining arguments of the original function of type F , or the result of this function obtained by applying it to the accumulated arguments and the new arguments as passed to the call. Example:


 int foo(int v1, int v2, int v3, int v4) { return v1 + v2 + v3 + v4; } auto c0 = kari::curry(foo); auto c1 = c0(15, 20); // partial application auto rr = c1(2, 5); // function call - foo(15,20,2,5) std::cout << rr << std::endl; // output: 42

Calling without arguments of a curryV function using curryV or curryN will result in an attempt to call it if there are enough arguments for this call. Otherwise, it returns a partially applied function. Example:


 auto c0 = kari::curryV(std::printf, "%d + %d = %d"); auto c1 = c0(37, 5); auto c2 = c1(42); // force call variadic function std::printf c2(); // output: 37 + 5 = 42

Implementation details


Citing implementation details I will use C ++ 17 in order to reduce the amount of text and avoid unnecessary explanations and piles of SFINAE , as well as implementations of what had to be added within the standard of the 14th year. All these details can be viewed in the repository of the project and at the same time put an asterisk :)



make_curry(F&& f, std::tuple<Args...>&& args)


An auxiliary function that creates a curry_t function object or applies the passed function f to the args arguments.


 template < std::size_t N, typename F, typename... Args > constexpr auto make_curry(F&& f, std::tuple<Args...>&& args) { if constexpr ( N == 0 && std::is_invocable_v<F, Args...> ) { return std::apply(std::forward<F>(f), std::move(args)); } else { return curry_t< N, std::decay_t<F>, Args... >(std::forward<F>(f), std::move(args)); } } template < std::size_t N, typename F > constexpr decltype(auto) make_curry(F&& f) { return make_curry<N>(std::forward<F>(f), std::make_tuple()); }

Two interesting points in this feature:




struct curry_t


The functional object that will store our accumulated arguments and the function that will need to be called in the final application, and that is what we will call and partially apply.


 template < std::size_t N, typename F, typename... Args > struct curry_t { template < typename U > constexpr curry_t(U&& u, std::tuple<Args...>&& args) : f_(std::forward<U>(u)) , args_(std::move(args)) {} private: F f_; std::tuple<Args...> args_; };

To store the accumulated args_ arguments in std :: tuple is a good idea for several reasons:


1) automatic handling of the situation with std :: ref , in order to store links when necessary, and by default by value
2) convenient use of the function on the arguments in it ( std :: apply )
3) it is already ready and do not write with your hands :)


The called object or the f_ function must also be stored by value and carefully select its type when creating it (this will be discussed later) by moving or copying it via the universal link in the constructor.


The template parameter N serves as a counter of applications for functions with a variable number of parameters.



curry_t::operator()(const As&...)


And of course, all the salt of what is happening in the caller of the functional object operator.


 template < std::size_t N, typename F, typename... Args > struct curry_t { // 1 constexpr decltype(auto) operator()() && { return detail::make_curry<0>( std::move(f_), std::move(args_)); } // 2 template < typename A > constexpr decltype(auto) operator()(A&& a) && { return detail::make_curry<(N > 0 ? N - 1 : 0)>( std::move(f_), std::tuple_cat( std::move(args_), std::make_tuple(std::forward<A>(a)))); } // 3 template < typename A, typename... As > constexpr decltype(auto) operator()(A&& a, As&&... as) && { return std::move(*this)(std::forward<A>(a))(std::forward<As>(as)...); } // 4 template < typename... As > constexpr decltype(auto) operator()(As&&... as) const & { auto self_copy = *this; return std::move(self_copy)(std::forward<As>(as)...); } }

We have four overloaded call operator functions.


  1. The function without parameters serves as a way to start trying to apply a function with a variable number of arguments (created with curryV or curryN ). In it, we reduce the application counter to zero, thus showing that it’s time to use the function and pass all the necessary make_curry functions to this function.


  2. The function from one argument lowers the application counter by one (if there is where to lower) and adds our new argument a into a tuple with the already accumulated arguments args_ and passes it to make_curry .


  3. The function of the variable number of arguments serves as a trick to partially apply several arguments. She recursively applies them one by one. Apply them all at once will not work for two reasons:


    • the application count may reach zero before the arguments run out
    • the f_ function can be called earlier and return another curried function and the following arguments are intended for it

  4. The latter function serves as a bridge to call curry_t by lvalue and call functions by rvalue .

The magic of what is happening is added to the ref-qualified functions. In short, with their help we learn that the object was called by the rvalue reference and you can safely move the arguments instead of copying to the final calling function make_curry . Otherwise, we are obliged to copy the arguments in order to preserve the possibility of calling this function once more knowing that its arguments are in place.


Bonuses


Before concluding, I would like to give a couple of examples of syntactic sugar built in kari.hpp and bundled with it as a bonus.


Operator sections


Programmers familiar with the Haskell language are familiar with the sections of operators, which allow us to briefly describe the partial use of operators in it. The construct (*2) , for example, generates a function from one argument, the result of which will be multiplication by 2 passed arguments. I wanted to portray something like this in C ++. No sooner said than done!


 using namespace kari::underscore; std::vector<int> v{1,2,3,4,5}; std::accumulate(v.begin(), v.end(), 0, _+_); // result: 15 std::transform(v.begin(), v.end(), v.begin(), _*2); // v = 2, 3, 6, 8, 10 std::transform(v.begin(), v.end(), v.begin(), -_); // v = -2,-3,-6,-8,-10

Function compositions


Well, the diagnosis would be inconclusive if the idea of ​​depicting the composition of functions had not come. For the operator of the composition operator * was chosen as the most outwardly similar composition available in the symbol in mathematics. They can also apply the resulting function to the argument. Result:


 using namespace kari::underscore; // 1 std::cout << (_*2) * (_+2) * 4 << std::endl; // output: 12 // 2 std::cout << 4 * (_*2) * (_+2) << std::endl; // output: 10

  1. the composition of the functions (*2) and (+2) is applied at 4 . (4 + 2) * 2 = 12
  2. the function (*2) is applied to 4 and the result is applied (+2) . (4 * 2 + 2) = 10

In this case, you can make quite complex compositions in the no- point notation , but they will be understood only by Haskell programmers :)


 // (. (+2)) (*2) $ 10 == 24 // haskell  std::cout << (_*(_+2))(_*2) * 10 << std::endl; // output: 24 // ((+2) .) (*2) $ 10 == 22 // haskell  std::cout << ((_+2)*_)(_*2) * 10 << std::endl; // output: 22

Conclusion


And without me it is clear that it is not worthwhile to apply this in real projects, but I had to say it. The goal was to test myself and the new C ++. Can I? Can C ++? Well, as you can see, somehow, but both were able. Special thanks to those who read to the end.


')

Source: https://habr.com/ru/post/340722/

More articles:


All Articles