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

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


The address of a local function can be taken. When that function is
called from any context, possibly another thread, it has access to the
locals that were lexically apparent there.


> If you're suggesting that the stacks be shared among threads, then
> you're no longer talking about "threads" per se, but rather about


Stack *access* is shared among threads. E.g. a thread can register
a stack object in a shared queue (such as a synchronization wait queue).
As long as it is dequeued before that frame terminates, everything is
cool. Commonly done.


If a downward-only lexical closure is implemented as a pointer into some
threads's stack memory (plus a function) that object can be passed to
another thread and used (as long as the context which created that
closure doesn't terminate).


When that sort of thing is done with threads, we cannot have a single
display array per lexical scope being mutated.


If the stack closures maintain local displays which are immutable,
then it can work.


The function which is called from the other thread is using that
thread's stack, of course, for the parameter passing and return and
all. Also for its freshly instantiated locals. However, the material
in the captured lexical scope is in the original stack. So is the
display vector which accesses the multiple levels of it.


The display is only used for acessing the lexical things outside of the
local function's body; its own locals and parameters are on the local
stack.


Ahd here is the kicker: *that* local environment can be captured by that
thread, together with that other environment. No problem; that thread
has a copy of the display in its stack frame and extends it with a pointer
to its own stuff. So now there is a display which references two
different stacks.


> No worries. IME, displays don't get much respect from modern
> textbooks - they are mentioned mostly in passing.


This is probably because of


1) a few decades of dominance of C, C++ and Java whose standard dialects
don't have scope capturing local functions. So no interest in the
mainstream software dev in local functions as such.
OOP techniques somewhat make up for the lack of closures. You use
an object with a method; the captured stuff is in the object.
Languages with "class scope" make it easy for the code in a class
method to access the object with simple, unqualified name references
like "foo", so that at least the body of a method is comparably
convenient to that of a closure.


2) real languages have proper lexical closures with indefinite
lifetimes. The display concept is still relevant but probably turn into
something else under a different name. (We are seeing much more use
of and interest in languages that have closures; but that interest is
largely in new ones that are poorly optimized.)


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


Displays, or something equivalent, is necessary to work out the nesting
of captured lexical scopes. Different contours of the scope have dynamic
activations that differ in lifetimes and have to be separate objects.
Those objects somehow have to be centrally referenced from places that
*somehow* have simultaneous access to them.


In a purely functional language, a simplifying aspect is that bindings
are immutable. We can capture a lexical scope by copying it; the user
cannot tell the difference between that and the original scope.
If variables are mutable, you know that you have a copy because a
variable assignment in the original scope isn't reflected in the
captured one.

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