Partial application and currying in C ++

Greetings.

I don’t know how it happened, but I was playing at leisure with lambda expressions in C ++ 11 (about which, by the way, I already wrote an article that gained surprisingly good popularity a couple of years ago), and under the influence of narcotic from Haskell language began to deal with such concepts as partial application and currying in the context of C ++. And for a start, perhaps, it would be nice for us to decide on these terms.

Actually, a partial application of a function is the ability to fix a specific value for one of the function parameters, that is, from a function from N parameters we get a function from N-1 parameters. If we have a binary function that adds two numbers:

int sum(int a, int b) { return a + b; } 

then we can fix a certain value behind one of the parameters, for example, 42. Thus, we get a new, unary function that adds the number 42 to its argument.
')
Strictly speaking, partial application of functions was also in the previous C ++ standard. This role was performed by two classes std::binder1st and std::binder2nd , as well as the well-known auxiliary functions std::bind1st and std::bind2nd , which simplify the creation of objects of the above classes. However, there is one problem: these binders do not know how to work with ordinary function pointers, because they need to know the type of parameters. To solve this and other problems in STL, functors are commonly used. To be honest, I would prefer to call them functional objects, since the word "functor" since acquaintance with Haskell is associated with a completely different entity. However, in C ++ programming circles, this term was fixed precisely for designating objects that can behave like functions; besides, it is faster to write :)

So how is this problem solved? If someone does not know, I will tell in two words. The std::binder1st and std::binder2nd , which by the way work only with binary functions, require the presence of several typedef in the functor you define: these are result_type, first_argument_type and second_argument_type. In order not to have to declare these types in your functor manually each time, you can simply inherit from std::binary_function<T0,T1,R> , where T0 and T1 are the function argument types, and R is the return type, respectively.

An example of using this whole thing is something like

 template <typename T> struct Sum : public std::binary_function<T, T, T> { T operator()(T const & a, T const & b) { return a + b; } }; //   std::for_each(intArray.begin(), intArray.end(), std::bind1st(Sum<int>(), 42)); 

Those who have been familiar with STL for a long time are not afraid of such constructions (and I, unfortunately, are among them), but believe me, the jumble of all these special characters and wrappers is frightening for beginners who came to C ++ from other languages. Readability is also better not to remember, because I saw the combination and more abruptly :) Especially since later in the Boost library a more powerful replacement appeared - Boost.Bind, which, however, differed even less (typical C ++ - way) . By the way, it should be noted that Boost.Bind migrated to the new C ++ 11 standard to replace the old binders, which I described above a little. However, who will use it when there is ... what? That's right, lambda! Well, it’s quite another thing :) Scribbling is less, readability is better (compared to binders, of course, but not with other languages;)).

So, we have the Sum functor, which we defined above. I may have forgotten to say, but in STL there is already a similar functor - std :: plus <>. But we will do without him, since we wrote our own one. In general, we have a binary functor, and we need to get a partially applied unary. With lambdas, it might look like this:

 using namespace std; //  for_each, begin  end // ... Sum<int> sum; for_each(begin(intArray)), end(intArray), [sum] (int const & n) { return sum(42, n); }); 

You may ask why we call sum(42, n) , when we can write return 42 + n; directly in the body of the lambda return 42 + n; . The remark, of course, is correct, but we are interested in precisely the partial application of the function, if you have not forgotten. In addition, the function could be much more complicated than simply summing two numbers.

How would we write it in Haskell? Perhaps, something like this would turn out:

 sum ab = a + b someFunc intList = map (λ n → sum 42 n) intList 

If you are not familiar with Haskell, do not despair. This code is similar to the last C ++ example. Now I will explain in a nutshell: in the first line we declared the function sum , which takes a and b , and returns their sum. Next, we declared some function that takes a list as a parameter (probably a list of integers, judging by the name of the parameter) and does something with it. The map function is an analogue of std::for_each , i.e. it takes a function and calls it for each item in the list. As a function, we pass a lambda, which calls the function sum , explicitly passing a fixed value as the first parameter, and the argument of the lambda naturally comes as the second parameter. None of this really matters ... Or rather, it would not matter if the same Haskell code could not be written like this:

 sum ab = a + b someFunc intList = map (sum 42) intList 

As we can see, this time, instead of lambda, we used a much shorter construction, namely the call to the binary function sum with one parameter. How does this work? Yes, very simple! :) The call (sum 42) will give us a new function that takes one parameter and then sums it up with the number 42. In essence, this is the same partial application - we just say to the sum function: “Here's your first parameter, remember it! But we don’t yet know the second parameter, so you’ll have to deal with it later. ” All this works due to the fact that all functions in Haskell are curried (by the way, there was such a mathematician - Haskell Curry;)). So it's time to figure out what it is.

First, currying is an operation. That is, it’s not just some kind of property or magical creature in the Haskell universe - it’s a transformation. Secondly, this is a transformation performed on a function: it takes a function from N parameters and converts it to a similar function from a single parameter, which returns a function from N-1 parameters. Let me explain by example. To do this, let's return to our C ++ function sum , but add one more parameter to it (just in case):

 template <typename T1, typename T2, typename T3, typename R> R sum(T1 a, T2 b, T3 c) { return a + b + c; } 

