Unexpected result when trying to compose a curried lambda with another lambda

Question

I am toying with C++11 lambdas and was trying to mimick some function from the functional module of the D programming language. I was actually trying to implement curry and compose. Here is the main that I am trying to get working:

int main()
{
    auto add = [](int a, int b)
    {
        return a + b;
    };
    auto add5 = curry(add, 5);

    auto composed = compose(add5, add);
    // Expected result: 25
    std::cout << composed(5, 15) << std::endl;
}

The problem is that I don't get the same result from g++ and clang++. I get:

• 35 with g++ 4.8.1
• 25 with g++ 4.8.2
• 25 with g++ 4.9
• 32787 with clang++ 3.5 (trunk used with Coliru)

g++ 4.8.2 and 4.9 give me the expected result. The results obtained from g++ 4.8.1 and clang 3.5 do not depend on the value passed to curry. I first thought that this may be a compiler bug, but it is more likely that I have an error in my code.

---

Here is my implementation of curry:

template<typename Function, typename First, std::size_t... Ind>
auto curry_impl(const Function& func, First&& first, indices<Ind...>)
    -> std::function<
        typename function_traits<Function>::result_type(
        typename function_traits<Function>::template argument_type<Ind>...)>
{
    return [&](typename function_traits<Function>::template argument_type<Ind>&&... args)
    {
        return func(
            std::forward<First>(first),
            std::forward<typename function_traits<Function>::template argument_type<Ind>>(args)...
        );
    };
}

template<typename Function, typename First,
         typename Indices=indices_range<1, function_traits<Function>::arity>>
auto curry(Function&& func, First first)
    -> decltype(curry_impl(std::forward<Function>(func), std::forward<First>(first), Indices()))
{
    using FirstArg = typename function_traits<Function>::template argument_type<0>;
    static_assert(std::is_convertible<First, FirstArg>::value,
                  "the value to be tied should be convertible to the type of the function's first parameter");
    return curry_impl(std::forward<Function>(func), std::forward<First>(first), Indices());
}

And here is my implementation of compose (note that I only wrote a binary compose while the D one is variadic):

template<typename First, typename Second, std::size_t... Ind>
auto compose_impl(const First& first, const Second& second, indices<Ind...>)
    -> std::function<
        typename function_traits<First>::result_type(
        typename function_traits<Second>::template argument_type<Ind>...)>
{
    return [&](typename function_traits<Second>::template argument_type<Ind>&&... args)
    {
        return first(second(
            std::forward<typename function_traits<Second>::template argument_type<Ind>>(args)...
        ));
    };
}

template<typename First, typename Second,
         typename Indices=make_indices<function_traits<Second>::arity>>
auto compose(First&& first, Second&& second)
    -> decltype(compose_impl(std::forward<First>(first), std::forward<Second>(second), Indices()))
{
    static_assert(function_traits<First>::arity == 1u,
                  "all the functions passed to compose, except the last one, must take exactly one parameter");

    using Ret = typename function_traits<Second>::result_type;
    using FirstArg = typename function_traits<First>::template argument_type<0>;
    static_assert(std::is_convertible<Ret, FirstArg>::value,
                  "incompatible return types in compose");

    return compose_impl(std::forward<First>(first), std::forward<Second>(second), Indices());
}

The class function_trait is used to get the arity, the return type and the type of the arguments of a lambda. This code heavily relies on the indices trick. Since I don't use C++14, I don't use std::index_sequence but an older implementation under the name indices. indices_range<begin, end> is an indices sequence corresponding to the range [begin, end). You can find the implementation of these helper metafunctions (as well as curry and compose) on the online version of the code, but they are less meaningful in this problem.

---

Do I have a bug in the implementation of curry and/or compose or are the bad results (with g++ 4.8.1 and clang++ 3.5) due to compiler bugs?

---

EDIT: You may find the code above not quite readable. So, here are versions of curry and compose that are exactly the same, but use alias templates to reduce the boilerplate. I also removed the static_asserts; while they may be helpful information, that's just too much text for the question and they do not play a part in the problem at hand.

template<typename Function, typename First, std::size_t... Ind>
auto curry_impl(const Function& func, First&& first, indices<Ind...>)
    -> std::function<
        result_type<Function>(
        argument_type<Function, Ind>...)>
{
    return [&](argument_type<Function, Ind>&&... args)
    {
        return func(
            std::forward<First>(first),
            std::forward<argument_type<Function, Ind>>(args)...
        );
    };
}

template<typename Function, typename First,
         typename Indices=indices_range<1, function_traits<Function>::arity>>
auto curry(Function&& func, First first)
    -> decltype(curry_impl(std::forward<Function>(func), std::forward<First>(first), Indices()))
{
    return curry_impl(std::forward<Function>(func), std::forward<First>(first), Indices());
}

template<typename First, typename Second, std::size_t... Ind>
auto compose_impl(const First& first, const Second& second, indices<Ind...>)
    -> std::function<
        typename result_type<First>(
        typename argument_type<Second, Ind>...)>
{
    return [&](argument_type<Second, Ind>&&... args)
    {
        return first(second(
            std::forward<argument_type<Second, Ind>>(args)...
        ));
    };
}

template<typename First, typename Second,
         typename Indices=make_indices<function_traits<Second>::arity>>
auto compose(First&& first, Second&& second)
    -> decltype(compose_impl(std::forward<First>(first), std::forward<Second>(second), Indices()))
{
    return compose_impl(std::forward<First>(first), std::forward<Second>(second), Indices());
}

Answer 1

As I believe others have mentioned in your comments, the issues relating to your code are lifetime issues. Note that you're passing the second parameter, 5, to curry as an rvalue:

auto add5 = curry(add, 5);

Then, in the invocation of the curry function, you're creating a copy of that variable on the stack as one of the parameters:

auto curry(Function&& func, First first)

Then, in your call to curry_impl you pass a reference to the first that won't exist once your call to curry completes. As the lambda you're producing uses a reference to a variable that no longer exists, you get undefined behavior.

To fix the problem you're experiencing, simply change the prototype of curry to use a universal reference to first and make sure you don't pass rvalues to curry:

template<typename Function, typename First,
         typename Indices=indices_range<1, function_traits<Function>::arity>>
auto curry(Function&& func, First&& first)
    -> decltype(curry_impl(std::forward<Function>(func), std::forward<First>(first), Indices()))
{
    using FirstArg = typename function_traits<Function>::template argument_type<0>;
    static_assert(std::is_convertible<First, FirstArg>::value,
                  "the value to be tied should be convertible to the type of the function's first parameter");
    return curry_impl(std::forward<Function>(func), std::forward<First>(first), Indices());
}

Then in main:

int foo = 5;
auto add5 = curry(add, foo);

Of course, limiting yourself to lvalue expressions is a pretty huge problem with the interface, so it's worth mentioning that if you planned on utilizing this outside of an exercise, it would be a good idea to provide an interface where rvalues can be used.

Then again, I would change it so that the resulting functor owns copies of its components as std::bind does. I know I would be a little perplexed if the following code didn't work:

std::function<int(int)> foo()
{
    std::function<int(int, int)> add = [](int a, int b)
    {
        return a + b;
    };
    return curry(add, 5);
}

---

Edit: I see now that some versions of gcc still require the values to be captured by value into the resulting lamba. GCC 4.9.0 20131229 is the build I tested it on which works fine.

Edit #2: specified correct usage per Xeo