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());
}

Helico

Can't you just solve it with std::bind for the currying part? Like auto add5 = std::bind(add, _1, 5);? – Williemaewillies

@JoachimPileborg It gives compiler errors. It seems that function_traits does not work for bind expressions; the reason would be that a bind expression has several overloads of operator(). – Helico

return [&] That looks highly suspicious. Such lambdas can be implemented by storing a pointer to EBP, instead of a reference to each captured entity. Are you sure you don't get lifetime issues with that? – Jerrodjerrol

In fact, if I replace the [&] with a [=] and the forwarding with moving, clang++ also prints 25. – Jerrodjerrol

@Jerrodjerrol Suspicious [&] is actually the reason I asked the question. If there is problem, it has to be with lifetime. – Helico

See https://mcmap.net/q/162785/-capturing-a-reference-by-reference-in-a-c-11-lambda/420683 – Jerrodjerrol

auto curry(Function&& func, First first) is taking first by value, and then tries to std::forward it. – Jerrodjerrol

I think you have to copy the arguments to curry at least once, so that the resulting std::function owns the arguments. Currently, there's a copy (because curry takes by value), but no copy ends up in the resulting std::function -- this means that std::forwarding the arguments makes no sense. In functional programming, there are no side effects (AFAIK), so move semantics itself should not be applied (otherwise, you can't apply that function object twice, e.g.). – Jerrodjerrol

@Jerrodjerrol You're right about the value forwarding. Seems like I forgot a && when writing it. – Helico

:D Fix that and try again with g++ – Jerrodjerrol

@If I only fix the && (and not the [&] -> [=]), I get 25 with clang++ but not the expected result with g++ 4.8.2. – Helico

I think @Jerrodjerrol may have it. In MSVC12, I can only get the expected result if I do one of two things: 1) modify curry to take an r-value reference to first, or 2) modify the lambda in curry_impl to capture first by-value instead of by-reference. – Mikey

@Jerrodjerrol Ok, if I fix the && and then take first by value in the capture and move it, it seems to work with g++ 4.8.2 and clang++ 3.5. – Helico

Yes, I think that's pretty much the fix to this specific problem, but I'm not sure if the use of move semantics here is appropriate (as I said). Consider apply or any other function that takes a function F and applies it to the elements of a list: F is called multiple times; if F is the result of curry, you might end up moving from the same objects several times. – Jerrodjerrol

@Jerrodjerrol Right. It also works if I simply gives first to func without any move. That may prevent the problem. – Helico

Interesting question. I tried another approach using variadic polymorphic functors (can be polymorphic lambda in C++14) and it simplifies implementation a bit as you don't have to care about argument types and indices. Also it supports currying and composition of polymorphic functors/lambdas as well. – Ami

@apoorvkul Yes. I intended to simplify that madness after the standardization of C++14 was approved :) – Helico

For what it's worth, I got 123523348 with clang-3.5 compiling in c++11 mode, 200753444 with c++14. Looks to me like a fun bug. – Phosphorite

Well, actually it's not that helpful at all. I get different answers every time I run it. Non-deterministic programs with no input and no random calls. Nice.. – Phosphorite

@Phosphorite If that doesn't tell you that you're using dangling pointers/references, I don't know what else would. I think this question is just an obfuscation of very basic snafus. The whole currying thing is just a good pretense :) – Hatter

What you are doing is not called 'currying'. It's called 'partial application' and can already be done with std::bind. Currying would allow your add lambda to be called like add(5)(10), i.e. make it take one argument and return a new callable. – Nun

@Nun Note that, as Joachim mentioned, using std::bind doesn't work when the resulting function needs to be used with his compose function. This is due to limitations in template deduction. – Phosphorite

@vmrob: No, this is due to a limitation in the compose function presented here, as it (wrongfully) inspects the input's argument / result types and uses std::function. :) To Morwenn: Note how the implementation of std.functional (linked to in the documentation) has changed the curry function to partial, with a deprecated version of curry for backwards compatibility. – Nun

@Nun My apologies, I'm not at all familiar with the D language. – Phosphorite

@Nun Good catch. That's kind of fun. – Helico

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

Phosphorite

Changing the parameter to a universal reference doesn't fix the lifetime bug. The passed argument (the 5 in your foo) only lives until the end of the return expression, and is still captured by reference in the resulting lambda. This 'fixed' code only works if you pass an lvalue that lives longer than the resulting lambda. – Nun

@Nun I don't know what I was thinking about the 5 literal being an lvalue. Editted to reflect that. I'll bet this appears to fix the problem only because it's a constant. The correct code would have to change to initialize another variable to 5, then pass that to curry. Not a good usage at all. – Phosphorite

Good, I see where I got confused. Also, I got confused the cases when references collapsing happens and when it does not. No wonder it does not work in the end... – Helico

I agree you should use copy-by-default as in the Standard Library functional parts. Then, you can opt-in to reference semantics by using something like std::ref/std::cref. IMO, this leads to less error prone code, since you can only get the lifetime issues if you explicitly use std::ref etc. – Jerrodjerrol