Can currying be implemented via coroutines?

Question

Is it possible to implement function currying via coroutines? How would you do it?

Normally, if I need to curry a function, I use boost::hana::curry, like this, but I'm curious to know if C++20's coroutines can serve the same task as well.

Answer 1

Currying in C++ more or less needs to look something like this.

There is an initiating function which takes a callable of some kind and returns a currying object:

auto curry = curry_func(some_function);

The currying object has an operator() overload that takes the next parameter and returns either a new currying object (either copying from or moving from the current object) or calls the function and returns its value. That last part requires some if constexpr gymnastics (or some equivalent). This means that the currying object needs to be some kind of template that knows at least the number of arguments it expects. So it may as well know their types.

So really, curry_func probably is curry_func<RetyrnType(Params...)>.

So what is going on in the currying object? It needs some way to store all of Params so that it can eventually invoke the curried call. It needs to store them in order, and it needs to then use them to invoke the callable. Also, we're creating new currying objects with each operator() invocation.

Can coroutines be used in a currying implementation? Yes, but not without a significant caveat.

Each curry function object (the things you call with a parameter) can only be called once. The elements of coroutine state cannot be copied, so if a curry function could be copied, it would have to be a shallow copy.

But there are some benefits. Most C++ curring implementations are horrifying nightmares of metaprogramming nonsense. Even at the highest level of how to apply the parameters to the function call, the code can get pretty ugly.

A coroutine currying implementation, by contrast, is pretty readable in the place where the parameters get applied. For example, this is what it looks like in the code I'm about to introduce:

template<std::size_t Sz>
using int_const = std::integral_constant<std::size_t, Sz>;

template<typename Ret, typename ...Params, std::size_t ...Ixs>
curried_function<0, Ret, Params...> curry_func_detail(Ret(*some_func)(Params...), std::index_sequence<Ixs...>)
{
  std::tuple args{ (co_yield int_const<Ixs>{})...};

  co_return std::apply(some_func, args);
}

template<typename Ret, typename ...Params>
curried_function<0, Ret, Params...> curry_func(Ret(*some_func)(Params...))
{
  return curry_func_detail(some_func, std::make_index_sequence<sizeof...(Params)>{});
}

curry_func_detail is pretty straightforward: an unpacked series of co_yields of integer constants. All of the complexity is hidden away in curried_function and its attendant types.

What this means is that you can relatively easily use the exact same coroutine machinery (curried_function and its ilk) to start playing different games. For example, this is what it would take to curry into two different functions:

template<std::size_t Sz>
using int_const = std::integral_constant<std::size_t, Sz>;

template<typename Ret1, typename ...Params1, std::size_t ...Ixs1, typename Ret2, typename ...Params2, std::size_t ...Ixs2>
curried_function<0, std::tuple<Ret1, Ret2>, Params1..., Params2...> double_curry_func_detail(
  Ret1(*func1)(Params1...), , std::index_sequence<Ixs1...>,
  Ret2(*func2)(Params2...), std::index_sequence<Ixs2...>)
{
  std::tuple args1{ (co_yield int_const<Ixs1 + 0>{})...};
  auto ret1 = std::apply(func1, args);

  std::tuple args2{ (co_yield int_const<Ixs2 + sizeof...(Params1)>{})...};
  auto ret2 = std::apply(func2, args);

  co_return std::tuple{ret1, ret2};
}

template<typename Ret1, typename ...Params1, typename Ret2, typename ...Params2>
auto double_curry_func(
  Ret1(*func1)(Params1...), Ret2(*func2)(Params2...))
{
  return double_curry_func_detail(func1, std::make_index_sequence<sizeof...(Params1)>{},
    func2, std::make_index_sequence<sizeof...(Params2)>{});
}

By contrast, taking an existing currying system and making it do something as relatively simple as this is... difficult. We could even start doing things like transforming parameters or something before passing them to the curried function.

The overall point is that the code that accumulates values and calls the function is distinct from the code that shepherds the values from the caller to the accumulation code. And the former is written in a fairly straightforward way.

That's really the only advantage of using coroutines.

---

So, what is actually going on here, implementation-wise? Here's a working example, so let's step through it.

co_yield e is a mechanism for transporting values between the coroutine function and the outside world, using the promise object as an intermediary. e is given to the promise via a call to yield_value. But the return value of that call is an awaitable that gets co_awaited on. This not only allows us to suspend the coroutine on each co_yield, it also allows us to use the awaitable's await_resume function to make co_yield e generate the parameter value.

Next, when we co_yield, we need to tell the promise which parameter we're trying to access. And we need to do that in a way that the promise can return different types (since the return type will dictate how co_await unpacks it).

That's the point of the integral_constant trick. We're sending a compile-time constant through a function parameter by template argument deduction. This allows yield_value to return await_for_index<I>, where I is the index passed. In turn, this allows await_for_index<I>::await_resume to return different values based on I. This compile-time index is forwarded to the promise so that it can return the right type as well.

So how do we actually shepherd the value? curried_function itself has an index in addition to the parameter types and return value. This tells us which parameter index we're talking about. This functor is neither copyable nor moveable (it can be made moveable, but I'll leave that as an exercise for the reader). Its operator() overload returns either another curried_function for the next parameter or the function's actual return value.

    auto operator()(parameter_t<ParamIndex, Params...> param) &&
    {
        promise_type &promise = hdl_.promise();
        promise.template set_param_value<ParamIndex>(param);

        hdl_.resume();

        if constexpr(ParamIndex + 1 == sizeof...(Params))
        {
            return promise.get_return_value();
        }
        else
        {
            return curried_function<ParamIndex + 1, Ret, Params...>(std::move(*this));
        }
    }

