|From:||George Neuner <email@example.com>|
|Date:||Tue, 13 Feb 2018 22:04:29 -0500|
|Organization:||A noiseless patient Spider|
|References:||18-02-009 18-02-012 18-02-016|
On Wed, 14 Feb 2018 00:59:34 +0000 (UTC), Kaz Kylheku <firstname.lastname@example.org> wrote:
>On 2018-02-13, Louis Krupp <email@example.com> wrote:
>> On Mon, 12 Feb 2018 11:25:36 -0800 (PST), firstname.lastname@example.org wrote:
>>>Suppose I have a simple C-like programming language: ...
>>>Like you can see, it supports nested functions.
>> gcc supports nested functions as an extension to C. Compiling this
>> program with -O0 -fdump-tree-all and looking at the generated files
>> might give you an idea of one way to do it: ...
>> Apparently, gcc chains stack frames, and accessing uplevel variables,
>> as when p3 uses k1 and k2, seems like it would take O(n) time, where n
>> is the nesting level.
>> The alternative, a display vector, seems like it would be easier to
>The problem is that these functions can recurse, including mutually.
>So that is to say, you can end up with a situation in which you have
>a single activation of main with a single k1 variable, but multiple
>activations of p2, with multiple k2's all being live at the
>To complicate things, the multiple active p2 functions can be lifted
>into function pointers, all of which are simultaneously valid.
>Each of those p2 pointers could be called back by some external function.
>Those calls have to establish an environment which resolves to the
>correct k2, and at the same time to the one and only k1.
>That doesn't rule out display vectors, but it seems like each function
>activation has to have its own complete display vector.
As long as each function creates a new stack frame when called, then
recursion is not relevant and a single display is sufficient to handle
The display tracks lexical parentage [who defined who], not call
chain parentage. Each display entry points to the stack frame of the
last function invoked that was defined at the corresponding lexical
The preamble of a function at, e.g., level 3, preserves display in
its own stack frame, and sets display to point to its own frame.
The postscript of the function restores the original display value
when the function ends.
[Obviously, the compiler must keep track of lexical levels in order
that each function update the proper display entry.]
When a function at level 4 needs something at level 2, it just looks
to display to find the proper stack frame. Regardless of
intervening recursions, the lexical environment is maintained:
display always will point to the latest invocation of the level 2
function which contains the current (level 4) function.
>For instance the p2 level functions need a two-level vector. Under
>the same main invocation, they share the vec entry pointing to
>the main frame; but each one has a different vec referencing its
>When a p3 executes it has its own 3 element vec. The vec and
>vec are copied from the parent p2. If a pointer to a p3 is captured,
>then its vec correctly references the particular dynamic p2 instance
>in which it is scoped; vec references its own environment.
>Under this scheme, we basically we need o(n^2) storage for the vectors,
>for n nesting levels in the absence of recursion.
No, you're missing something. I just haven't figured out what.
>The compiler can determine which functions aren't subject to indirection
>and avoid allocating the trampoline space for that.
With the classic implementation, every non-leaf function has to do its
part to maintain the lexical environment. But the allocation overhead
is just one saved pointer per stack frame.
>[As I recall, you do need a display with a pointer for each lexical scope,
>but so long as you don't expect closures to work, you can do it in
>constant time with a fixed location where each scope stores its
>current frame pointer. If you want closures, then you're into tree
>shaped stacks and garbage collected stack frames. -John]
You still do have closures of sorts ... they just are distributed
through the stack frames of the current function call chain.
A display cannot handle persistent closures, such as in Lisp, where a
nested function may be invoked after its parent terminates, outside of
the runtime environment that defined it.
Return to the
Search the comp.compilers archives again.