From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,99ab4bb580fc34cd X-Google-Attributes: gid103376,public From: wolff@inf.fu-berlin.de (Thomas Wolff) Subject: Re: Q: access to subprogram Date: 1996/07/10 Message-ID: <4s0qm7$htm@fu-berlin.de> X-Deja-AN: 167620947 references: <4rb9dp$qe6@news1.delphi.com> <4rud55$5b0@fu-berlin.de> <4rvo07$bbl@goanna.cs.rmit.edu.au> organization: Freie Universitaet Berlin x-access: 16 17 19 newsgroups: comp.lang.ada Date: 1996-07-10T00:00:00+00:00 List-Id: A few more responses and remarks about implementation and design issues of procedure parameters (please excuse if some of them are redundant due to other's remarks), consisting of five sections: 1. about the design decision 2. about the implementation and its assumed overhead 3. about incorrect implementations 4. about static chains 5. about future design issues ----------------------------------------------------------------------------- 1. about the design decision Robert A Duff: : Remember that the discussion during the design of Ada 9X was NOT about : "we don't know how to implement this in theory" -- it was more like, : "we've got a multi-target back end (back ends), and we don't want to : mess with it (them)". Also note that I argued strongly IN FAVOR of : downward closures, and lost the argument. To base design decisions for a language supposed to be an important one on compiler considerations is a very bad idea, I think! A shame that you lost that argument...; And Norman H. Cohen: : (By the way, I share Bob Duff's amazement at the noninclusion of downward : closures--we called them downward at the time--in Ada 95, and I say this : as one of those Bob described as urging the removal rather than the : addition of proposed Ada-95 features. I viewed the inclusion of downward : closures as the REMOVAL of an arbitrary restriction. The decision was : not made in ignorance. Bill Taylor had made what I considered an : irrefutable case for downward closures, showing how much easier it would : be to write iterators if downward closures were allowed. It came down to : a conflict between the interests of Ada programmers and the interests of : a minority of Ada implementors, and in this case the interests of the few : implementors using displays prevailed.) So the shame goes on this minority of Ada implementors who were so lame not to recognize how an efficient implementation with displays can be done. ----------------------------------------------------------------------------- 2. about the implementation and its assumed overhead Robert A Duff: : 1. Displays are too much trouble, in the presence of downward closures. No, you only need to find the right trick once. (How much trouble is "too much" anyway?) : 2. Therefore, if we have that feature, compiler writers are forced to : use static links (...) : : 3. Displays are clearly faster than static links, for normal direct calls. : : 4. Therefore, we've got a distributed overhead; QED. Due to the invalid first assumption, this pseudo-proof is bogus. Richard A. O'Keefe: : What happened? When did everyone forget? Indeed. : Yes, there is overhead: but the overhead of rewinding the display : is incurred only on entry to / exit from a formal procedure; there : need be *NO* extra overhead for calling visible procedures. Robert Dewar: : > ... the provision : > of closures would push you away from using displays, and hence No, ... Robert Dewar: : parameters in Pascal or Algol, if done right, clearly violates this, and : requires entire sections of displays to be saved and restored. But only for calls of formal procedures. : Steelman specifically excluded procedure parameters. One of the stated : reasons was to allow the use of simple mechanisms (i.e. displays) to : handle uplevel references. Ada 83 followed this design choice, and : Ada 95 did not. A reasonable change, but the inevitable possible : consequences was that displays would not fit well. However, Ada 95 I do not quite understand your argument about who followed which design choice as I thought according to this discussion both Adas cannot pass procedure parameters. However, contradicting the feature with display implementation is not an inevitable consequence as has meanwhile been shown in this thread. I said: : Why not just push the display on the stack and pass its address?? : (If you really wanted to pass the display itself for some reason, you : could still use the program's maximal display size, wasting a few : bytes in these occasional cases.) Robert Dewar: : That's the original Algol-60 approach but it is never used these : days that I know of, since it is in practice definitely inferior : to both static links and the use of global displays. It introduces : unconditionally a large overhead of copying the display at every : call whether or not it is useful to do so. This overhead would not have to be taken on every call as you say but only on calls of formal procedures. Don't you think this is acceptable? Robert A Duff: : I agree -- it's not *that* big of a deal. But "just push the display on : the stack" is an operation that involves compile-time-unknown-sized : stuff, which is where the complexity comes from. And "use the max" : involves link-time knowledge, and most compilers (while very smart at : compile time) are very stupid at link time, and changing that fact : involves a lot of work. Norman H. Cohen: : The size of a display for a given procedure IS known at compile time. : It is equal to the number of procedures that lexically surround that : procedure (give or take one, depending on the details of a given : implementation). Robert A Duff about my idea of implementing it: : The "solution above" is viable, but is not the simplest solution. The It is probably the simplest solution that uses displays. : simplest solution is to use static links. (And that solution has the : desirable property that calling via an access-to-procedure will not : involve inordinate overhead.) Even in the display solutions that do have overhead I would not call it "inordinate" - anyway, as Richard A. O'Keefe also describes, there need be no overhead at all. But I don't understand why you think a "simple" solution (which is disputable) is the best solution for such a basic thing. As I said before, I don't see how static chains can show an advantage without relying heavily on optimization. ----------------------------------------------------------------------------- 3. about incorrect implementations Robert Dewar: : By the way, over the years, many Pascal and Algol compilers have cheated. This is also known as the "most-recent" error. : You have to write a bit of a clever test program to see the difference : between properly restoring the full display environment and not bothering. The test program fits on a cake. - But then, how should I interpret your words: : In other words, the usual invariant for level N of a global display is : that it points to the most recent level N procedure on the dynamic : invocation scheme. This is just the way compilers have cheated, i. e. no correct implementation of the Algol semantics, said "most-recent" error. ----------------------------------------------------------------------------- 4. about static chains I said: : Why should displays be a menace where static links are not? Who would : actually prefer to really follow static links at all, effectively almost : *searching* for variables at run-time? Until now I thought this would : only be a theoretical concept and perhaps one of very early compilers. Robert A Duff: : Are you saying that static links are some sort of theoretical concept : from days-gone-by, and nowadays all smart compiler-writers use : displays? Certainly not true. I think *most* compiler-writers use : static links, just because it makes things simpler. The horrible : "searching" you imagine is ameliorated by simple CSE elimination. And : it's never terrible, since average nesting is approximately 0.01 levels : deep. Robert Dewar: : Static links are by far the more common way of handling uplevel : references, and are far from being "only a theoretical concept". : Most modern compilers use static links. There is no searching : involved, just loading the entries that are needed, and if they : are used frequently, they will stay in registers anyway. By "almost *searching*" I meant that the chain has to be followed until the desired level is reached, thus having a few indirections per access. I would, however, not like the idea that a compiler's efficiency in a basic design question depends on optimization. : In fact the idea of static links came a little later on, the early : Algol-60 compilers used displays. Thanks to you two to point out that static chains are really used today. (I still wonder why.) ----------------------------------------------------------------------------- 5. about future design issues I: : >I am sad about this, too. I have also always deplored that this : >feature was removed during Wirth's transition from Pascal to Modula, : >presumably for the same unconvincing reasons as used in this : >discussion. : Robert A Duff: : I was annoyed at that (about Modula-2) long before I joined the Ada 9X : project. I think the real story is that there are two totally different : features, and both are desirable: : : 1. You can pass procedures around, and copy them willy-nilly, and : save them in global variables. This is "call backs". Pascal : does not have this feature. Modula-2 does, and Ada 95 does. : : 2. You can pass procedures IN, and call them, but must never save : them in global variables. Pascal has this feature. Modula-2 : does not. Ada 95 does not, unless you count generic formal : subprograms, which support MOST of this, but not quite all, : and are overly verbose (IMHO). : : Both of the above are desirable, but not at the same time. Is there any research in the literature about making these two more compatible in terms of safety and efficiency? Robert A Duff: : >Compare my other response in this thread for remarks about the : >desirability of the discussed language feature. : : Please understand that I'm arguing from two opposing points of view : here. (1) I really think downward closures should have been included : in Ada 95, and (2) I'm trying to explain the arguments about why they : were not (which I disagree with, but are nonetheless rational : arguments). I understand this and have already quoted your previous remark : Also note that I argued strongly IN FAVOR of : downward closures, and lost the argument. Maybe your position was not strong enough because you thought yourself the feature would require overhead? Can we hope you'll take up the argument when it comes to Ada 99? ----------------------------------------------------------------------------- Thomas Wolff