Currying with Lambdas

Recently I have been skimming through the presentations from CPPCon 2015. I came across Andre Bergner’s short look at an implementation for currying functions in C++. Admittedly I jumped through it without close attention, so I don’t know what his design goals were (above the generic currying of functions) nor whether he was working under any limitations. However I did see it was basically storing the partially applied arguments in std::tuple‘s and used std::index_sequence machinations for unpacking the tuples.

I thought surely this can instead be done easily with a lambda to the advantage of a lot less syntactic noise.

C++ Considerations

With this in mind I decided to have a look at what an implementation might look like were it to use lambdas. I had to set some design goals and without having an actual use for currying a function, I chose them arbitrarily. Heres the list of them:

  • Issue: It’s not possible to determine what arguments every function might accept as a compile-time calculation without testing against specific arguments. Functions in general may be overloaded, may have default parameters, may use variadic templates, or variable argument lists. I either have to limit the curry implementation to accept only functions with fixed signatures, or alternately test whether the curried function is invokable every time a new parameter is given.
  • Decision: Use the more general (and simpler) implementation and have the curry implementation support C++ functions with unknown number and type of arguments – testing whether it can execute with the arguments provided at each step.
    This means a function with default parameters will never accept entries for them in its curried form. It would have invoked the target function when the last non-default parameter was provided.
    It also means that if one passes incorrect arguments through, the curried function would continue to accept more ad infinitum. It could never be sure whether some future argument might be acceptable to the curry’d function.
  • Issue: C++ functions are very particular about what type qualifiers their arguments have: either for selecting the best match when the function is overloaded or when references come into play. The choice is how to capture the arguments’ types for storage.
  • Decision: I don’t have any use-case or argument to make for supporting parameters whose type qualifiers are preserved. As currying is applied more in functional programming, I figured capture-by-value would be simpler, more true to its origins and make the code more readable.
    An implementation which follows this would mean currying functions which accept references for parameters doesn’t make sense.

The Implementation

The trick here is really in how to get the arguments into a lambda one-by-one, and then how to get them out of the lambda when we need to eventually invoke the intended function.

Every time the caller provides an additional argument to the curried function we’ll get the compiler to check whether the function can now be called with the arguments collected so far. If it can we simply return the result. If it cannot we need to return a new function object which has captured all the arguments provided until now and is able to accept a new argument – at which point it will again check whether it has sufficient arguments to invoke the original curry’d function.

It makes sense to split out the captured arguments from the function we’re going to pass them to. So really what our capture looks like is a lambda which takes a function as a parameter and it calls that function with all the arguments in its capture. That way we have a method of easily getting things into the capture (ie: through the lambda’s capture) and out of the capture (invoke the lambda with a function and it will pass all of its captured values to that function).

#include <iostream>
using namespace std;

struct yes {};

template< typename FUNC >
struct is_callable_with
{
	template< typename... PARAMS , typename = decltype(std::declval<FUNC>()(std::declval<PARAMS>()...)) >
	yes test(int,PARAMS...) const;

	void test(...) const;

	template< typename... PARAMS >
	auto operator() (PARAMS...) const -> decltype(test(0, std::declval<PARAMS>()...));
};

template< typename FUNC, typename CAPTURE >
using is_callable_by_capture = std::is_same< yes, decltype(std::declval<CAPTURE>()(std::declval<is_callable_with<FUNC>>())) >;

// case for when FUNC can be called with the current CAPTURE
template< typename FUNC, typename CAPTURE >
auto curry_impl(FUNC f, CAPTURE c, ...)
{
	return c(f);
}

// case for when FUNC cannot be called with current CAPTURE
// and we assume this is because an additional entry in the CAPTURE is needed
template< typename FUNC, typename CAPTURE, typename = std::enable_if_t< !is_callable_by_capture<FUNC,CAPTURE>::value > >
auto curry_impl(FUNC f, CAPTURE c, int)
{
	return [f,c](auto new_param) {
		auto make_new_capture = [new_param](auto... params) {
			return [new_param, params...](auto callee) {
				return callee(params..., new_param);
			};
		};

		return curry_impl(f, c(make_new_capture),0);
	};
}

