Re: nested functions

reji_thomas@symantec.com wrote:
> From my understanding, a compiler uses
>
> 1. Lambda lifting where the nested function is hoisted to global level
> passing free variables through an env pointer or as explicit arguments.
>
> 2.Static chaining or displays which uses pointers to the corresponding
> stackframe in which the non local variable is defined.


It's rare to see mentioned in the same context as the former is
generally associated with functional languages and the latter
procedural.


First, you can use lambda lifting in a procedural language, but all
variables that are modified by an inner procedure must be passed by
reference (see fx. Guy Steele's "ultimate lambda" paper). If that's a
significant number *and* the inner procedure can't outlive the outer
(can't "escape" it context), then you may be better of with static
chaining.


Static chaining & displays for functional languages have been used
(see fx. Paul Appel's papers), but there are two problems: they are
prone to space leaks (in the case of the inner context surviving the
outer) and they are generally slower that passing just the needed
parameters in registers.




> One of my questions is
>
> whether lambda lifting cannot solve any cases which chaining/displays
> can only solve?.


I hope I answered that question. The answer is no (assuming the passing
by reference as needed).


> My next doubt is regarding the nested function support from GCC using
> trampolines. I could see that in case of function pointers of nested
> functions GCC was generating the code on the stack to move the frame
> pointer of the function in which the nested function is nested to ECX
> and then to do a jump to the nested function.
>
>
> My question is
> Whether GCCs support for nested functions is similar to nested function
> support in functional languages like haskell/scheme and do trampolines
> provide any advantage other than access time.?
  >
  > I realise that you cannot return a nested func pointer and pass it
  > around since theres no way GCC associates state with the ptr.


Exactly! Trampolines are a sad compromise to implement closure-like
structures in a way that can co-exist with ordinary C (which expects
function pointers to point to code, not data structures). For language
implementations with direct support for closures, it's generally
better to use a structure with free variables and a function pointer
(very much like a C++ object and one virtual function).


There are exceptions to this which are hard to classify. Check
"Optimization for Lazy Functional Languages" by Urban Boquist for a
really all-out approach (and google "jhc haskell").


Regards
Tommy

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