9

This question comes from Can lambda functions be recursive? . The accepted answer says the recursive lambda function shown below works.

std::function<int (int)> factorial = [&] (int i) 
{ 
    return (i == 1) ? 1 : i * factorial(i - 1); 
};

However, it is pointed out by a comment that

such a function cannot be returned safely

, and the reason is supplied in this comment:

returning it destroys the local variable, and the function has a reference to that local variable.

I don't understand the reason. As far as I know, capturing variables is equivalent to retaining them as data members (by-value or by-reference according to the capture list). So what is "local variable" in this context? Also, the code below compiles and works correctly even with -Wall -Wextra -std=c++11 option on g++ 7.4.0.

#include <iostream>
#include <functional>

int main() {

    std::function<int (int)> factorial = [&factorial] (int i)
    {
        return (i == 1) ? 1 : i * factorial(i - 1);
    };

    std::cout << factorial(5) << "\n";

}

Why is the function unsafe? Is this problem limited to this function, or lambda expression as a whole?

ynn
  • 3,386
  • 2
  • 19
  • 42
  • 7
    I think the comment means you can't return it from a function. So if you can't have `std::function foo();` return your `factorial`. `factorial` would be a local variable in `foo()` and your returned function object would have a reference to it. – François Andrieux Aug 19 '19 at 17:28
  • 2
    See [this](http://coliru.stacked-crooked.com/a/115d92bd28f209dd). It could blow up, it could work. All we know for sure is it is UB. – NathanOliver Aug 19 '19 at 17:30
  • https://en.cppreference.com/w/cpp/language/ub – Jesper Juhl Aug 19 '19 at 17:33
  • Possible duplicate of [C++ Returning reference to local variable](https://stackoverflow.com/questions/4643713/c-returning-reference-to-local-variable) (the root cause is the same) – L. F. Aug 19 '19 at 17:37
  • @FrançoisAndrieux Thank you. Now I understand what does the comment want to say. I should have been careful enough not to misread "be returned" as "return". – ynn Aug 19 '19 at 17:39
  • @L.F. I admit the root cause is the same, but my question is rather about the interpretation of the comment. Actually I know a reference to a variable out of scope results in UB... – ynn Aug 19 '19 at 17:46
  • @ynn Yeah, technically speaking your code is indeed returning a reference to local variable (as a data member of a closure type) – L. F. Aug 19 '19 at 17:46
  • @L.F. Yes, but not out of scope. So my code is not ill-formed, I think. (I misunderstood the cited comment to mean codes like mine is unsafe. Because I'm not really familiar with lambda expression, I suspected that there would be non-trivial structure which is unsafe, so I posted my question.) – ynn Aug 19 '19 at 17:53
  • 2
    @ynn The example you show in your question has well defined behavior. – François Andrieux Aug 19 '19 at 17:53
  • @ynn Your code is perfectly fine, but since you appear to be asking about the comment, I suggested that dupe. – L. F. Aug 19 '19 at 17:54
  • @L.F. I thought "A is a duplicate of B" meant "A is relatively directly related to B, and A can be solved just by reading B". So I didn't agree with you. But the "duplicate suggestion" in this website is not so strict, maybe? – ynn Aug 19 '19 at 17:58

1 Answers1

9

This is because in order to be recursive, it uses type erasure and captures the type erased container by reference.

This has the effect of allowing to use the lambda inside itself, by refering to it indirectly using the std::function.

However, for it to work, it must capture the std::function by reference, and that object has automatic storage duration.

Your lambda contains a reference to a local std::function. Even if you return the std::function by copy, the lambda will still refer to the old one, that died.

To make a secure to return recursive lambda, you can send the lambda to itself in an auto parameter and wrap that in another lambda:

auto factorial = [](auto self, int i) -> int { 
    return (i == 1) ? 1 : i * self(self, i - 1); 
};

return [factorial](int i) { return factorial(factorial, i); };
Guillaume Racicot
  • 39,621
  • 9
  • 77
  • 141