Zero-Overhead C++17 Currying & Partial Application

Modern C++ standards introduce powerful features that enable functional programming patterns to flourish. Among these, currying and partial application stand out as particularly useful techniques.

In this article, we will:

• Explain the concepts of currying and partial application.
• Implement a generic constexpr zero-overhead curry function in C++17.
• Analyze the generated assembly to demonstrate the lack of overhead.

Understanding Currying

Currying is a technique in which a function that takes multiple arguments is transformed into a sequence of functions, each taking a single argument.

Example: Non-Curried vs. Curried Function

A simple function with three parameters:

auto add3(int a, int b, int c) {
    return a + b + c;
}
add3(1, 2, 3); // Returns 6.

A curried version:

auto curried_add3(int a) {
    return [a](int b) {
        return [a, b](int c) {
            return a + b + c;
        };
    };
}
curried_add3(1)(2)(3); // Returns 6.

Benefits of Currying

Currying allows for incremental argument binding, improving readability and reducing redundancy:

auto add2_one = curried_add3(1);
auto add1_three = add2_one(2);

add1_three(3); // Returns 6.
add1_three(4); // Returns 7.

This can be useful in practical scenarios such as filtering or searching through a collection:

std::vector<std::string> names{/* ... */};

auto find_in_names = curried_find(std::begin(names))(std::end(names));
auto jack = find_in_names("Jack");
auto rose = find_in_names("Rose");

Understanding Partial Application

Partial application refers to fixing a subset of a function’s arguments, returning another function with a reduced number of arguments.

Example: Partial Application

partial_add3(1, 2, 3);  // Returns 6.
partial_add3(1)(2, 3);  // Returns 6.
partial_add3(1, 2)(3);  // Returns 6.
partial_add3(1)(2)(3);  // Returns 6. (Currying!)

This can be implemented in C++17 using recursion, variadic templates, if constexpr, and fold expressions:

template <typename... Ts>
auto partial_add3(Ts... xs) {
    static_assert(sizeof...(xs) <= 3);

    if constexpr (sizeof...(xs) == 3) {
        return (0 + ... + xs);
    } else {
        return [xs...](auto... ys) {
            return partial_add3(xs..., ys...);
        };
    }
}

Implementing a Generic curry Function

We aim to write a curry function that:

• Enables currying and partial application for any function object.
• Is constexpr-friendly when applicable.
• Introduces zero overhead compared to manual implementations.

Declaration

template <typename TF>
constexpr decltype(auto) curry(TF&& f);

The return type decltype(auto) ensures that the final function call retains the exact return type of the original function.

Definition

template <typename TF>
constexpr decltype(auto) curry(TF&& f) {
    if constexpr (std::is_invocable_v<TF>) {
        return std::forward<TF>(f)();
    } else {
        return [xf = std::forward<TF>(f)](auto&&... partials) mutable constexpr {
            return curry([
                partial_pack = std::tuple{std::forward<decltype(partials)>(partials)...},
                yf = std::move(xf)
            ](auto&&... xs) constexpr -> decltype(auto) {
                return std::apply([&yf](auto&&... ys) -> decltype(auto) {
                    return std::invoke(yf, std::forward<decltype(ys)>(ys)...);
                }, std::tuple_cat(partial_pack, std::tuple{std::forward<decltype(xs)>(xs)...}));
            });
        };
    }
}

How It Works

1. The base case executes the function when all required arguments are present.
2. Otherwise, the function returns a lambda that captures partial arguments and recursively calls curry.
3. Arguments are stored in a tuple and applied using std::apply.

Performance Analysis

To verify that curry introduces no overhead, we compare generated assembly for direct calls vs. curried calls.

Benchmark Code

constexpr auto sum = [](auto a, auto b, auto c, auto d, auto e, auto f, auto g, auto h) constexpr {
    return a + b + c + d + e + f + g + h;
};

constexpr auto expected = sum(0, 1, 2, 3, 4, 5, 6, 7);

constexpr auto s0 = curry(sum)(0, 1, 2, 3, 4, 5, 6, 7);
constexpr auto s1 = curry(sum)(0)(1, 2, 3, 4, 5, 6, 7);

Results

Optimization Level	Baseline (Lines)	curry (Lines)	Overhead
O0	14	14	0%
O1	2	2	0%
O2	2	2	0%
O3	2	2	0%
Ofast	2	2	0%

No additional overhead is introduced when using curry.

Compiler Bugs & Issues

While curry is efficient, it exposes some compiler limitations:

• Some versions of g++ crash with internal errors.
• clang++ has issues handling the recursion depth.

These issues have been reported:

• GCC bug #78006
• Clang bug #31435

Conclusion

C++17 allows for a zero-overhead, generic curry implementation that supports both currying and partial application. The assembly analysis confirms that modern compilers optimize curry effectively. Despite some compiler issues, curry is a powerful tool for functional programming in C++.