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

Groups > comp.compilers > #1971

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

Show key headers only | View raw

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.

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

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.

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

>>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).  Relative
hardware costs have also shifted somewhat.  Bottom line: Better
reevaluate the options yourself.

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

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