Path: csiph.com!weretis.net!feeder6.news.weretis.net!nntp.club.cc.cmu.edu!micro-heart-of-gold.mit.edu!newsswitch.lcs.mit.edu!ottix-news.ottix.net!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.compilers
Subject: Re: Add nested-function support in a language the based on a stack-machine
Date: Sat, 17 Feb 2018 16:39:04 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 76
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <18-02-034@comp.compilers>
References: <18-02-009@comp.compilers> <18-02-012@comp.compilers> <18-02-016@comp.compilers> <18-02-018@comp.compilers> <18-02-023@comp.compilers> <18-02-029@comp.compilers> <18-02-032@comp.compilers>
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="93689"; mail-complaints-to="abuse@iecc.com"
Keywords: code, algol60
Posted-Date: 17 Feb 2018 12:34:47 EST
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
Xref: csiph.com comp.compilers:1964

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 (there was an influential paper that convinced everyone of
that).  IIRC the additional cost is in updating the display on calls
and returns.

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

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.

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

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

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