Functional Utility in C++ (Curry, Partial Binding and Pipeline)

Question

TLDR

I created a curry/partial binding "lib. My request for "code review" is, what possible improvements I need to achieve "release quality", if I wanted to release this as a lib?

You can see the end result here. https://godbolt.org/z/SnFnFt

Complete story and analyzing the code

This weekend I caught myself testing some new C++2x functionalities and come up with a "lib" that allow me to do this:

int sum(int a, int b, int c)
{
    return a+b+c;
}
...
auto f = $(sum);
std::cout << "1: " << f(1)(2)(3) << std::endl;
std::cout << "2: " << f(1,2)(3) << std::endl;
std::cout << "3: " << f(1)(2,3) << std::endl;
std::cout << "4: " << f(1,2,3) << std::endl;
std::cout << "5: " << (f << 1 << 2 << 3)() << std::endl;
std::cout << "6: " << (f << 1 << 2)(3) << std::endl;
std::cout << "7: " << (f << 1)(2, 3) << std::endl;
...
auto v = std::vector<int>{1,2,3};
std::transform(std::begin(v), std::end(v),
    std::begin(v),
    $$(
        $(sum) << 1 << 2,
        $(times) << 2)
    );
std::cout << "11: " << v << std::endl;

Complete code is at the end of this post. I will try to explain my rationale and the code as much as possible here.

The code relies heavily on "parameter pack" and "fold expressions" and very complex enable_if. Truly the only complex and hard-to-read part of the code, in my opinion. But let me try to explain it as much as possible.

It all start at the function $. TF here is meant to be callable. TF* is, of course, a pointer to this callable. In the example above, a pointer to sum. All I do here is create my wrapper class and return it. All the "magic" will happen in side this wrapper.

template <typename TF>
auto $(TF* f)
{
    return typename make_f<TF>::type
    {
        std::make_tuple(f)
    };
}

Here I have my first problem. To create my wrapper I need to know all TF arguments types, because I will use them to guarantee the binding is correct.

There is a "very easy way" to do this.

template<typename... TArgs> struct types { using type = std::tuple<TArgs...>; };

template<class T> struct args;
template<class TReturn, class... TArgs> struct args<TReturn     (TArgs...)> : types<TArgs...> {};
template<class TReturn, class... TArgs> struct args<TReturn  (*)(TArgs...)> : types<TArgs...> {};
template<class T> using args_t = typename args<T>::type;

