Elements of functional programming in C ++: partial application

I will not go deep into the theory. What is a partial application is easy to find on the Internet. Including on Wikipedia .

In short, this is a mechanism for fixing k arguments of a function from n arguments, making it a function of (n - k) arguments.

 //    f   : int f (int a, int b, int c, int d) { return a + b + c + d; } //    : auto g = part(f, 1, 2); // 1 + 2 + ... //   : assert(g(3, 4) == 10); // ... + 3 + 4 = 10 

On this topic there are already a lot of publications, including on Habré:

1. C ++ Variadic templates. Currying and partial application
2. Partial application and currying in C ++
3. Curry on C ++

And the “ How should I make function curry? ” Branch on stackoverflow is just a storehouse for those who first come across this topic.

Unfortunately, the quantity has not yet turned into quality, and I never saw a good, usable variant. In this case, that's curious.

Remarkable fact number one . In the mentioned articles there are all the techniques that are needed to implement the correct (in my opinion) partial application.

It is only necessary to carefully analyze everything and put the cubes in the correct order. This is what I am going to do in this article.

Content

1. Goals
2. Existing solutions
3. Philosophizing
4. New solution
5. Implementation
6. Conclusion

Goals

So, what goals are set before us:

1. Actually implementation of the required functionality

   
   
   

   That is, the implementation of some kind of partial application of the function.

   
   
   

2. Highest possible efficiency

   
   
   

   We must not forget that we write in C ++, one of the basic principles of which is the principle of "Abstraction without overhead" (see Stroustrup, Foundations of C ++ ).

   
   
   

   In particular, there should not be any extra copying and no extra transfer.

   
   
   
   Hidden text

   I will add that this is not only one of the most important places in programming with pluses, but at the same time one of the most interesting.
   
   
   

3. Ease of use

   
   
   

   It should be easy for an application programmer to create partially applied functions.

   
   
   

   It should also be easy for him to use partially applied functions in conjunction with existing solutions. For example, transfer a partially applied function to some standard algorithm.

   
   
   

Existing solutions

The authors of the existing solutions offer two main options. Let us name their application whenever possible and explicit application .

Application whenever possible

This technique is that the result of a partial application is a function that can be partially applied again. And the call to the original function occurs when the received arguments are already enough to make the call.

 //   : int f (int a, int b, int c, int d); //   : auto g = part(f); //   : auto h = g(1); //       `f`,     . //    : auto i = h(2, 3); //   -     `f`. //   ,    , , //    . assert(i(4) == 10); 

Pretty ingenious idea. But, unfortunately, in practice does not work.

Why? Suppose we want to partially apply a function that calculates the sum of an arbitrary number of variables:

 auto sum (auto ... xs); 

In this case, we do not know when to stop in the process of partial application.

This sum is calculated both from one, and from two, and from three, and in general from any number of variables.

Therefore, the previous example breaks at the second step, if instead of f substitute sum :

 auto g = part(sum); auto ??? = g(1); //  ,   ? 

The same will happen if the function has multiple overloads with different numbers of arguments. It will be unclear which one should be called.

There is another problem when you can "slip" the correct number of arguments. In our example, it can be represented as:

 auto g = part(f, 1, 2, 3); auto h = g(4, 5, 6); // ... 

Then the function will be partially applied to infinity, and will never be called.

Explicit application

So, the authors say, since we don’t know when to stop a partial application, let's do it explicitly.

Namely, we will create an overload of the "parenthesis" operator with no arguments, the call of which will mean that we need to call an internal function with those parameters that have already been partially applied:

 auto g = part(sum); auto h = g(1); //  ,   ?  ! auto i = h(2, 3, 4, 5, 6); //      . assert(i() == 21); //    . 

The old problem is solved. But there was a new one.

Now every use of a partially applied function implies the knowledge that this is a partially applied function. This means that it cannot be used in standard algorithms. They simply do not know that after throwing arguments, you need to call empty "parentheses".

Philosophizing

To advance further, we will slightly philosophize and express a couple of important thoughts.

First thought

Partial application is a deferred call. In other words, partial application does not produce any "partial calculations". It simply remembers several arguments and waits for the rest to come.

If for the sum, product, and other associative functions, it is still possible to come up with a crutch that will be able to return the partially calculated result (the sum or the product of the numbers obtained earlier), and continue the partial application, then for an arbitrary function such solution will not work.

Second thought

In C ++, there is no built-in partial application mechanism. This means that the programmer, generally speaking, does not expect that only some of the arguments can be given to any arbitrary function, and the others can "throw away" sometime later.

Consequently, when working with partial applications, the programmer knows that he is using it.

Hence, partial application in the C ++ language will always be explicit .

Result of reflection

It turns out that these options are not suitable. Due to seemingly small shortcomings, these “cool” solutions have to be recognized as extremely impractical, and therefore unsuitable for everyday use.

Still, don't forget that C ++ is not a functional language. It is not so easy to take and transfer the design and ideology of one language to another. Here, as with the translation of poetry from a foreign language: the translation should be not literal, but poetic, that is, rhyme in the language of translation.

New solution

Based on all the above, I came to the following conclusion. Since the programmer always knows where he has a partial application, and where the function call, we can both simplify and make our model more universal.

