alternative to nested procedures

Discussion in 'C Programming' started by Quinnie, Oct 27, 2003.

  1. Quinnie

    Quinnie Guest

    Hi,

    I have a homework assignment that I'm so confused and really need help
    with. Here's the description, any help would be appreciated. Thanks!

    Assume we have a statically-scoped language with nested procedures.
    That is, a procedure
    (or function) can contain local procedures (and functions). Procedures
    can be nested arbitrarily
    deep. The scoping rules for procedure names (i.e., the ability to call
    a procedure from
    a particular point in a program) is really the same as the scoping
    rules for local variables:
    A name is visible in the block in which it is declared and in all
    enclosed blocks (procedures)
    unless shadowed by a declaration of the same name. So at any given
    point in a program the
    visible names are those declared in all enclosing blocks (except for
    those that are hidden).
    Instead of implementing this language using static links to access
    non-local variables, we
    can first transform programs into ones that contain no nesting of
    procedures, i.e., a C-like
    structure with just a main program and a (flat) set of procedure
    declarations. The key idea
    behind this transformation is adding appropriate parameters to
    procedures so that they are
    passed (by reference) all of the (previously non-local) variables that
    they need in addition
    to the globals and their locals. Give an algorithm for this
    transformation.
    To provide a starting framework, assume that a program is given as
    input data with the
    following operations supported:
    children(P) - returns all the procedures declared local to procedure P
    body(P) - returns the body of procedure P
    called(P) - returns the set of procedures called in the body of P.
    You may or may not find these definitions useful. You should define
    additional ones to
    make your algorithm clearer.
    This problem is a subtle one and care should be taken to ensure that
    you've considered
    all possible cases. For example, simply adding all the non-local
    variables in a procedure P
    to P's parameter list is not always sufficient. A proper solution
    requires you to analyze the
    program and the "flow" of information (variables) through the program.
    You will need to
    iteratively collect this information until you are sure you have it
    all.
    This assignment requires you to do some thinking about a new kind of
    problem and
    come up with a solution based on some new ideas. (But no proofs are
    involved!) Feel free
    to discuss this among yourselves and with me.
    Ambitious students may also try to reason why their proposed algorithm
    gives a correct
    transformation.



    note that my professor doesn't like the idea of redefining all nested
    procedures as global, and then add to the parameter list of each
    nested procedure an object representing the variables of the parent
    procedure

    any thoughts? Thanks!
     
    Quinnie, Oct 27, 2003
    #1
    1. Advertising

  2. Quinnie

    Chris Torek Guest

    In article <>
    Quinnie <> writes:
    >I have a homework assignment that I'm so confused and really need help
    >with. ...


    The problem has nothing to do with C per se; comp.programming is
    certainly a much more appropriate group.

    [Problem description snipped; my summary: produce an algorithm
    for transforming lexically-nested procedures into parameterized
    unnested procedures, given a limited set of operations on the
    procedures and their variables. The algorithm you will need is
    quite common and is called "transitive closure".]

    >... For example, simply adding all the non-local
    >variables in a procedure P
    >to P's parameter list is not always sufficient.


    In particular, consider what happens if you have:

    procedure outermost() {
    variables t, u, v, w, and z all defined here
    ...
    procedure P(var x) {
    procedure Q(var y) {
    touch variable z
    }
    touch variable w
    }
    }

    Procedure P here uses "w", which is not local to P, but it also
    calls Q, which uses "z", which is *also* not local to P. If Q is
    moved to the "outermost" level, and P calls Q, outermost() will
    need to pass *both* w *and* z to P, so that P can pass z on to Q.

    >note that my professor doesn't like the idea of redefining all nested
    >procedures as global, and then add to the parameter list of each
    >nested procedure an object representing the variables of the parent
    >procedure


    This method works if done right -- instead of adding "the" parent's
    locals, you must add ALL the parents' locals, so that both P *and*
    Q get *both* "w" and "z" -- but is overkill. In this case it would
    mean that P and Q also get t, u, and v. It also requires renaming
    steps so that if P has its own local t, you do not attempt to have
    two variables named "t" in the outer-ized P.

    To bring this all back to C, this kind of problem does come up now
    and then, especially with "callback functions". My preferred method
    is not to add one parameter per pass-through variable, but rather
    to collect up the passed-through state in a "context" structure.
    The (no-longer-nested) "inner" procedures like P then read:

    struct P_context {
    int i; /* if there is an "i" */
    double w; /* the "w" seen above in the nested code */
    /* and so on -- a copy of "z" might be in here too */
    };

    void P(any regular args, struct P_context *ctx) {
    ... code ...
    ctx->w = value; /* as needed */
    ... more code ...
    }

    Actual situations in which P has a "pass-through" parameter for Q
    are quite rare (indeed, I think I have never come across one myself),
    and I would tend to go for ad-hoc solutions for those. (For instance,
    Q might just take a single "pointer to z" parameter, and P_context
    might have "Z_TYPE *zp;" as a member.)
    --
    In-Real-Life: Chris Torek, Wind River Systems
    Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
    email: forget about it http://67.40.109.61/torek/index.html (for the moment)
    Reading email is like searching for food in the garbage, thanks to spammers.
     
    Chris Torek, Oct 27, 2003
    #2
    1. Advertising

  3. Quinnie

    pete Guest

    Quinnie wrote:
    >
    > Hi,
    >
    > I have a homework assignment that I'm so confused and really need help
    > with. Here's the description, any help would be appreciated. Thanks!
    >
    > Assume we have a statically-scoped language with nested procedures.


    > any thoughts? Thanks!


    Seems to me, more like a topic for
    news:comp.programming

    --
    pete
     
    pete, Oct 27, 2003
    #3
    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. Russ Perry Jr
    Replies:
    2
    Views:
    4,288
    Russ Perry Jr
    Aug 20, 2004
  2. Ron
    Replies:
    1
    Views:
    310
  3. Neil Zanella

    nested procedures and the C language

    Neil Zanella, Nov 6, 2003, in forum: C Programming
    Replies:
    5
    Views:
    332
    osmium
    Nov 6, 2003
  4. Chad E. Dollins
    Replies:
    3
    Views:
    681
    Kai-Uwe Bux
    Nov 8, 2005
  5. request@no_spam.com
    Replies:
    5
    Views:
    458
Loading...

Share This Page