So args_t<(int (*) (int,int)> returns std::tuple<int,int>.
See more here: https://godbolt.org/z/h4sbtW

With this I can build my wrapper type with:

using type = Func<TF, args_t<TF>, std::tuple<TF*>>;

This is the type of the wrapper completely unbound. Its template parameters are: 1 - function type;
2 - std:tuple of TF arguments, as we saw above'
3 - std:tuple of all bound parameters so far. Up until now just the function pointer.

The idea now is that everytime you give one more argument, I store in a "bigger" tuple with std::tuple_cat(old, new_argument), until this "catted" tuple matches the function definition.

Then I just call the target function.

The "heart" of the code that does that is:

template <typename TF,
    typename... TArgs,
    typename... TBounds>
struct Func<TF, std::tuple<TArgs...>, std::tuple<TF*, TBounds...>>
{
...
// all args to the target function
using tuple_args = std::tuple<TArgs...>;        
// bound args so far
using tuple_bound = std::tuple<TF*, TBounds...>;
...
// bound args store in a tuple
tuple_bound bound;                              
...
// magic happen here: bind, partial apply on operator()
template <
        typename... TBinds,
        size_t QTD = sizeof...(TBinds),

        // avoid binding more arguments than possible
        typename = std::enable_if_t<QTD <= (sizeofArgs - sizeofBounds)>,

        // test if arguments types match, otherwise generate compiler error
        // more on this below
        typename = std::enable_if_t<
            types_match<
            sizeofBounds,
                tuple_args,
                std::tuple<TBinds...>,                
                std::make_index_sequence<sizeof...(TBinds)>
            >::type::value                  
        >
    >
    auto operator() (TBinds... binds)                       
    {                                       
        auto newf = Func<TF, tuple_args,    
            std::tuple<TF*, TBounds..., TBinds...>
        >
        {
            std::tuple_cat(bound, std::make_tuple(binds...))
        };
        // if we bound exactly the number of args, call target function
        // else returns a partial applied function
        if constexpr (QTD == (sizeofArgs - sizeofBounds))           
            return newf();
        else 
            return newf;                            
    }
}

I have a "Func" template specialization for when the bind is complete:

template <typename TF, typename... TArgs>
struct Func<TF, std::tuple<TArgs...>, std::tuple<TF*, TArgs...>>
{
    std::tuple<TF*, TArgs...> bound;

    auto operator() ()
    {
        return std::apply(fwd, bound);
    }

    static auto fwd(TF* f, TArgs... args)
    {
        return f(args...);
    }
};

It guarantees that only the exact types are bound and it only allows you to call the function. In theory it represents a "auto (*) ()" function. If that was possible.

One nice feature of all of this, is that I can generate an (horrible) compile error when you try to bind arguments with the wrong type. This is done by the enable_if below that exists on the "operator ()" of the Func class.

template <
        // all new arguments that you are trying to bind
        typename... TBinds,
        // enabled only if the new binds match possible arguments
        typename = std::enable_if_t<
            types_match<
                sizeofBounds,
                tuple_args,
                std::tuple<TBinds...>,                
                std::make_index_sequence<sizeof...(TBinds)>
            >::type::value  

The "magic" here is:

1 - tuple_args would be, for example, std:tuple<int,int>;
2 - We have not bound anything yet, so sizeofBounds is zero, and we are passing TBinds... new arguments. So, I need to check if these new types match what is expected. I do this with the types_match type trait. It receives two std::tuple and an offset, and check if their types match.

Something like this.

std::is_same<
    decltype(std::get<0>(tuple1),
    decltype(std::get<0 + OFFSET>(tuple2)
> && std::is_same<
    decltype(std::get<1>(tuple1),
    decltype(std::get<1 + OFFSET>(tuple2)
> && ...

See more here: https://godbolt.org/z/wG8JYr

This allows you to bind any number of arguments at any time. The only constraints are that the types must match, and you cannot bind more than needed.

All of this seems like a huge burden to a simple function call, but "Godbolting" this with:

($(sum) << rand() << rand() << rand())();

generates:

call    rand
mov     ebx, eax # ebx = rand()

call    rand
mov     ebp, eax # ebp = rand()

call    rand     # eax = rand()

add     ebp, ebx
add     ebp, eax # ebp = ebp + ebx + eax

Which I consider a wonderful result. The compiler optimization killed everything. Wonderful beasts they are!

I even did a small performance test to assert this. The performance is pretty much identical to normally calling the function.

https://github.com/xunilrj/sandbox/blob/master/sources/cpp/func/main.cpp#L87

TEST_CASE("Func.Performance.Should not be slower than manual code", "[ok]")
{
    using namespace std;

    // I will generate some random numbers below

    random_device rnd_device;
    mt19937 mersenne_engine{ rnd_device() };
    uniform_int_distribution<int> dist{ 1, 52 };
    auto gen = [&dist, &mersenne_engine]() { return dist(mersenne_engine); };
    vector<int> vec(3);

    std::clock_t    start;
    start = std::clock();

    // Benchmark. Manual calling sum with tree random numbers
    /* MANUAL CODE */
    auto r = true;
    for (int i = 0; i < 10000000; ++i)
    {
        generate(begin(vec), end(vec), gen);
        auto expected = sum(vec[0], vec[1], vec[2]);

        //using this just to guarantee that the compiler will not drop my code.
        r &= (sum(vec[0], vec[1], vec[2]) == expected);
    }
    /* MANUAL CODE */
    auto manualTime = (std::clock() - start) / (double)(CLOCKS_PER_SEC / 1000);


    start = std::clock();
    // Now we are using the "lib" code
    /* FUNC CODE */
    auto rr = true;
    for (int i = 0; i < 10000000; ++i)
    {
        generate(begin(vec), end(vec), gen);
        auto expected = sum(vec[0], vec[1], vec[2]);

        auto f = $(sum) << vec[0] << vec[1] << vec[2];

        // again just to guarantee nothing is dropped.
        rr &= (f() == expected);
    }
    /* FUNC CODE */
    auto funcTime = (std::clock() - start) / (double)(CLOCKS_PER_SEC / 1000);


    std::cout << "manual: " << manualTime 
        << ", func: " << funcTime 
        << " (func/manual = " << (float)funcTime / (float)manualTime << ")" << std::endl;
    REQUIRE(r == rr);

    // Assert that we are inside a "noise threshold" in RELEASE
    #ifdef NDEBUG
        REQUIRE(funcTime < (manualTime * 1.05)); // Func cannot be 5% slower than manual code
    #endif
}

Complete code using the "lib":
https://github.com/xunilrj/sandbox/blob/master/sources/cpp/func/main.cpp

Possible steps would be:

1 - Test with member function;
2 - Test functions with (references, pointers, moves etc...);
3 - Test with Polymorphism;
4 - Test with unmaterialized templates;
5 - The pipeline function creates a tuple of "constructed" objects. Is this avoidable?
6 - Test bounding High-Order-Functions with other function and "partial applied" function.
7 - Test with more callback, events, observers etc... systems.

Complete "lib" code:
https://github.com/xunilrj/sandbox/blob/master/sources/cpp/func/func.h

Me going through what/why and how:
https://github.com/xunilrj/sandbox/tree/master/sources/cpp/func

Complete code

#include <tuple>
#include <iostream>
#include <type_traits>
#include <algorithm>
#include <vector>

template <typename TF,
    typename TArgs,
    typename TBound>
struct Func{};

template <typename TF, typename... TArgs>
struct Func<TF, std::tuple<TArgs...>, std::tuple<TF*, TArgs...>>
{
    std::tuple<TF*, TArgs...> bound;

    auto operator() ()
    {
        return std::apply(fwd, bound);
    }

    static auto fwd(TF* f, TArgs... args)
    {
        return f(args...);
    }
};

template <typename TF,
    typename... TArgs,
    typename... TBounds>
struct Func<TF, std::tuple<TArgs...>, std::tuple<TF*, TBounds...>>
{
    using result_of = std::invoke_result_t<TF, TArgs...>;

    using tuple_args = std::tuple<TArgs...>;
    using tuple_bound = std::tuple<TF*, TBounds...>;

    constexpr static size_t sizeofArgs = sizeof...(TArgs);
    constexpr static size_t sizeofBounds = sizeof...(TBounds);

    using next_argument = std::tuple_element_t<sizeofBounds, tuple_args>;

    tuple_bound bound;

    template <size_t OFFSET,
        typename TAs,
        typename TBs,
        typename SQ>
    struct types_match  {};
    template <size_t OFFSET,
        typename TAs,
        typename TBs,
        size_t... IA>
    struct types_match<OFFSET, 
        TAs, 
        TBs,
        std::index_sequence<IA...>
    > 
    {
        using type = std::conjunction<
            std::is_same<
                std::tuple_element_t<OFFSET + IA, TAs>,
                std::tuple_element_t<IA, TBs>
            >...
        >;
    };

    template <
        typename... TBinds,
        size_t QTD = sizeof...(TBinds),
        typename = std::enable_if_t<QTD <= (sizeofArgs - sizeofBounds)>,
        typename = std::enable_if_t<
            types_match<
            sizeofBounds,
                tuple_args,
                std::tuple<TBinds...>,                
                std::make_index_sequence<sizeof...(TBinds)>
            >::type::value
        >
    >
    auto operator() (TBinds... binds)
    {
        auto newf = Func<TF, tuple_args,
            std::tuple<TF*, TBounds..., TBinds...>
        >
        {
            std::tuple_cat(bound, std::make_tuple(binds...))
        };
        if constexpr (QTD == (sizeofArgs - sizeofBounds))
            return newf();
        else 
            return newf;
    }

    template <
        typename... TBinds,
        size_t QTD = sizeof...(TBinds),
        typename = std::enable_if_t<QTD <= (sizeofArgs - sizeofBounds)>,
        typename = std::enable_if_t<
            types_match<
            sizeofBounds,
                tuple_args,
                std::tuple<TBinds...>,                
                std::make_index_sequence<sizeof...(TBinds)>
            >::type::value
        >
    >
    auto operator << (TBinds... binds)
    {
        auto newf = Func<TF, tuple_args,
            std::tuple<TF*, TBounds..., TBinds...>
        >
        {
            std::tuple_cat(bound, std::make_tuple(binds...))
        };
        return newf;
    }
};


template <typename TF>
struct make_f
{
    template<typename... TArgs> struct types { using type = std::tuple<TArgs...>; };

    template<class Sig>
    struct args;

     template<class R, class...Args>
    struct args<R (Args...)> : types<Args...>
    {        
    };

    template<class R, class...Args>
    struct args<R (*)(Args...)> : types<Args...>
    {        
    };

    template<class Sig> using args_t = typename args<Sig>::type;

    using type = Func<TF, args_t<TF>, std::tuple<TF*>>;
};

template <typename TF>
auto $(TF* f)
{
    return typename make_f<TF>::type
    {
        std::make_tuple(f)
    };
}

template <typename Fs1, typename... Fs>
struct pipeline
{
    using functions_type = std::tuple<
        Fs1,
        Fs...
    >;
    functions_type fs;

    using data_type = std::tuple<
        typename Fs1::next_argument,
        typename Fs1::result_of,
        typename Fs::result_of...
    >;

    data_type t;

    pipeline(Fs1 fs1, Fs... fs) :  fs{fs1, fs...}, t{}
    {
    }

    auto operator() (typename Fs1::next_argument arg)
    {
        std::get<0>(t) = arg;
        call_pipe(t, fs,
            std::make_index_sequence<sizeof...(Fs) + 1>{}
        );
        return std::get<std::tuple_size_v<data_type> - 1>(t);
    }

    template <size_t... Is>
    void call_pipe(data_type& t,
        functions_type& fs,
        std::index_sequence<Is...> s)
    {
        ((
            std::get<Is + 1>(t) = 
                std::get<Is>(fs)
                    ( std::get<Is>(t) )
        ),...);
    }
};

template <typename Fs1, typename... Fs>
auto $$(Fs1 fs1, Fs... fs)
{
    return pipeline{fs1, fs...};
}


template<typename T>
std::ostream& operator << (std::ostream& out, const std::vector<T>& items)
{
    out << "[";
    for(auto&& x : items) out << x << ",";
    return out << "]";
}

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

int times(int a, int b)
{
    return a*b;
}

int main (int argc, char** argv)
{
    auto f = $(sum);
    std::cout << "1: " << f(1)(2)(3) << std::endl;
    std::cout << "2: " << f(1,2)(3) << std::endl;
    std::cout << "3: " << f(1)(2,3) << std::endl;
    std::cout << "4: " << f(1,2,3) << std::endl;

    std::cout << "5: " << (f << 1 << 2 << 3)() << std::endl;
    std::cout << "6: " << (f << 1 << 2)(3) << std::endl;
    std::cout << "7: " << (f << 1)(2, 3) << std::endl;

    auto v = std::vector<int>{1,2,3};
    std::transform(std::begin(v), std::end(v),
        std::begin(v),
        $(times) << 2);
    std::cout << "8: " << v << std::endl;

    std::transform(std::begin(v), std::end(v),
        std::begin(v),
        $(times)(2));
    std::cout << "9: " << v << std::endl;

    auto p1 = $$($(sum) << 1 << 2, $(times) << 2);
    std::cout << "10: " << p1(4) << std::endl;

    std::transform(std::begin(v), std::end(v),
        std::begin(v),
        $$($(sum) << 1 << 2, $(times) << 2));
    std::cout << "11: " << v << std::endl;
    return 0;
}

Answer 1

This is a cool idea. You can improve the code by using the STL utilities that support currying/composition.

For currying, there is std::bind and std::bind_front:

// this is the STL way to curry functions
auto demoSTL() {
    auto sum1 = std::bind_front(sum, 1);
    auto sum123 = std::bind_front(sum1, 2, 3);
    auto call = sum123();
    return call;
}

You can make template wrappers around std::bind_front to make the interface look like your $ function. Here's some starter code: https://godbolt.org/z/S-kni4.

One major advantage of the STL functions is that they do type checking for you. It's always nice to have (relatively) bug free code written for you for free! So you might as well use that instead of writing complex enable_ifs and tuple_cats.

One of the hard parts of currying as you've implemented it is checking whether the operator() should return a value or another currying object. This is a bit easier if you are restricted to function pointers (as your code is). But if you want to support all callables, it's harder. Consider this case:

struct Overloaded {
    int foo(int) { /*...*/ }
    int foo(int, int) { /*...*/ }
};

What should $(foo)(1) do? Should it call the first overload or curry the second one?

You can get around this problem and simplify your code by changing the interface a little bit. Let the user decide when a function should be called. Then $(foo)(1)() calls the first overload and $(foo)(1)(2)() calls the second overload. Let std::bind_front deal with compiler errors in case the programmer puts the call in the wrong place. This allows you to support all callables.

I don't have as much to say about composition. Note that the raw language already has good support for composition with calls like multiply2(sum4(5)) (or a lambda that does the same thing)... if you would rather write compose(sum4, multiply2)(5) then you can write wrappers, but it gets a pretty ugly (IMO) when you have more than one input/output. Might be easier to just write a lambda every time you want to compose functions.