It will consist of two stages:

1. Capture the original arguments.
2. Unconditional challenge with remaining arguments.

I will illustrate with an example.

 //   : auto sum (auto ... xs); //      . auto f = part(sum, 1, 2, 3); //      `f`. //   : assert(f(4) == 10); assert(f(4, 5) == 15); assert(f(4, 5, 6) == 21); 

If you need to partially apply a few more arguments, they are "added" using the same explicit function call of a partial application:

 auto g = part(f, 4, 5); //  part(sum, 1, 2, 3, 4, 5). 

This is std::bind !

It seems, but no. On the one hand, std::bind allows you to handle arguments more flexibly. Put them in arbitrary places, mix, etc.

On the other hand, std::bind requires explicit placement of placeholders and does not work with an arbitrary number of arguments. That is, the user is obliged to indicate in advance how many arguments will be “bled out” in the future, and on what specific places in the call they will stand.

Therefore, I believe that the resulting solution is quite independent and is not a special case of any other existing mechanisms.

Implementation

Perhaps the most interesting part. Code. At the beginning of the article I already mentioned one remarkable fact. So, there is another one.

Wonderful fact number 2 . In the standard library (C ++ 17) there is almost everything necessary for the implementation of partial application for this model.

We need only to define one operation, which, however, is also expressed through the same standard tools.

So, we need (complete and exhaustive list):

1. std :: forward
2. std :: move
3. std :: forward_as_tuple
4. std :: apply
5. std :: invoke
6. std :: tuple_cat
7. std :: make_tuple

When I said that there is almost everything necessary, I meant that you need to define one function:

 template <typename T> constexpr decltype(auto) forward_tuple (T && t) { return apply(forward_as_tuple, std::forward<T>(t)); } 

This function takes an arbitrary tuple and returns a new tuple consisting of references to the elements of the input tuple. If the input tuple contains links to lvalue , then they remain so. The same objects that were stored in the tuple are passed by reference to the rvalue .

Now we can say with confidence that we already have everything we need. You can write code.

1. part function

   
   
   

    template <typename ... As> constexpr auto part (As && ... as) -> part_fn<decltype(std::make_tuple(std::forward<As>(as)...))> { return {std::make_tuple(std::forward<As>(as)...)}; } 

   
   
   

   Accepts an arbitrary number of arguments, the first of which is a certain function or functional object. Stores them all into one tuple using the make_tuple function and returns this tuple wrapped in the part_fn structure.

   
   
   

2. part_fn structure

   
   
   

    template <typename Tuple> struct part_fn { template <typename ... As> constexpr decltype(auto) operator () (As && ... as) const & { return apply(invoke, std::tuple_cat(forward_tuple(t), std::forward_as_tuple(std::forward<As>(as)...))); } template <typename ... As> constexpr decltype(auto) operator () (As && ... as) & { return apply(invoke, std::tuple_cat(forward_tuple(t), std::forward_as_tuple(std::forward<As>(as)...))); } template <typename ... As> constexpr decltype(auto) operator () (As && ... as) && { return apply(invoke, std::tuple_cat(forward_tuple(std::move(t)), std::forward_as_tuple(std::forward<As>(as)...))); } Tuple t; }; 

   
   
   

   1. Stores partially applied objects: a function and its first k arguments.

      
      
      

   2. It has a bracket operator that takes an arbitrary number of arguments.

      
      
      
      1. When called, a tuple of links to the input arguments is formed using the function forward_as_tuple .
      2. A tuple with previously saved objects is also converted to a link tuple using the function defined by us forward_tuple .
      3. Both tuples of links are glued into one using the function tuple_cat . It turns out one big tuple of links.
      4. The glued-up tuple is expanded and passed to the invoke function using the apply function.
      5. The invoke function call on the received arguments.
      
      
      
   
   
   

Everything.

In this place, lovers of cunning template code (like me, for example) should be slightly disappointed.

On the other hand, the simplicity, the elegance of the solution and the fact that it is assembled from only a few standard "cubes" indirectly indicates that it is quite viable and can be easily integrated into the application code.

Using

 int modulo_less (int modulo, int a, int b) { return (a % modulo) < (b % modulo); } auto v = std::vector<int>{...}; std::sort(v.begin(), v.end(), part(modulo_less, 7)); 

Thanks to the make_tuple call, std::ref/cref supported:

 int append (std::string & s, int x) { return s += std::to_string(x); } auto s = std::string("qwerty"); auto g = part(append, std::ref(s)); g(5); g(6); assert(s == "qwerty56"); 

And by using the invoke function, various complex cases will be supported, such as calling a class method (see std :: invoke ), etc.

And all this is "out of the box" and without any special gestures from our side.

Conclusion

Why I think my decision is right.

1. It is simple and transparent. It is assembled from "elementary" components that already exist in the language.
2. It is effective. Abstraction without overhead.
3. Reliably like a hammer. No "magic".
4. It is well integrated into the existing programming paradigm in C ++.
5. Compatible with tools that are used in the standard library. For example, with reference_wrapper for signaling about passing parameters by reference (as in std::make_tuple , std::bind , std::thread ), and also, very importantly, with algorithms.

»Full source code here .

To the content