Emulating nested function behaviour

Discussion in 'C Programming' started by Wolfgang Draxinger, Dec 27, 2007.

  1. 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: , ICQ: 134682867
     
    Wolfgang Draxinger, Dec 27, 2007
    #1
    1. Advertising

  2. 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.
     
    Harald van Dijk, Dec 27, 2007
    #2
    1. Advertising

  3. 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: , ICQ: 134682867
     
    Wolfgang Draxinger, Dec 27, 2007
    #3
  4. Wolfgang Draxinger <> 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) <>
    [...]
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Dec 27, 2007
    #4
  5. 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.
     
    Harald van Dijk, Dec 27, 2007
    #5
  6. Wolfgang Draxinger

    Thad Smith Guest

    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
     
    Thad Smith, Dec 28, 2007
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    3
    Views:
    648
    Gary Thorpe
    Sep 1, 2005
  2. Mike Orb

    Emulating variables static to the page

    Mike Orb, Sep 2, 2005, in forum: ASP .Net
    Replies:
    2
    Views:
    410
    Mike Orb
    Sep 2, 2005
  3. Ben Fidge

    Emulating referrers?

    Ben Fidge, Dec 14, 2005, in forum: ASP .Net
    Replies:
    1
    Views:
    1,625
    Kevin Spencer
    Dec 14, 2005
  4. Ben Fidge

    Emulating referrers?

    Ben Fidge, Dec 14, 2005, in forum: ASP .Net
    Replies:
    0
    Views:
    527
    Ben Fidge
    Dec 14, 2005
  5. Richard A. DeVenezia

    Nested function X vs. nested varX = function

    Richard A. DeVenezia, Sep 8, 2003, in forum: Javascript
    Replies:
    1
    Views:
    135
    Code Ronin
    Sep 9, 2003
Loading...

Share This Page