Recursive lambda callbacks without Y Combinator

Question

I want to create a callback that recursively returns itself as a callback.

The proposed recursion method is a function to have a reference to itself:

std::function<void (int)> recursive_function = [&] (int recurse) { std::cout << recurse << std::endl; if (recurse > 0) { recursive_function(recurse - 1); } }; 

This does not work as soon as you return it from a function:

 #include <functional> #include <iostream> volatile bool no_optimize = true; std::function<void (int)> get_recursive_function() { std::function<void (int)> recursive_function = [&] (int recurse) { std::cout << recurse << std::endl; if (recurse > 0) { recursive_function(recurse - 1); } }; if (no_optimize) { return recursive_function; } return [] (int) {}; } int main(int, char **) { get_recursive_function()(10); } 

which gives a segmentation error after pin 10 , because the link becomes invalid.

How should I do it? I have successfully used what I consider Y Combinator (which I will post as an answer), but it is very confusing. Is there a better way?

---

Other attempts

I tried a boring approach wrapping it in another layer of callbacks:

 #include <functional> #include <iostream> #include <memory> volatile bool no_optimize = true; std::function<void (int)> get_recursive_function() { // Closure to allow self-reference auto recursive_function = [] (int recurse) { // Actual function that does the work. std::function<void (int)> function = [&] (int recurse) { std::cout << recurse << std::endl; if (recurse > 0) { function(recurse - 1); } }; function(recurse); }; if (no_optimize) { return recursive_function; } return [] (int) {}; } int main(int, char **) { get_recursive_function()(10); } 

but this does not work in a real scenario where the function is delayed and called by the outer loop:

 #include <functional> #include <iostream> #include <memory> #include <queue> volatile bool no_optimize = true; std::queue<std::function<void (void)>> callbacks; std::function<void (int)> get_recursive_function() { // Closure to allow self-reference auto recursive_function = [] (int recurse) { // Actual function that does the work. std::function<void (int)> function = [&] (int recurse) { std::cout << recurse << std::endl; if (recurse > 0) { callbacks.push(std::bind(function, recurse - 1)); } }; function(recurse); }; if (no_optimize) { return recursive_function; } return [] (int) {}; } int main(int, char **) { callbacks.push(std::bind(get_recursive_function(), 10)); while (!callbacks.empty()) { callbacks.front()(); callbacks.pop(); } } 

which gives 10 , then 9 , and then segmentation errors.

Answer 1

As you pointed out correctly, there is an invalid link from the lambda capture [&] .

Your returns are functors of all kinds, so I assume that the exact type of return does not matter, simply because it behaves like a function if it were callable.

If recursive_function wrapped in a struct or class , you can map the call statement to the recursive_function element. There is a problem capturing the this variable. It will be captured using this at creation, so if the object is copied bit by bit, the original this may not be valid. Thus, the corresponding this can be passed to the function at run time (this this problem may not be a problem, but it depends a lot on when and how you call this function).

 #include <functional> #include <iostream> volatile bool no_optimize = true; struct recursive { std::function<void (recursive*, int)> recursive_function = [] (recursive* me, int recurse) { std::cout << recurse << std::endl; if (recurse > 0) { me->recursive_function(me, recurse - 1); } }; void operator()(int n) { if (no_optimize) { recursive_function(this, n); } } }; recursive get_recursive_function() { return recursive(); } int main(int, char **) { get_recursive_function()(10); } 

Alternatively, if recursive_function can be static , then declaring it as such in the source code sample can also do the trick for you.

I wanted to add some generality to the answer above, i.e. make it a template;

 #include <functional> #include <iostream> volatile bool no_optimize = true; template <typename Signature> struct recursive; template <typename R, typename... Args> struct recursive<R (Args...)> { std::function<R (recursive const&, Args... args)> recursive_function; recursive() = default; recursive(decltype(recursive_function) const& func) : recursive_function(func) { } template <typename... T> R operator()(T&&... args) const { return recursive_function(*this, std::forward<Args>(args)...); } }; recursive<void (int)> get_recursive_function() { using result_type = recursive<void (int)>; if (!no_optimize) { return result_type(); } result_type result ([](result_type const& me, int a) { std::cout << a << std::endl; if (a > 0) { me(a - 1); } }); return result; } int main(int, char **) { get_recursive_function()(10); } 

How it works? Basically, it moves recursion from within the function (i.e., calls itself) to the object (i.e., the Function Operator on the object itself) to implement recursion. In get_recursive_function , the result type recursive<void (int)> used as the first argument to the recursive function. This is const& , because I implemented operator() as const according to most standard algorithms and the default for a lambda function. This requires some “collaboration” with the function executor (i.e., using the me parameter, which is *this ) to get recursion, but for this price you get a recursive lambda that is not dependent on the stack link.

Answer 2

All programming problems can be solved with another layer of indirection, with the exception of too many layers of indirection.

My goal is to create a recursive<void(int)> that will allow you to easily create a recursive lambda. To do this, you pass a lambda with the signature void(recursive<void(int)>, int) - the first argument is what you call to make the recursive call.

Then I will bind it in the nodes and make it a fully recursive function with the signature void(int) .

