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

George Neuner <gneuner2@comcast.net> wrote:
> On Fri, 02 Mar 2018 09:30:42 GMT, anton@mips.complang.tuwien.ac.at
> (Anton Ertl) wrote:
>
> >George Neuner <gneuner2@comcast.net> writes:
> >>On Sat, 17 Feb 2018 16:39:04 GMT, anton@mips.complang.tuwien.ac.at
> >>(Anton Ertl) wrote:
> >>
> >>>Kaz Kylheku <217-679-0842@kylheku.com> writes:
> >>>>On 2018-02-15, George Neuner <gneuner2@comcast.net> wrote:
> >>>>> No worries. IME, displays don't get much respect from modern
> >>>>> textbooks - they are mentioned mostly in passing.
> >>>>
> >>>>This is probably because of
> >>>
> >>>This is because displays were found to be more costly for Algol-like
> >>>languages
> >>
> >>More costly than what?
> >
> >Static link chains.
> >
> >>> IIRC the additional cost is in updating the display on calls
> >>>and returns.
> >>
> >>Which is no different from the overhead to maintain static links
> >
> >Wrong. Consider the following nesting of functions:
> >
> >A
> > B
> > C
> >D
> >
> >With a display, in C you have built up a display pointing to the
> >frames of C, B, and A. When performing a call from C to D, you throw
> >that away and replace it with a display pointing to just the frame of
> >D. When returning from D, you have to restore the old display.
>
> No. D and A are at the same lexical level. On entry, D will replace
> A's entry in the display, and will restore A's entry on exit.
>
> The scope rules say D can't see or call B or C. If it calls A, then A
> replaces it at the same lexical level. When A returns, D's link is
> restored.


You assume no procedure parameters (boring case). With procedure
parameters C can pass itself (or B or other procedure at the
same lexical level) to D and D can call it. So dynamic chain
can be:


A B C D C


and innermost C needs to see A variables in its display.
IIUC resolving this required copies that make display
management O(n) (n being depth of static chain).


> No problem. And no need to preserve the whole display.
>
> >If you don't maintain a static link chain, you have to save the
> >complete display of C on the call and restore it on return.
>
> No you don't.
>
>
> >Note that D may itself call functions that need more display, so you don't get
> >away with just saving and restoring the first slot of the display.
> >IIRC this was the variant looked at in the paper that concluded that
> >displays are more costly.
>
> That is simply wrong unless you change the whole semantics.
>
> As long as call sites are restricted to being within the definition
> scope of the called function [as is true in Pascal],


Pascal without procedural parameters.


--
                                                            Waldek Hebisch

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