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