template< typename T >
auto curry(T func)
{
	return curry_impl(func, [](auto f) {return f();}, 0);
}

//--------------------------

int print(int a, int b, int c)
{
	std::cout << "Printing " << a << " " << b << " " << c << std::endl;
	return 99;
}

int main() {
	auto c_0 = curry(print); // curried function ready to receive arguments
	auto c_1 = c_0(1); // first argument provided
	auto c_2 = c_1(2); // second argument provided
	auto return_value = c_2(3); // final argument

	std::cout << "Printing returned " << return_value << std::endl;
	
	return 0;
}

Online code compiler here.

The implementation is tricky to describe. Hopefully it kind of speaks for itself. There are a few things I’d like to highlight though:

– Clearly we need an entry point which accepts a regular C++ function and returns it’s curried version. So this is curry(). It simply defers the actual currying to curry_impl() as the latter needs to take the current capture. To this end curry() provides the initial capture (which is empty because no arguments have been provided yet).

– We already know that we need two compilation paths: one for when we still need more arguments (returns a function object accepting the additional argument) and another for when we have enough and can invoke the intended function to exact its payload. The split here is in the two curry_impl() functions. Some template SFINAE magic helps the compiler choose which one should be called whenever a new argument is provided to the curried function.

– Looking at the curry_impl() function for the case when the caller still needs to provide more arguments: note the make_new_capture lambda. Thats how we take the new argument the caller has just provided and add it to all the ones already provided. We ask the previous capture (with all the previous arguments) to call the new one with its argument list. We then make a new capture which includes both the new value and all the previous ones. Pretty neat huh? But mind bending!

SFINAE Gotcha

I’m going to assume anyone reading this is familiar with SFINAE (if not, follow the link). There is a little trick to using it in the code sample. It may not be obvious on first look.

Since SFINAE only applies to ill-formed template expressions or template deduction when generating a type, any error caused by ill-formed code in the body of a template function is still a hard error. So in the code above it might be tempting do the switch between which implementation of curry_impl() to call by doing this: ask the compiler to look at decltype( capture( func ) ) which would in effect say “try to get the capture to pass its arguments to the function and tell us the return type”.

This results in a hard error because the mismatch actually occurs in the body of operator() on the capture lambda, and not in the decltype() clause we’d use in the template argument list.

What we need is for the body of the lambda to always be well-formed code but still be able to somehow use SFINAE to determine whether function f can be called with the arguments captured in the capture lambda.

Since the capture lambda is designed to call _any_ function we give it, the solution is simple: define a function object (in this case called is_callable_with) which declares an operator() that accepts any number of arguments. The function object is templated on the type we’d like to test. Then in a decltype() expression we can ask the compiler what the return type would be if an instance of is_callable_with<FUNC> were to be passed into the capture lambda. The capture lambda can never fail to have a well-formed body since the is_callable_with<> function object accepts any number and type of argument.

In this case is_callable_with declares that in the case where F would be invokable with the arguments it sees, its operator() would return type yes. This then becomes the return type of the lambda capture which would call it and so we can do some SFINAE magic based on that.

Of course since we never actually invoke is_callable_with<>, it only needs to be a declaration.

Hopefully the code is somewhat readable, if mind-bending. It was a fun exercise but I have no immediate use-case I can think of for it.

Future Considerations

I think some of the downsides to this implementation could be done away with. It is possible, for instance, to see whether adding machinery to curry() could figure out a known signature for the function it is wrapping.

Should the signature be known (or alternately given to it as a template parameter) then we could do away with the SFINAE test and instead have a recursive template function if the number and types for the arguments are known when curry() is called.

Additionally if all argument types are known then the curried form can easily be type-erased by a std::function after every application of an argument. Since I don’t have use-cases I would like to solve by currying a function, I don’t know how big a deal this would be.

The existing implementation could be the backup for when the signature is not known. I haven’t given this more than cursory thought because, as mentioned at the start of this post, I have no actual use-case in C++ for any of this.

I also think that with the right incantations of &&, std::forward and its cronies, it’s possible to present the captured types to the final function with all (or most) of their qualifiers. However having a partially bound function where the arguments could be references sounds like a recipe for disaster.

Advertisements
Currying with Lambdas

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s