Rendered at 21:04:12 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
mbeavitt 9 hours ago [-]
Why would someone want to use a nested function, practically speaking?
mananaysiempre 9 hours ago [-]
Good C style is that every function that accepts a callback should also accept an opaque context pointer it then passes through unchanged to the callback. Usually the caller will allocate a structure on the stack or the heap, stash some of its local variables there, then use them in the callback. A nested function does the structure back-and-forth for you in the stack-allocated case. In GCC’s original formulation it also passes the context pointer implicitly
size_t filter(bool (*predicate)(int), int *p, size_t n) {
for (size_t r = 0, w = 0; r < n; r++) {
if (predicate(p[r])) p[w++] = p[r];
}
return w;
}
size_t lowpass(int limit, int *p, size_t n) {
bool lower(int value) {
return value < limit; // use the parent's local variable
}
return filter(lower, p, n);
}
but that requires an executable stack and TFA is about avoiding that part.
charleslmunger 2 hours ago [-]
And if you want to write a templated data structure without actual templating or fancy macros, doing so with force-iined functions calling function pointers that are constant at the call site is a great way to do it. Unfortunately it's ugly and annoying to do this without nested functions :-/
jcranmer 9 hours ago [-]
When you want to use lambdas, but your language doesn't have lambdas, so you reach for the nearest thing instead.
uecker 8 hours ago [-]
Lambdas are just anonymous nested functions. But I like named nested functions more because they are more readable and would prefer them in most cases.
Ideally you have both as most languages have.
I always wondered why C++ only added lambdas, but observing WG21 for a while, I assume this is just a random walk in language design. (not that it is different in WG14)
wasmperson 6 hours ago [-]
> Lambdas are just anonymous nested functions.
The important feature of lambdas is that they are expressions, not that they lack a name. The advantage of function expressions is you can write the body of the function exactly at the place where it is used. With GCC nested functions you either have to write the body of the function before its first use or else write the declaration of the function twice.
This matters for long chains of continuation passing:
foo(arg1, arg2, [](){
// do some work
bar(arg3, arg4, [](){
// do some more work
baz(arg5, arg6, [](){
});
});
});
Compare to the following, where the control flow is all out of order:
void cb(void){
// Do some work
void cb2(void){
// do some more work
void cb3(void){
}
baz(arg5, arg6, cb3);
}
bar(arg3, arg4, cb2);
}
foo(arg1, arg2, cb);
uecker 6 hours ago [-]
I agree with your point.
But I usually prefer the later anyway, because the code usually is not as nested anyway and having a name is often helpful, and also because I find the nested code with lambdas also not too readable. Other languages have better syntax for chaining functions in this way, i.e. with lambdas I would like to write like this:
(edit: or something, I think I got it a bit wrong, but you get the idea)
But I agree, sometimes lambdas are better so it would be good to have both.
(There is the classical hack to define lambdas using statement expressions and nested functions.)
eru 7 hours ago [-]
I can write numbers like three by just writing 3 in my code. When I want a named number I use a syntax like x = 3. Why should functions be any different? A language doesn't need different ways to name things for each type of thing. Integers, strings, functions etc: they can all use the same mechanism for naming.
uecker 7 hours ago [-]
I agree if your language is designed like this from the beginning as functional languages are, but in C you already have different syntax for functions. (edit: rephrased)
astrobe_ 3 hours ago [-]
No exactly. "Lambdas" are usually function closures [1]. Which do not exist in C and were quite "late" in C++, because decent support of closures require automatic memory management (GC).
C++ lambda/closures are a bit clunky because you have to specify if the captures are by reference or by value, and you're better of having a good idea of what you're doing.
GCC's nested functions can also capture variables by reference. A closure combines the function with the environment which is essentially what my wide pointer is that contains the static chain that points to the environment. But for full support of first-class functions you would want return functions even below the level of where the captured variables live which is not possible with GCC's nested functions because they are on the stack and then go out of scope. So yes, this would require moving them to the heap and generally GC. Which is why the attempts to put C++'s "lambdas" into C are problematic, because naively copied lambda design will work even less well in C compared to C++ where you at least have smart pointers.
Lambda expressions in C++ are simply syntactic sugar for defining function objects (aka functors): structs that overload operator() so you can call them as functions. Once you realize this, their features and limitations become immediately clear.
For example, here is a typical use of a lambda expression to filter a vector of values:
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5};
int threshold = 5;
std::erase_if(v, [&](int i) { return i < threshold; });
// prints 5 9 6 5
for (int i : v) std::cout << i << '\n';
}
The lambda expression is essentially shorthand for:
...
int threshold = 5;
struct lambda_t {
int &threshold;
bool operator()(int i) {
return i < threshold;
}
};
std::erase_if(v, lambda_t{threshold});
...
You could always do this in C++. The added value of the lambda expression syntax is that the compiler generates the boilerplate, and generates a unique name for lambda_t.
The important takeaway is that every lambda expression corresponds with a unique type that is _not_ a function type, but a class type. Consequently, lambda expressions can only be passed to template functions like std::erase_if, which are parameterized with the callback type.
You cannot pass a lambda expression to a function that expects a function pointer (e.g. bool(*)(int) in this example), and that's where they differ from GCC-style nested functions, which actually behave like functions. It also explains why lambda expressions don't need a trampoline.
As an aside, you _can_ pass lambdas to non-generic functions using a type-erasing wrapper like std::function, but std::function is itself a class type too, so that still doesn't allow you to convert it to a plain function pointer.
Finally, you can of course assign a name to a lambda expression value, using this common pattern:
auto greet = [](const char *name) { std::cout << "Hello " << name << "!\n"; }
greet("Alice");
greet("Bob");
(Note that `auto` is necessary here because there is no way to explicitly refer to the compiler-generated name for the lambda type.)
This is the closest you can get to a local function definition in C++. Admittedly the syntax is a little odd. You might wonder why there wasn't some additional syntactic sugar to make the definition look more normal. I suspect that wasn't a random decision, but rather intentionally avoiding conflicts with existing language extensions like GCC's local function syntax.
uecker 2 hours ago [-]
Regarding function syntax in C++: GCC's C++ frontend does not support nested functions. But more importantly, even if it did, I do not think there would be any conflict at all. While lambdas are lowered to function objects with an unique anonymous type in C++, the semantics of a lambda that uses lvalue capture
auto f = [&](int x) - > int { return x + z; };
is the same as GCC's nested function
int f(int x) { return x + z; }
except that latter can be converted via a trampoline to a regular function pointer (and maybe the observable type). But you could do just the same with a lambda using a trampoline! In any case, there is no conflict, either this conversion is allowed and one needs some hack to make it work such as a trampoline or it is not.
So in C++ you could simply lower such nested functions to lambdas and it would cause no confusion with GCC's nested functions at all, because from a user's point of view they would work identically.
wasmperson 1 hours ago [-]
> lambda expressions can only be passed to template functions
> there is no way to explicitly refer to the compiler-generated name for the lambda type.
"Voldemort" types. While intellectually I get the explanation for why C++/Rust lambdas are like this, I still strongly dislike them. Occasionally being unable to even articulate what something is feels like a failure in language design.
C recently got type inference via the "auto" keyword and it seemed like almost immediately there was a proposal to add voldemort types to the language.
gpderetta 2 hours ago [-]
>You cannot pass a lambda expression to a function that expects a function pointer (e.g. bool(*)(int) in this example)
To be pedantic, you can: as long as the lambda doesn't close over any local variable, the object will decay to a function pointer.
mananaysiempre 9 hours ago [-]
C++ bundles together a way to write functions inline in an expression (what I’d call “lambdas” in general) and a way to create closures with strictly nested lifetimes, but there’s no law of nature tying the two together. Even in C++ the essentially separate declaration “auto f = [&](... blah ...) { ... 50 lines of code ... };” is pretty common. (And of course GCC’s nested functions predate C++11 by twenty years.)
anta40 9 hours ago [-]
Say to strictly enforce modularity, e.g helper functions that can only be accessed within its function.
Pascal supports it (at least Turbo Pascal, no idea about ISO Pascal).
Joker_vD 7 hours ago [-]
For a counterpoint, see David R. Hanson's "Is block structure necessary?" (1981) [0] — back in those days, "block structure" meant nested routines with nested scopes — which argues that having instead a proper module system, with explicit control over what's being exported from a module, not only gives a better modularity, decomposition, and encapsulation, but also simplifies both the language's implementation, and the run-time structures it needs (remember displays, and the hardware support for them e.g. x86's ENTER?).
Block structure is traditionally considered an a priori requirement for algorithmic program-
ming languages. Most new languages since Algol-60 have block structure. Reasons exist,
however, to omit the general form of block structure — nested procedure definitions in which
references to identifiers defined in outer procedures are permitted — from programming
languages, especially those intended for systems programming applications. This paper
reviews the concept of block structure and considers its advantages and disadvantages. It
concludes that, in many cases, a module facility is superior to block structure and should be
considered in lieu of block structure in future languages.
The traditional way of doing this in C is simply static functions. Every .c file has exactly one non-static function and all the other helper functions are static.
5 hours ago [-]
sltkr 9 hours ago [-]
For the non-capturing case: mainly to improve readability by allowing utility functions to be defined close to where they are used and with short names.
For the capturing case: to access context that is not available through global variables or function arguments, i.e., the same reason why closures are useful in other languages.
Here's an example, where I have a list of points that I want to sort based on distance to a chosen target point. I can use qsort() which takes an arbitrary comparison function, but has no way to provide context to that function beyond the input arguments:
#include <stdio.h>
#include <stdlib.h>
int main() {
struct Point {
int x, y;
} points[3] = {
{ 3, 1 },
{ 2, 2 },
{ 5, 7 } };
struct Point target = { 4, 5 };
long dsq(const struct Point *p) {
long dx = p->x - target.x, dy = p->y - target.y;
return dx*dx + dy*dy;
}
int compare(const void *p, const void *q) {
long a = dsq(p), b = dsq(q);
return (a > b) - (a < b);
}
qsort(points, 3, sizeof(struct Point), compare);
for (int i = 0; i < 3; ++i) {
printf("%d,%d\n", points[i].x, points[i].y);
}
}
Note here that dsq() is a local function that accesses the `target` variable in the local function scope.
The usual workaround in standard C is to pass the necessary context as a function argument. That's why qsort_r() exists, which takes a context argument to be passed to compare(), but that's a non-standard GNU extension.
This practice of passing context pointers around is ubiquitous in C code, and it works, but it can get messy especially if you need access to multiple variables or variables from more than one nested scope. There is also a type safety issue: these context pointers are necessarily passed as void* which means they have to be cast back to the real type before use, which is where bugs can be introduced if the caller and receiver disagree on the actual type.
int main() {
struct Point {
int x, y;
} points[3] = {
{ 3, 1 },
{ 2, 2 },
{ 5, 7 }
};
struct Point target = { 4, 5 };
long dsq(const struct Point *p) {
long dx = p->x - target.x, dy = p->y - target.y;
return dx*dx + dy*dy;
}
typedef typeof(dsq) dsq_f;
int compare(const void *p, const void *q, void *data) {
wide(dsq_f) *dsq = data;
long a = CALL(*dsq, (p)), b = CALL(*dsq, (q));
return (a > b) - (a < b);
}
qsort_r(points, 3, sizeof(struct Point), compare, &CLOSURE(dsq_f, dsq));
for (int i = 0; i < 3; ++i)
printf("%d,%d\n", points[i].x, points[i].y);
}
There are slightly different ways how to define the helper macros, I am still experimenting a bit. Here you could avoid the typedef if defined differently. But ideally, there would be native language support that avoids these macros.
listeria 6 hours ago [-]
Well, if you're already using qsort_r, what's the point of using nested functions, if you can have a context pointer with the target?
And if you're not using qsort_r, but reaching for _Thread_local, the target can be _Thread_local instead of dsq.
uecker 6 hours ago [-]
Fair. If you only have one object to access such as the target pointer, then it probably makes not much difference with void-pointer based APIs such as qsort_r (for new APIs it would add type safety). Where it removes more boilerplate code is when you have several such objects and would have to create an extra data structure to access them.
uecker 6 hours ago [-]
Or without qsort_r, you could use a thread local variable:
I use them all the time. It's one of the nicest and cleanest features of D. It's an elegant way of:
1. grouping together strongly related functions that are implicitly private to the enclosing function
2. obviating the need to create a struct in order to pass common context to multiple functions
For an example, here's a tree walking function that uses a nested function for the recursion:
private void unrollWalker(elem* e, uint defnum, Symbol* v, targ_llong increment, int unrolls) nothrow
{
int state = 0;
/***********************************
* Walk e in execution order, fixing it according to state.
* state == 0..unrolls-1: when eincrement is found, remove it, advance to next state
* state == 1..unrolls-1: replacing instances of v with v+(state*increment),
* state == unrolls-1: leave eincrement alone, advance to next state
* state == unrolls: done
*/
void walker(elem* e) @trusted
{
assert(e);
const op = e.Eoper;
if (ERTOL(e))
{
if (e.Edef != defnum)
{
walker(e.E2); // this function is @trusted because of this union access
walker(e.E1);
}
}
else if (OTbinary(op))
{
if (e.Edef != defnum)
{
walker(e.E1);
walker(e.E2);
}
}
else if (OTunary(op))
{
assert(e.Edef != defnum);
walker(e.E1);
}
else if (op == OPvar &&
state &&
e.Vsym == v)
{
// overwrite e with (v+increment)
elem* e1 = el_calloc();
el_copy(e1,e);
e.Eoper = OPadd;
e.E1 = e1;
e.E2 = el_long(e.Ety, increment * state);
}
if (OTdef(op) && e.Edef == defnum)
{
// found the increment elem; neuter all but the last one
if (state + 1 < unrolls)
{
el_free(e.E1);
el_free(e.E2);
e.Eoper = OPconst;
e.Vllong = 0;
}
++state;
}
}
walker(e);
assert(state == unrolls);
}
Only one argument needs to be passed to walker(), because the other context data is accessible from the enclosing function.
Just a little cleaner than placing it in the global or file namespaces.
kloop 9 hours ago [-]
So that you can name a section of code without polluting the namespace.
slashdave 5 hours ago [-]
Encapsulation
mananaysiempre 10 hours ago [-]
What about your older patch where -fno-trampolines meant a function pointer could either be a code pointer or a closure (descriptor) pointer, distinguished by a tag?
uecker 9 hours ago [-]
My old patch from 2018? This was not accepted to GCC because it relied on function pointers being aligned and there were concerns with this.
But I prefer this approach anyhow, as it does not impose any run-time cost for checking the tag, and is easier to optimize.
tpoacher 9 hours ago [-]
What's a "trampoline"?
jcranmer 9 hours ago [-]
In this context:
Nested functions have a different ABI from regular C functions, due to the invisible static chain register that needs to be set up. C has no way of indicating this different ABI, so GCC happily lets you cast a nested function to a C function pointer by creating a little tiny function that puts the right value in the static chain register before calling the nested function. This little tiny function is the trampoline.
Since the trampoline needs to live somewhere, GCC puts it on the stack, requiring the stack to be executable and consequently a whole lot of people hate the feature because it's a walking security nightmare.
uecker 8 hours ago [-]
Correct (although the nightmare part is a bit exaggerated since return-oriented programming showed that non-executable stack does not help a lot). GCC can also put the trampoline on the heap, but this also has downsides.
For me the main downside of trampolines is that the optimizer can not de-virtualize the trampoline again. This could be implemented, but avoiding the creation of the trampoline in the first place is much better.
kccqzy 7 hours ago [-]
C++ solves this problem by simply not allowing a nested function (lambda) to be converted to a function pointer, and thereby avoids this problem of trampolines and executable stack altogether. I think that’s a better design.
uecker 7 hours ago [-]
C++ has the same solution as I propose here: A wide function pointer type.
In C++ it is called std::function, but this comes with a bit of baggage. C++ 26 has std::function_ref which would be the exact equivalent to my wide pointer.
A C++ lambda that doesn't close over anything can be converted to a function pointer: https://eel.is/c++draft/expr.prim.lambda#closure-12 This feature does turn out to be useful if you need to pun a C++ interface into a function pointer for a C ABI function.
kccqzy 3 hours ago [-]
I know that but it’s not relevant to the discussion. A nested function in C (or rather GCC-flavored C) that doesn’t close over anything doesn’t need a trampoline anyways.
mananaysiempre 9 hours ago [-]
Could be a number of things depending on context. In this case it’s a short function that adjusts some things and jumps to the actual functions (a “thunk” is another term for this). Specifically, if in GCC you write
int f(int x) {
int g(int y) { ... use x and y ... }
...
h(&g);
...
}
then what the compiled code for f does is construct on the stack a short piece of machine code:
mov <well-known register>, <frame pointer>
jmp <start of g’s code>
and &g points to the start not of g’s code but of this snippet on the stack, which has the parent function’s frame pointer compiled into it as a literal constant. The snippet is called a trampoline.
monster_truck 9 hours ago [-]
It's where you jump and then get immediately bounced back. Basically GOTOs with params
eru 7 hours ago [-]
If you have proper tail call optimisation, then tail calls are GOTOs with params.
Trampolines allow you to simulate that, even when your compiler / language doesn't handle tail calls properly.
I always wondered why C++ only added lambdas, but observing WG21 for a while, I assume this is just a random walk in language design. (not that it is different in WG14)
The important feature of lambdas is that they are expressions, not that they lack a name. The advantage of function expressions is you can write the body of the function exactly at the place where it is used. With GCC nested functions you either have to write the body of the function before its first use or else write the declaration of the function twice.
This matters for long chains of continuation passing:
Compare to the following, where the control flow is all out of order:But I usually prefer the later anyway, because the code usually is not as nested anyway and having a name is often helpful, and also because I find the nested code with lambdas also not too readable. Other languages have better syntax for chaining functions in this way, i.e. with lambdas I would like to write like this:
(edit: or something, I think I got it a bit wrong, but you get the idea)But I agree, sometimes lambdas are better so it would be good to have both.
(There is the classical hack to define lambdas using statement expressions and nested functions.)
C++ lambda/closures are a bit clunky because you have to specify if the captures are by reference or by value, and you're better of having a good idea of what you're doing.
[1] https://en.wikipedia.org/wiki/Closure_(computer_programming)
If you are interested, I explore the design space here. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3654.pdf
For example, here is a typical use of a lambda expression to filter a vector of values:
The lambda expression is essentially shorthand for: You could always do this in C++. The added value of the lambda expression syntax is that the compiler generates the boilerplate, and generates a unique name for lambda_t.The important takeaway is that every lambda expression corresponds with a unique type that is _not_ a function type, but a class type. Consequently, lambda expressions can only be passed to template functions like std::erase_if, which are parameterized with the callback type.
You cannot pass a lambda expression to a function that expects a function pointer (e.g. bool(*)(int) in this example), and that's where they differ from GCC-style nested functions, which actually behave like functions. It also explains why lambda expressions don't need a trampoline.
As an aside, you _can_ pass lambdas to non-generic functions using a type-erasing wrapper like std::function, but std::function is itself a class type too, so that still doesn't allow you to convert it to a plain function pointer.
Finally, you can of course assign a name to a lambda expression value, using this common pattern:
(Note that `auto` is necessary here because there is no way to explicitly refer to the compiler-generated name for the lambda type.)This is the closest you can get to a local function definition in C++. Admittedly the syntax is a little odd. You might wonder why there wasn't some additional syntactic sugar to make the definition look more normal. I suspect that wasn't a random decision, but rather intentionally avoiding conflicts with existing language extensions like GCC's local function syntax.
So in C++ you could simply lower such nested functions to lambdas and it would cause no confusion with GCC's nested functions at all, because from a user's point of view they would work identically.
> there is no way to explicitly refer to the compiler-generated name for the lambda type.
"Voldemort" types. While intellectually I get the explanation for why C++/Rust lambdas are like this, I still strongly dislike them. Occasionally being unable to even articulate what something is feels like a failure in language design.
C recently got type inference via the "auto" keyword and it seemed like almost immediately there was a proposal to add voldemort types to the language.
To be pedantic, you can: as long as the lambda doesn't close over any local variable, the object will decay to a function pointer.
Pascal supports it (at least Turbo Pascal, no idea about ISO Pascal).
For the capturing case: to access context that is not available through global variables or function arguments, i.e., the same reason why closures are useful in other languages.
Here's an example, where I have a list of points that I want to sort based on distance to a chosen target point. I can use qsort() which takes an arbitrary comparison function, but has no way to provide context to that function beyond the input arguments:
Note here that dsq() is a local function that accesses the `target` variable in the local function scope.The usual workaround in standard C is to pass the necessary context as a function argument. That's why qsort_r() exists, which takes a context argument to be passed to compare(), but that's a non-standard GNU extension.
This practice of passing context pointers around is ubiquitous in C code, and it works, but it can get messy especially if you need access to multiple variables or variables from more than one nested scope. There is also a type safety issue: these context pointers are necessarily passed as void* which means they have to be cast back to the real type before use, which is where bugs can be introduced if the caller and receiver disagree on the actual type.
And if you're not using qsort_r, but reaching for _Thread_local, the target can be _Thread_local instead of dsq.
1. grouping together strongly related functions that are implicitly private to the enclosing function
2. obviating the need to create a struct in order to pass common context to multiple functions
For an example, here's a tree walking function that uses a nested function for the recursion:
Only one argument needs to be passed to walker(), because the other context data is accessible from the enclosing function.https://github.com/dlang/dmd/blob/master/compiler/src/dmd/ba...
But I prefer this approach anyhow, as it does not impose any run-time cost for checking the tag, and is easier to optimize.
Nested functions have a different ABI from regular C functions, due to the invisible static chain register that needs to be set up. C has no way of indicating this different ABI, so GCC happily lets you cast a nested function to a C function pointer by creating a little tiny function that puts the right value in the static chain register before calling the nested function. This little tiny function is the trampoline.
Since the trampoline needs to live somewhere, GCC puts it on the stack, requiring the stack to be executable and consequently a whole lot of people hate the feature because it's a walking security nightmare.
For me the main downside of trampolines is that the optimizer can not de-virtualize the trampoline again. This could be implemented, but avoiding the creation of the trampoline in the first place is much better.
In C++ it is called std::function, but this comes with a bit of baggage. C++ 26 has std::function_ref which would be the exact equivalent to my wide pointer.
https://godbolt.org/z/GaP9jb5rE
Trampolines allow you to simulate that, even when your compiler / language doesn't handle tail calls properly.