recursive lambda and capture (segfault)

Question

Compiler

g++ (Ubuntu 5.2.1-22ubuntu2) 5.2.1 20151010

Snippet 1 (& capture)

#include <functional>

int main()
{
  std::function<void ()> func = [&] () {
    func();
  };
  return 0;
}

Snippet 2 (func capture)

#include <functional>

int main()
{
  std::function<void ()> func = [func] () {
    func();
  };
  return 0;
}

Both snippets compile but why does running the second result in a segmentation fault?

Answer 1

Capture occurs before the construction of the std::function.

So you capture an uninitialized (not even default constructed!) copy of std::function<void()> func. All by itself the capture of the std::function is UB (copying a variable before it is constructed!), and invoking it is going to be even "more UB" (invoking a copy of a non-constructed std::function!).

The reference case captures a reference to func, which is allowed even before it is initialized, so long as it is only used once initialized.

The downside to the reference case is that the lambda only remains valid within the scope of func. A copy of it is also invalid once func goes out of scope. This, in my experience, sucks.

To do a real "full strength" recursive lambda, you need something like a y-combinator.

Here is short a C++14 y-combinator:

template<class F>
auto y_combinate( F&& f ) {
  return [f = std::forward<F>(f)](auto&&...args) {
    return f(f, decltype(args)(args)...);
  };
}

you pass it a lambda that expect a reference to itself as the first argument:

std::function<void ()> func = y_combinate( [](auto&& self) {
    self(self);
  }
);

and it does the rest.

The y-combinator requirement is because you don't have access to your own this within the body of a lambda. So we add one.

The above y-combinator is only 90%, as it doesn't handle r/l value and const-ness of the function object passed in perfectly. But it will serve most of the time.

This is a slightly better y-combinate:

template<class F>
struct y_combinate_t {
  F f;
  template<class...Args>
  decltype(auto) operator()(Args&&...args)const {
    return f(*this, std::forward<Args>(args)...);
  }
};
template<class F>
y_combinate_t<std::decay_t<F>> y_combinate( F&& f ) {
  return {std::forward<F>(f)};
}

which makes use a bit better:

std::function<void ()> func = y_combinate( [](auto&& self) {
    self();
  }
);

the self passed in now does not have to be passed self itself when invoked.