Path: csiph.com!weretis.net!feeder6.news.weretis.net!feeder.usenetexpress.com!feeder-in1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Kaz Kylheku <217-679-0842@kylheku.com> Newsgroups: comp.compilers Subject: Re: Add nested-function support in a language the based on a stack-machine Date: Sat, 17 Feb 2018 16:13:10 +0000 (UTC) Organization: Aioe.org NNTP Server Lines: 122 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <18-02-032@comp.compilers> References: <18-02-009@comp.compilers> <18-02-012@comp.compilers> <18-02-016@comp.compilers> <18-02-018@comp.compilers> <18-02-023@comp.compilers> <18-02-029@comp.compilers> Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="82883"; mail-complaints-to="abuse@iecc.com" Keywords: code Posted-Date: 17 Feb 2018 11:24:39 EST X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:1963 On 2018-02-15, George Neuner 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 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.