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

On Wed, 14 Feb 2018 18:06:40 +0000 (UTC), Kaz Kylheku
<217-679-0842@kylheku.com> wrote:


>On 2018-02-14, George Neuner <gneuner2@comcast.net> wrote:
>
>> 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.)


I understand, and you're correct that the display needs to be counted
as part of the thread switch context. But each thread also would be
using from a separate stack, so having the entire display saved in
each frame is overkill when all that's needed is a single pointer.


If you're suggesting that the stacks be shared among threads, then
you're no longer talking about "threads" per se, but rather about
"scheduler activations", which are subtly different from threads.
I'm not aware of any non-research system that is based on activations.




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


No worries. IME, displays don't get much respect from modern
textbooks - they are mentioned mostly in passing. The basic problem
is that, while they are quite useful for an Algol-like language, they
can be problematic for an OO or functional language.


George

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