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

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

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