Re: recursive nested functions

On Jun 25, 1:30 pm, nojb <n...@uchicago.edu> wrote:
> Hello,
>
> I'm writing a compiler for a language that admits recursive nested
> functions and I am stuck trying to figure out how to handle them. My
> objective is to lift all nested functions to top level and pass all
> their free variables explicitly as parameters. For this, I have to
> figure out which variables are free. So when I'm analyzing the body
> of each function, I record its free variables. But then obviously when
> I come across a function call, I have to add _its_ free variables to
> the list of the enclosing function. You can see how this will loop
> endlesly if we allow recursive functions...
>
> I would guess there is a standard way to handle this, so if anyone can
> point me to it, it would be greatly appreciated.
>
> Thank you very much,
> N
> [I think you'll find that the usual approach is to expand out to N levels
> for a relatively small N, then give up and generate normal calls. -John]


Check the literature on lambda lifting. Although the theory was
worked out for functional languages, it works for imperative ones,
too. You need to pass references around rather than values. Function
pointers generally need to be "fat" i.e. to include references to all
bound variables.


I'm not sure of the problem you are describing. It sounds like you
are confusing dynamic and static scopes. Lambda lifting makes sense
only in the context of static scopes. A function F that declares a
variable X will still declare X in the lifted code. Calls to a
function G originally nested within F will pass X (or a reference to
it), and G will accept the reference. If G calls itself recursively,
it passes the same reference to X it received. Same if it calls a
nested function H that ultimately calls G.


Gene

Return to the comp.compilers page.
Search the comp.compilers archives again.