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

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/

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