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

Groups > comp.compilers > #1966

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

Show key headers only | View raw

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?

>(there was an influential paper that convinced everyone of
>that).  IIRC the additional cost is in updating the display on calls
>and returns.

Which is no different from the overhead to maintain static links, and
faster to use when you need non-locals more than one lexical level
distant.

>Unfortunately, I don't have a reference to the paper above.  You can
>probably find a reference in old compiler books.

I'd really like to see that paper to find out what they are comparing
to display [and using what language].

It certainly is true that closeure conversion is a better solution
overall because it flattens all non-local accesses to use a single
indirection ... but it also significantly complicates the compiler,
and creates a need for handling wide pointers (or equivalent).  Many
useful languages simply don't need that extra complexity.


>Of course, given that you are using a different language that probably
>uses nested functions quite differently from what was used in that
>paper, you may want to reevaluate the balance of display vs. static
>chains.

I would never use static chains ... if display wasn't viable I would
jump straight to closure conversion.


>>> The basic problem
>>> is that, while they are quite useful for an Algol-like language, they
>>> can be problematic for an OO or functional language.
>
>The funny thing is that, while displays were found to be suboptimal
>for Algol-like languages, they can be used for type inclusion tests,
>used in many OO languages [Cohen:acm:toplas:1991].  There are a bunch
>of other solutions to this problem, so I don't know if displays are
>used for this purpose in current systems, though.
>
>@Article{Cohen:acm:toplas:1991,
>  author =	"Norman H. Cohen",
>  title =	"Type-Extension Type Tests Can Be Performed In Constant
>		 Time",
>  journal =	"ACM Transactions on Programming Languages and
>		 Systems",
>  volume =	"13",
>  number =	"4",
>  pages =	"626--629",
>  month =	oct,
>  year = 	"1991",
>  refs = 	"2",
>  checked =	"19940624",
>  source =	"Dept. Library",
>  keywords =	"class, descriptor, display, extensible data type,
>		 inheritance, membership test, object-oriented
>		 programming, type extension, type test",
>  note = 	"Technical Correspondence",
>  abstract =	"Wirth's proposal for type extensions includes an
>		 algorithm for determining whether a give value belongs
>		 to an extension of a given type. In the worst case,
>		 this algorithm takes time proportional to the depth of
>		 the type-extension hierarchy. Wirth describes the loop
>		 in this algorithm as ``unavoidable,'' but in fact, the
>		 test can be performed in constant time by associating a
>		 ``display'' of base types with each type descriptor.",
>  xref = 	"Wirth:acm:toplas:1988",
>  reffrom =	"Corney:Gough:plasa:1994",
>}
>
>I dimly remember a letter to the editor by Wirth where he appreciated
>that finally a good use for the display had been found.

Thanks for that pointer ... going to have to read that.


>>Displays, or something equivalent, is necessary to work out the nesting
>>of captured lexical scopes. Different contours of the scope have dynamic
>>activations that differ in lifetimes and have to be separate objects.
>>Those objects somehow have to be centrally referenced from places that
>>*somehow* have simultaneous access to them.
>
>Static link chains work fine.

Yes, they do work - but they are the lowest performance option for
non-local accesses.


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