43

Is this lambda recursion valid?

#include <functional>
#include <iostream>

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

   std::cout << g(10); // 3628800
}

It appears to compile and run ok, but I'm nervous about closing over g in the same statement that I initialise it. Strict validity on a scale of 1-10...?

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
  • In C#, that wouldn't compile; you'd need to break it into two statements. – SLaks Dec 21 '11 at 19:19
  • 3
    C++0x examples [here](http://zamjad.wordpress.com/2011/09/22/c-recursive-lambda-functions/) break it into 2 statements, but never explains why. – Joe Dec 21 '11 at 19:20
  • I think it's undefined behaviour. Lambdas aren't designed to recursion cause it's a anonymous function, am I right? – Hauleth Dec 21 '11 at 19:33
  • @Hauleth: I have a name for it (`g`), but I don't know when the reference is formed and thus whether it's bound to a valid `std::function` object. – Lightness Races in Orbit Dec 21 '11 at 19:38
  • 3
    Well `g` has been declared before the initialiser, and I'm pretty sure it's valid to take a reference to a declared but uninitialised object, in which case this is fine. I'll see if I can find some Standardese to back that up. – Mike Seymour Dec 21 '11 at 19:45
  • Yeah, I know you named it, but I'm asking for general purposes. IMHO it's kind of weird way to use lambdas cause `g` is empty while U are trying to use it. – Hauleth Dec 21 '11 at 19:46
  • @MikeSeymour: That's my gut feeling too, but I'm finding it completely unspecified. Actually, I can't find: (a) when the closure is formed, _or_ (b) rules about references here. http://stackoverflow.com/questions/6189096/standard-reference-for-int-foo-foo is similar but we need a new question about `int foo(int& y) { return 0; } int x = foo(x);` I think, to serve as a basis for this question! Unless we can prove that lambdas do late binding and thus it'd be irrelevant.. – Lightness Races in Orbit Dec 21 '11 at 19:48
  • 1
    @SLaks: It would also not compile in java, where is the point? – PlasmaHH Dec 21 '11 at 19:59
  • @PlasmaHH: AFAIK, the Java equivalent (final variable with local inner class) would compile. – SLaks Dec 21 '11 at 20:08
  • @SLaks: So would the C# equivalent (that is, two statements). So where is the point in that C++ code does not compile as C#? How does it provide any insight into the issue? – PlasmaHH Dec 21 '11 at 20:27
  • 1
    @PlasmaHH: He's just making a side comment for comparison; where in C++ I had to ask this question, in C# the syntax prohibits the issue coming up. It's interesting. – Lightness Races in Orbit Dec 21 '11 at 20:30
  • @PlasmaHH: In Java, I don't think you need two statements. In C++, you do not need two statements. In C#, you do. See http://stackoverflow.com/questions/5488015/does-anonymous-recursion-work-in-net-it-does-in-mono – SLaks Dec 21 '11 at 20:30
  • 1
    If that wasn't allowed, we might try to pass the lambda to itself as a parameter. Any ideas how to make this work: `auto fact = [](??? g, int k) { return (k ? k * g(k-1) : 1); };` What's the type of g? Then we'd call it with `fact(fact,5)` to get the factorial of 5. Is there any hope? – Aaron McDaid Dec 21 '11 at 20:48
  • 2
    @AaronMcDaid: You're trying to invent the [Y Combinator](http://en.wikipedia.org/wiki/Fixed-point_combinator). Functional programming is lots of fun. – SLaks Dec 21 '11 at 21:04
  • @SLaks. Indeed. I'd have mentioned that if comments allowed more space :-) I program mostly in C++ and a little in Haskell. I'm hoping to use more Haskell-type ideas in due course in my C++. I think C++ needs a garbage collector before I can start porting all the Haskell libraries into C++ ! – Aaron McDaid Dec 21 '11 at 21:17
  • @AaronMcDaid: Just use C#; it's the best of both worlds. Or F#. – SLaks Dec 21 '11 at 21:28
  • 1
    @AaronMcDaid : See [Boost.Phoenix](http://www.boost.org/libs/phoenix/) if you're not familiar with it already. – ildjarn Dec 21 '11 at 21:43
  • @SLaks, I've considered that many times (including F#) over the years. But I'm a Linux user. I'm aware of Mono and so on, but I'm not quite ready to make the leap from the comfort of g++ (and ghc for Haskell) – Aaron McDaid Dec 21 '11 at 21:46
  • @ildjarn , Phoenix is back onto my todo list (again). After the holidays maybe! – Aaron McDaid Dec 21 '11 at 21:53
  • 2
    @Downvoter: Why's that, then? – Lightness Races in Orbit Dec 22 '11 at 19:49

1 Answers1

22

At the point at which you capture g by reference, it has been declared, so the name is available for use:

3.3.2/1 The point of declaration for a name is immediately after its complete declarator (Clause 8) and before its initializer

You are allowed to use objects in limited ways before they are initialised - basically, anything that doesn't depend on the value is OK:

3.8/6 before the lifetime of an object has started but after the storage which the object will occupy has been allocated [...] any glvalue that refers to the original object may be used but only in limited ways. [...] using the properties of the glvalue that do not depend on its value is well-defined.

So by my understanding, what you are doing is well-defined.

(Although, being ultrapedantic, I don't think it's specified when the storage for an automatic object is allocated, and 8.3.2/5 says that "a reference shall be initialized to refer to a valid object" without defining "valid", so there's scope to argue that it's not well-defined).

Mike Seymour
  • 249,747
  • 28
  • 448
  • 644
  • I'd agree that binding a reference shouldn't necessitate an lvalue-to-rvalue conversion, but the language's semantics in this area are _very_ hard to interpret. :( Even for C++! – Lightness Races in Orbit Dec 21 '11 at 19:59
  • OK, I think this satisfies me! – Lightness Races in Orbit Dec 21 '11 at 20:06
  • 1
    I was just about to post this :P Like any function definition, the code isn't executed right then; `g` does not need a value for the same reason `k` does not need a value, from the perspective of the definition. `g` is being used with `[&g]`, but that's only taking the address of the future function. And `g` exists at that point because the declarations happens before the assignment. – Christopher Neylan Dec 21 '11 at 20:10
  • @user112358132134: Forming a pointer is not identical to binding a reference, the object is under construction and thus has some potentially complex semantics, and the point at which the lambda contents are executed is not relevant. And there's no assignment here. – Lightness Races in Orbit Dec 21 '11 at 20:12
  • 1
    @user112358132134 Although by intuition you might be correct, you might also see that we are moving in strict language lawyer territory here, where a reference doesn't need to be implemented like pointer and where practically working UB is still UB. – Christian Rau Dec 21 '11 at 22:48
  • 3
    It would be worth pointing out that this would not be legal if (as is usually recommended for lambdas) you declare the type of `fact` as `auto`: an `auto` variable cannot be used in its own initializer. – Richard Smith Jan 02 '12 at 19:14
  • @ChristopherNeylan: yes, as you said, it works _because_ it is a std::function; if std::function is replaced with auto (making g a 'pure' lambda) it will fail – slashmais Apr 01 '18 at 09:29