alternative to nested procedures

[Quinnie]

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!

 

[Chris Torek]

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

 

[pete]

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