The function gives the promise the appropriate parameter, then resumes the coroutine. If that was the last parameter, it assumes the coroutine co_returned and returns the return value. Otherwise, it returns a new curried_function that services the next parameter.

Note that it is declared &&. This is important, as it does a de-facto move from *this into the new curry function. So if you don't call it as a prvalue, it must be called with an explicit std::move. This makes it difficult to call it more than once, and makes sure that everyone understands visually that you are, in fact, moving *this and therefore should not touch it after this operation.

This also means that there is exactly and only one object with a valid coroutine_handle at any one time.

Note that it would not be too difficult to make a multi-parameter version of this operator() overload.

The last part to touch on is how the promise shepherds the parameter. It stores it internally in a variant. This is done to keep the promise from having to store all of the parameters and to ensure that the parameters don't have to be default constructible.

Note that we don't unpack co_yield within the actual function call because in C++, there is no guarantee that parameters are evaluated in order. And we need in-order evaluation here, as the coroutine and the machinery need to be on the same page with regard to which parameter is currently being retrieved. So we instead unpack them in a brace-init-list inside of the initialization a std::tuple.

---

So here's the full code:

#include <iostream>
#include <utility>
#include <coroutine>
#include <tuple>
#include <variant>
#include <optional>

template<std::size_t ParamIndex, typename ...Params>
using parameter_t = std::tuple_element_t<ParamIndex, std::tuple<Params...>>;

template<std::size_t ParamIndex, typename Ret, typename ...Params>
class curried_function;

template<typename Ret, typename ...Params>
class curry_promise
{
    public:
        curry_promise() = default;

        template<std::size_t Ix>
        void set_param_value(parameter_t<Ix, Params...> param)
        {
            curr_param_.template emplace<Ix + 1>(param);
        }

        template<std::size_t Ix>
        parameter_t<Ix, Params...> get_curr_param()
        {
            return std::get<Ix+1>(curr_param_);
        }

        template<std::size_t I>
        auto yield_value(std::integral_constant<std::size_t, I>)
        {
            return await_for_index<I>(*this);
        }

        auto initial_suspend() noexcept {return std::suspend_never{};}
        auto final_suspend() noexcept {return std::suspend_always{};}

        curried_function<0, Ret, Params...> get_return_object();

        void unhandled_exception() { std::terminate(); }

        void return_value(Ret ret)
        {
            ret_.emplace(ret);
        }

        Ret get_return_value() const
        {
            return *ret_;
        }

        template<std::size_t Ix>
        class await_for_index
        {
        public:
            await_for_index(curry_promise &promise) : promise_{promise} {}

            bool await_ready() noexcept {return false;}

            void await_suspend(std::coroutine_handle<curry_promise> h) noexcept {}

            parameter_t<Ix, Params...> await_resume() noexcept
            {
                return promise_.template get_curr_param<Ix>();
            }

        private:
            curry_promise &promise_;
        };

    private:
        std::variant<std::monostate, Params...> curr_param_;
        std::optional<Ret> ret_;
};


template<std::size_t ParamIndex, typename Ret, typename ...Params>
class curried_function
{
public:
    using promise_type = curry_promise<Ret, Params...>;

    auto operator()(parameter_t<ParamIndex, Params...> param) &&
    {
        promise_type &promise = hdl_.promise();
        promise.template set_param_value<ParamIndex>(param);

        hdl_.resume();

        if constexpr(ParamIndex + 1 == sizeof...(Params))
        {
            return promise.get_return_value();
        }
        else
        {
            return curried_function<ParamIndex + 1, Ret, Params...>(std::move(*this));
        }
    }

    //Non-copyable, non-moveable.
    curried_function(curried_function const&) = delete;

    ~curried_function() { hdl_.destroy(); }

    template<std::size_t Sz, typename Ret2, typename ...Params2>
    friend class curried_function;

    friend class curry_promise<Ret, Params...>;

private:
    template<std::size_t OtherIndex>
    curried_function(curried_function<OtherIndex, Ret, Params...> &&prev_func)
        : hdl_{std::exchange(prev_func.hdl_, nullptr)}
    {
    }

    curried_function(std::coroutine_handle<promise_type> hdl)
        : hdl_(hdl) {}

private:
    std::coroutine_handle<promise_type> hdl_;
};

template<typename Ret, typename ...Params>
curried_function<0, Ret, Params...> curry_promise<Ret, Params...>::get_return_object()
{
    return curried_function<0, Ret, Params...>(std::coroutine_handle<curry_promise>::from_promise(*this));
}

template<std::size_t Sz>
using int_const = std::integral_constant<std::size_t, Sz>;

template<typename Ret, typename ...Params, std::size_t ...Ixs>
curried_function<0, Ret, Params...> curry_func_detail(Ret(*some_func)(Params...), std::index_sequence<Ixs...>)
{
  std::tuple args
  { (co_yield int_const<Ixs>{})...};

  co_return std::apply(some_func, args);
}

template<typename Ret, typename ...Params>
curried_function<0, Ret, Params...> curry_func(Ret(*some_func)(Params...))
{
  return curry_func_detail(some_func, std::make_index_sequence<sizeof...(Params)>{});
}





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

void co_test()
{
}

int main()
{
    std::cout << test(1, 2.3, 3) << std::endl;
    std::cout << curry_func(test)(1)(2.3)(3) << std::endl;
    return 0;
}

Answer 2

I'm going to say that no, you can't reasonably create a curry mechanism with C++ corotines, because the corotine state is not copyable, i.e. the following code can't work

int g(int x, int y, int z) { return x + y + z; }
auto f = curry(g);
auto f1 = f(10);
auto f2 = f1(12);
auto f3 = f1(25); // error, can't re-use f1