Here is my recursive<Signature> implementation:

 template<class Sig> struct recursive; template<class R, class... As> struct recursive< R(As...) > { using base_type = std::function<R(recursive, As...)>; private: std::shared_ptr< base_type > base; public: template<typename...Ts> auto operator()(Ts&&... ts) const -> typename std::result_of< base_type( recursive, Ts... ) >::type { return (*base)(*this, std::forward<Ts>(ts)...); } recursive(recursive const&)=default; recursive(recursive&&)=default; recursive& operator=(recursive const&)=default; recursive& operator=(recursive &&)=default; recursive() = default; template<typename L, typename=typename std::result_of< L(recursive, As...) >::type> explicit recursive( L&& f ): base( std::make_shared<base_type>(std::forward<L>(f))) {} explicit operator bool() const { return base && *base; } }; 

That is, admittedly, quite difficult. I did a bunch of things to make it more efficient, such an ideal shipment. In addition, unlike std::function , double checks that the type of lambda passing on it matches the signature that it wants.

I believe, but did not confirm that I made it friendly to make the signature lambdas void(auto&&,int) . Does anyone know a fully compatible C ++ 1y online compiler?

The above is just a template. What matters is how it looks in terms of use:

 std::function<void (int)> get_recursive_function() { auto f = [] (recursive<void(int)> self, int recurse) { std::cout << recurse << std::endl; if (recurse > 0) { self(recurse - 1); } }; return recursive< void(int) >( f ); }; 

Here we use the popular auto f = lambda syntax. No need to directly store it in std::function .

Then we explicitly apply it to recursive<void(int)> , which binds it in nodes and removes the recursive<void(int)> argument in f from the front and provides the signature void(int) .

This requires your lambda to take recursive<void(int)> self as its first parameter and do the recursion through it, but that doesn't seem harsh. If I wrote it just to the right , it could work with auto&& self as the first parameter, but I'm not sure.

recursive<?> works for any signature, naturally.

living example

And, with delayed calls in the outer loop , it still works. Please note that I got rid of this global variable (it will work with it as a global variable, it just feels dirty to leave it).

In C ++ 1y, we can eliminate type erasure and shared_ptr overhead that you see above (with the recursive a shared_ptr<function<?>> object). You need to provide a return value since I cannot get result_of to unravel my mess:

 struct wrap {}; template<class R, class F> struct recursive { using base_type = F; private: F base; public: template<class... Ts> R operator()(Ts&&... ts) const { return (*base)(*this, std::forward<Ts>(ts)...); } recursive(recursive const&)=default; recursive(recursive&&)=default; recursive& operator=(recursive const&)=default; recursive& operator=(recursive &&)=default; recursive() = delete; template<typename L> recursive( wrap, L&& f ): base( std::forward<L>(f) ) {} }; template<class T>using decay_t = typename std::decay<T>::type; template<class R, class F> recursive<R, decay_t<F>> recurse( F&& f ) { return recursive<R, decay_t<F>>(wrap{}, std::forward<F>(f)); } 

Then the get_recursive_function implementation is a little different (where I added some state for fun):

 std::function<void (int)> get_recursive_function(int amt) { auto f = [amt] (auto&& self, int count) { std::cout << count << std::endl; if (count > 0) { self(count - amt); } }; return recurse<void>( std::move(f) ); }; int main() { auto f = get_recursive_function(2); f(10); } 

using std::function in the return value of get_recursive_function is optional - you can use auto in C ++ 1y. There is still some overhead compared to the ideal version (where the lambda can access its own operator() ) because operator() probably doesn't know that it is called recursively on the same object when it calls self .

It would be tempting to allow operator()( blah ) inside the body of a lambda to allow a recursive call to lambda. This will probably be very little code.

Answer 3

My current workaround, which is unfortunately complicated, is:

 #include <functional> #include <iostream> #include <queue> volatile bool no_optimize = true; std::queue<std::function<void (void)>> callbacks; 

(I think this is Y Combinator , but I'm not sure.)

 std::function<void (int)> y_combinator( std::function<void (std::function<void (int)>, int)> almost_recursive_function ) { auto bound_almost_recursive_function = [almost_recursive_function] (int input) { y_combinator(almost_recursive_function)(input); }; return [almost_recursive_function, bound_almost_recursive_function] (int input) { almost_recursive_function(bound_almost_recursive_function, input); }; } 

This is a basic function; he does not call himself, but the argument that he conveyed. This argument should be the most recursive function.

 std::function<void (std::function<void (int)>, int)> get_almost_recursive_function() { auto almost_recursive_function = ( [] (std::function<void (int)> bound_self, int recurse) { std::cout << recurse << std::endl; if (recurse > 0) { callbacks.push(std::bind(bound_self, recurse - 1)); } } ); if (no_optimize) { return almost_recursive_function; } return [] (std::function<void (int)>, int) {}; } 

Thus, the desired function can be performed by applying a combinator to an almost recursive function.

 std::function<void (int)> get_recursive_function() { return y_combinator(get_almost_recursive_function()); } 

When main is executed, it outputs 10 , 9 , ..., 0 , as you need.

 int main(int, char **) { callbacks.push(std::bind(get_recursive_function(), 10)); while (!callbacks.empty()) { callbacks.front()(); callbacks.pop(); } } 

Answer 4

Since you are already dealing with std::function , which adds a bit of overhead everywhere, you can add a memory preservation that will add indirection to the calling site only with unique_ptr :

 std::unique_ptr<std::function<void (int)>> CreateRecursiveFunction() { auto result = std::make_unique<std::function<void (int)>>(); auto ptr = result.get(); *result = [ptr] (int recurse) { // c++1y can also capture a reference to the std::function directly [&func = *result] std::cout << recurse << std::endl; if (recurse > 0) { (*ptr)(recurse - 1); // with c++1y func( recurse - 1 ) } }; return result; }