Since we are only interested in the types of parameters and return values, we will write down its type as follows:

 sum :: ((T1 × T2 × T3) → R) 

This record means that the function takes three arguments of types T1, T2 and T3, respectively, and returns a value of type R. Actually, after currying, by definition, we should get something like this:

 sum :: (T1 → ((T2 × T3) → R)) 

That is, it is a function that takes one parameter of type T1, and returns another function, which in turn takes two arguments of types T2 and T3, respectively, and returns (as before) a value of type R. In essence, we “bite off” the first parameter of the function and say, they say, "we remember him, do not worry." And then we return a similar function that takes one less parameter. Nothing like? Why, based on this, partial application can be realized!

But ... in fact, I was a little tricky. If everything worked that way, then we would have to curry the resulting function after partially applying each successive function argument. Judge for yourself: we have a ternary function that we curry and get a unary function. We transfer this single parameter to this unary function and get another binary function as a result. Now, if we want to perform a partial application for one more parameter, we will have to perform the currying again, only now for the binary function. It makes no sense to fool yourself with this each time, so in fact, as a result of the currying, we get the following:

 sum :: (T1 → (T2 → (T3 → R))) 

In essence, this is the same thing, but instead of returning a binary function, we return it immediately as a curried one. Thus, we obtained a chain of unary functions from the multi-input function, which, firstly, will allow us to partially apply the arguments in order, and secondly, when applying all the arguments, it will behave equivalently to the original function, that is, it will give the same result at the output .

I hope so far everything has been more or less clear. But, I think, many of you are already pointing a finger at the monitor with an exclamation: “Well, finally show the code of the bljad already!” It’s reasonable, I can’t argue. Therefore, with the theory finished, go to practice. The year 2012 is in the courtyard, so we will use the new C ++ 11 standard, although we will try to limit ourselves only to what Microsoft Visual Studio 2010 supports - in terms of supporting the new standard, it is probably the most lagging behind of release compilers.

Let's start with the simple. There is a binary function. As a result of currying, we need to get a unary function, which returns us another unary function. Using C ++ 11 makes it easier than a steamed turnip:

 #include <cstddef> #include <iostream> using namespace std; template <typename R, typename T0, typename T1> function<function<R(T1)>(T0)> curry_(function<R(T0,T1)> f) { return [=] (T0 const & t0) -> function<R(T1)> { return [=] (T1 const & t1) { return f(t0, t1); }; }; } int sum(int a, int b) { return a + b; } int main() { auto curried_sum = curry_<int,int,int>(sum); cout << sum(42, 10) << endl; // => 52 cout << curried_sum(42)(10) << endl; // => 52 return EXIT_SUCCESS; } 

In general, there are such things: our function curry_ depends on three template parameters (the types of the function arguments and the type of the return value). It takes an object of type std::function<> as an argument. If anyone does not know, this is such a universal container that can store functors, lambdas and even function pointers (Yay! No more smutter :)). What matters to us is that it is essentially a functional object, that is, it has operator() overloaded. Next, we simply return the unary lambda (essentially an anonymous functor), which returns another unary lambda. It is practically one-to-one translation of the definition of the term currying from Russian to C ++.

Now came the important point. Anyone who has read this far should ask their inner voice which option they like more:

 std::bind1st(std::function<int(int,int)>(sum), 42)(10); //  curry_<int,int,int>(sum)(42)(10); 

If the first, you can not continue to read, believe me. If the second, then I have to admit to you ... I don’t really like the second one myself, although in my opinion it’s already much better than the first.

Anyway, I am slightly annoyed by the need to explicitly specify the types of arguments and return value. The compiler cannot automatically print all types on its own, so it has to be prompted. In addition, if we want to overload the curry_ function for a ternary function, we will fail because the compiler cannot distinguish between instances of std::function<> . As I understand it, the reason for this is that the std::function<> a template constructor defined, which accepts any type, but we will not go into it now, because I’m not completely sure that I understood the problem correctly. However, the fact remains. And with this you need to do something.

The question of the need to specify the types of arguments and the return value will try to solve as follows. The curry_ function will curry_ left as it is, and for it we will write a template wrapper, which will take any type as a template parameter. Next, we write something like function_traits (by the way, it’s strange that there’s no such thing in the standard, no?), In which we will memorize the types of arguments, etc. The approach of writing the so-called traits classes is universally used in the STL, so why shouldn't we do that.

 template <typename Func> struct function_traits {}; //      template <typename R, typename T0, typename T1> struct function_traits<R(*)(T0,T1)> { typedef R result_type; typedef T0 first_argument_type; typedef T1 second_argument_type; }; //   curry_ template <typename Functor> function< function< typename function_traits<Functor>::result_type(typename function_traits<Functor>::second_argument_type) >(typename function_traits<Functor>::first_argument_type) > curry(Functor f) { return curry_ < typename function_traits<Functor>::result_type , typename function_traits<Functor>::first_argument_type , typename function_traits<Functor>::second_argument_type > (f); } 

