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: George Neuner Newsgroups: comp.compilers Subject: Re: Add nested-function support in a language the based on a stack-machine Date: Tue, 13 Feb 2018 22:04:29 -0500 Organization: A noiseless patient Spider Lines: 93 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <18-02-018@comp.compilers> References: <18-02-009@comp.compilers> <18-02-012@comp.compilers> <18-02-016@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 8bit Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="7034"; mail-complaints-to="abuse@iecc.com" Keywords: code Posted-Date: 13 Feb 2018 22:20:19 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:1955 On Wed, 14 Feb 2018 00:59:34 +0000 (UTC), Kaz Kylheku <217-679-0842@kylheku.com> wrote: >On 2018-02-13, Louis Krupp 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.] 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. >For instance the p2 level functions need a two-level vector. Under >the same main invocation, they share the vec[0] entry pointing to >the main frame; but each one has a different vec[1] referencing its >own frame. > >When a p3 executes it has its own 3 element vec[]. The vec[0] and >vec[1] are copied from the parent p2. If a pointer to a p3 is captured, >then its vec[1] correctly references the particular dynamic p2 instance >in which it is scoped; vec[2] 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. George