Re: Add nested-function support in a language the based on a stack-machine

On 2018-02-14, George Neuner <gneuner2@comcast.net> wrote:
> On Wed, 14 Feb 2018 00:59:34 +0000 (UTC), Kaz Kylheku <217-679-0842@kylheku.com> wrote:
>>On 2018-02-13, Louis Krupp <lkrupp@nospam.pssw.com.invalid> wrote:
>>> On Mon, 12 Feb 2018 11:25:36 -0800 (PST), dror.openu@gmail.com 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
>>same time.
>>
>>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 nesting.
>
> 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
> level.
>
> The preamble of a function at, e.g., level 3, preserves display[3] in
> its own stack frame, and sets display[3] to point to its own frame.
> The postscript of the function restores the original display[3] value
> when the function ends.
> [Obviously, the compiler must keep track of lexical levels in order
> that each function update the proper display entry.]


Yes; it is clear that there can be a single display vector which is
associated with the entire lexical scope as a whole, and then the
local scopes just mutate the entries in the vector, taking care
to save and restore them (which requires some local storage, by the
way, but less than in the scheme I describe).


The problem with this saving and restoring is that it's not thread safe.
If there are multiple invocations of the p2 scope, and they can be
entered by independent threads, we're in trouble if there is a single
pointer to that scope in a single display. (Excluding that from being a
requirement is fairly reasonable.)


The model I described simply replicates the display, allowing immutable
local copies of it in each frame. When a scope is entered via
indirection, it just installs a context pointer referencing the display.
(Of course, that context pointer has to be saved and restored.
It could just be the regular frame pointer, with the display being
at some well known offset in the frame.)


> When a function at level 4 needs something at level 2, it just looks
> to display[2] to find the proper stack frame. Regardless of
> intervening recursions, the lexical environment is maintained:
> display[2] always will point to the latest invocation of the level 2
> function which contains the current (level 4) function.


(Under what I described, that display[2] is in that function's own
display[] array rather than a shared one. That display[2] is
initialized and never mutated.)


> No, you're missing something. I just haven't figured out what.


I'm missing the space optimization that a single display can be
(serially) shared, in spite of multiple activations of scopes, as long
as the entries are saved and restored.

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