Emulating nested function behaviour

[Wolfgang Draxinger]

If you know languages like Python or D you know, that nested
functions can be really handy.

Though some compilers (looking at GCC) provide the extension of
nested functions, I wonder, how one could implement an
equivalent behaviour with plain C (in this case I'm thinking of
the language I'm developing, which shall be converted into C for
target compilation). So far I didn't touch the topic "nested
functions", since I just don't see an elegant way to implement
them, but I want them, .

The problem is, that a nested functions resides within the scope
of the enclosing function and thus sees all variables of that.
Of course, if I were not seeking for portability, I could just
fiddle around with assembler on the stack. But I'd like to do as
much in C as possible.

So far the "best" solution I came up with was to create a struct
for each function, containing all it's variables:

struct _foo_variables {
int a;
int b;
short c;
/* ... */
};

static void _nest_foo_bar(struct _foo_variables * const
_foo_variables)
{
}

void foo()
{
struct _foo_variables _variables;
/* ... */
_nest_foo_bar(&_variables);
}

But this doesn't look very elegant.

By nature nested functions can only be called from within the
scope of the enclosing function. I wonder if there's a more
elegant way, to access a calling function's variables from the
called function. I presume not, but maybe I'm wrong. I'm most
concerned about the performance impact due to the need of
dereferencing stuff - most architectures are more efficient in
addressing stuff on the stack, than from arbitrary pointers,
even if they point on the stack. I don't know how good compilers
are nowadays to figure out what's going on, and optimizing this
into frame pointer relative access. Yeah, I know "premature
optimization..."

lambda expressions were implemented quite easyly using the ffcall
library; lambdas (how I specified them for my language) can't
access variables outside the scope anyway, since they're first
class objects to be passed around.

Of course I could just omit the whole idea of nested functions,
but they're so damn usefull in some occasions.

Wolfgang Draxinger

 

[Harald van Dijk]

The problem is, that a nested functions resides within the scope of the
enclosing function and thus sees all variables of that. Of course, if I
were not seeking for portability, I could just fiddle around with
assembler on the stack. But I'd like to do as much in C as possible.

The problem isn't just that a nested function sees the variables of the
enclosing function, but that it sees the variables of the specific call
of the enclosing function, which can be different from the most recent
call if the function is recursive. In other words:

int f(int (*fp)(void)) {
int fp_is_null = (fp == 0);
int nestedfunction(void) {
return fp_is_null;
}
return fp_is_null ? f(nestedfunction) : fp();
}

Obviously, nested functions are non-standard, but the only implementation
in C I'm familiar with would let f(0) return 1, even though when
nestedfunction is called, the most recent call to f has set fp_is_null to
0.

So far the "best" solution I came up with was to create a struct for
each function, containing all it's variables:

struct _foo_variables {
int a;
int b;
short c;
/* ... */
};

static void _nest_foo_bar(struct _foo_variables * const _foo_variables)
{
}

void foo()
{
struct _foo_variables _variables;
/* ... */
_nest_foo_bar(&_variables);
}

But this doesn't look very elegant.

If you want to stick with standard C, you need to pass a pointer to the
local function's data explicitly.

By nature nested functions can only be called from within the scope of
the enclosing function.

Within the execution of the enclosing function. Because of function
pointers, it might be from outside of the enclosing function's scope.

I wonder if there's a more elegant way, to
access a calling function's variables from the called function. I
presume not, but maybe I'm wrong. I'm most concerned about the
performance impact due to the need of dereferencing stuff - most
architectures are more efficient in addressing stuff on the stack, than
from arbitrary pointers, even if they point on the stack. I don't know
how good compilers are nowadays to figure out what's going on, and
optimizing this into frame pointer relative access. Yeah, I know
"premature optimization..."

Again only referring to the one implementation I'm familiar with, the
function I posted would cause problems. It dynamically creates code at
runtime, on the stack, in order to save a pointer to the data. If you
save that pointer yourself, as a parameter to the called function,
exactly as you suggested, the code is standard C, and causes no problems.
It's not the most elegant solution, but it's a functional and correct
solution, so I suggest you stick with that.

 

[Wolfgang Draxinger]