Well, only two dozen lines of not too readable code, and we can already write like this:

 cout << curry(sum)(42)(10) << endl; 

In my opinion, this is a success! :) It remains to implement curry_ for ternary functions, and even so that we do not have to start another function name for these purposes - let everything be solved by overloading functions. So far, the instinct tells me that this will be problematic. Look at least at the curry wrapper function: it takes only one parameter (directly the function to be curried), but it should always return objects of different types depending on the arity of the function (that is, it will return a function that returns a function, or a function that returns a function, a return function, or ... mmm, perhaps enough).

To solve this problem, you will have to slightly resist with metaprogramming to think and find inspiration. So, first we need to distinguish between the unary, binary, ternary, ... n-ary functions. I think for this you can add a static constant to function_traits , which will be initialized with different values ​​depending on the specialization of the template. Next, we will add an additional dummy argument to our curry wrapper function, which will only participate in resolving the function overload at the compilation stage.

We get the following:

 template <typename Func> struct function_traits {}; //      template <typename R, typename T0> struct function_traits<R(*)(T0)> { typedef R result_type; typedef T0 argument_type; static const int arity = 1; }; //      template <typename R, typename T0, typename T1> struct function_traits<R(*)(T0,T1)> { typedef R result_type; typedef T0 first_argument_type; typedef T1 second_argument_type; static const int arity = 2; }; //     template <typename R, typename T0, typename T1, typename T2> struct function_traits<R(*)(T0,T1,T2)> { typedef R result_type; typedef T0 first_argument_type; typedef T1 second_argument_type; typedef T2 third_argument_type; static const int arity = 3; }; //     template<typename Functor, int NArgs> struct count_args : std::enable_if<function_traits<Functor>::arity == NArgs> { static_assert(NArgs >= 0, "Negative number? WTF?"); }; //  //       ,     template <typename Functor> Functor curry(Functor f, typename count_args<Functor, 1>::type * = 0) { return f; } //   template <typename Functor> std::function< std::function< typename function_traits<Functor>::result_type(typename function_traits<Functor>::second_argument_type) >(typename function_traits<Functor>::first_argument_type) > curry(Functor f, typename count_args<Functor, 2>::type * = 0) { return curry_ < typename function_traits<Functor>::result_type , typename function_traits<Functor>::first_argument_type , typename function_traits<Functor>::second_argument_type > (f); } //   template <typename Functor> std::function< std::function< std::function< typename function_traits<Functor>::result_type(typename function_traits<Functor>::third_argument_type) >(typename function_traits<Functor>::second_argument_type) >(typename function_traits<Functor>::first_argument_type) > curry(Functor f, typename count_args<Functor, 3>::type * = 0) { return curry_ < typename function_traits<Functor>::result_type , typename function_traits<Functor>::first_argument_type , typename function_traits<Functor>::second_argument_type , typename function_traits<Functor>::third_argument_type > (f); } 

In general, everything is very clear here. We implemented function overloading by adding a second dummy parameter. This parameter uses std::enable_if to “turn off” unsuitable curry options during overload resolution. We also added the implementation of currying for unary functions, which simply returns the original function. It remains to write the implementation for the function curry_ for ternary functions. In the theoretical part, I mentioned that during the currying of the ternary function, the result would be a unary, which theoretically could return a function of two arguments, but in fact returns its curried version. With this knowledge, the implementation for the three arguments is extremely simple:

 <typename R, typename T0, typename T1, typename T2> function<function<function<R(T2)>(T1)>(T0)> curry_(function<R(T0,T1,T2)> f) { return [=] (T0 const & t0) -> function<function<R(T2)>(T1)> { return curry_<R,T1,T2>([=] (T1 const & t1, T2 const & t2) { return f(t0,t1,t2); }); }; } 

In general, I wrapped all this (except for examples of use, of course) in the mega namespace and added function_traits for functors to specializations, stuffed it into one header file and uploaded it to GitHub . It will be necessary to add README somehow :) Now we can write any nonsense using ternary functions. Yes, even like this:

 string foo(string s, int i, double d) { ostringstream str; str << s << ": " << i << " . = " << d << "$"; return str.str(); } int main() { cout << mega::curry(foo)("-")(2)(9.95) << endl; // => -: 2 . = 9.95$ return EXIT_SUCCESS; } 

The beauty of this approach is that new, more specific functions can be built on the fly from the “wider” ones. How and where exactly this can be applied, everyone decides for himself.

Honestly, I didn’t check whether something similar had already been implemented, so I don’t exclude that I wrote another bicycle, because it was interesting to me from an academic point of view. In addition, from the point of view of optimality, for the time being I did not go into much detail either. I can immediately say that the C ++ compiler optimizes such things as not so good, so as a result we get a whole bundle of call 's with dragging different information between registers. But for the convenience you have to pay.

Thanks for attention.

May the Force be with you.

PS I have an early morning, and online, I will most likely appear closer in the evening. So do not do much holivarte without me :)