18

Possible Duplicate:
Recursive lambda functions in c++0x

Why can't I call a lambda recursively if I write it as:

auto a = [&]
{ 
   static int i = 0; i++;
   std::cout << i << std::endl; 
   if (i<10) 
     a(); //recursive call
};

It gives compilation error (ideone):

prog.cpp:8:18: error: '((const main()::<lambda()>*)this)->main()::<lambda()>::a' cannot be used as a function

prog.cpp: In function 'int main()':
prog.cpp:9:9: error: variable 'auto a' with 'auto' type used in its own initializer

What does the error mean?

I understand the reason why I can't write this:

auto i=i+1; //error: unable to deduce 'auto' from '<expression error>'

We can't write this because the type of i has to be deduced from it's initialization, which means the type cannot be deduced if i itself appears in the initialization (ideone). But how does it matter in case of lambda? If I'm not wrong, the type of a lambda is determined by it's parameter(s) and the return type; it doesn't depend on the body if it returns nothing (in which case, the return type is deduced as void, irrespective of other statements in the lambda-body).

Anyway, I got a workaround, and I can use std::function instead as:

std::function<void()> a = [&] 
{ 
   static int i = 0; i++;
   std::cout << i << std::endl; 
   if (i<10) 
      a();
};

which compile fines (ideone). But I'm still interested to know the reason why the auto version doesn't compile.

Community
  • 1
  • 1
Nawaz
  • 353,942
  • 115
  • 666
  • 851
  • I think the problem is related to you ending up with an implicit capture of `a`, as a reference which would recurse infinitely because `a` itself ends up as a member of `a`. – Flexo Oct 22 '11 at 18:02
  • @awoodland: What does that mean? Please elaborate on that. – Nawaz Oct 22 '11 at 18:04
  • 3
    The type of the lambda also depends on the captures, which I suspect is the issue here. If you don't use `a` then the compiler doesn't care, but when you do it doesn't know what type of object to use. – Dennis Zickefoose Oct 22 '11 at 18:06
  • The theoretical CS textbook way to recursive lambdas is passing the function to itself as a parameter. – Patrick Oct 22 '11 at 18:09
  • @DennisZickefoose: I didn't understand this part of your comment >> `but when you do it doesn't know what type of object to use.` Why does it know then? – Nawaz Oct 22 '11 at 18:15
  • 2
    I don't think that the type of a lambda expression needs to depend on its parameters, return type or its captures. Recall that a lambda expression's type is just a class type. `struct internal_lambda_object0;` is the type `internal_lambda_object0` independent of what member functions or data members it has. – Johannes Schaub - litb Oct 22 '11 at 18:16
  • 2
    @Johannes: please, put a `__` in that name somewhere ;-) – Steve Jessop Oct 22 '11 at 18:31

3 Answers3

15

The reason is that there is no special case for lambda-expression initializers of auto variables.

Such special cases would be prone to errors and misuses. You need to define the rules when you propose that something like a() should work. How is the operator() looked up? What is the precise state of a's type? Will the type be complete? (which implies that you already know the capture list of the lambda). Once you have formulated that in a format reasonable for a spec, it would be easier to make statements on it.

Allowing your use case would mean yet another case where you need to scan ahead in code, because to determine the type of a in a() you must be sure that the initializer ends with nothing that could "unlambda" the type

struct y { void operator()() { } };
template<typename T> y operator+(T, y) { return y(); }
auto x = [] { x(); } + y();

In this case, x() would call y::operator(), not the lambda.

As it is now, a is simply forbidden to be mentioned in its entire initializer. Because in C++, auto is not a type. It is merely a type specifier standing for a to-be-deduced type. As a consequence, an expression can never have type auto.

Johannes Schaub - litb
  • 496,577
  • 130
  • 894
  • 1,212
  • 3
    "If you capture a by reference, then you will call a danging reference once you copy your lambda and the original a goes out of scope." - of course, all capture-by-reference is prone to this error/misuse, so I doubt that it motivates the committee in not providing a special case to allow `auto a` here to be captured by reference. – Steve Jessop Oct 22 '11 at 18:34
  • Together with the problem of capturing `a`, another reason that it's not possible to recursively call the closure is that there is otherwise no way to refer to that closure object: `this` designates the enclosing class object, if any. – Luc Danton Oct 23 '11 at 04:14
6

As I see it the important difference between the auto a case and the std::function<void()> a case is that the type std::function<void()> doesn't know/care about what the type of the real function it refers to really is. Writing:

std::function<void()> a;

is perfectly fine, where as:

auto a;

makes little sense. So when the time comes to synthesize the capture if you use std::function<void()> all that needs to be known about the type is already known, whereas with auto it's not yet known.

BenMorel
  • 34,448
  • 50
  • 182
  • 322
Flexo
  • 87,323
  • 22
  • 191
  • 272
  • 2
    I believe this is the correct answer, and that if you were able to know the name of the lambda type generated by the compiler (which you cannot), then you could use that name in the decl instead of `auto`. However, I could easily see this being in the "undefined behavior" category. – Michael Price Oct 22 '11 at 18:29
  • @MichaelPrice - I did try to dig out the quote on "you can never know the name of the type of a lambda" for this answer but I can't remember which section it was in. – Flexo Oct 22 '11 at 18:32
2

In a recursive function f is defined by f and return type of f is also determined by f in case of auto so it leads to infinite recursion.

when auto tries to derive a type. decltype(f()) will further deduce to another decltype(f)` as f derives to f e.g. a call on anything recursive is recursive too. return type determination turns recursive when applied on a recursive function. in a recursive function end of the recursion may be done on runtime. but determination is static only

Neel Basu
  • 12,638
  • 12
  • 82
  • 146
  • 1
    @Neel: This doesn't make sense to me. When there is no return statement in the body, how can it return anything? Are you implying that `deep recursive level` means that lambda-body is infinitely large that it can't know the existence or non-existence of return statement(s)? – Nawaz Oct 22 '11 at 18:27
  • @awoodland: Thanks, I'vent looked at the comments yet. @Nawaz: In every function there exist a mathematical possibility to return something syntactic scanning for `return` syntax for visualization only. – Neel Basu Oct 22 '11 at 18:32
  • 3
    +1 for picture appropriateness – Dennis Zickefoose Oct 22 '11 at 18:34
  • 1
    @Neel: I still didn't understand it. Anyway, what I mean is that the recursive call doesn't increase or decrease the possibility of return statement(s). Return statement(s) can be statically determined. (By the way, I didn't downvote your answer). – Nawaz Oct 22 '11 at 18:38
  • assume `determineReturnType(f)` determines return type of `f` so `determineReturnType(f)` will further derive to determineReturnType(f)` as `f` derives to `f` e.g. a call on anything recursive is recursive too. return type determination turns recursive when applied on a recursive function. in a recursive function end of the recursion may be done on runtime. but determination is static only. – Neel Basu Oct 22 '11 at 18:42
  • 3
    A mathematical analysis of the function is unnecessary here... the C++ language has very explicit rules about deducing return types, and one of them is that if there is no `return` statement the result is `void`. What else happens in the function is immaterial. – Dennis Zickefoose Oct 22 '11 at 18:53