Rendered at 22:43:52 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
alexey-salmin 1 days ago [-]
This article somehow omits the 80% of both the complexity and the benefits of the GCC nested functions which makes them pointless. Namely you can cast them to function pointers and pass them e.g. as a comparator to the sort() routine. Substituting the right parent frame parameter at the time the nested function is called down the stack is tricky and requires either an explicit support in the ABI (ia-64) or an executable stack to build a trampoline or a special logic to wrap function pointers with a special but set [1].
Without all this nested functions are as useful as the "rewritten" examples in the article, one can easily do that by hand without any compiler or language support.
This problem doesn't arise with C++ lambdas because you pass them around as special objects, not as bare function pointers.
There are many language features can be rewritten by hand into other simpler forms, you could rewrite loops into gotos, C++ objects into structures, etc. This does not show that those things are not useful. But the point of the article was not to show why nested functions are useful, for which I would certainly have used more interesting examples.
jcranmer 1 days ago [-]
The author has been trying to push for the inclusion of nested functions into the C standard, and a lot of the resistance comes from the existence of trampolines and all of the issues that causes. His response to those issues is... to basically go "nested functions, Objective-C blocks, and C++ lambdas are all the same thing if you squint at them hard enough" and ignore all of the very real semantic differences between all of them.
For my part, I'll point out that there is one rather important difference between nested functions and C++ lambdas that the author completely ignores, as exhibited by this godbolt example: https://godbolt.org/z/35beWrrTe (note the differences in the generated assembly, especially that which cannot be explained merely by -O0 code generation).
uecker 8 hours ago [-]
I am not the only one who wants nested functions and function literals (lambdas) in C (as in basically any other modern language) and I explained every time that trampolines are not needed for this. It is frankly quite tiring that every time this topic comes up, still someone incorrectly claims that we can not have nested functions because of trampolines, or makes some other incorrect claim on how GCC implements nested functions.
BTW: I also very carefully analyzed all the semantic differences, which led me to the conclusion that putting C++ lambda semantics into C would be a bad idea. one can read this here: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3654.pdf
I also do not understand why you think the generated assembly needs to be identical, or why this is a "rather important difference".
aw1621107 13 hours ago [-]
> note the differences in the generated assembly, especially that which cannot be explained merely by -O0 code generation
Do you mind elaborating for those of us who aren't familiar with what to expect from the compiler?
jcranmer 10 hours ago [-]
In the nested function, the variable x is passed in edi, and the pointer to the nested stack frame is passed in r10. In the lambda, the variable x is passed in esi, and the 'this' pointer for the lambda is passed in rdi. The function-level ABIs end up being quite different.
uecker 7 hours ago [-]
Thanks, but now you should explain why you think this slight (and well understood) difference in calling convention is a rather important difference.
jcranmer 6 hours ago [-]
I can write the signature of the generated function of a C++ lambda as a C function. I cannot write the signature of a generated GCC nested function as a C function.
If your argument is that ABI doesn't matter, then by all means, propose a patch to GCC to change the ABI and see if it gets accepted.
uecker 6 hours ago [-]
I can not write the signature of a function that requires a static chain (which exist in many languages) in C, because we have not added such a feature to the language. But we could. And we should, because we now need a (type-unsafe) extension (__builtin_call_with_static_chain) to invoke such functions.
I do not want to change the ABI for nested functions as it is a useful ABI and a cross-language standard. ABI obviously matters, but it is not a fundamental difference in implementation that makes nested functions fundamentally different to C++ lambdas. If your point is merely that a compiler translating nested functions to lambdas would need to adapt the ABI in this case, I agree. This is not difficult though. And this question is relevant only if one allows taking the address of a nested function, because as long as it is called only locally, the compiler can use whatever ABI it wants.
jcranmer 4 hours ago [-]
Okay, so you accept that nested functions have a different ABI than C++ lambdas. And it looks like you accept that neither ABI is going to change. So long as the two features have different ABIs, they cannot be compatible with one another.
> And this question is relevant only if one allows taking the address of a nested function
And that question is very relevant since taking the address of such functions (to pass to other functions, e.g., qsort) is one of the main use cases for their existence.
uecker 4 hours ago [-]
The ABI does not need to be compatible, because there is no way to call a C++ lambda directly from C.
If you take the address of a lambda function you get a pointer to an object of anonymous type, so you can not pass it to qsort, and qsort would also not know how to call this.
But if we added a feature similar to std::function_ref to C (i.e. a wide function pointer type), then such a type could be used to call both, nested functions and C++'s lambdas, and - in fact - many callable entities from other languages too. But for C++'s lambdas this would always involve a compiler generated thunk that adapts the ABI. This is also exactly what happens in C++ if you use std::function, because even in C++ you can not pass the address of lambda to a function without first erasing the type and creating the thunk.
Similar to how std::function_ref creates a thunk in C++ that calls the lambda so that it has a generic type-erased API that can be passed to non-templates, a conversion to a wide pointer would create a thunk that adapts the call from the nested function pointer ABI (that already exits for other languages also in LLVM whether we standardize the C feature or not) to whatever the lambda needs.
Showing things that are optimized by fully inlining into one function don't actually demonstrate equivalency, because you end up omitting anything that might actually evidence a difference in the semantics. And I get that, for your use cases, those differences might not matter. But as a compiler engineer, I can't say that only those use cases matter and therefore they're equivalent for all practical purposes.
It is also very unhelpful when you insist that this is "compatible" with other languages, where "compatible" actually means "compatible, if you put in a bunch of work in both languages to make something that makes them compatible, none of which I'm actually describing." Especially when there are competing proposals that do have compatibility in the sense of "I don't have to modify the C++ compiler to let it use this thing."
tptacek 7 hours ago [-]
Doesn't this imply that the two functions have different semantics for capturing the environment?
uecker 7 hours ago [-]
No, why? It simply means that the arguments are in different registers.
pjmlp 17 hours ago [-]
Starting by not being portable.
Also misses that the way C++ lambdas work is that one design requirement was that they should be syntax sugar for the functor[0] pattern from C++98.
[0] - Not to mix with ML functors, rather classes with call operator overloaded.
cenamus 18 hours ago [-]
Can't you convert non-capturing lambdas to function pointers?
alexey-salmin 17 hours ago [-]
Yes. The non-capturing case is equivalent to a static function for both lambdas and GCC nested functions.
einpoklum 1 days ago [-]
> This problem doesn't arise with C++ lambdas because you pass them around as special objects, not as bare function pointers.
If they don't capture anything, I believe you _can_ pass them as bare function pointers.
lpribis 1 days ago [-]
Sure, but in that case they are equivalent to a static function so there's no benefit of lambda other than syntax sugar.
6yyyyyy 23 hours ago [-]
The benefit is that you don't have to solve one of the hard problems in computer science (naming things).
moxxymiller 16 hours ago [-]
Capturing lambdas in a language without a GC (or a borrow checker) are kinda fraught with footguns.
uecker 7 hours ago [-]
This is not my experience.
WalterBright 23 hours ago [-]
The D language's nested functions are implemented with a static link and a dynamic link. You're all familiar with the dynamic link, which is a pointer to the calling function's stack frame (EBP on x86_64 processors). The static link is the interesting one, it is a pointer to the statically enclosing stack frame.
Thus, to access stack variables two enclosing functions up, the static link is walked twice.
A reference to a nested function in D is represented by a pair - a pointer to the function, and the static link. (Called a "delegate" in D parlance.) Interestingly, this is the same layout as taking a reference to a member function, where the "this" pointer takes the place of the static link.
This means that references to nested functions are ABI compatible with references to member functions.
Lambdas in D are just a more compact syntax for nested functions.
ack_complete 16 hours ago [-]
Sadly, I've never seen a C++ compiler use this (old) technique for lambda reference captures. The main compilers all seem to just use individual references for each capture instead of a single reference to the stack frame, which makes the lambdas with a lot of reference captures more expensive.
gpderetta 13 hours ago [-]
Things get complicated when a lambda that capture by reference is capturing things that are not on a single stack frame (or a stack frame at all). Then you have references to references. You could rely on the optimizer, but the capture has ABI implications.
account42 10 hours ago [-]
Does ABI really matter when the lambda is always compiled in the same translation unit as the function from which variables are captured? Seems to me that compilers should be free to optimize the simple cases to a single stack frame reference while falling back to whatever for others.
jcranmer 9 hours ago [-]
Yes, it does. The lambda still needs to follow the C++ object model in case someone might use it like a regular C++ object. It's possible to change the ABI with escape analysis that proves you know all of the uses of the lambda to change the ABI, but a) that escape analysis is surprisingly easily defeated [1] and b) ABI-changing optimizations tend to be much more common in research papers than production compilers because getting them right on real code is a lot more difficult than it looks.
[1] The lambda function probably has the same linkage as the function the lambda is contained in, which likely isn't "the only copy of this function is in this TU" but rather "this function may appear in several TUs, but all of these copies are equivalent and you can pick whichever one you like as the actual body." Very different opportunities there!
yvdriess 13 hours ago [-]
I really like languages that embrace the duality of "closures are a poor man's object, objects are a poor man's closure".
hirvi74 18 hours ago [-]
Isn't it RBP the 64-bit register?
WalterBright 3 hours ago [-]
Yes. My mistake.
torginus 1 days ago [-]
> In GCC, nested functions are lowered in an early middle-end pass. During this pass, all variables of the parent that are accessed by the nested function are collected into a single synthetic structure, and a pointer to this structure is passed to the nested function in a hidden argument
Generally this is a bit nicer than having explicit lambdas, but I thought the 'best-case' scenario would be if GCC saw into the stack layout of the calling function and could manipulate the calling functions stored stack variables (and saved registers). After all, a debugger can track what variable goes where at every line of code, so this can be done.
Not sure if this would be useful or practical, but would be a nice bit of nerd cred.
jcranmer 23 hours ago [-]
> Generally this is a bit nicer than having explicit lambdas, but I thought the 'best-case' scenario would be if GCC saw into the stack layout of the calling function and could manipulate the calling functions stored stack variables (and saved registers).
A modern compiler IR is probably going to be an SSA-based infinite virtual register set model. In such a model, any variable without its address taken ends up being a register (which may happen to be spilled to the stack). Referencing the variable via a nested function means its a local variable whose address escapes, which kills a lot of optimization potential. It's probably possible to adjust SSA to handle this, but it's a lot of work for little benefit, especially since closure models (closures being regular objects with an unnameable type and an overloaded call operator) have taken over nested functions in language design and thus it isn't really applicable for modern languages.
> After all, a debugger can track what variable goes where at every line of code, so this can be done.
Variable value tracking breaks down pretty much the moment any optimization happens.
uecker 8 hours ago [-]
I think you should read my article ;-) ... because the point is that nested functions in C are basically implemented in a very similar way as C++'s lambdas with "unnameable types" a frontend detail.
The idea that "closures ... have taken over nested functions in language design and thus it isn't really applicable for modern languages." is true only if you think C++ as basically the only modern language and everything else with nested functions is not modern, which is ... an interesting take.
I'm shocked that you didn't even pick up Rust, given how frequently I mention it on the WG14 reflector.
alexey-salmin 17 hours ago [-]
>> After all, a debugger can track what variable goes where at every line of code, so this can be done.
> Variable value tracking breaks down pretty much the moment any optimization happens.
I think for nested functions it's not [only] a question of performance/optimizations but of correctness. Even if you properly unwind the stack like a debugger trying to find the parent frame, you may actually find multiple due to recursion. It's impossible to know which one is "yours" unless at least some information about the parent frame was passed to the nested function at invocation time. It can't be a truly static function.
torginus 23 hours ago [-]
This is where I retort about what you wrote not being exactly right, and then you reveal that you have 20 years of professional experience writing compilers, including the one most of the software I run was built with.
Without all this nested functions are as useful as the "rewritten" examples in the article, one can easily do that by hand without any compiler or language support.
This problem doesn't arise with C++ lambdas because you pass them around as special objects, not as bare function pointers.
[1] https://gcc.gnu.org/onlinedocs/gccint/Trampolines.html
This one explains how you can avoid the use of trampolines in GCC 17: https://uecker.codeberg.page/2026-07-14.html
The documentation is here: https://gcc.gnu.org/onlinedocs/gcc/Constructing-Calls.html
There are many language features can be rewritten by hand into other simpler forms, you could rewrite loops into gotos, C++ objects into structures, etc. This does not show that those things are not useful. But the point of the article was not to show why nested functions are useful, for which I would certainly have used more interesting examples.
For my part, I'll point out that there is one rather important difference between nested functions and C++ lambdas that the author completely ignores, as exhibited by this godbolt example: https://godbolt.org/z/35beWrrTe (note the differences in the generated assembly, especially that which cannot be explained merely by -O0 code generation).
BTW: I also very carefully analyzed all the semantic differences, which led me to the conclusion that putting C++ lambda semantics into C would be a bad idea. one can read this here: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3654.pdf
I also do not understand why you think the generated assembly needs to be identical, or why this is a "rather important difference".
Do you mind elaborating for those of us who aren't familiar with what to expect from the compiler?
If your argument is that ABI doesn't matter, then by all means, propose a patch to GCC to change the ABI and see if it gets accepted.
I do not want to change the ABI for nested functions as it is a useful ABI and a cross-language standard. ABI obviously matters, but it is not a fundamental difference in implementation that makes nested functions fundamentally different to C++ lambdas. If your point is merely that a compiler translating nested functions to lambdas would need to adapt the ABI in this case, I agree. This is not difficult though. And this question is relevant only if one allows taking the address of a nested function, because as long as it is called only locally, the compiler can use whatever ABI it wants.
> And this question is relevant only if one allows taking the address of a nested function
And that question is very relevant since taking the address of such functions (to pass to other functions, e.g., qsort) is one of the main use cases for their existence.
If you take the address of a lambda function you get a pointer to an object of anonymous type, so you can not pass it to qsort, and qsort would also not know how to call this.
But if we added a feature similar to std::function_ref to C (i.e. a wide function pointer type), then such a type could be used to call both, nested functions and C++'s lambdas, and - in fact - many callable entities from other languages too. But for C++'s lambdas this would always involve a compiler generated thunk that adapts the ABI. This is also exactly what happens in C++ if you use std::function, because even in C++ you can not pass the address of lambda to a function without first erasing the type and creating the thunk.
So there is no compatibility problem.
https://godbolt.org/z/vEP5G9Pfr
Similar to how std::function_ref creates a thunk in C++ that calls the lambda so that it has a generic type-erased API that can be passed to non-templates, a conversion to a wide pointer would create a thunk that adapts the call from the nested function pointer ABI (that already exits for other languages also in LLVM whether we standardize the C feature or not) to whatever the lambda needs.
Edit: slightly updated example.
Showing things that are optimized by fully inlining into one function don't actually demonstrate equivalency, because you end up omitting anything that might actually evidence a difference in the semantics. And I get that, for your use cases, those differences might not matter. But as a compiler engineer, I can't say that only those use cases matter and therefore they're equivalent for all practical purposes.
It is also very unhelpful when you insist that this is "compatible" with other languages, where "compatible" actually means "compatible, if you put in a bunch of work in both languages to make something that makes them compatible, none of which I'm actually describing." Especially when there are competing proposals that do have compatibility in the sense of "I don't have to modify the C++ compiler to let it use this thing."
Also misses that the way C++ lambdas work is that one design requirement was that they should be syntax sugar for the functor[0] pattern from C++98.
[0] - Not to mix with ML functors, rather classes with call operator overloaded.
If they don't capture anything, I believe you _can_ pass them as bare function pointers.
Thus, to access stack variables two enclosing functions up, the static link is walked twice.
A reference to a nested function in D is represented by a pair - a pointer to the function, and the static link. (Called a "delegate" in D parlance.) Interestingly, this is the same layout as taking a reference to a member function, where the "this" pointer takes the place of the static link.
This means that references to nested functions are ABI compatible with references to member functions.
Lambdas in D are just a more compact syntax for nested functions.
[1] The lambda function probably has the same linkage as the function the lambda is contained in, which likely isn't "the only copy of this function is in this TU" but rather "this function may appear in several TUs, but all of these copies are equivalent and you can pick whichever one you like as the actual body." Very different opportunities there!
Generally this is a bit nicer than having explicit lambdas, but I thought the 'best-case' scenario would be if GCC saw into the stack layout of the calling function and could manipulate the calling functions stored stack variables (and saved registers). After all, a debugger can track what variable goes where at every line of code, so this can be done.
Not sure if this would be useful or practical, but would be a nice bit of nerd cred.
A modern compiler IR is probably going to be an SSA-based infinite virtual register set model. In such a model, any variable without its address taken ends up being a register (which may happen to be spilled to the stack). Referencing the variable via a nested function means its a local variable whose address escapes, which kills a lot of optimization potential. It's probably possible to adjust SSA to handle this, but it's a lot of work for little benefit, especially since closure models (closures being regular objects with an unnameable type and an overloaded call operator) have taken over nested functions in language design and thus it isn't really applicable for modern languages.
> After all, a debugger can track what variable goes where at every line of code, so this can be done.
Variable value tracking breaks down pretty much the moment any optimization happens.
The idea that "closures ... have taken over nested functions in language design and thus it isn't really applicable for modern languages." is true only if you think C++ as basically the only modern language and everything else with nested functions is not modern, which is ... an interesting take.
I'm shocked that you didn't even pick up Rust, given how frequently I mention it on the WG14 reflector.
> Variable value tracking breaks down pretty much the moment any optimization happens.
I think for nested functions it's not [only] a question of performance/optimizations but of correctness. Even if you properly unwind the stack like a debugger trying to find the parent frame, you may actually find multiple due to recursion. It's impossible to know which one is "yours" unless at least some information about the parent frame was passed to the nested function at invocation time. It can't be a truly static function.