Path: csiph.com!weretis.net!feeder6.news.weretis.net!feeder.usenetexpress.com!feeder-in1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: George Neuner Newsgroups: comp.compilers Subject: Re: Add nested-function support in a language the based on a stack-machine Date: Thu, 1 Mar 2018 13:48:26 -0500 (EST) Organization: A noiseless patient Spider Lines: 105 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <18-03-002@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> <18-02-034@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 8bit Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="3555"; mail-complaints-to="abuse@iecc.com" Keywords: design, code Posted-Date: 01 Mar 2018 13:48:26 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:1966 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 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