Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1955

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

Show all headers | View raw

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

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

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Add nested-function support in a language the based on a stack-machine dror.openu@gmail.com - 2018-02-12 11:25 -0800
  Re: Add nested-function support in a language the based on a stack-machine dror.openu@gmail.com - 2018-02-12 14:16 -0800
    Re: Add nested-function support in a language the based on a stack-machine Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2018-02-13 12:10 +0100
  Re: Add nested-function support in a language the based on a stack-machine Louis Krupp <lkrupp@nospam.pssw.com.invalid> - 2018-02-13 00:42 -0700
    Re: Add nested-function support in a language the based on a stack-machine Kaz Kylheku <217-679-0842@kylheku.com> - 2018-02-14 00:59 +0000
      Re: Add nested-function support in a language the based on a stack-machine George Neuner <gneuner2@comcast.net> - 2018-02-13 22:04 -0500
        Re: Add nested-function support in a language the based on a stack-machine Kaz Kylheku <217-679-0842@kylheku.com> - 2018-02-14 18:06 +0000
          Re: Add nested-function support in a language the based on a stack-machine George Neuner <gneuner2@comcast.net> - 2018-02-15 11:41 -0500
            Re: Add nested-function support in a language the based on a stack-machine Kaz Kylheku <217-679-0842@kylheku.com> - 2018-02-17 16:13 +0000
              Re: Add nested-function support in a language the based on a stack-machine anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2018-02-17 16:39 +0000
                Re: Add nested-function support in a language the based on a stack-machine George Neuner <gneuner2@comcast.net> - 2018-03-01 13:48 -0500
                Re: Add nested-function support in a language the based on a stack-machine Kaz Kylheku <217-679-0842@kylheku.com> - 2018-03-01 19:26 +0000
                Re: Add nested-function support in a language the based on a stack-machine Kaz Kylheku <217-679-0842@kylheku.com> - 2018-03-02 00:38 +0000
                Re: Add nested-function support in a language the based on a stack-machine George Neuner <gneuner2@comcast.net> - 2018-03-02 02:48 -0500
                Re: Add nested-function support in a language the based on a stack-machine rpw3@rpw3.org (Rob Warnock) - 2018-03-03 16:00 +0000
                Re: Add nested-function support in a language the based on a stack-machine anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2018-03-02 09:30 +0000
                Re: Add nested-function support in a language the based on a stack-machine anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2018-03-05 15:01 +0000
                Re: Add nested-function support in a language the based on a stack-machine George Neuner <gneuner2@comcast.net> - 2018-03-05 15:51 -0500
                Re: Add nested-function support in a language the based on a stack-machine George Neuner <gneuner2@comcast.net> - 2018-03-05 14:39 -0500
                Re: Add nested-function support in a language the based on a stack-machine John Levine <johnl@taugh.com> - 2018-03-06 04:31 +0000
                Re: Add nested-function support in a language the based on a stack-machine Kaz Kylheku <217-679-0842@kylheku.com> - 2018-03-06 18:17 +0000
                Re: Add nested-function support in a language the based on a stack-machine Kaz Kylheku <157-073-9834@kylheku.com> - 2018-03-11 03:19 +0000
                Re: Add nested-function support in a language the based on a stack-machine Tomasz Kowaltowski <tk@ic.unicamp.br> - 2018-03-06 12:10 -0300
                Re: Add nested-function support in a language the based on a stack-machine bartc <bc@freeuk.com> - 2018-03-06 19:02 +0000
                Re: Add nested-function support in a language the based on a stack-machine antispam@math.uni.wroc.pl - 2018-04-29 16:29 +0000
              Re: Add nested-function support in a language the based on a stack-machine George Neuner <gneuner2@comcast.net> - 2018-03-01 13:49 -0500
    Re: Add nested-function support in a language the based on a stack-machine George Neuner <gneuner2@comcast.net> - 2018-02-13 22:37 -0500
  Re: Add nested-function support in a language the based on a stack-machine George Neuner <gneuner2@comcast.net> - 2018-02-13 23:27 -0500
  Re: Add nested-function support in a language the based on a stack-machine Shoefoot <shoefoot@gmail.com> - 2018-02-14 12:27 -0800

csiph-web