Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > alternative to nested procedures

Reply
Thread Tools

alternative to nested procedures

 
 
Quinnie
Guest
Posts: n/a
 
      10-27-2003
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!
 
Reply With Quote
 
 
 
 
Chris Torek
Guest
Posts: n/a
 
      10-27-2003
In article <(E-Mail Removed) >
Quinnie <(E-Mail Removed)> 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 (4039.22'N, 11150.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.
 
Reply With Quote
 
 
 
 
pete
Guest
Posts: n/a
 
      10-27-2003
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
 
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
Quicktime Alternative, RealPlayer Alternative & Media Player Classic John Capleton Computer Support 3 12-05-2005 07:41 AM
Nested Vector Nester Classes are Nested in my Brain Chad E. Dollins C++ 3 11-08-2005 04:46 AM
Nested iterators (well, not nested exactly...) Russ Perry Jr Java 2 08-20-2004 06:51 PM
nested procedures and the C language Neil Zanella C Programming 5 11-06-2003 02:17 PM
Nested procedures and procedure parameters Ron C Programming 1 08-28-2003 02:47 PM



Advertisments