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

Groups > comp.compilers > #1976

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

Show all headers | View raw

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.

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], and every
function does its little part to maintain the display, then there is
NO POSSIBLE function call sequence that requires saving/restoring the
whole display.

Each function needs only save/restore the single display entry for its
own lexical level.  Scope visibility rules dictate that no function
can see lower into the display than its own level - so what those
entries point to is irrelevant.



>If you maintain a static link chain, you can restore the display of C
>from the static link chain, but you now have the cost of maintaining
>the static link chain and in addition the cost of maintaining the
>display, which is obviously more costly than just the static chain
>alone.  If you go that way, you can actually produce an intermediate
>scheme, where you cache static link accesses that you need, and the
>cached accesses are similar to (the needed part of) a display.

First, your example does not show any need for a static chain.

Second: the cost to maintain a display is just a single extra pointer
field in the call frame, one pointer copy and 2 pointer stores.

FYI, the amortized cost of a display MAY be less than to maintain the
static chain.

For a static chain:

 - a call sideways in the same scope needs the same link as the
   caller. That can be fetched from the caller's frame.
but
 - a call upwards to a higher scope (such as C->D in your example)
   needs a link pointer which it doesn't have available locally.
   The preamble code must go up the caller's chain to find the correct
   scope link to put in the new frame.


OTOH, the steps to maintain the display are the same regardless of
what function is called:
 - save the display entry for my lexical level.
 - replace the display entry with a pointer to my frame.
 - restore the display entry on exit.



>>I'd really like to see that paper to find out what they are comparing
>>to display [and using what language].
>
>The language was probably Algol or one of it's direct offspring.
>
>Anyway, if I get around to it, I will search for a reference to the
>paper in our library, but if someone else can supply the reference,
>that would be cool.

I really would like to see it.  Algol doesn't do anything that would
make a display more work than static chaining.  But it would matter
what code base they studied and how those programs were written.  As
you mention below, single level accesses are very cheap with static
links [deeper accesses are not].

I can't agree or disagree with a paper I haven't read.  And certainly
I can't refute it's conclusions.


>>>Static link chains work fine.
>>
>>Yes, they do work - but they are the lowest performance option for
>>non-local accesses.
>
>The first non-local level has the same performance as a display.  Are
>deeper accesses frequent enough to pay for the increased cost of
>maintaining the display?  The paper's answer was no, but that may vary
>from language to language (and with usage patterns).

That's true.  If the majority of non-local accesses are a single level
away, then the display has no advantage for access.  But it still may
have an advantage for maintenance.

It only takes a few upward function calls or deep non-local accesses
to F_ performance of a static chain.


>hardware costs have also shifted somewhat.  Bottom line: Better
>reevaluate the options yourself.

Good advice !!!

There still are plenty of uses for simple Pascal-like languages.  Many
DSL applications simply don't need multi-threading, objects, or other
stuff that a general purpose language might need.

Displays are just a tool in your toolkit ... you need to read the
directions and use them appropriately.


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