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.
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).
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.
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.
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.
> 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.
> 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.
>> 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.
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.
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.
[1] https://gcc.gnu.org/onlinedocs/gccint/Trampolines.html
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).
> 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?
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.
Can't you convert non-capturing lambdas to function pointers?
Yes. The non-capturing case is equivalent to a static function for both lambdas and GCC nested functions.
> 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.
Sure, but in that case they are equivalent to a static function so there's no benefit of lambda other than syntax sugar.
Capturing lambdas in a language without a GC (or a borrow checker) are kinda fraught with footguns.
The benefit is that you don't have to solve one of the hard problems in computer science (naming things).
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.
I really like languages that embrace the duality of "closures are a poor man's object, objects are a poor man's closure".
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.
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.
Isn't it RBP the 64-bit register?
> 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.
> 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.
>> 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.
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.