Can lambdas translate into functions?

Question

Common knowledge dictated that lambda functions are functors under the hood.

In this video (@ about 45:43) Bjarne says:

I mentioned that a lambda translates into a function object, or into a function if that's convenient

I can see how this is a compiler optimization (ie it doesn't change the perception of lambdas as unnamed functors which means that eg lambdas still won't overload) but are there any rules that specify when this is applicable?

Edit

The way I understand the term translate (and that's what I'm asking about) has nothing to do with conversion (I'm not asking whether lambdas are convertible to function ptr etc). By translate I mean "compile lambda expressions into functions instead of function objects".

As mentioned in cppreference : The lambda expression constructs an unnamed prvalue temporary object of unique unnamed non-union non-aggregate type, known as closure type.

The question is : can this object be ommited and have a plain function instead? If yes, then when and how?

---

^{Note: I imagine one such rule being "don't capture anything" but I can't find any reliable sources to confirm it}

Answer 1

TLDR: if you only use lambda to convert it to a function pointer (and only invoke it via that function pointer), it is always profitable to omit the closure object. Optimizations which enable this are inlining and dead code elimination. If you do use the lambda itself, it is still possible to optimize the closure away, but requires somewhat more aggressive interprocedural optimization.

I will now try to show how that works under the hood. I will use GCC in my examples, because I'm more familiar with it. Other compilers should do something similar.

Consider this code:

#include <stdio.h>

typedef int (* fnptr_t)(int);
void use_fnptr(fnptr_t fn)
{
    printf("fn=%p, fn(1)=%d\n", fn, fn(1));
}

int main()
{
    auto lam = [] (int x) { return x + 1; };
    use_fnptr((fnptr_t)lam);
}

Now, I compile it and dump intermediate representation (for versions prior to 6, you should add -std=c++11):

g++ test.cc -fdump-tree-ssa

A little cleaned-up and edited (for brevity) dump looks like this:

// _ZZ4mainENKUliE_clEi
main()::<lambda(int)> (const struct __lambda0 * const __closure, int x)
{
    return x_1(D) + 1;
}

// _ZZ4mainENUliE_4_FUNEi
static int main()::<lambda(int)>::_FUN(int) (int D.2780)
{
    return main()::<lambda(int)>::operator() (0B, _2(D));
}

// _ZZ4mainENKUliE_cvPFiiEEv
main()::<lambda(int)>::operator int (*)(int)() const (const struct __lambda0 * const this)
{
    return _FUN;
}

int main() ()
{
    struct __lambda0 lam;
    int (*<T5c1>) (int) _3;
    _3 = main()::<lambda(int)>::operator int (*)(int) (&lam);
    use_fnptr (_3);
}

That is, lambda has 2 member functions: function call operator and a conversion operator and one static member function _FUN, which simply invokes lambda with this set to zero. main calls the conversion operator and passes the result to use_fnptr - exactly as it is written in the source code.

I can write:

extern "C" int _ZZ4mainENKUliE_clEi(void *, int);

int main()
{
    auto lam = [] (int x) { return x + 1; };
    use_fnptr((fnptr_t)lam);
    printf("%d %d %d\n", lam(10), _ZZ4mainENKUliE_clEi(&lam, 11), __lambda0::_FUN(12));
    printf("%p %p\n", &__lambda0::_FUN, (fnptr_t)lam);
   return 0;
}

This program outputs:

fn=0x4005fc, fn(1)=2
11 12 13
0x4005fc 0x4005fc

Now, I think it's pretty obvious, that the compiler should inline lambda (_ZZ4mainENKUliE_clEi) into _FUN (_ZZ4mainENUliE_4_FUNEi), because _FUN is the only caller. And inline operator int (*)(int) into main (because this operator simply returns a constant). GCC does exactly this, when compiling with optimization (-O). You can check this like:

g++ test.cc -O -fdump-tree-einline

Dump file:

// Considering inline candidate main()::<lambda(int)>.
//   Inlining main()::<lambda(int)> into static int main():<lambda(int)>::_FUN(int).

static int main()::<lambda(int)>::_FUN(int) (int D.2822)
{
    return _2(D) + 1;
}

The closure object is gone. Now, a more complicated case, when lambda itself is used (not a function pointer). Consider:

#include <stdio.h>

#define PRINT(x)    printf("%d", (x))
#define PRINT1(x)   PRINT(x); PRINT(x); PRINT(x); PRINT(x);
#define PRINT2(x)   do { PRINT1(x) PRINT1(x) PRINT1(x) PRINT1(x) } while(0)

__attribute__((noinline)) void use_lambda(auto t)
{
    t(1);
}

int main()
{
    auto lam = [] (int x) { PRINT2(x); };
    use_lambda(lam);
    return 0;
}

GCC will not inline lambda, because it is rather huge (that is what I used printf's for):

g++ test2.cc -O2 -fdump-ipa-inline -fdump-tree-einline -fdump-tree-esra

Early inliner's dump:

Considering inline candidate main()::<lambda(int)>
  will not early inline: void use_lambda(auto:1) [with auto:1 = main()::<lambda(int)>]/16->main()::<lambda(int)>/19, growth 46 exceeds --param early-inlining-insns

But "early interprocedural scalar replacement of aggregates" pass will do what we want:

;; Function main()::<lambda(int)> (_ZZ4mainENKUliE_clEi, funcdef_no=14, decl_uid=2815, cgraph_uid=12, symbol_order=12)
IPA param adjustments: 0. base_index: 0 - __closure, base: __closure, remove_param
  1. base_index: 1 - x, base: x, copy_param

The first parameter (i.e., closure) is not used, and it gets removed. Unfortunately interprocedural SRA is not able to optimize away indirection, which is introduced for captured values (though there are cases when it would be obviously profitable), so there is still some room for enhancements.

Answer 2

From Lambda expressions §5.1.2 p6 (draft N4140)

The closure type for a non-generic lambda-expression with no lambda-capture has a public non-virtual non- explicit const conversion function to pointer to function with C ++ language linkage having the same parameter and return types as the closure type’s function call operator.

Answer 3

The standard quote has already been posted, I want to add some examples. You can assign lambdas to function pointers as long as there are no captured variables:

Legal:

int (*f)(int) = [] (int x) { return x + 1; };  // assign lambda to function pointer
int z = f(3);  // use the function pointer

Illegal:

int y = 5;
int (*g)(int) = [y] (int x) { return x + y; };  // error

Legal:

int y = 5;
int z = ([y] (int x) { return x + y; })(2);  // use lambda directly

---

(Edit)
Since we can not ask Bjarne what he meant exactly, I want to try a few interpretations.

"translate" meaning "convert"
This is what I understood initially, but it is clear now that the question is not about this possible meaning.

"translate" as used in the C++ standard, meaning "compile" (more or less)
As Sebastian Redl already commented, there are no function objects on the binary level. There is just opcodes and data, and the standard does not talk about, or specify, any binary formats.

"translate" meaning "being semantically equivalent"
This would imply that if A and B are semantically equivalent, the produced binary code for A and B could be the same. The rest of my answer uses this interpretation.

A closure consists of two parts:

• the statements in the lambda body, "code"
• the captured variable values or references, "data"

This is equivalent to a functor, as already stated in the question.

Functors can be seen as a subset of objects, because they have code and data, but only one member function: the call operator. So closures could be seen as semantically equivalent to a restricted form of objects.

A function on the other hand, has no data associated with it. There are the arguments of course, but these must be supplied by the caller and can change from one invocation to the other. This is a semantic difference to a closure, where the bound variables can not be changed and are not supplied by the caller.

A member function is not something independent, as it can not work without its object, so I think the question refers to a freestanding function.

So no, a lambda is in general not semantically equivalent to a function.

There is the obvious special case of a lambda with no captured variables, where the functor consists only of the code, and this is equivalent to a function.

But, a lambda could be said to be semantically equivalent to a set of functions. Each possible closure (distinct combination of values/references for the bound variables) would be equivalent to one function in that set. Of course this can only be useful when the bound variables can only have a very limited set of values / are references to only a few different variables, if at all.
For example I see no reason why a compiler could not treat the following two snippets as (almost*) equivalent:

void Test(bool cond, int x)
{
    int y;
    if(cond) y = 5;
    else y = 3;
    auto f = [y](int x) { return x + y; };
    // more code that
    // uses f
}

A clever compiler could see that y can only have the values 5 or 3, and compile as if it would be written like this:

int F1(int x)
{
    return x + 5;
}

int F2(int x)
{
    return x + 3;
}

void Test(bool cond, int x)
{
    int (*f)(int);
    if(cond) f = F1;
    else f = F2;
    // more code that
    // uses f
}

(*) Of course it depends on what more code that uses f does exactly.

Another (maybe better) example would be a lambda that always binds the same variable by reference. Then, there is only one possible closure, and so it is equivalent to a function, if the function has access to that variable by other means than by passing it as an argument.

---

Another observation that might be helpful is that asking

can this object [closure] be ommited and have a plain function instead? If yes, then when and how?

is more or less the same as asking when and how a member function can be used without the object. Since lambdas are functors, and functors are objects, the two questions are closely related. The bound variables of the lambda correspond to the data members of the object, and the lambda body corresponds to the body of the member function.

Answer 4

To give another kind of insight, let have a look to the code produced by clang when compiling the following snippet:

int (*f) = []() { return 0; }

If you compile this with:

clang++ -std=c++11 -S -o- -emit-llvm a.cc

You get the following LLVM bytecode for the lambda definition:

define internal i32 @"_ZNK3$_0clEv"(%class.anon* %this) #0 align 2 {
  %1 = alloca %class.anon*, align 8
  store %class.anon* %this, %class.anon** %1, align 8
  %2 = load %class.anon** %1
  ret i32 0
}

define internal i32 @"_ZN3$_08__invokeEv"() #1 align 2 {
  %1 = call i32 @"_ZNK3$_0clEv"(%class.anon* undef)
  ret i32 %1
}

The first function takes an instance of %class.anon* and return 0: that's the call operator. The second creates an instance of this class (undef) and then call its call operator and return the value.

When compiled with -O2, the whole lambda is turned into:

define internal i32 @"_ZN3$_08__invokeEv"() #0 align 2 {
  ret i32 0
}

So that's a single function that returns 0.

I mentioned that a lambda translates into a function object, or into a function if that's convenient

That's exactly what clang does! It transforms the lambda into a function object, and when possible optimize it to a function.

Answer 5

No, it can't be done. Lambdas are defined to be functors, and I don't see the as-if rule helping here.

[C++14: 5.1.2/6]: The closure type for a non-generic lambda-expression with no lambda-capture has a public non-virtual non-explicit const conversion function to pointer to function with C++ language linkage (7.5) having the same parameter and return types as the closure type’s function call operator. [..]

…followed by similar wording for generic lambdas.