The problem isn't just that a nested function sees the
variables of the enclosing function, but that it sees the
variables of the specific call of the enclosing function, which
can be different from the most recent call if the function is
recursive.

Of course, but doing tricks like unwiding the stack would take
this into account. But C does not define anything about stacks,
and I want the generated code to be as generic as possible.

Within the execution of the enclosing function. Because of
function pointers, it might be from outside of the enclosing
function's scope.

Yes of course. But the C code is supposed to be generated and not
modified directly. And all "nested" functions are declared
static, so it should be impossible to get a function pointer to
them from outside code - the code generator will definitely not
assign nested functions to function pointers that are outside
the scope of the containing function.

Well, nobody's supposed to see/touch the generated code under
normal conditions. I'm still thinking about, how I can get debug
information, which is referencing the "original" source code,
from which the C code is generated. Probably I've to fiddle
around with the DWARF data on the link level, but that's a
different problem and not related to C.

Wolfgang Draxinger

 

[Keith Thompson]

If you know languages like Python or D you know, that nested
functions can be really handy.

Though some compilers (looking at GCC) provide the extension of
nested functions, I wonder, how one could implement an
equivalent behaviour with plain C (in this case I'm thinking of
the language I'm developing, which shall be converted into C for
target compilation). So far I didn't touch the topic "nested
functions", since I just don't see an elegant way to implement
them, but I want them, .

[...]

I don't have any concrete suggestions, just an observation. The fact
that you're (thinking of) writing a compiler that uses C as an
intermediate language gives you an advantage: the generated C doesn't
have to be particularly easy to read, as long as it's correct.

Using C as a target language is not uncommon. I'm sure there are
existing implementations for languages that support nested
subroutines. Many of those are likely to be open source; even those
that aren't are likely to let you see the generated C code. (Eiffel
is one likely example that springs to mind.) You can get ideas from
other people's work.

You might also have better luck in comp.compilers. Note that it's a
moderated group; responses aren't likely to be fast, especially at
this time of year.

 

[Harald van Dijk]

Of course, but doing tricks like unwiding the stack would take this into
account. But C does not define anything about stacks, and I want the
generated code to be as generic as possible.

No, that's just it: unwinding the stack wouldn't take that into account,
because unwinding the stack would leave you at the innermost call to the
outer function. The example function I gave would generate the exact
opposite result this way.

Yes of course. But the C code is supposed to be generated and not
modified directly. And all "nested" functions are declared static, so it
should be impossible to get a function pointer to them from outside code
- the code generator will definitely not assign nested functions to
function pointers that are outside the scope of the containing function.

That will save you from a lot of problems. In that case, might I suggest
transforming what would become

int f(void) {
int data;

int nested(void) {
/* do things with data */
}
}

into

static int f_nested(void);
struct f_data {
int data;
} *f_data;

int f(void) {
struct f_data data, *prev_data;

prev_data = f_data;
f_data = &data;

/* ... */

f_data = prev_data;
}

static int f_nested(void) {
/* do things with f_data->data */
}

? This way, f_nested will have access to the data from the most recent
call to f, and even if f calls itself recursively, you won't invalidate
pointers to the local data. You just need to make sure to restore the
pointer after you return from f, that's all.

 

[Thad Smith]

No, that's just it: unwinding the stack wouldn't take that into account,
because unwinding the stack would leave you at the innermost call to the
outer function. The example function I gave would generate the exact
opposite result this way.


That will save you from a lot of problems. In that case, might I suggest
transforming what would become

int f(void) {
int data;

int nested(void) {
/* do things with data */
}
}

into

static int f_nested(void);
struct f_data {
int data;
} *f_data;

int f(void) {
struct f_data data, *prev_data;

prev_data = f_data;
f_data = &data;

/* ... */

f_data = prev_data;
}

static int f_nested(void) {
/* do things with f_data->data */
}

I was following up to the point where Harald suggested "in that case" with
the recommendation of using the most recent. Wolfgang's statement thatdoes not eliminate the problem with Harald's recursive example where the
address is taken from /within/ the outer function, then passed to itself or
an outside function which saves the pointer, calls f and, in a nested
context, uses the earlier saved pointer.

Wolfgang, are you saying that a pointer to the nested function cannot be taken?