Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Emulating nested function behaviour

Reply
Thread Tools

Emulating nested function behaviour

 
 
Wolfgang Draxinger
Guest
Posts: n/a
 
      12-27-2007
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
--
E-Mail address works, Jabber: http://www.velocityreviews.com/forums/(E-Mail Removed), ICQ: 134682867

 
Reply With Quote
 
 
 
 
Harald van Dijk
Guest
Posts: n/a
 
      12-27-2007
On Thu, 27 Dec 2007 20:14:15 +0100, Wolfgang Draxinger wrote:
> 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.
 
Reply With Quote
 
 
 
 
Wolfgang Draxinger
Guest
Posts: n/a
 
      12-27-2007
Harald van Dijk wrote:

> 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.

>> 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.


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
--
E-Mail address works, Jabber: (E-Mail Removed), ICQ: 134682867

 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      12-27-2007
Wolfgang Draxinger <(E-Mail Removed)> writes:
> 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.

--
Keith Thompson (The_Other_Keith) <(E-Mail Removed)>
[...]
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
Harald van Dijk
Guest
Posts: n/a
 
      12-27-2007
On Thu, 27 Dec 2007 21:56:29 +0100, Wolfgang Draxinger wrote:
> Harald van Dijk wrote:
>> 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.


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.

>>> 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.

>
> 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.
 
Reply With Quote
 
Thad Smith
Guest
Posts: n/a
 
      12-28-2007
Harald van Dijk wrote:
> On Thu, 27 Dec 2007 21:56:29 +0100, Wolfgang Draxinger wrote:
>> Harald van Dijk wrote:
>>> 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.

>
> 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.
>
>>>> 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.

>> 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 */
> }
>


I was following up to the point where Harald suggested "in that case" with
the recommendation of using the most recent. Wolfgang's statement that
>> so it should be impossible to get a function pointer to them from
>> outside code

does 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?


--
Thad
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Emulating referrers? Ben Fidge ASP .Net 1 12-14-2005 07:06 PM
Emulating referrers? Ben Fidge ASP .Net 0 12-14-2005 04:30 PM
Emulating variables static to the page Mike Orb ASP .Net 2 09-02-2005 03:24 PM
Emulating floating point gthorpe@ee.ryerson.ca VHDL 3 09-01-2005 09:03 PM
Nested function X vs. nested varX = function Richard A. DeVenezia Javascript 1 09-09-2003 12:11 AM



Advertisments