Currying and partial application in C++14

In this article I’m going to tell you about one of the currying options and partial application of the functions in C++ which is my personal favourite. I’m also going to show my own pilot implementation of this thing and explain the point of currying without complex mathematical formula, making it really simple for you. We’ll also see what’s under the hood of kari.hpp library which we’ll be using for currying functions. Anyway, there are lots of fascinating stuff inside, so welcome!

Currying

So, what is currying? I guess it’s one of those words you hear from Haskell programmers all the time (after monad, of course). Essentially, the definition of the term is pretty simple, so those readers who have already written on ML type languages or Haskell, or who knows what it means from elsewhere, feel free to skip this section.

Currying — is the technique of transforming a function that takes N arguments into one function, which takes a single argument and returns the function of the next argument, and it goes on and one until we return the last argument’s function, which is going to represent the overall result. I think it helps if I show you examples:

Here we have a binary addition function. And what if we want to turn it into single variable function? It’s actually very simple:

No, what did we do? We took a value based on a single argument called lambda that in turn takes the second argument and performs the addition itself. As the result, we can apply the curried function curried_sum2 to our arguments one by one :

And that’s actually the whole point of currying operation. Of course, it’s possible to do it with functions of any arity — it’s going to work absolutely the same way. We will return a curried function of N-1 arguments every time we take the value from another argument:

Partial application

Partial application — is a way of calling functions of N arguments when they take only a part of the arguments and return another function of the remaining arguments.

In this regard it should be noted that in languages like Haskell this process works automatically, behind a programmer’s back. What we’re trying to do here is to perform it explicitly, i.e. to call our sum3 function like this: sum3(38,3)(1) or maybe like this: sum3(38)(3,1). On top of that, if one function returns another function that has been curried, it can be also called using the list of the first function's arguments. Let's see the example:

We actually have got a little ahead of ourselves here, showing an example of kari.hpp usage, so yes, it does that.

Setting the goals

Before we write something, it’s necessary (or desirable) to understand what we want to have in the end. And we want to have an opportunity to curry and partially apply any function that can be called in C++. Which are:

• lambdas (including generic ones)
• function objects (functors)
• functions of any arity (including templates)
• variadic functions
• methods of a class

Variadic functions can be curried by specifying an exact number of arguments we want to curry. Standard interaction with std::bind and its results are also desirable. And of course, we need an opportunity to apply multiple-variable functions and call nested functions so that it would seem like we’ve been working with one curried function.

And we must not forget about performance, too. We need to minimize computational costs of wrappers, transfer of arguments and their storage. It means we have to move instead of copying, store only what we really need, and return (with further removal) the data as fast as possible.

Author, you’ve been trying to invent std::bind one again!

Yes, and no. std::bind is undoubtedly a powerful and proven tool, and I don't intend to write its murderer or alternative. Yes, it can be used for currying and explicit partial application (with specifying exactly what arguments we're applying, and where, and how many). But it sure it not the most convenient approach, not to mention that it's not always applicable since we have to know the arity of function and write specific bindings depending on that. For example:

API

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

Returns a function object of curry_t type (a curried function) with optional arguments args applied or with the result of application of the arguments to the given function f (is the function is nullary, or the arguments transferred were enough to call it).

If f parameter contains the function that has already been curried, it returns its copy with the arguments args applied.

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

Allows to curry functions with variable number of arguments. After that these functions can be called using () operator with no arguments. For example:

If f parameter contains a function that has already been curried, it returns its copy with altered type of application for variable number of arguments with the arguments args applied.

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

Allows to curry functions with variable number of arguments by specifying an exact number N of arguments we want to apply (except those given in args). For example:

If f parameter contains a function that has already been curried, it returns its copy with altered type of application for N arguments with the arguments args applied.

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

Some auxiliary structures for checking if a function has already been curried. For example:

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

The operator allowing a full or partial application of a curried function. Returns the curried function of remaining arguments of the initial function F, or value of this function obtained by its application on the backlog of old arguments and new arguments as. For example:

If you call a curried function with no arguments using curryV or curryN, it will be called if there are enough arguments. Otherwise, it will return a partially applied function. For example:

Details of implementation

When giving you details of implementation, I’m going to use C++17 in order to keep the text of the article short and avoid unnecessary explanations and piled SFINAE, as well as examples of implementations I had to add within the C++14 standard. All these you can find in the project repository, where you can also add it to your favourites :)

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

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

Now, there are two interesting things about this function:

• we apply it to the arguments only if it’s callable for these arguments and the application counter N is at zero
• if the function is not callable, we consider this call as partial application and create a function object curry_t containing the function and the arguments

struct curry_t

The function object supposed to store the backlog of arguments and the function we will call when applying it in the end. This object is what we’re going to call and apply partially.

There’s a number of reasons why we store the backlog of arguments args_ in std::tuple:

1. situations with std::ref are handled automatically to store references when we need to, by default based on the value
2. convenient application of a function according to its arguments (std::apply)
3. it’s readymade, so you don’t have to write it from scratch :)

We have store the object we call and the function f_ by its value, too, and be careful when choosing the type when creating one (I'm going to expand on this issue below), or moving, or copying it using universal reference in the constructor.

A template parameter N acts as an application counter for variadic functions.

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

And, of course, the thing that makes it all work — the operator which calls the function object.

The calling operator has four functions overloaded.

1. A function with no parameters allowing to start applying the variadic function (created by curryV or curryN). Here we decrement the application counter down to zero, making it clear that the function is ready to be applied, and then we give everything that's required for that to make_curry function.
2. A function of a single argument that decrements the application counter by 1 (if it’s not at zero) and puts our new argument a in the backlog of arguments args_ and transfers all this to make_curry.
3. A variadic function that is actually a trick for partial application of various arguments. What it does is applies them recursively, one by one. Now, there are two reasons why they can’t be applied all in once: a) the application counter can get down to zero before there are no arguments left. b) the function f_ can be called earlier and return another curried function, so all the next arguments will be intended for it
4. The last function acts as a bridge between calling curry_t using lvalue and calling functions using rvalue.

The tags of ref-qualified functions make the whole process almost magical. To put it short, with their help we get to know that an object was called using rvalue reference and we can just move the arguments instead of copying them in the end calling function make_curry. Otherwise we'd have to copy the arguments in order to still have an opportunity to call this function again, making sure the arguments are still there.

Bonuses

Before proceeding to the conclusion, I would like to show you a couple of examples of the syntactic sugar they have in kari.hpp which can be qualified as bonuses.

Operator sections

The programmers who’ve already worked with Haskell should be familiar with operator sections allowing to give a short description of the operators applied. For instance, structure (*2), generates a single-argument function, returning the result of multiplication of this argument by 2. So, what I wanted was to try writing something like that in C++. No sooner said than done!

Function composition

And of course I wouldn’t be a complete wacko if I haven’t tried to write a function composition. As the composition operator I chose operator * as the closest (by the look of it) of all symbols available to the composition sign in maths. I used it to apply the resulting function for an argument, too. So, that's what I got:

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

The same way you can build quite complex compositions in pointfree style, but bear in mind only Haskell programmers will understand these :)

Conclusion

I think it was pretty clear before that there’s no need to use these techniques in real projects. But still, I must mention that. After all, my goal was to prove myself and check new C++ standard. Would I be able to do this? And would C++? Well, I guess, you just saw like we both have kind of done that. And I’m really grateful to all guys who read the whole thing.

Originally published at habr.com.