* Re: Q: access to subprogram
@ 1996-07-15 0:00 tmoran
1996-07-15 0:00 ` Robert Dewar
0 siblings, 1 reply; 133+ messages in thread
From: tmoran @ 1996-07-15 0:00 UTC (permalink / raw)
In <dewar.837008174@schonberg> Robert Dewar said:
>(although as I mentioned in an earlier note, it is what Intel implements
>in their hardware - the ENTER instruction).
>...
>I wonder who designed this feature at Intel? Someone who knew a bit, but
>not really enough, about how to deal with up level displays. The ENTER
Has anyone ever published a genealogy of CPU architectures? My
impression has always been that the Intel, or West Coast, architecture
derived from HP which derived from Burroughs. The 'display' would seem
to follow that. (As opposed to the Dec/C/East Coast architecture ;)
^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-15 0:00 Q: access to subprogram tmoran @ 1996-07-15 0:00 ` Robert Dewar 0 siblings, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-15 0:00 UTC (permalink / raw) tmoran asks " Has anyone ever published a genealogy of CPU architectures? My impression has always been that the Intel, or West Coast, architecture derived from HP which derived from Burroughs. The 'display' would seem to follow that. (As opposed to the Dec/C/East Coast architecture ;)" There is a fairly complete history of the designb of Intel architectures in my book on microprocessors (McGraw Hill 1990). There is no HP or Burroughs influence to speak of in these designs (at least not up through the 8086, it is certainly possible that someone familiar with HP or Burroughs machines was involved later on). ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram @ 1996-07-05 0:00 tmoran 1996-07-06 0:00 ` Robert A Duff 0 siblings, 1 reply; 133+ messages in thread From: tmoran @ 1996-07-05 0:00 UTC (permalink / raw) So if one is interfacing with a system that uses call-backs, any target of a call-back can only appear in the main procedure if the relevant 'type xxx is access procedure yyy' also appears in the main procedure? So even with a wonderful set of bindings done as library routines to handle all the details, the minimum Windows program requires the user to write a main procedure (which may be trivial) and a separate package that does the work. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-05 0:00 tmoran @ 1996-07-06 0:00 ` Robert A Duff 0 siblings, 0 replies; 133+ messages in thread From: Robert A Duff @ 1996-07-06 0:00 UTC (permalink / raw) In article <4rjvo0$7gg@news1.delphi.com>, <tmoran@bix.com> wrote: >So if one is interfacing with a system that uses call-backs, any target >of a call-back can only appear in the main procedure if the relevant >'type xxx is access procedure yyy' also appears in the main procedure? Clearly, a call-back function has to live "forever" -- you're handing its address off to, say, some windowing system that will call it whenever the mouse is clicked. Therefore, the callback function typically has to live as long as the whole program. Unfortunately, the main subprogram does not last as long as the whole program. Lots of package elaboration can happen before the main subprogram starts, and tasks can keep running for a long time after the main subprogram ends. Given this model, which has existed since Ada 83, it makes no sense to have callbacks nested with the main subprogram (or any other subprogram). You can of course complain that this is the wrong model, or you can complain, yeah but I don't need no stinkin' tasks, so why do I have to be bothered with all this extra complexity. Note also that the main subprogram can be recursive and reentrant. For example, suppose a library package creates a task that calls the main subprogram (in parallel with the "normal" call to the main subprogram, from the environment task). Clearly, there had better not be any callback functions in there. >So even with a wonderful set of bindings done as library routines to >handle all the details, the minimum Windows program requires the user >to write a main procedure (which may be trivial) and a separate package >that does the work. There is no requirement to even have a main procedure at all (in Ada 95). Alternatively, even if there *is* a main subprogram, you should be able to write it in C, if you like. One final point: It's hard for me to get too excited about not being able to put callback functions inside the main subprogram, because lots of people have done lots of callback stuff in C, and you can't put a callback function inside the main function in C, either (you can't nest functions AT ALL in C). - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Q: access to subprogram @ 1996-07-02 0:00 tmoran 1996-07-02 0:00 ` Robert A Duff ` (3 more replies) 0 siblings, 4 replies; 133+ messages in thread From: tmoran @ 1996-07-02 0:00 UTC (permalink / raw) Could someone please explain "subprogram must not be deeper than access type". I want package utilities to offer type p is access procedure(x:in integer); and procedure do_stuff(how : in p); But if my main program 'with utilities' and procedure this_is_how(x:in integer); .. utilities.do_stuff(this_is_how'access); I get that message from GNAT 3.04 for DOS. I also note the same problem prevents compilation of the PMV16 OS/2 bindings, and is gotten around in the new OS/2 bindings with "this_is_how'unrestricted_access", which I don't see in the LRM. The message indicates an understandable problem, but what's the workaround to allow my package utilities to offer a do_stuff procedure. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 tmoran @ 1996-07-02 0:00 ` Robert A Duff 1996-07-02 0:00 ` Robert Dewar ` (16 more replies) 1996-07-24 0:00 ` Jon S Anthony ` (2 subsequent siblings) 3 siblings, 17 replies; 133+ messages in thread From: Robert A Duff @ 1996-07-02 0:00 UTC (permalink / raw) In article <4rb9dp$qe6@news1.delphi.com>, <tmoran@bix.com> wrote: >Could someone please explain > "subprogram must not be deeper than access type". Here, "deeper" means more nested within a subprogram or block_stm or task_body. Nested within a subprogram is the usual problem. >I want package utilities to offer > type p is access procedure(x:in integer); >and > procedure do_stuff(how : in p); > >But if my main program 'with utilities' and > procedure this_is_how(x:in integer); >.. > utilities.do_stuff(this_is_how'access); Right, that's illegal. You need to put This_Is_How in a library package; then it will work. The main subprogram is a subprogram, and therefore represents a deeper level of nesting. You can't take 'Access of something *inside* a subprogram, and let that pointer value live outside the subprogram. Note that Ada tasks can keep running long after the main subprogram is done. >I get that message from GNAT 3.04 for DOS. I also note the same problem >prevents compilation of the PMV16 OS/2 bindings, and is gotten around >in the new OS/2 bindings with "this_is_how'unrestricted_access", which >I don't see in the LRM. The message indicates an understandable >problem, but what's the workaround to allow my package utilities to >offer a do_stuff procedure. The Unrestricted_Access attribute is indeed not part of the Ada language. It is a GNAT-specific extension. I've used it some in my own code, I must admit. It's dangerous, in the sense that if you leave the scope containing This_Is_How, and then call through the pointer, you will get nonsense. During the design of Ada 9X, we proposed a SAFE way of taking 'Access of more-deeply-nesting subprograms. To this day, I remain astonished and sad that this particular feature didn't make it into Ada 95. After all, even Pascal has that feature! And GNU C, which allows nested functions (unlike standard C) allows this feature. The work-around is to use generics. Pass in This_Is_How as an actual to a generic formal procedure. This is verbose, and doesn't allow recursion. Alternatively, bully your favorite Ada compiler vendor to support 'Unrestricted_Access. This is sad, since 'Unrestricted_Access is inherently unsafe, whereas we know how to provide the same functionality safely. Sigh. Note also that 'Unrestricted_Access on objects is even less safe -- it can produce a totally meaningless pointer from the start. I would much prefer if GNAT had separated these two things into two separate features. - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 ` Robert A Duff @ 1996-07-02 0:00 ` Robert Dewar 1996-07-03 0:00 ` Jon S Anthony ` (15 subsequent siblings) 16 siblings, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-02 0:00 UTC (permalink / raw) "Note also that 'Unrestricted_Access on objects is even less safe -- it can produce a totally meaningless pointer from the start. I would much prefer if GNAT had separated these two things into two separate features." Now Bob, let's not get *too* carried away with worrying about the safety of this feature! 'Unrestricted_Access on an object is *exactly* equivalent to taking the 'Address of something and then unchecked_converting it to a pointer, something that was often done in Ada 83 days, but clearly Unrestricted_Access is preferable since at least it is typed. As to making two separate features, hmmmm ... after all 'Access itself in Ada really is used for two totally difference purposes, so the use of Unrestricted_Access for two similarly different purposes seemed quite consistent to me :-) ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 ` Robert A Duff 1996-07-02 0:00 ` Robert Dewar @ 1996-07-03 0:00 ` Jon S Anthony 1996-07-03 0:00 ` Robert Dewar ` (8 more replies) 1996-07-03 0:00 ` Fergus Henderson ` (14 subsequent siblings) 16 siblings, 9 replies; 133+ messages in thread From: Jon S Anthony @ 1996-07-03 0:00 UTC (permalink / raw) In article <Dtxu2p.97F@world.std.com> bobduff@world.std.com (Robert A Duff) writes: > During the design of Ada 9X, we proposed a SAFE way of taking 'Access of > more-deeply-nesting subprograms. To this day, I remain astonished and > sad that this particular feature didn't make it into Ada 95. After > all, even Pascal has that feature! And GNU C, which allows nested > functions (unlike standard C) allows this feature. Bob, Is there an "elevator version" of why people didn't want this in? Tucker, if you are reading this, what swayed you to not let this in???? It's not one of those things that bothers me all that much (well, it hasn't) but it is indeed curious... /Jon -- Jon Anthony Organon Motives, Inc. 1 Williston Road, Suite 4 Belmont, MA 02178 617.484.3383 jsa@organon.com ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Jon S Anthony @ 1996-07-03 0:00 ` Robert Dewar 1996-07-03 0:00 ` Mark A Biggar ` (7 subsequent siblings) 8 siblings, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-03 0:00 UTC (permalink / raw) Jon asks: "Is there an "elevator version" of why people didn't want this in? Tucker, if you are reading this, what swayed you to not let this in???? It's not one of those things that bothers me all that much (well, it hasn't) but it is indeed curious..." The history is as follows. Ada 83 is carefully designed so that a display model can be efficienctly used for uplevel references (I am talking about a single global display, or more accurately one display per task). The above is fact, and is not open to question or opinion :-) Many people, me included, feel that the display model is more efficient, especially for Ada programs which are often deeply nested and often contain up level references. That however is open to argument (although I think the case for displays is pretty solid). Anyway the correctness of this argument is not relevant to the point at hand. Several implementations (notably Alsys and RR), accepting this argument, use displays for up level references. Once you introduce unrestricted access to procedures, displays are a bit of a menace, and probably this tips the scales in favor of static links (if you believe like me that displays are more efficient, this can also be read as meaning that the introduction of unrestricted access to procedures would introduce distributed inefficiency -- but that still is NOT the reason this feature was excluded). However, there was a real concern that existing implementations not be too badly discombobulated by Ada 95, *especially* in the code generatoin department (remember that a typical vendor like Alsys has one front end and dozens of backends -- not all compilers are like this, GCC has only one back end, but many compilers do have myultiple backends). The discussion centered around this implementation compatibility issue, with several people (me included) arguing that it would be a serious barrier to Ada 95 if existing display implementations had this obstacle thrown up. And that argument carried the day, especially considering that reasonable work arounds could be found in almost all cases of proposed use. Note that this compatibility issue is not just theoretical. The about to be released version of Ada 95 for NT/Win95 from Tompson (using the Intermetrics front end), uses displays for uplevel addressing (a consequence is that it would NOT be easy in this compiler to implement the Unrestricted_Access attribute). ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Jon S Anthony 1996-07-03 0:00 ` Robert Dewar @ 1996-07-03 0:00 ` Mark A Biggar 1996-07-03 0:00 ` Robert Dewar 1996-07-03 0:00 ` Robert A Duff 1996-07-03 0:00 ` Robert A Duff ` (6 subsequent siblings) 8 siblings, 2 replies; 133+ messages in thread From: Mark A Biggar @ 1996-07-03 0:00 UTC (permalink / raw) In article <JSA.96Jul2221357@organon.com> jsa@organon.com (Jon S Anthony) writes: >In article <Dtxu2p.97F@world.std.com> bobduff@world.std.com (Robert A Duff) writes: >> During the design of Ada 9X, we proposed a SAFE way of taking 'Access of >> more-deeply-nesting subprograms. To this day, I remain astonished and >> sad that this particular feature didn't make it into Ada 95. After >> all, even Pascal has that feature! And GNU C, which allows nested >> functions (unlike standard C) allows this feature. >Is there an "elevator version" of why people didn't want this in? Tucker, >if you are reading this, what swayed you to not let this in???? It's >not one of those things that bothers me all that much (well, it hasn't) >but it is indeed curious... If I remember right, it was felt that implementing "closures" (which is the solution to this problem) placed an unacceptable distributed overhead on programs that didn't use the feature. Also I think that half the then current Ada implementations were using "static links" and the other half were using "displays" and implementing "clousers" would have been real difficult for one of those groups (the "display" bunch I think). -- Mark Biggar mab@wdl.lmco.com ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Mark A Biggar @ 1996-07-03 0:00 ` Robert Dewar 1996-07-06 0:00 ` Robert A Duff 1996-07-03 0:00 ` Robert A Duff 1 sibling, 1 reply; 133+ messages in thread From: Robert Dewar @ 1996-07-03 0:00 UTC (permalink / raw) Mark said "If I remember right, it was felt that implementing "closures" (which is the solution to this problem) placed an unacceptable distributed overhead on programs that didn't use the feature. Also I think that half the then current Ada implementations were using "static links" and the other half were using "displays" and implementing "clousers" would have been real difficult for one of those groups (the "display" bunch I think)." The displays issue was the real reason. Closures is a difficult term because it means two totally different things, sometimes distinguished as upwards closures (easy to do), and downwards closures (more complex, typically requiring implicit heap allocation). No one seriously suggested adding downward closures to Ada 95 (although there is at least one person who loudly proclaims that this was a fatal mistake and that Ada 95 is useless as a result -- of course you can find such a person for almost any feature missing from the language :-) During discussion of the subprogram pointer issue, the term closure was often used, but in the more restricted ("upwards") sense, but this may have caused some residual confusion. (and just in case I give the wrong impression, I fully understand that full closures, preferably in conjunction with partial parametrization of higher order functions, lend tremendous expressive power -- for example Ackerman's function can be written using primitive recursion if you have these notions around), but I think the capability goes beyond the appropriate semantic level for Ada -- no doubt that statement should set of a mini-thread :-) ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Robert Dewar @ 1996-07-06 0:00 ` Robert A Duff 1996-07-08 0:00 ` Norman H. Cohen 0 siblings, 1 reply; 133+ messages in thread From: Robert A Duff @ 1996-07-06 0:00 UTC (permalink / raw) In article <dewar.836413642@schonberg>, Robert Dewar <dewar@cs.nyu.edu> wrote: >(and just in case I give the wrong impression, I fully understand that >full closures, preferably in conjunction with partial parametrization of >higher order functions, lend tremendous expressive power -- for example >Ackerman's function can be written using primitive recursion if you have >these notions around), but I think the capability goes beyond the >appropriate semantic level for Ada -- no doubt that statement should >set of a mini-thread :-) OK, sounds like an interesting mini-thread to me. :-) Ignore efficiency and implementation difficulty, for the moment. Show me an example or two illustrating the tremendous expressive power, using some imagined syntax for expressing full closures. (I know there's some expressive power there, but it's not clear to me how tremendous it is. I'm wondering if I've just not had enough experience in Lisp, etc. I've done some Lisp programming, and used closures, but don't miss them *all* that much in Ada-like languages.) - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-06 0:00 ` Robert A Duff @ 1996-07-08 0:00 ` Norman H. Cohen 1996-07-08 0:00 ` Robert Dewar 1996-07-11 0:00 ` Robert A Duff 0 siblings, 2 replies; 133+ messages in thread From: Norman H. Cohen @ 1996-07-08 0:00 UTC (permalink / raw) In article <Du4tvx.13s@world.std.com>, bobduff@world.std.com (Robert A Duff) writes: |> Ignore efficiency and implementation difficulty, for the moment. Show |> me an example or two illustrating the tremendous expressive power, using |> some imagined syntax for expressing full closures. (I know there's some |> expressive power there, but it's not clear to me how tremendous it is. |> I'm wondering if I've just not had enough experience in Lisp, etc. I've |> done some Lisp programming, and used closures, but don't miss them *all* |> that much in Ada-like languages.) Full closures are what LISP programmers call FUNARGs. First, a simple example: type Integer_Map_Type is access function (N: Integer) return Integer; function Add_M_To (M: Integer) return Integer_Map_Type is -- A function that returns M more than its formal parameter: function Result_Function (N: Integer) return Integer is begin return N + M; end Result_Function; begin return Result_Function'Access; -- illegal in Ada 95 end Add_M_To; Add_1_To : Integer_Map_Type := Add_M_To(M => 1); Add_5_To : Integer_Map_Type := Add_M_To(M => 5); X : Integer := Add_1_To(10); -- returns 11 Y : Integer := Add_5_To(10); -- returns 15 Add_M_To returns a pointer to a function more deeply nested than the access type Integer_Map_Type, in violation of Ada-95 rules. Note that the function pointed to, Result_Function, refers to M, which is a formal parameter of Add_M_To and thus, in Ada 95, goes out of existence when Add_M_To returns. In a language supporting full closures, the value of M is not obliterated when Add_M_To returns. What Add_M_To returns is a value designating not only the function Result_Function, but also the environment in which that function is to be executed, in this case an environment in which M is bound to 1 or to 5. The state of the environment during the call on Add_M_To is retained as part of this result value even after Add_M_To returns. Now for a more intricate example. Robert Dewar mentioned that Ackermann's function can be programmed out of straightforward loops if full closures are supported. The classic definition of Ackermann's function is: A(0,n) = n+1 A(m,0) = A(m-1,1) for m>0 A(m,n) = A(m-1,A(m,n-1)) for m>0, n>0 If we view A as an unbounded array and let R[m] be the function corresponding to the m\th "row" of this array, so that A(m,n) = R[m](n), these equations become: R[0](n) = n+1 R[m](0) = R[m-1](1) for m>0 R[m](n) = R[m-1] o R[m](n-1) for m>0, n>0 (where o represents functional composition) By repeatedly replacing R[m](...) in the third equation by the definition for R[m] given in the third equation, we get, for m>0: R[m](n) = R[m-1] o R[m](n-1) = R[m-1] o R[m-1] o R[m](n-2) = R[m-1] o R[m-1] o R[m-1] o R[m](n-3) ... = R[m-1] o ... o R[m-1] o R[m](0) \ / \-----------------/ n times Then, by replacing R[m](0) according to the second equation, we get R[m](n) = R[m-1] o ... o R[m-1] (1) \ / \-----------------/ n+1 times In other words, R[0] = the successor function (from the first equation) For m>0, the function R[m] is derived from the function R[m-1] as follows: Given an argument n, R[m] returns the result of starting with 1 and applying R[m-1] repeatedly, n+1 times. Here's a formulation using Ada plus full closures: package Unbounded_Naturals is type Unbounded_Natural is private; -- a type representing arbitrarily large nonnegative integers ... function "+" (Left: Unbounded_Natural; Right: Natural) return Unbounded_Natural; function "-" (Left: Unbounded_Natural; Right: Natural) return Unbounded_Natural; function "=" (Left: Unbounded_Natural; Right: Natural) return Boolean; function To_Unbounded_Natural (N: Natural) return Unbounded_Natural; ... private ... end Unbounded_Naturals; with Unbounded_Naturals; use Unbounded_Naturals; package Ackermann_Computation is function Ackermann (M, N: Integer) return Unbounded_Natural; end Ackermann_Computation; package body Ackermann_Computation is type Ackermann_Row_Type is access function (N: Unbounded_Natural) return Unbounded_Natural; function Row_Zero (N: Unbounded_Natural) return Unbounded_Natural is begin return N + 1; end Row_Zero; function Successor_Row (F: Ackermann_Row_Type) return Ackermann_Row_Type is function Next_Row (N: Unbounded_Natural) return Unbounded_Natural is Counter : Unbounded_Natural := N + 1; Result : Unbounded_Natural := 1; begin while Counter /= 0 loop Result := F(Result); -- F is the parameter of the surrounding function Counter := Counter - 1; end loop; return Result; end Result; begin return Next_Row'Access; -- Illegal in Ada 95 end Successor_Row; function Ackermann (M, N: Integer) return Unbounded_Natural is Row: Ackermann_Row_Type := Row_Zero'Access; -- R[0] begin for I in 1 .. M loop Row := Successor_Row(Row); -- Compute R[1] from R[0], R[2] from R[1], ... end loop; return Row ( To_Unbounded_Natural(N) ); -- i.e., R[m](n) end Ackermann; end Ackermann_Computation; The magic is inside Successor_Row, which returns a pointer to a function more deeply nested than the access type Ackermann_Row_Type, in violation of Ada-95 rules. The function pointed to, Next_Row, refers to F, which is a formal parameter of Successor_Row. Successor_Row returns a value designating both the function Next_Row and the environment in which that function is to be executed, in which F is bound to a particular Ackermann_Row_Type value. (After each iteration of the for-loop, Row designates the function Next_Row and an environment in which F is bound to whatever the value of Row was at the BEGINNING of that iteration.) -- Norman H. Cohen ncohen@watson.ibm.com ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-08 0:00 ` Norman H. Cohen @ 1996-07-08 0:00 ` Robert Dewar 1996-07-11 0:00 ` Robert A Duff 1 sibling, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-08 0:00 UTC (permalink / raw) Thankyou Norman for that nicely worked out example of Ackerman, now what do you say Bob? (Bob asked for a demo of the power of closures) :-) :-) ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-08 0:00 ` Norman H. Cohen 1996-07-08 0:00 ` Robert Dewar @ 1996-07-11 0:00 ` Robert A Duff 1996-07-12 0:00 ` Robert A Duff 1996-07-14 0:00 ` Norman H. Cohen 1 sibling, 2 replies; 133+ messages in thread From: Robert A Duff @ 1996-07-11 0:00 UTC (permalink / raw) In article <4rre7j$pv7@watnews1.watson.ibm.com>, Norman H. Cohen <ncohen@watson.ibm.com> wrote: [... stuff about closures] Norman gave a couple of nice examples illustrating how closures work Thank you. But I was hoping for something more about what makes closures so great (as opposed to how they work). I'm still unsure why closures are such a wonderful thing. Some comments: Ackermann's function isn't something I want to calculate very often. Is there a more "practical" example? One can represent closures explicitly using heap-allocated tagged objects. A closure in a language that supports full closures is represented by the address of the function, plus some representation of the environment in which that function is called. And this stuff has to be allocated in the heap, since it can live essentially forever. One can do the same thing *explicitly* in Ada, by putting the "environment" stuff into an object, and allocating it on the heap. I show a different version of package body Ackermann_Computation below, that works this way. Doing this requires the data that's in the closure to be explicitly marked as such (by being components of the tagged type(s)). In Norm's "true closures" solution, it's implicit -- that is, whatever Norm's Next_Row function happens to reference is what needs to be packaged up in the closure. Is there some advantage to that implicitness? Does it make things more substantially more convenient in some way that I don't understand? It seems to me that it's an *advantage* to make things explicit -- it seems nice that a local variable (or parameter) in Ada doesn't live longer than the containing scope -- it makes it easier to understand what the purpose of that local is. And if you want it to live longer, you *explicitly* put it in the heap. The solution below explicitly creates heap objects representing closures, whereas Norman's solution implicitly allocates some stack frames in the heap. The "closures by hand" solution is approximately the same size as (a little bigger than) Norm's solution. Norman's solution is perhaps more elegant. But it doesn't seem that full closures make the grass greener and the sky bluer and the birds sing more sweetly and all the other wonderfulness that some people seem to like so much. And of course there's a cost -- stack frames would have to be heap-allocated in general, and a good compiler would want to do all kinds of fancy analysis to avoid that when possible. So, I guess my question is, "Yeah, it's nice, but what's the big deal?" (By the way, surely the *simplest* solution is just a direct translation from the definition: function Ackermann (M, N: Unbounded_Natural) return Unbounded_Natural is begin if M = 0 then return N+1; elsif N = 0 then return Ackermann(M-1, 1); else return Ackermann(M-1, Ackermann(M, N-1)); end if; end Ackermann; ) What's the most *efficient* method for calculating Ackermann's? OK, here's my "closures-by-hand" solution: package body Ackermann_Computation is package Container is -- We need to put Ackermann_Row_Type in a package, so -- Invoke will be primitive. type Ackermann_Row_Type is abstract tagged limited null record; -- Six reserved words in a row! function Invoke(R: Ackermann_Row_Type; N: Unbounded_Natural) return Unbounded_Natural is abstract; -- Invokes the closure represented by R, with parameter N. type Ackermann_Row_Ptr is access Ackermann_Row_Type'Class; end Container; use Container; type Row_Zero_Type is new Ackermann_Row_Type with null record; function Invoke(R: Row_Zero_Type; N: Unbounded_Natural) return Unbounded_Natural; function Invoke(R: Row_Zero_Type; N: Unbounded_Natural) return Unbounded_Natural is begin return N + 1; end Invoke; type Successor_Row_Type(Pred: access Ackermann_Row_Type'Class; Row_Num: Natural) is new Ackermann_Row_Type with null record; -- Pred points to the predecessor row of this row. This is analogous -- to the parameter F in Norman's Successor_Row function. function Invoke(R: Successor_Row_Type; N: Unbounded_Natural) return Unbounded_Natural; function Invoke(R: Successor_Row_Type; N: Unbounded_Natural) return Unbounded_Natural is Counter : Unbounded_Natural := N + 1; Result : Unbounded_Natural := 1; begin while Counter /= 0 loop Result := Invoke(R.Pred.all, Result); Counter := Counter - 1; end loop; return Result; end Invoke; function Ackermann (M, N: Natural) return Unbounded_Natural is Row: Ackermann_Row_Ptr := new Row_Zero_Type; -- R[0] begin for I in 1 .. M loop Row := new Successor_Row_Type(Pred => Row, Row_Num => I); -- Compute R[1] from R[0], R[2] from R[1], ... end loop; return Invoke(Row.all, To_Unbounded_Natural(N)); -- i.e., R[m](n) end Ackermann; end Ackermann_Computation; And here's Norm's solution using closures, for comparison: package body Ackermann_Computation is type Ackermann_Row_Type is access function (N: Unbounded_Natural) return Unbounded_Natural; function Row_Zero (N: Unbounded_Natural) return Unbounded_Natural is begin return N + 1; end Row_Zero; function Successor_Row (F: Ackermann_Row_Type) return Ackermann_Row_Type is function Next_Row (N: Unbounded_Natural) return Unbounded_Natural is Counter : Unbounded_Natural := N + 1; Result : Unbounded_Natural := 1; begin while Counter /= 0 loop Result := F(Result); -- F is the parameter of the surrounding function Counter := Counter - 1; end loop; return Result; end Result; begin return Next_Row'Access; -- Illegal in Ada 95 end Successor_Row; function Ackermann (M, N: Integer) return Unbounded_Natural is Row: Ackermann_Row_Type := Row_Zero'Access; -- R[0] begin for I in 1 .. M loop Row := Successor_Row(Row); -- Compute R[1] from R[0], R[2] from R[1], ... end loop; return Row ( To_Unbounded_Natural(N) ); -- i.e., R[m](n) end Ackermann; end Ackermann_Computation; - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-11 0:00 ` Robert A Duff @ 1996-07-12 0:00 ` Robert A Duff 1996-07-14 0:00 ` Norman H. Cohen 1 sibling, 0 replies; 133+ messages in thread From: Robert A Duff @ 1996-07-12 0:00 UTC (permalink / raw) In article <DuDwA9.99F@world.std.com>, Robert A Duff <bobduff@world.std.com> wrote: >OK, here's my "closures-by-hand" solution: >... After a couple of hours of CPU time, I see that A(4,1) = 65533. Many hours later, it's still working on A(4,2). :-) - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-11 0:00 ` Robert A Duff 1996-07-12 0:00 ` Robert A Duff @ 1996-07-14 0:00 ` Norman H. Cohen 1 sibling, 0 replies; 133+ messages in thread From: Norman H. Cohen @ 1996-07-14 0:00 UTC (permalink / raw) In article <DuDwA9.99F@world.std.com>, bobduff@world.std.com (Robert A Duff) writes: |> One can represent closures explicitly using heap-allocated tagged |> objects. A closure in a language that supports full closures is |> represented by the address of the function, plus some representation of |> the environment in which that function is called. And this stuff has to |> be allocated in the heap, since it can live essentially forever. Correct. The usual implementation of the stack in a "retention-strategy" language (so called because the environment of a call may be retained even after that call returns) is as a linked list of heap-allocated activation records. Pushing a record onto the stack consists of setting its link field to point to the old top record and setting the top pointer to point to the new record; popping the stack consists of setting the top pointer to point to what is currently pointed to by the link field of the top record. If the environment pointed to by the top record did not become part of any closure, this causes the record to become inaccessible, and eventually it gets garbage-collected. Otherwise, since some live object is still pointing to the old top record, it remains in existence. (Association lists work this way in LISP, and full closures are constructed by calling FUNCTION, which returns a list consisting of the special atom FUNARG, the A-list for the environment in which FUNCTION was evaluated, and the S-expression that was passed to FUNCTION.) |> One |> can do the same thing *explicitly* in Ada, by putting the "environment" |> stuff into an object, and allocating it on the heap. I show a different |> version of package body Ackermann_Computation below, that works this |> way. |> |> Doing this requires the data that's in the closure to be explicitly |> marked as such (by being components of the tagged type(s)). In Norm's |> "true closures" solution, it's implicit -- that is, whatever Norm's |> Next_Row function happens to reference is what needs to be packaged up |> in the closure. Is there some advantage to that implicitness? Does it |> make things more substantially more convenient in some way that I don't |> understand? It seems to me that it's an *advantage* to make things |> explicit -- it seems nice that a local variable (or parameter) in Ada |> doesn't live longer than the containing scope -- it makes it easier to |> understand what the purpose of that local is. And if you want it to |> live longer, you *explicitly* put it in the heap. Whether the explicitness is a blessing or a curse depends on the level of abstraction you are used to. I presume that in typical circumstances you find the implicit manipulation of registers in A := B + C; preferable to the explicit manipulation of registers in LOAD R1, B LOAD R2, C ADD R3,R1,R2 STORE R3,A Similarly, for a programmer in a functional language such as ML, closures and higher-order functions are the usual language of discourse, the lowest level of abstraction. An ML programmer does not want to be bothered with the low-level details of implementing closures. The purpose of adding full closures to Ada would be to allow programming at that same very high level of abstraction. (This was not, of course, part of either the Ada-83 or Ada-95 requirements.) |> The solution below explicitly creates heap objects representing |> closures, whereas Norman's solution implicitly allocates some stack |> frames in the heap. Bob's solution is similar to one I created several years ago when experimenting with the use of Ada-83 tasks to represent function manipulable as first class objects. The task type had an Apply entry with an in parameter giving the function argument and an out parameter giving the function result. There were other entries to "construct" such a function. That is, calling the entry would place the task in a state where future calls on the Apply entry would cause it to behave like one function or another. One of the entries caused the task to move into a loop where Apply acted like the R[0] function, setting its out parameter to one more than the value of its in parameter. Another entry, with a pointer to a task object of the same type, presumably representing some Ackermann "row" R[i], would cause the task to move into a loop where Apply acted like the R[i+1] function, using its in parameter to control how many times the R[i] function would be applied to 1, and setting the out parameter to the result. (It would have been nice to have task types where different task objects had different task bodies implementing the same interface, but that's another discussion for another day.) |> What's the most *efficient* method for calculating Ackermann's? No doubt to special-case the lower rows: function Ackermann (M, N: Unbounded_Natural) return Unbounded_Natural is Counter : Unbounded_Natural; Result : Unbounded_Natural; begin if M = 0 then return N+1; elsif M = 1 then return 2*N+3; elsif M = 2 then return 2**(N+2) - 3; else Counter := N + 1; Result := 1; while Counter /= 0 loop Result := Ackermann(M-1, Result); Counter := Counter - 1; end loop; endif; end Ackermann; Note that Ackermann(3,n) is (if I didn't make a clerical error) 3 2 - 1 . . . 2 - 1 2 - 1 2 - 3 where the number of 2s is n. Thus even using some special representation for unbounded integers, we quickly exhaust all the storage in the address space to represent the result. Thus we need not worry about efficiency past this point; the computation is intractable. -- Norman H. Cohen ncohen@watson.ibm.com ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Mark A Biggar 1996-07-03 0:00 ` Robert Dewar @ 1996-07-03 0:00 ` Robert A Duff 1996-07-03 0:00 ` Robert Dewar 1996-07-09 0:00 ` Thomas Wolff 1 sibling, 2 replies; 133+ messages in thread From: Robert A Duff @ 1996-07-03 0:00 UTC (permalink / raw) In article <4re2ng$t7u@wdl1.wdl.loral.com>, Mark A Biggar <mab@dst17.wdl.loral.com> wrote: >If I remember right, it was felt that implementing "closures" (which is the >solution to this problem) placed an unacceptable distributed overhead >on programs that didn't use the feature. Also I think that half the then >current Ada implementations were using "static links" and the other half >were using "displays" and implementing "clousers" would have been real >difficult for one of those groups (the "display" bunch I think). We're only talking about "downward closures", which means you can pass a subprogram (or a pointer to it, which amounts to the same thing) to a subprogram. Nobody ever seriously proposed that Ada should support full closures (as in Lisp), where you can *return* a subprogram from a function. Full closures means you really have to store "stack frames" in the heap, in general, rather than on the stack, and garbage collect them. The part about static links vs. displays is correct, although I don't think it was really 50/50. I think *most* imlementations used static links. It is true that downward closures are harder to implement using displays. It is certainly possible, however. I know of a Pascal compiler that did it. Downward closures are a standard part of Pascal, and this particular Pascal compiler used displays. The issue was not one of distributed overhead, though. Passing displays around may be less efficient, but only in the case where the downward closure feature is actually used. It would have no effect on the efficiency of plain vanilla subprogram calls. The issue was primarily implementation complexity (for those implementations that use displays). The inefficiency issue was raised also (why add a feature if it's going to be so inefficient that noone can use it?). The latter argument always seemed bogus to me. There was never a distributed overhead argument. Oh, and of course, there's the "we don't need it" argument. Passing a subprogram as a generic formal parameter does almost the same thing, though more verbosely, and with a lot of space-inefficiency (unless your implementation knows how to share generics). Generics can't be recursive, though. I remember exactly one instance in my career where I used recursive downward closures (in Pascal). - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Robert A Duff @ 1996-07-03 0:00 ` Robert Dewar 1996-07-09 0:00 ` Thomas Wolff 1 sibling, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-03 0:00 UTC (permalink / raw) OOps, Bob Duff and I are using downward/upward exactly opposite in our posts on closures, I think Bob is right, and I was wrong. Downward is the easy one, Upward is the hard one (which has to save parameter instances). ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Robert A Duff 1996-07-03 0:00 ` Robert Dewar @ 1996-07-09 0:00 ` Thomas Wolff 1996-07-09 0:00 ` Robert Dewar 1996-07-10 0:00 ` Robert A Duff 1 sibling, 2 replies; 133+ messages in thread From: Thomas Wolff @ 1996-07-09 0:00 UTC (permalink / raw) Robert Dewar: >>>Q: access to subprogram : Once you introduce unrestricted access to procedures, displays are a bit : of a menace, and probably this tips the scales in favor of static links : (if you believe like me that displays are more efficient, this can also : be read as meaning that the introduction of unrestricted access to procedures : would introduce distributed inefficiency -- but that still is NOT the reason : this feature was excluded). 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: >>>Q: access to subprogram : There are two major ways of implementing up-level variable references in : a language with nested procedures: Static links, and displays. With : displays, it is somewhat difficult to implement passing nested : procedures as parameters, because you have to pass the display, which is This is not true, see below. : not of compile-time-known size. Passing a static link is easy -- it's : just a single address. Some implementations of Ada 83 used displays. 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.) : The primary reason for not putting the feature in was to ease the pain : for such implementations. This was done at a time when the general : feeling was that Ada 9X had more than enough new features, and we : shouldn't be adding things, but removing them. It is a very unfortunate decision to leave out a nice feature of systematic program construction just for leaving out features. Mark A Biggar: >>>Q: access to subprogram : In article <JSA.96Jul2221357@organon.com> jsa@organon.com (Jon S Anthony) wri tes : : : >In article <Dtxu2p.97F@world.std.com> bobduff@world.std.com (Robert A Duff) wri : tes: : >> During the design of Ada 9X, we proposed a SAFE way of taking 'Access of : >> more-deeply-nesting subprograms. To this day, I remain astonished and : >> sad that this particular feature didn't make it into Ada 95. After : >> all, even Pascal has that feature! And GNU C, which allows nested : >> functions (unlike standard C) allows this feature. 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. : If I remember right, it was felt that implementing "closures" (which is the : solution to this problem) placed an unacceptable distributed overhead : on programs that didn't use the feature. Also I think that half the then : current Ada implementations were using "static links" and the other half : were using "displays" and implementing "clousers" would have been real : difficult for one of those groups (the "display" bunch I think). No, with the solution indicated above there is no overhead (i. e. for programs that don't use the feature) and no big inefficiency for programs that do use the feature and no difficulty either apart from having to understand what should happen in the implementation. When I recently gave a talk on a topic related to this, some members of the audience also seemed to recall they had the impression this was difficult or inefficient... I wonder how this rumor evolved. Compare my other response in this thread for remarks about the desirability of the discussed language feature. Thomas Wolff ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-09 0:00 ` Thomas Wolff @ 1996-07-09 0:00 ` Robert Dewar 1996-07-10 0:00 ` Robert A Duff 1 sibling, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-09 0:00 UTC (permalink / raw) Thomas Wolff 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. Static links are by far the more common way of hanling 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. In fact the idea of static links came a little later on, the early Algol-60 compilers used displays. 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.) 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. (Yes, I know the Intel x86 hardware uses that approach. I use this as one of the examples of very bad CISC design, not only is an over-complex instruction built-in, but it is a bad algorithm that is built-in!) ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-09 0:00 ` Thomas Wolff 1996-07-09 0:00 ` Robert Dewar @ 1996-07-10 0:00 ` Robert A Duff 1996-07-10 0:00 ` Richard A. O'Keefe 1 sibling, 1 reply; 133+ messages in thread From: Robert A Duff @ 1996-07-10 0:00 UTC (permalink / raw) In article <4rud55$5b0@fu-berlin.de>, Thomas Wolff <wolff@inf.fu-berlin.de> wrote: >Robert Dewar: >>>Q: access to subprogram > : Once you introduce unrestricted access to procedures, displays are a bit > : of a menace, and probably this tips the scales in favor of static links > : (if you believe like me that displays are more efficient, this can also > : be read as meaning that the introduction of unrestricted access to procedures > : would introduce distributed inefficiency -- but that still is NOT the reason > : this feature was excluded). >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. 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 A Duff: >>>Q: access to subprogram > : There are two major ways of implementing up-level variable references in > : a language with nested procedures: Static links, and displays. With > : displays, it is somewhat difficult to implement passing nested > : procedures as parameters, because you have to pass the display, which is >This is not true, see below. > : not of compile-time-known size. Passing a static link is easy -- it's > : just a single address. Some implementations of Ada 83 used displays. >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.) 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. > : The primary reason for not putting the feature in was to ease the pain > : for such implementations. This was done at a time when the general > : feeling was that Ada 9X had more than enough new features, and we > : shouldn't be adding things, but removing them. >It is a very unfortunate decision to leave out a nice feature of >systematic program construction just for leaving out features. Agreed. But what's done is done. (Until Ada 0X, or until you prefer some other language. ;-)) >Mark A Biggar: >>>Q: access to subprogram > : In article <JSA.96Jul2221357@organon.com> jsa@organon.com (Jon S Anthony) wri >tes > : : > : >In article <Dtxu2p.97F@world.std.com> bobduff@world.std.com (Robert A Duff) >wri > : tes: > : >> During the design of Ada 9X, we proposed a SAFE way of taking 'Access of > : >> more-deeply-nesting subprograms. To this day, I remain astonished and > : >> sad that this particular feature didn't make it into Ada 95. After > : >> all, even Pascal has that feature! And GNU C, which allows nested > : >> functions (unlike standard C) allows this feature. >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. 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. Of course, the Smalltalk solution makes even Pascal's equivalent look verbose. And of course, I'm assuming in all of the above that "full closures" are not supported (since they subsume all of the above, and more, but require a totally different run-time model). > : If I remember right, it was felt that implementing "closures" (which is the > : solution to this problem) placed an unacceptable distributed overhead > : on programs that didn't use the feature. Also I think that half the then > : current Ada implementations were using "static links" and the other half > : were using "displays" and implementing "clousers" would have been real > : difficult for one of those groups (the "display" bunch I think). >No, with the solution indicated above there is no overhead (i. e. for >programs that don't use the feature) and no big inefficiency for programs >that do use the feature and no difficulty either apart from having to >understand what should happen in the implementation. When I recently >gave a talk on a topic related to this, some members of the audience >also seemed to recall they had the impression this was difficult or >inefficient... I wonder how this rumor evolved. The "solution above" is viable, but is not the simplest solution. The simplest solution is to use static links. (And that solution has the desirably property that calling via an access-to-procedure will not involve inordinate overhead.) >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). - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-10 0:00 ` Robert A Duff @ 1996-07-10 0:00 ` Richard A. O'Keefe 1996-07-10 0:00 ` Robert Dewar 1996-07-10 0:00 ` Robert A Duff 0 siblings, 2 replies; 133+ messages in thread From: Richard A. O'Keefe @ 1996-07-10 0:00 UTC (permalink / raw) bobduff@world.std.com (Robert A Duff) writes: >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. Ah, but - if a procedure at lexical level N - directly encloses a procedure at lexical level N+1 - which is passed as a parameter all that has to be copied into the parent's activation record is D[1:N] whose size is known at compile time. The child (or the child's wrapper) needs to allocate space to hold the old values of D[1:N] when it is entered. >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. Lisp, Scheme, ML, ... have this. > 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. I'm not quite sure what "not at the same time means". If it means "not in the same language", I'd disagree. If it means "not in the same program", I wouldn't agree either. There's someone here doing a Masters thesis on adding support to Ada for a particular design pattern. I don't want to say too much, because he's just beginning implementation studies (what a wonderful thing GNAT is), but basically, callbacks are needed to do it right, and Ada's rules are a major headache. But the very programs that will benefit from this facility are also likely to abstract iteration as well, thus needing 1 and 2 in the same program. In Lisp, there would be no point in his thesis as the whole thing is not only utterly trivial, it is a well understood and long used technique. My PL/I is rather rusty, but I know rav reads c.l.a. Doesn't PL/I have procedure variables as well as procedure parameters? -- Fifty years of programming language research, and we end up with C++ ??? Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-10 0:00 ` Richard A. O'Keefe @ 1996-07-10 0:00 ` Robert Dewar 1996-07-10 0:00 ` Robert A Duff 1 sibling, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-10 0:00 UTC (permalink / raw) Richard said "Ah, but - if a procedure at lexical level N - directly encloses a procedure at lexical level N+1 - which is passed as a parameter all that has to be copied into the parent's activation record is D[1:N] whose size is known at compile time. The child (or the child's wrapper) needs to allocate space to hold the old values of D[1:N] when it is entered." Sure, this is the well known scheme that was used in the original Algol-60 compiler, and was used frequenly early on, and is almost never used now (although as I mentioned in an earlier note, it is what Intel implements in their hardware - the ENTER instruction). The reason that this loses to static links is that unconditionally you end up copying the display whether you need it or not. In the case of static links, you only climb the chain (once per procedure if a reasonable optimizer is in use) if it is needed. With the scheme above, you have a huge chain of procedures that never do any up level references copying around large displays if the nesting depth is deep, just so that someone in the future might be able to reference one element of this display. I wonder who designed this feature at Intel? Someone who knew a bit, but not really enough, about how to deal with up level displays. The ENTER instruction is an instruction that should never ever be used on any of the Intel x86 arcitectures. Even the version with a zero count is highly dubious if you look at the timings. A perfect example of silly CISC design. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-10 0:00 ` Richard A. O'Keefe 1996-07-10 0:00 ` Robert Dewar @ 1996-07-10 0:00 ` Robert A Duff 1996-07-10 0:00 ` Thomas Wolff 1 sibling, 1 reply; 133+ messages in thread From: Robert A Duff @ 1996-07-10 0:00 UTC (permalink / raw) In article <4rvo07$bbl@goanna.cs.rmit.edu.au>, Richard A. O'Keefe <ok@goanna.cs.rmit.edu.au> wrote: >> 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. > >Lisp, Scheme, ML, ... have this. > >> 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). I didn't really describe what I meant very well. In (1), I meant that you can assign them into global variables, but you're not allowed to pass nested ones. In (2), I meant that you get nesting, but not the assignment. Lisp has full closures, which subsumes both (1) and (2), and also achieves some things that neither (1) and (2) can do. >>Both of the above are desirable, but not at the same time. > >I'm not quite sure what "not at the same time means". If it means >"not in the same language", I'd disagree. If it means "not in the >same program", I wouldn't agree either. I didn't mean either of those two. I agree that a language should have both 1 and 2, and you should be allowed to use them in the same program. I just meant that the purposes are different, and you can view them as two separate features. You use (1), for example, when you want to hand a procedure to the windowing system, saying please call it when the mouse is clicked. You use (2), for example, in iterators -- please crawl around this data structure, and call so-and-so procedure for each component. This is all assuming that you don't want to pay for full closures. (As I said, full closures subsume both of the above features.) My point is that you can retain the stack-based run-time model of Ada, and retain safety against dangling pointers, and still support both (1) and (2) in the language. And the safety doesn't need to involve expensive run-time checks. - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-10 0:00 ` Robert A Duff @ 1996-07-10 0:00 ` Thomas Wolff 1996-07-10 0:00 ` Robert Dewar 1996-07-10 0:00 ` Robert A Duff 0 siblings, 2 replies; 133+ messages in thread From: Thomas Wolff @ 1996-07-10 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-10 0:00 ` Thomas Wolff @ 1996-07-10 0:00 ` Robert Dewar 1996-07-10 0:00 ` Robert A Duff 1 sibling, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-10 0:00 UTC (permalink / raw) Thomas Wolff said "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..." You cannot really mean this as an absolute principle. All languages are designed with some concern for implementability. A wonderful Ada 95 which no one implemented would not be much use to anyone. Sure it is true that any single feature will not make the difference (but that's what camels and straws are all about). You can argue that the decision was made wrong in this particular case, but to say that as a general principle it is wrong to consider implementation issues seems quite off base. : 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?) It is not just that they are too much trouble, but that they are inefficient for the purpose at hand (when procedure pointers are around). As to only needing to find the right trick once, that's wrong. Complete solutions need linker involvement, and that tends to mean finding the solution more than once and fighting various linker capabilities. As to how much trouble is "too much" that of course is central to the judgment of the trade off. 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. Yes, and calls of formal procedures are what we are talking about here! 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. No, of course you can pass procedure parameters in Ada 95. You really ought to look at the language feature here to see how the accessibility restrictions work. You can have procedure pointers and procedures as parameters in Ada 95, it is just that there are some limitations. Obviously a careful understanding of the limitations is important in judging how much functionality has been given up for implementation concerns. If you are assuming that Ada 95 completely eliminated procedure parameters, then your understanding of this thread is a bit distorted, since that would clearly have been totally unacceptable to everyone. 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? I don't like the overhead, but could live with it. But in any case that has nothing at all to do with the decision to exclude the fully general solution, although it is true that calling a formal procedure in Ada 95 does NOT require this overhead, even if you are using displays. The issue was the difficulty of implementation, not the overhead. We discussed this difficulty in considerable detail (with the implementors involved), so we certainly had the information to understand what these difficulties were. : 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. Here I lose you technically. The invariant I give is EXACTLY the correct one for Algol-60 semantics, and for Ada 83 and Ada 95 semantics. As I noted it can be modified to make it more efficient by considering only procedures which contain other procedures, but you seem to contest the invariant I state above, and that I don't understand. 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. The idea of a compiler's efficiency depending on optimization does not seem odd at all to me. Certainly your puzzlement that static chains are widely used is perhaps explained by this difference. The fundamental assumption that is made in choosing static links is the assumption that compilers will successfully eliminate wasteful duplicate following of the chain. Ah, looking back, I think I see why you did not like my invariant, you are assuming it is applied to a single global display, and that of course is not possible with generalized procedure parameters, although it is possible with the procedure parameters of Ada 95. OK, exactly so! You need multiple displays if you have procedure parameters, and that is the source of the unpleasant overhead. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-10 0:00 ` Thomas Wolff 1996-07-10 0:00 ` Robert Dewar @ 1996-07-10 0:00 ` Robert A Duff 1 sibling, 0 replies; 133+ messages in thread From: Robert A Duff @ 1996-07-10 0:00 UTC (permalink / raw) In article <4s0qm7$htm@fu-berlin.de>, Thomas Wolff <wolff@inf.fu-berlin.de> wrote: >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. Ada 83 does not. Ada 95 does, so long as the actual procedure is not too nested. It's the more-nested case that we're all chatting about. And of course Ada 83 and Ada 95 both allow passing procedures to generics (even the nested case). This was part of the argument -- who needs downward closures when we have generics. (The generic solution is horribly verbose, in my opinion, but it does work in most cases.) >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? Ada 99? Maybe Ada 07 or so... I'll be too old by then. ;-) - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Jon S Anthony 1996-07-03 0:00 ` Robert Dewar 1996-07-03 0:00 ` Mark A Biggar @ 1996-07-03 0:00 ` Robert A Duff 1996-07-08 0:00 ` Norman H. Cohen 1996-07-19 0:00 ` Brian Rogoff ` (5 subsequent siblings) 8 siblings, 1 reply; 133+ messages in thread From: Robert A Duff @ 1996-07-03 0:00 UTC (permalink / raw) In article <JSA.96Jul2221357@organon.com>, Jon S Anthony <jsa@organon.com> wrote: >Is there an "elevator version" of why people didn't want this in? Tucker, >if you are reading this, what swayed you to not let this in???? It's >not one of those things that bothers me all that much (well, it hasn't) >but it is indeed curious... There are two major ways of implementing up-level variable references in a language with nested procedures: Static links, and displays. With displays, it is somewhat difficult to implement passing nested procedures as parameters, because you have to pass the display, which is not of compile-time-known size. Passing a static link is easy -- it's just a single address. Some implementations of Ada 83 used displays. The primary reason for not putting the feature in was to ease the pain for such implementations. This was done at a time when the general feeling was that Ada 9X had more than enough new features, and we shouldn't be adding things, but removing them. - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Robert A Duff @ 1996-07-08 0:00 ` Norman H. Cohen 1996-07-09 0:00 ` Robert A Duff 0 siblings, 1 reply; 133+ messages in thread From: Norman H. Cohen @ 1996-07-08 0:00 UTC (permalink / raw) In article <Dtyt4K.Jvx@world.std.com>, bobduff@world.std.com (Robert A Duff) writes: |> With |> displays, it is somewhat difficult to implement passing nested |> procedures as parameters, because you have to pass the display, which is |> not of compile-time-known size. 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). In essence, a display is an array of pointers to the stack frames for the current activations of each subprogram surrounding the current subprogram. The array is typically small, fast access to the values of the array elements is crucial for efficient access to nonlocal variables, and the array indices needed for addressing nonlocal variables are always known at compile time, so the elements of this array are typically stored in registers. (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.) -- Norman H. Cohen ncohen@watson.ibm.com ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-08 0:00 ` Norman H. Cohen @ 1996-07-09 0:00 ` Robert A Duff 0 siblings, 0 replies; 133+ messages in thread From: Robert A Duff @ 1996-07-09 0:00 UTC (permalink / raw) In article <4rr5tu$sap@watnews1.watson.ibm.com>, Norman H. Cohen <ncohen@watson.ibm.com> wrote: >The size of a display for a given procedure IS known at compile time. True (assuming you don't "really" support separate compilation of subunits). But the size of "THE display" is the max of all those. This is not known at compile time, but at link time. To package up a display along with the corresponding procedure (when 'Access is done), you have to either know that max size, and copy that much into a compiler-generated variable, or else you have to manage varying-size displays (and copy THAT much) -- note that the caller who does P.all(...) doesn't know where P came from, and so either has to be TOLD the size of P's display, or always use the max. Or, I suppose you could simply say that the max is 10, and forbid nesting more than 10 levels deep. Perhaps a reasonable restriction, but I hate having arbitrary restrictions like that, if it's feasible to avoid. Any of the above are quite implementable, but I think that static links are clearly simpler for the implementation. >... I viewed the inclusion of downward >closures as the REMOVAL of an arbitrary restriction. Me, too. This is an illustration of Robert's point about simplicity. We were all shouting for more simplicity, but everybody had their own idea of simplicity (simple to describe in the RM vs. simple to implement vs. simple to learn for a beginner vs. simple to use for an experienced programmer vs. etc etc etc). >... 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.) Well, to be fair, if the implementers can't implement, the users are kind of stuck. Probably not true in this particular case, but in the general case, you don't want to just add every feature anybody wants. If the compiler gets too big, it gets too buggy -- no matter how much money you spend on it, apparently. - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Jon S Anthony ` (2 preceding siblings ...) 1996-07-03 0:00 ` Robert A Duff @ 1996-07-19 0:00 ` Brian Rogoff 1996-07-22 0:00 ` Richard A. O'Keefe 1996-07-23 0:00 ` Brian Rogoff 1996-07-22 0:00 ` Brian Rogoff ` (4 subsequent siblings) 8 siblings, 2 replies; 133+ messages in thread From: Brian Rogoff @ 1996-07-19 0:00 UTC (permalink / raw) ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes: dewar@cs.nyu.edu (Robert Dewar) writes: <... about the decision to omit "downward closures"...> >As to whether the decision is right in retrospect? hard to say. So far >I have not seen any really convincing examples. Self-fulfilling prophecy. It's a better use of my time to figure out how I _can_ accomplish something in Ada 95 (my favourite imperative language) than to construct examples showing what I'd like to do and can't. If I _were_ going to spend time on that, I'd explain why I would like to be able to pass a generic procedure as a generic parameter (not an *instance* of a generic procedure, the generic itself). I guess I would ask Pascal programmers how useful they found this, and whether any interesting idioms emerged which used this feature. The same for similar languages (does Borland's Delphi have Pascal-like downward closures?). The iterator example is a good one I think, but apparently not good enough. Maybe a few more useful examples, and a consensus on the implementation issues would enable this issue to be reopened in the future. While I (as a user) think that downward closures and some other language tidying would have been good, the ability to write OCXes easily in GNAT would be far more useful :-). -- Brian ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-19 0:00 ` Brian Rogoff @ 1996-07-22 0:00 ` Richard A. O'Keefe 1996-07-23 0:00 ` Brian Rogoff 1 sibling, 0 replies; 133+ messages in thread From: Richard A. O'Keefe @ 1996-07-22 0:00 UTC (permalink / raw) rogoff@sccm.Stanford.EDU (Brian Rogoff) writes: [about nested procedures as parameters of other procedures] >I guess I would ask Pascal programmers how useful they found this, and whether >any interesting idioms emerged which used this feature. As an old Algol/Pascal programmer, I would answer "very useful". I don't quite grasp the intent of the "any useful idioms" question. Procedures as parameters are an abstraction mechanism. Hen's teeth, even Fortran has them. Why? So you can build abstractions like "integrate over an interval"; "Monte-Carlo integration in N-dimensional space"; "find the minimum of a function over an interval"; "find the mimimum of a function in N-space" (Nelder-Mead, for example); "solve ODE"; ... Now it _is_ possible to do a lot of this using Ada generics. Let's consider one special case, and I'll use Scheme syntax. (define (integrate-1D L1 U1 F) ; compute and return ; integral F(x) dx for x in [L1,U1] <<some expression>> ) (define (integrate-2D L1 U1 L2 U2 F) ; compute and return ; integral F(x,y) dx dy for x in [L1,U1] y in [L2,U2] (integrate-1D L2 U2 (lambda (y) (integrate-1D L1 U1 (lambda (x) (F x y)) )) )) The Pascal (ISO 10206) equivalent would be function Integrate_1D(L1, U1: Real; function F(x: Real): Real): Real; (* some locals *) begin (* some body *) end; function Integrate_2D(L1, U1, L2, U2: Real; function F(x, y: Real): Real): Real; function Inner(y: Real): Real; function Curried_F(x: Real): Real; begin Curried_F := F(x, y) end; begin Inner := Integrate_1D(L1, U1, Curried_F) end; begin Integrate_2D := Integrate_1D(L2, U2, Inner) end; The Ada equivalent of this would be generic with function F(x: Float) return Float; function Integrate_1D(L1, U1: Float) return Float; function Integrate_1D(L1, U1: Float) return Float is -- some locals begin -- some body end; generic with function F(x, y: Float) return Float; function Integrate_2D(L1, U1, L2, U2: Float) return Float; function Integrate_2D(L1, U1, L2, U2: Float) return Float is function Outer_Integrand(y: Float) return Float is function Inner_Integrand(x: Float) return Float is begin return F(x, y); end Inner_Integrand; function Inner_Integrator is new Integrate_1D(F => Inner_Integrand); begin return Inner_Integrator(L1, U1); end Outer_Integrand; function Outer_Integrator is new Integrate_1D(F => Outer_Integrand); begin return Outer_Integrator(L2, U2); end Integrate_2D; [Layout chosen to give Scheme no unfair advantage with respect to number of lines needed. I would normally lay the Ada version out exactly the way that AQAS guidelines recommend.] In the Scheme version, only the top-level procedures need names. In the Pascal version, the lambda-expressions have to be given names; there is nothing in the Pascal model which actually *requires* this; Pascal *could* be extended with context-sensitive lambda-expressions so as to allow function Integrate_2D(L1, U1, L2, U2: Real; function F(x, y: Real): Real): Real; begin Integrate_2D := Integrate_1D(L2, U2, lambda (y) Integrate_1D(L1, U1, lambda (x) F(x, y))); end; without requiring any backend changes. In the Ada version, not only do the *arguments* of Integrate_1D need names, so also do the *calls*. In the Scheme and Pascal versions, there is one copy of Integrate_1D which is called twice. In the Ada version, at least as compiled by "gcc -S -O" (gcc 2.7.2, gnat 3.04, SPARC Solaris 2.5), there are two copies of Integrate_1D. The optimised SPARCompiler Pascal code for a program using this is in fact about half the size of optimised GNAT Ada code. For this example, it doesn't seem so important, but consider larger examples, and consider caching effects. Most of all, consider the effect on program style and clarity. Many people, of whom I am one, consider passing procedures as parameters a *fundamental* control structure (really fundamental; people in this camp like to use it as a primitive to explain IF), and while it is possible to program without it, so would it be possible to program in a language with no FOR statements or where no expression was allowed to have more than one operator or where there was no automatic storage allocation. All of these are *possible*, but why make programming any harder than it has to be? >Maybe a few more useful examples, and a consensus on the implementation >issues would enable this issue to be reopened in the future. Procedures as parameters have been around since the late 1950s. There are many thousands of commercially important Fortran programs and libraries using them. There are libraries full of books about the functional programming paradigm and the importance of procedures as a (not "the", "a") tool of abstraction. >While I (as a user) think that downward closures and some other language >tidying would have been good, the ability to write OCXes easily in GNAT >would be far more useful :-). One must be practical. I would far rather have Ada 95 *now* the way it is than the way it might have been "some time next year". Any time I want a language with less compromise, I can turn to Clean. -- Fifty years of programming language research, and we end up with C++ ??? Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-19 0:00 ` Brian Rogoff 1996-07-22 0:00 ` Richard A. O'Keefe @ 1996-07-23 0:00 ` Brian Rogoff 1996-07-23 0:00 ` Robert A Duff 1996-07-26 0:00 ` Brian Rogoff 1 sibling, 2 replies; 133+ messages in thread From: Brian Rogoff @ 1996-07-23 0:00 UTC (permalink / raw) bobduff@world.std.com (Robert A Duff) writes: In article <ROGOFF.96Jul22154757@sccm.Stanford.EDU>, Brian Rogoff <rogoff@sccm.stanford.edu> wrote: >ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes: > rogoff@sccm.Stanford.EDU (Brian Rogoff) writes: > [about nested procedures as parameters of other procedures] > > >I guess I would ask Pascal programmers how useful they found this, and whether > >any interesting idioms emerged which used this feature. Iterators. Hi Bob, While this is now straying a bit from Ada 95, I'm curious as to whether you find Pascal style iterators using downward funargs (there, I'm using Lisp terminology) superior to CLU/Sather-1.0 style iterators. And how do the Ada 95 alternatives stack up? Also, were these downward funargs widely used, or was there a small set of problems in which they were the ideal vehicle of expression, like the multidimensioal integration example? I realize in Scheme that functions are used for everything, so I am interested more in the answer for Pascal and other Ada-like languages. This is a really fascinating question in language design. I'd like find some examples like the ones Richard O'Keefe posted, and see what the best Ada 95 alternatives are. That way I can get a better sense as to how much we are really missing. - Bob (ex-Pascal-programmer) -- Brian (hopefully ex-C-programmer ;-) ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-23 0:00 ` Brian Rogoff @ 1996-07-23 0:00 ` Robert A Duff 1996-07-26 0:00 ` Brian Rogoff 1 sibling, 0 replies; 133+ messages in thread From: Robert A Duff @ 1996-07-23 0:00 UTC (permalink / raw) In article <ROGOFF.96Jul23093858@sccm.Stanford.EDU>, Brian Rogoff <rogoff@sccm.stanford.edu> wrote: >Hi Bob, Hi Brian, > While this is now straying a bit from Ada 95, Indeed. I hope people don't get too annoyed at us for discussing general language design stuff. >.. I'm curious as to >whether you find Pascal style iterators using downward funargs (there, I'm >using Lisp terminology) superior to CLU/Sather-1.0 style iterators. No. When I was a Pascal programmer many years ago, I used procedures-as-params a lot for iterators. But CLU iterators are clearly superior. I don't know Sather, but from what I've read, they seem even more superior. >...And >how do the Ada 95 alternatives stack up? Not very well, I'm afraid. You can use generics, but you end up with a lot of verbose junk for some simple things. Sigh. >... Also, were these downward funargs >widely used, or was there a small set of problems in which they were the ideal >vehicle of expression, like the multidimensioal integration example? I'd say Pascal's downward "funargs" were widely used for iterators. At least in the code I saw, and the code I wrote. >...I realize >in Scheme that functions are used for everything, so I am interested more in >the answer for Pascal and other Ada-like languages. > > This is a really fascinating question in language design. Indeed. >...I'd like >find some examples like the ones Richard O'Keefe posted, and see what the >best Ada 95 alternatives are. That way I can get a better sense as to how much >we are really missing. Ada's generics can do *almost* everything that Pascal can do. They can't recurse, in Ada, like they can in Pascal. (I needed that once.) And they're verbose, as I said. Smalltalk's version is pretty nice, by the way. You don't pass procedures -- you pass blocks. And that avoids the annoyance of having to name something that doesn't need or deserve a name -- it's just the Body_Of_The_Loop, or whatever. - Bob P.S. I was away for more than a week, so I may have missed some answers to my question about full closures. Did anybody answer that? ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-23 0:00 ` Brian Rogoff 1996-07-23 0:00 ` Robert A Duff @ 1996-07-26 0:00 ` Brian Rogoff 1996-07-28 0:00 ` Robert A Duff 1 sibling, 1 reply; 133+ messages in thread From: Brian Rogoff @ 1996-07-26 0:00 UTC (permalink / raw) bobduff@world.std.com (Robert A Duff) writes: Brian Rogoff <rogoff@sccm.stanford.edu> wrote: >Anecdotal evidence, but useful. Anecdotal is all you ever get in this business. ;-) Correct. But by collecting this anecdotal evidence and analyzing it we can hopefully get some idea of what we're doing :-). > Ada's generics can do *almost* everything that Pascal can do. They > can't recurse, in Ada, like they can in Pascal. (I needed that once.) > And they're verbose, as I said. > >Do you feel that they are the right solution though? No. They work in many cases, but they're not the best solution. That's my feeling too, although when I thought about it more I couldn't really rationalize why I disliked generics so much for this problem and yet like the use of null bodied generic formal package parameters for signatures. Maybe in a few days the generic approach won't seem so bad. >Was this the "why are they any better than wrapping up the environment and >func in a tagged type" question? Yes. Not just "why are they better", but "why are the a LOT better" (which is the claim I often hear). I think that you posted that you like Smalltalk blocks a lot, which are essentially just anonymous closures, right? I think the beauty of this construct is that you can implement lots of features cleanly in terms of it, like control structures. Also the implementation of closures on objects seems heavy/verbose to me. I think in a language like Smalltalk, which already has GC, that upward funargs and objects are (a LOT) better than objects alone. On the other hand, if you are asking if they are so much better than explicitly managing the heap that Ada should adopt GC :-), I'd say no. -- Brian ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-26 0:00 ` Brian Rogoff @ 1996-07-28 0:00 ` Robert A Duff 0 siblings, 0 replies; 133+ messages in thread From: Robert A Duff @ 1996-07-28 0:00 UTC (permalink / raw) In article <ROGOFF.96Jul26095803@sccm.Stanford.EDU>, Brian Rogoff <rogoff@sccm.stanford.edu> wrote: >I think that you posted that you like Smalltalk blocks a lot, which are >essentially just anonymous closures, right? Yes, I did post that. But it's not because they are full closures -- almost all of the uses in my code, and almost all of the uses I've seen, are the downward kind. The reason I like them is that you can do things like iterators without a lot of fuss. In Pascal, using the procedures-as-parameters method, you have to write a procedure for the body of the loop, and you have to give it a name. In Ada, using the generics method, you have to do that, and you also have to write a generic instantiation, and give *that* a name. You end up cluttering the program with useless names for things that should really be anonymous (The_Loop_Body, or Do_One_Item, or whatever). So, I like Smalltalks blocks because they are anonymous. I also like them because they are written in line. When I write a loop, I want to write the iteration stuff controlling the loop, and then I want the repeated statements to be inside the loop. The procedures-as-params solution forces a weird ordering in the code. >....I think the beauty of this >construct is that you can implement lots of features cleanly in terms of >it, like control structures. No, that merely requires downward closures. I'm still looking for an example that really makes the upward direction look wonderfully powerful. >...Also the implementation of closures on objects >seems heavy/verbose to me. True. But that's OK, unless full closures are really as powerful and commonly needed as I've heard. Also, the heavy/verbose way of doing it has an advantage -- it makes quite clear which data is going to survive the return of this procedure (by being attached to a closure), as opposed to purely "local" data. - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Jon S Anthony ` (3 preceding siblings ...) 1996-07-19 0:00 ` Brian Rogoff @ 1996-07-22 0:00 ` Brian Rogoff 1996-07-23 0:00 ` Robert A Duff ` (2 more replies) 1996-07-24 0:00 ` Brian Rogoff ` (3 subsequent siblings) 8 siblings, 3 replies; 133+ messages in thread From: Brian Rogoff @ 1996-07-22 0:00 UTC (permalink / raw) ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes: rogoff@sccm.Stanford.EDU (Brian Rogoff) writes: [about nested procedures as parameters of other procedures] >I guess I would ask Pascal programmers how useful they found this, and whether >any interesting idioms emerged which used this feature. As an old Algol/Pascal programmer, I would answer "very useful". I don't quite grasp the intent of the "any useful idioms" question. Idiom in the sense of "pattern", an interesting interaction with other features of the language they appear in. In Ada, for example, the idiom to simulate mixin inheritance involves parametrizing a mixin type with its enclosing type through access discriminants. Other languages might have other features to do the same thing. Procedures as parameters are an abstraction mechanism. Hen's teeth, even Fortran has them. Why? So you can build abstractions like "integrate over an interval"; "Monte-Carlo integration in N-dimensional space"; "find the minimum of a function over an interval"; "find the mimimum of a function in N-space" (Nelder-Mead, for example); "solve ODE"; ... Scheme was my first language. I like it, and I understand the benefits of closures and lazy evaluation and such. But Ada is designed to have a fairly intuitive performance model for most operations, unlike Scheme. Also, as I am sure you know, Ada 95 has access to subprogram, which can be used to implement the numerical routines you describe, albeit not as cleanly as you do. By "procedure parameters", I take it that you mean the general case of Pascalish nested procedures, but not Scheme or ML closures, which require more sophisticated (usually garbage collected) runtimes. <... excellent example of how composition of functions leads to concise multidimensional integrator from single dimensional version sadly deleted > Yes, the version with generics isn't as pretty as the version with downward closures in Pascal, even without your extension. I could code the same thing with other Ada 95 features, but I agree that for some things this functional style is very appropriate. Most of all, consider the effect on program style and clarity. Many people, of whom I am one, consider passing procedures as parameters a *fundamental* control structure (really fundamental; people in this camp like to use it as a primitive to explain IF), and while it is possible to program without it, so would it be possible to program in a language with no FOR statements or where no expression was allowed to have more than one operator or where there was no automatic storage allocation. All of these are *possible*, but why make programming any harder than it has to be? I am not the right person to argue against this, since I think it should have been part of the language, but there are arguments about the effect of this feature on implementations using shared generics, and about the impact on existing implementations. At least one company dropped its Ada efforts, ostensibly for the reason of added implementation burden. I think all issues of the interaction of the implementation of downward closures with other parts of the language would have to have been closed for this argument to have been won. As I said above though, I agree that this approach is also easier to understand (more readable!) than the generic approach. In fact it is hard to imagine a more understandable approach... >Maybe a few more useful examples, and a consensus on the implementation >issues would enable this issue to be reopened in the future. Procedures as parameters have been around since the late 1950s. There are many thousands of commercially important Fortran programs and libraries using them. There are libraries full of books about the functional programming paradigm and the importance of procedures as a (not "the", "a") tool of abstraction. Almost all of the books on functional programming use full "upward" closures, which are not quite what Ada would get if these get added to GNAT say. There are also books around on simulating the features of functional languages with "functor" objects. I find these idioms a little clumsy, but I think that I'll wait a while to pronounce judgement. It may be that as I get more used to Ada I'll find those and other methods more palatable... Or maybe they'll all look like Rube Goldberg devices and I'll keep wishing it were different. But for me the choice is not between Ada 95 and Clean or ML, but Ada 95 and C++. Ada 95 still looks very good ;-). -- Brian ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-22 0:00 ` Brian Rogoff @ 1996-07-23 0:00 ` Robert A Duff 1996-07-24 0:00 ` Brian Rogoff 1996-07-24 0:00 ` Richard A. O'Keefe 2 siblings, 0 replies; 133+ messages in thread From: Robert A Duff @ 1996-07-23 0:00 UTC (permalink / raw) In article <ROGOFF.96Jul22154757@sccm.Stanford.EDU>, Brian Rogoff <rogoff@sccm.stanford.edu> wrote: >ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes: > rogoff@sccm.Stanford.EDU (Brian Rogoff) writes: > [about nested procedures as parameters of other procedures] > > >I guess I would ask Pascal programmers how useful they found this, and whether > >any interesting idioms emerged which used this feature. Iterators. - Bob (ex-Pascal-programmer) ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-22 0:00 ` Brian Rogoff 1996-07-23 0:00 ` Robert A Duff @ 1996-07-24 0:00 ` Brian Rogoff 1996-07-26 0:00 ` Robert A Duff 1996-07-30 0:00 ` Brian Rogoff 1996-07-24 0:00 ` Richard A. O'Keefe 2 siblings, 2 replies; 133+ messages in thread From: Brian Rogoff @ 1996-07-24 0:00 UTC (permalink / raw) bobduff@world.std.com (Robert A Duff) writes: Brian Rogoff <rogoff@sccm.stanford.edu> wrote: >.. I'm curious as to >whether you find Pascal style iterators using downward funargs (there, I'm >using Lisp terminology) superior to CLU/Sather-1.0 style iterators. No. When I was a Pascal programmer many years ago, I used procedures-as-params a lot for iterators. But CLU iterators are clearly superior. I don't know Sather, but from what I've read, they seem even more superior. Yes, Sather iterators are a pleasure to use. There is a paper on the web page about their design, and I imagine it has been published by now. On the other hand, their integration into Ada would have been rather major, whereas the Pascal approach would probably have been easier. >...And >how do the Ada 95 alternatives stack up? Not very well, I'm afraid. You can use generics, but you end up with a lot of verbose junk for some simple things. Sigh. Ada generics are great, but it seems that they are (over)used to hide certain ugly little corners of the language (like jgv's mutually recursive types fix). I don't like using them for this. >... Also, were these downward funargs >widely used, or was there a small set of problems in which they were the ideal >vehicle of expression, like the multidimensioal integration example? I'd say Pascal's downward "funargs" were widely used for iterators. At least in the code I saw, and the code I wrote. Anecdotal evidence, but useful. So when the feature was there, people used it a lot. Ada's generics can do *almost* everything that Pascal can do. They can't recurse, in Ada, like they can in Pascal. (I needed that once.) And they're verbose, as I said. Do you feel that they are the right solution though? The generic approach to function composition looked ugly to me, whereas the direct approach looks beautiful. That may be subjective, but I don't think so. I bet even most of the people who argued against this feature in Ada would admit that for this problem, generics are kind of ugly. Smalltalk's version is pretty nice, by the way. You don't pass procedures -- you pass blocks. And that avoids the annoyance of having to name something that doesn't need or deserve a name -- it's just the Body_Of_The_Loop, or whatever. Just like Scheme, which had anonymous and named lambda expressions. I suppose that in a future Ada, called Ada 0X rather than the plaintive sounding Ada 0Y, we could have anonymous downward funargs, as Richard O'Keefe suggested for Pascal. - Bob P.S. I was away for more than a week, so I may have missed some answers to my question about full closures. Did anybody answer that? Was this the "why are they any better than wrapping up the environment and func in a tagged type" question? -- Brian ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-24 0:00 ` Brian Rogoff @ 1996-07-26 0:00 ` Robert A Duff 1996-07-30 0:00 ` Brian Rogoff 1 sibling, 0 replies; 133+ messages in thread From: Robert A Duff @ 1996-07-26 0:00 UTC (permalink / raw) In article <ROGOFF.96Jul24163007@sccm.Stanford.EDU>, Brian Rogoff <rogoff@sccm.stanford.edu> wrote: >Anecdotal evidence, but useful. Anecdotal is all you ever get in this business. ;-) > Ada's generics can do *almost* everything that Pascal can do. They > can't recurse, in Ada, like they can in Pascal. (I needed that once.) > And they're verbose, as I said. > >Do you feel that they are the right solution though? No. They work in many cases, but they're not the best solution. > P.S. I was away for more than a week, so I may have missed some answers > to my question about full closures. Did anybody answer that? > >Was this the "why are they any better than wrapping up the environment and >func in a tagged type" question? Yes. Not just "why are they better", but "why are the a LOT better" (which is the claim I often hear). - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-24 0:00 ` Brian Rogoff 1996-07-26 0:00 ` Robert A Duff @ 1996-07-30 0:00 ` Brian Rogoff 1 sibling, 0 replies; 133+ messages in thread From: Brian Rogoff @ 1996-07-30 0:00 UTC (permalink / raw) bobduff@world.std.com (Robert A Duff) writes: In article <ROGOFF.96Jul26095803@sccm.Stanford.EDU>, Brian Rogoff <rogoff@sccm.stanford.edu> wrote: >I think that you posted that you like Smalltalk blocks a lot, which are >essentially just anonymous closures, right? Yes, I did post that. But it's not because they are full closures -- almost all of the uses in my code, and almost all of the uses I've seen, are the downward kind. On reflection, this makes a lot of sense, because a lot of the uses I saw of full closures in Scheme (in the SICP book) would use Smalltalk objects. So in a language with both objects and closures, full closures might seem redundant. If your experience can be generalized, it seems like some kind of (potentially anonymous) downward closure construct would fit in well with the Ada ideal of "high abstraction if it can be easily implemented efficiently". I guess that this is one of the constructs Magnus Kempe had in mind when he mentioned that he thought Ada could have headed further in the direction of functional programming. <... other reasons for liking anonymous blocks deleted ...> >....I think the beauty of this >construct is that you can implement lots of features cleanly in terms of >it, like control structures. No, that merely requires downward closures. I'm still looking for an example that really makes the upward direction look wonderfully powerful. I'm still thinking :-). I don't know if you'll find a "killer example", just a wide range of examples that can be solved using closures. >...Also the implementation of closures on objects >seems heavy/verbose to me. True. But that's OK, unless full closures are really as powerful and commonly needed as I've heard. Powerful, yes. If you have objects, downward closures, packages and generics, they might be a bit redundant. -- Brian ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-22 0:00 ` Brian Rogoff 1996-07-23 0:00 ` Robert A Duff 1996-07-24 0:00 ` Brian Rogoff @ 1996-07-24 0:00 ` Richard A. O'Keefe 1996-07-26 0:00 ` Ken Garlington 2 siblings, 1 reply; 133+ messages in thread From: Richard A. O'Keefe @ 1996-07-24 0:00 UTC (permalink / raw) rogoff@sccm.Stanford.EDU (Brian Rogoff) writes: >Idiom in the sense of "pattern", an interesting interaction with other >features of the language they appear in. I didn't say that I didn't grasp the *meaning* of the word "idiom" in this context, only that I didn't grasp the *intent* of the question. The point is that this is such a basic and quirk-free building block that you don't think in terms of "idioms" for it any more than you think in terms of there being special idioms for assignment statements or while loops. >Scheme was my first language. I like it, and I understand the benefits of >closures and lazy evaluation and such. But Ada is designed to have a fairly >intuitive performance model for most operations, unlike Scheme. Concerning performance models: I spent this afternoon (when not talking to students) taking the integration example and beefing it up to the point where it would plausibly take a reasonable amount of time. I produced three versions: Ada (using generic instantiation) compiled with gnatmake -gnatp -cargs -O4 Size: 94 lines. Pascal (using nested procedures passed as parameters) compiled with SPARCompiler 4.0 pc -s -native -O4 Size: 57 lines. Scheme compiled with stalin -copt "-O4" -d -On -dc (this compiles Scheme to C, then uses gcc as a back end) Size: 40 lines. Guess what: the Pascal and Ada versions both took 18 seconds on a "sunu4, Ultra-Enterprise", whatever that is, while the Scheme version took 6 seconds. I guess Scheme running 3 times faster than Ada or Pascal is not "intuitive" for many programmers. To be really honest, I *thought* I knew what the cost model for generics was, but have heard repeatedly in this newsgroup that I shouldn't think of generic instantiation as macro instantiation. >Also, as I am sure you know, Ada 95 has access to subprogram, which can be >used to implement the numerical routines you describe, albeit not as cleanly >as you do. Yes, I do know. The point I am defending, which has been made before by others, is that "access to procedure" is one thing, and "procedure as parameter" is another, and that you don't *need* to allow access to procedure in order to either implement or use procedure as parameter, and you particularly don't need to allow restrictions related to the former to limit the use of the latter. >By "procedure parameters", I take it that you mean the general case >of Pascalish nested procedures, but not Scheme or ML closures, which require >more sophisticated (usually garbage collected) runtimes. Exactly so. Although the code generated for the Scheme version of this program uses stack allocation and does (and _can_ do) no garbage collection. > <... excellent example of how composition of functions leads to concise > multidimensional integrator from single dimensional version > sadly deleted > >> Most of all, consider the effect on program style and clarity. In this particular case (big is bad). Scheme : Pascal : Ada Size 4 : 6 : 9 Time 1 : 3 : 3 DO NOT EXTRAPOLATE THE SIZE OR TIME NUMBERS TO OTHER KINDS OF PROBLEMS. >I am not the right person to argue against this, since I think it should have >been part of the language, but there are arguments about the effect of this >feature on implementations using shared generics, and about the impact on >existing implementations. I must have missed the discussion of how this would affect shared generics. I am all in favour of shared generics, but surely generics cannot _always_ be shared, so there's always a fallback strategy, or have I misunderstood? >Almost all of the books on functional programming use full "upward" closures, >which are not quite what Ada would get if these get added to GNAT say. This is misleading. They use *languages* in which there are few or no restrictions on closures. This does not mean that every *program* using closures in these books or in day-to-day functional programming uses upward closures all over the place. >Or maybe they'll all look like Rube Goldberg devices and I'll keep wishing >it were different. But for me the choice is not between Ada 95 and Clean or >ML, but Ada 95 and C++. Ada 95 still looks very good ;-). Well, if you want object orientation, there's O'Caml, which is supposed to be pretty good. -- Fifty years of programming language research, and we end up with C++ ??? Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-24 0:00 ` Richard A. O'Keefe @ 1996-07-26 0:00 ` Ken Garlington 1996-07-30 0:00 ` Richard A. O'Keefe 0 siblings, 1 reply; 133+ messages in thread From: Ken Garlington @ 1996-07-26 0:00 UTC (permalink / raw) Richard A. O'Keefe wrote: > > Ada (using generic instantiation) > compiled with gnatmake -gnatp -cargs -O4 > Size: 94 lines. I don't know how to read the gnat command lines, so could some one tell me if this means all exceptions are suppressed? Also, is source line size being given here as a measure of efficiency? What were the other measures compared to the alternatives (readability, reusability, etc.)? > I guess Scheme running 3 times faster than Ada or Pascal is not "intuitive" > for many programmers. It's certainly not intuitive to _me_. However, I would certainly have no problem with a statement that a particular Scheme toolset might generate code that is three times more efficient than an Ada _toolset_, for a given host/target platform. (Do we really believe GNAT is the most efficient Ada compiler available, for example? I keep reading that not all optimizations have been implemented in GNAT yet...) -- LMTAS - "Our Brand Means Quality" ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-26 0:00 ` Ken Garlington @ 1996-07-30 0:00 ` Richard A. O'Keefe 0 siblings, 0 replies; 133+ messages in thread From: Richard A. O'Keefe @ 1996-07-30 0:00 UTC (permalink / raw) Ken Garlington <garlingtonke@lmtas.lmco.com> writes: >Richard A. O'Keefe wrote: >> >> Ada (using generic instantiation) >> compiled with gnatmake -gnatp -cargs -O4 >> Size: 94 lines. >I don't know how to read the gnat command lines, so could some one tell me >if this means all exceptions are suppressed? If I may quote from "gnatinfo.txt" To disable constraint checks, compile the program with th "-gnatp" option. This is equivalent to having Pragma suppress applied to everything. So yes, it does suppress everything. -O4 is high optimisation level. >Also, is source line size being given here as a measure of efficiency? Don't be ridiculous, of *course* not. The number of source lines required to express the same algorithm naturally is an inverse measure of EXPRESSIVENESS, and has no intrinsic connexion whatsoever with efficiency. Why would you imagine otherwise? The sole measure of efficiency I proposed is TIME. >What were the other measures compared to the alternatives >(readability, reusability, etc.)? Obviously, if it takes you more lines, it's likely to be harder to read. I have no objective measurements of readability. I believe that I am equally familiar with all four languages (I have, and have studied hard, the standards for all of them, and have written a fair amount of code in all four). In this case: Scheme is the most readable. Pascal comes close; no warping to fit the language. The C code is shorter, but it has some nasty internal coupling, so I rank the Ada code (all connections explicit) as more readable (though longer) than the C. As for re-use, where I can be objective: Scheme is by far the most reusable, having no constraints on reuse at all. The Pascal code is cut-and-paste reusable; in Turbo Pascal or Think Pascal or ISO Pascal Extended the integration code could be in a unit/module. The Ada code is as reusable as the Pascal code, in the sense of requiring no modifications for reuse, but has higher reuse costs. (It takes more source code to effect reuse, and generates more object code). The C code was not written for re-use. The need to explicitly simulate funargs by passing environment pointers pushes up reuse cost; unlike the Scheme and Pascal code you cannot combine the integration functions with *existing* real-valued functions but must write glue code. >> I guess Scheme running 3 times faster than Ada or Pascal is not "intuitive" >> for many programmers. >It's certainly not intuitive to _me_. However, I would certainly have no problem >with a statement that a particular Scheme toolset might generate code that is >three times more efficient than an Ada _toolset_, for a given host/target >platform. (Do we really believe GNAT is the most efficient Ada compiler available, >for example? I keep reading that not all optimizations have been implemented in >GNAT yet...) For sure. Stalin has a fair bit in common, I think, with VORTEX, with the Self compiler, and with Stanford's FUSE. The common factor here is tools that start with very high level languages and optimise the heck out of them; there are analyses and transformations that they perform which I expect Gnat will _never_ perform. Partly this is because they deal with simpler languages. For Ada, I think it is more important to get tasking absolutely right than to perform aggressive optimisations. Note also that in a previous thread in this group I was pleased to report that GNAT's time for a certain numerical program was close to the time from SPARCompiler Fortran 77. Whether or not GNAT is the best, it is pretty darned good. But please, don't attack a proposition your interlocutor never defended. Gnat is the best Ada compiler *I've* got, that's all. So far I have tried this example in Clean 1.0 -- not the latest version Gambit 2.2.2 -- pretty recent, but maybe not the latest Think C 5.0 -- far from the latest version on the Mac Gnat 3.04 -- not the latest version SPARCompiler C 4.0 -- is the latest version SPARCompiler Pascal 4.0 -- is the latest version Gcc 2.7.2 -- probably not the latest any more Stalin 0.6 -- latest generally available on an UltraSparc. Why these versions? Because that's what I've got. That's all. Remember: I am not interested in establishing which _language_ is the best. My sole concern was to provide an example showing that the restrictions on procedure parameters which make my example *impossible* to write directly in Ada 95 are not *necesary* for efficiency. This does not, unfortunately, prove that it would be easy for _any_ Ada vendor to support Algol-style funargs, still less that it would have been affordable for _every_ Ada vendor to do so. ALL my example can accomplish, and I believe it does accomplish this, is to show that Algol/Pascal-style funargs are fully consistent with more efficiency than I can currently get from a good Ada compiler. -- Fifty years of programming language research, and we end up with C++ ??? Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Jon S Anthony ` (4 preceding siblings ...) 1996-07-22 0:00 ` Brian Rogoff @ 1996-07-24 0:00 ` Brian Rogoff 1996-07-26 0:00 ` Richard A. O'Keefe ` (2 subsequent siblings) 8 siblings, 0 replies; 133+ messages in thread From: Brian Rogoff @ 1996-07-24 0:00 UTC (permalink / raw) ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes: Concerning performance models: I spent this afternoon (when not talking to students) taking the integration example and beefing it up to the point where it would plausibly take a reasonable amount of time. I produced three versions: Ada (using generic instantiation) compiled with gnatmake -gnatp -cargs -O4 Size: 94 lines. Pascal (using nested procedures passed as parameters) compiled with SPARCompiler 4.0 pc -s -native -O4 Size: 57 lines. Scheme compiled with stalin -copt "-O4" -d -On -dc (this compiles Scheme to C, then uses gcc as a back end) Size: 40 lines. Guess what: the Pascal and Ada versions both took 18 seconds on a "sunu4, Ultra-Enterprise", whatever that is, while the Scheme version took 6 seconds. I guess Scheme running 3 times faster than Ada or Pascal is not "intuitive" for many programmers. Note that the Pascal compiler was not any better than GNAT on this. The data does suggest that the nested procedure approach may have performance advantages in addition to its general advantages as a simple programming construct. What is stalin doing? Is it dependent on any simplifying assumptions about the code? To be really honest, I *thought* I knew what the cost model for generics was, but have heard repeatedly in this newsgroup that I shouldn't think of generic instantiation as macro instantiation. I like Ada generics, but this is one of those cases where using generics as a workaround seems ugly to me, so I'd write integrators differently. I agree with your point that generics are one of the parts of the language model where the performance model is less clear. >> Most of all, consider the effect on program style and clarity. In this particular case (big is bad). Scheme : Pascal : Ada Size 4 : 6 : 9 Time 1 : 3 : 3 DO NOT EXTRAPOLATE THE SIZE OR TIME NUMBERS TO OTHER KINDS OF PROBLEMS. This is a nice little example of the conciseness of this style, and I think anyone would be hard pressed to say that the Ada version would be more readable. >I am not the right person to argue against this, since I think it should have >been part of the language, but there are arguments about the effect of this >feature on implementations using shared generics, and about the impact on >existing implementations. I must have missed the discussion of how this would affect shared generics. I am all in favour of shared generics, but surely generics cannot _always_ be shared, so there's always a fallback strategy, or have I misunderstood? It was one of the refs in Norman Cohen's precis of the discussion, from Randy Brukardt at RR Software. Here is the relevant excerpt: --------------------------------------------------------------------------- To put the problem in a nutshell: If 'Access is allowed in generic bodies, generic code sharing requires distributed overhead. (Or compilers have to do body analysis of generics in order to prevent sharing on them). To explain this in detail, I'd have to give a crash course on the construction of shared generics. However, here is a simplified version of the problem: A shared generic passes in some way a pointer to a data area identifying the generic, and containing its local objects. [Note that this exists in any but the most simplified versions of sharing - any sharing algorithm which allows data in the generic specification or body would have the problem]. However, an access-to-subprogram does not know that the routine comes from a generic, or even which generic. The solution to this problem in the specification is to construct a 'wrapper' routine at instantiation time, which knows about the appropriate generic instantiation. However, a wrapper cannot be built for 'Accesses in the generic body inside the generic body. To do so at instantiation time requires that the body be compiled before the instantiation, something that has generally been considered bad in Ada 83. Doing so eliminates virtually all of the advantages of sharing. The main alternative would be to carry and add generic data to every use of a access to subprogram object - a significant distributed overhead. (Note that GNU's solution of generating the wrapper at runtime will not work on some operating systems, because these systems prohibit self-modifying code for security reasons. We have even had problems doing this on some UNIX systems, for this reason. Therefore, it is not a generally applicable solution). The result that that eliminating the restrictions on 'Access would make some code easy to write, but would force the junking of existing code sharing algorithms, or make the cost of access-to-subprogram substantially higher than in competing languages. Those both are very bad ideas. Randy. --------------------------------------------------------------------------- >Almost all of the books on functional programming use full "upward" closures, >which are not quite what Ada would get if these get added to GNAT say. This is misleading. They use *languages* in which there are few or no restrictions on closures. This does not mean that every *program* using closures in these books or in day-to-day functional programming uses upward closures all over the place. How much are upward funargs used in day to day functional programming? I think Bob Duff is still looking for a compelling example of why they are so much better than the explicitly simulated closure via an instance of a tagged type. >Or maybe they'll all look like Rube Goldberg devices and I'll keep wishing >it were different. But for me the choice is not between Ada 95 and Clean or >ML, but Ada 95 and C++. Ada 95 still looks very good ;-). Well, if you want object orientation, there's O'Caml, which is supposed to be pretty good. I've played with it. The Win NT versions' GUI doesn't work. The language is nice, but I often do work where I can't tolerate boxing of certain types, like numerical or pixel types in arrays, and CAML is a bit weak here. Ada bindings to the Win 32 API also help. -- Brian ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Jon S Anthony ` (5 preceding siblings ...) 1996-07-24 0:00 ` Brian Rogoff @ 1996-07-26 0:00 ` Richard A. O'Keefe 1996-07-28 0:00 ` Robert A Duff 1996-07-28 0:00 ` Fergus Henderson 1996-07-29 0:00 ` Richard A. O'Keefe 1996-07-30 0:00 ` Jon S Anthony 8 siblings, 2 replies; 133+ messages in thread From: Richard A. O'Keefe @ 1996-07-26 0:00 UTC (permalink / raw) ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes: > I spent this afternoon (when not talking to students) taking the > integration example and beefing it up to the point where it would > plausibly take a reasonable amount of time. I produced three > versions: [now four, using two C compilers] Lang Time Size How compiled Ada 18 94 3.04 gnatmake -gnatp -cargs -O4 Pascal 18 57 SPARCompiler 4.0 pc -s -native -O4 C 20 92 2.7.2 gcc -O4 C 13 92 SPARCompiler 4.0 cc -fsimple -native -fast -xO4 Scheme 6 40 stalin -copt "-O4" -d -On -dc Scheme 5 40 stalin -cc cc -copt "-native -xO4" -d -On Seconds Lines rogoff@sccm.Stanford.EDU (Brian Rogoff) writes: >Note that the Pascal compiler was not any better than GNAT on this. The C code simulates a model where top level procedures do not have a static link, but nested procedures do (a realistic implementation model). The C times bracket the Ada/Pascal times. The really interesting thing was that the Ada, Pascal, and Scheme versions worked the first time they got through the compiler, while the C version crashed. (lclint pointed me to an uninitialised variable...) >The data >does suggest that the nested procedure approach may have performance >advantages in addition to its general advantages as a simple programming >construct. What is stalin doing? Is it dependent on any simplifying >assumptions about the code? The -d option says "inexact numbers are C doubles". The -On option says "do not check for exact integer overflow", which I put in to make the comparison fair. The -dc option says "yes you can use alloca"; as you see from the last line, leaving it out didn't make much difference. Does Stalin make any simplifying assumptions about the code? Well, it doesn't support bignums or rationals (neither do Ada, Pascal, or C). It doesn't support complex arithmetic (neither does C, and neither does SPARCompiler Pascal, even though it's in the current standard.) It doesn't support DELAY/FORCE (nor do Ada, Pascal, or C). It doesn't support LOAD (adding new code at run time, or replacing existing code). Neither do Ada, Pascal, or C. Stalin makes *no* other assumptions about the program. Even CAR and CDR receive no special magic treatment. It just does a really thorough job of static analysis and optimisation. Jeff Siskind has put a *lot* of work into the algorithms in this compiler. It's a one-man show; he is the only one working on it, and his latest grant proposal to do more work on it was turned down, so it is also by a rather large margin the slowest of the compilers tested. This is a pity, because while a lot of the methods in Stalin are related to dynamically typed languages, "Stalin also does global static life-time analysis for all allocated data. This allows much temporary allocated storage to be reclaimed without garbage collection. Finally, Stalin has very efficient strategies for compiling closures." Of course, when you introduce OOP, dynamic typing joins the party, so it's not that clear that Stalin has nothing to contribute to the art of Ada compilation. >A shared generic passes in some way a pointer to a data area identifying the >generic, and containing its local objects. I see. This is like "type classes" as found in Mercury and Haskell. I note that Haskell manages to combine this with unrestricted closures; I don't know how the Glasgow Haskell Compiler handles it, but I don't _think_ it involves run-time code generation. >The result that that eliminating the restrictions on 'Access would make some >code easy to write, but would force the junking of existing code sharing >algorithms, or make the cost of access-to-subprogram substantially higher than >in competing languages. Those both are very bad ideas. Ah *hah*. This is *not* an argument against procedure parameters, it is an argument against identifying them with procedure *pointers*. The force of the integration example is that even though current Ada "has" procedure parameters they can't be *used* for the things that people have historically wanted to use them for, Now I understand why it was thought that the maximum size of the display mattered: people wanted to know how much stuff to put in a procedure pointer, and a procedure pointer of a type declared at lexlevel N needs N+c pointers, and a pointer declared who-knows-where needs who-knows-how-many pointers. Fine, but NONE of this is a problem with procedure parameters, only with bodging them up Borland-style as procedure pointers. >How much are upward funargs used in day to day functional programming? I >think Bob Duff is still looking for a compelling example of why they are >so much better than the explicitly simulated closure via an instance of a >tagged type. Whenever you simulate any mechanism, - you lose clarity This is demonstrated by the line numbers. - you introduce the risk of error The Scheme and Pascal versions didn't have to "simulate" anything. They worked, as soon as the compiler was happy with them. The C version crashed, precisely *because* having to simulate the feature added complexity, and I slipped, even though I was transcribing code, not rewriting from scratch. All I had to worry about was how to simulate the feature, in < 100 lines of code, and I got it wrong. - you lose efficiency. The compiler doesn't understand the feature. It compiles your simulation using general methods. In this example, even when I told the SPARCompiler C compiler (there is no redundancy there; that's it's name) to in-line some crucial functions, it didn't improve the speed. The fact that Stalin really thoroughly understands procedures does pay off in this small example where procedure calling is a major cost factor. One might as well say, "why have direct language support for OOP? You can always simulate it!" And in fact Scheme programmers have often said this, because a language that takes procedures really seriously makes it dead simple to simulate OOP with procedures. -- Fifty years of programming language research, and we end up with C++ ??? Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-26 0:00 ` Richard A. O'Keefe @ 1996-07-28 0:00 ` Robert A Duff 1996-07-29 0:00 ` Richard A. O'Keefe 1996-07-28 0:00 ` Fergus Henderson 1 sibling, 1 reply; 133+ messages in thread From: Robert A Duff @ 1996-07-28 0:00 UTC (permalink / raw) In article <4t9un9$imn@goanna.cs.rmit.edu.au>, Richard A. O'Keefe <ok@goanna.cs.rmit.edu.au> wrote: >>How much are upward funargs used in day to day functional programming? I >>think Bob Duff is still looking for a compelling example of why they are >>so much better than the explicitly simulated closure via an instance of a >>tagged type. > >Whenever you simulate any mechanism, >...[all manner of evil happens] True, but the logical conclusion is that all useful mechanisms that anybody has ever thought of should be included in the language. One has to make a trade-off between a useful gizmo and language complexity (etc). Anyway, I think this argument is getting confused between "downward closures" and "full closures". If I understand your example correctly, it needs downward closures, but not full closures. True? I have argued in favor of downward closures (because in my experience they have been very useful, and they are very cheap to implement). But I remain unconvinced about full closures (because they seem less commonly needed, and they are substantially more expensive to implement -- although your benchmark shows that in at least one case, the run-time cost is a myth). And the only serious example anybody posted was Ackermann's function, which is useful in explaining how full closures work, but doesn't exactly make me want to use them every day. I have never in my entire career needed to compute Ackermann's function, as far as I can recall. ;-) - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-28 0:00 ` Robert A Duff @ 1996-07-29 0:00 ` Richard A. O'Keefe 1996-07-29 0:00 ` Robert A Duff 0 siblings, 1 reply; 133+ messages in thread From: Richard A. O'Keefe @ 1996-07-29 0:00 UTC (permalink / raw) bobduff@world.std.com (Robert A Duff) writes: >>Whenever you simulate any mechanism, >>...[all manner of evil happens] >True, but the logical conclusion is that all useful mechanisms that >anybody has ever thought of should be included in the language. One has >to make a trade-off between a useful gizmo and language complexity >(etc). I do not call that a logical conclusion. "All useful mechanisms which have ever been *commonly used* should be included" comes closer to being a reasonable generalisation of what I wrote. >Anyway, I think this argument is getting confused between "downward >closures" and "full closures". If I understand your example correctly, >it needs downward closures, but not full closures. Right. And that is all _I_ have ever been talking about in this thread. As it happens, I like full closures, principally because they fit very well with a "building blocks" approach to reuse, and because it greatly simplifies things like graphic programming in Clean: it's the *compiler's* job to worry about which things need to survive for a callback, not mine. But I am not advocating full closures (or continuations, or first class environments, or anything sexy) for Ada. All I am saying is that one specific feature -- downward funargs -- has proven its usefulness over many years in a lot of other languages, is demonstrably clumsy to simulate in Ada 83, can demonstrably be implemented efficiently by a compiler (5 seconds for the program in Scheme compiled by Stalin into C then into SPARC code by SPARCompiler C SC4.0, compared with 18 seconds for the program in Ada compiled by GNAT 3.04 GCC 2.7.2), was expected for Ada 95, but arrived in an unusable fashion because that feature was confounded with another feature, namely access-to-procedure. You can have nested procedures as parameters without procedure pointers (Pascal, Fortran, Algol 60). You have have procedure pointers without nested procedures as parameters (C). You can have both without restriction (Lisp, Scheme, ML, Smalltalk). The point is, you don't *have* to tangle them up, and the restrictions that are necessary for the one (procedure pointers) if you don't want to support full closures are NOT necessary for the other (procedures as parameters). Not only that, you *can* tangle them up in a different way from the Ada 95 way: you say that the lexical level of a procedure parameter is the lexical level of the procedure in whose header it appears, and forbid (copies) of that parameter outliving the callee. So it would have been possible to have both procedure pointers with a lexical level restriction (thus permitting an implementation in which library level pointers are fully compatible with C) *and* unrestricted passing of nested procedures as parameters. >I have argued >in favor of downward closures (because in my experience they have been >very useful, and they are very cheap to implement). But I remain >unconvinced about full closures (because they seem less commonly needed, >and they are substantially more expensive to implement -- although your >benchmark shows that in at least one case, the run-time cost is a myth). Ahem. My benchmark is solely concerned with DOWNward closures, not full closures. Just because I ran the benchmark in a language which supports full closures doesn't mean that the benchmark itself used that power. >And the only serious example anybody posted was Ackermann's function, >which is useful in explaining how full closures work, but doesn't >exactly make me want to use them every day. Well, the classic application of full closures in Scheme is OOP. Scheme has far too many OOP dialects, because it is extremely easy for everyone to implement their own OOP system using closures. The classic *idiom* using closures is simulating modules: (define export1) ; top level placeholder declarations (define export2) (let ( <<local declarations >> ) (set! export1 (lambda <<args>> <<body>>)) (set! export2 (lambda <<args>> <<body>>))) The exported functions have access to the local declarations. My argument about simulation extends to this as well: it is better to have a module construct so that the compiler knows what you are up to and can check that you got it right. -- Fifty years of programming language research, and we end up with C++ ??? Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-29 0:00 ` Richard A. O'Keefe @ 1996-07-29 0:00 ` Robert A Duff 0 siblings, 0 replies; 133+ messages in thread From: Robert A Duff @ 1996-07-29 0:00 UTC (permalink / raw) In article <4tha38$1p@goanna.cs.rmit.edu.au>, Richard A. O'Keefe <ok@goanna.cs.rmit.edu.au> wrote: >I do not call that a logical conclusion. >"All useful mechanisms which have ever been *commonly used* should be >included" comes closer to being a reasonable generalisation of what I >wrote. Fair enough. >Ada 95, but arrived in an unusable fashion because that feature was >confounded with another feature, namely access-to-procedure. I don't understand why you say that. It's not historically accurate. The MRT was well aware of the two different features, and proposed two different features, with different sets of rules. The "passing nested procedures as params" features was not included in the final design. You can complain about that fact (and I will agree), but you shouldn't complain that the language designers "confounded" the two features -- they didn't. >Ahem. My benchmark is solely concerned with DOWNward closures, not full >closures. Just because I ran the benchmark in a language which supports >full closures doesn't mean that the benchmark itself used that power. Right. I just meant that your benchmark shows that it's possible for downward closures to be efficient even in a language that has full closures (a distributed overhead issue). We already knew that, of course -- there are compilers for many languages that require heap-allocated stack frames in general, but are capable of avoiding that it many cases. And anyway, your benchmark is just one example, and thus not very convincing on this point. >Well, the classic application of full closures in Scheme is OOP. Which of course doesn't convince *me* that full closures are a Very Good Thing, since I'm happy to have the OOP features built in, and do the "similating" in the other direction. >My argument about simulation extends to this as well: it is better to have >a module construct so that the compiler knows what you are up to and can >check that you got it right. ... And apparently you agree. Either one can be used to "simulate" the other. So, is there any reason to have both? - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-26 0:00 ` Richard A. O'Keefe 1996-07-28 0:00 ` Robert A Duff @ 1996-07-28 0:00 ` Fergus Henderson 1 sibling, 0 replies; 133+ messages in thread From: Fergus Henderson @ 1996-07-28 0:00 UTC (permalink / raw) ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes: >This is like "type classes" as found in Mercury and Haskell. Mercury doesn't have type classes, I'm afraid, only pure parametric polymorphism. Maybe in some later version... (You can do the same sort of things using parametric polymorphism by explicitly passing the necessary operations as higher-order predicates or functions, but it's a bit more cumbersome than Haskell's type classes.) -- Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit" PGP: finger fjh@128.250.37.3 | -- the last words of T. S. Garp. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Jon S Anthony ` (6 preceding siblings ...) 1996-07-26 0:00 ` Richard A. O'Keefe @ 1996-07-29 0:00 ` Richard A. O'Keefe 1996-07-30 0:00 ` Jon S Anthony 8 siblings, 0 replies; 133+ messages in thread From: Richard A. O'Keefe @ 1996-07-29 0:00 UTC (permalink / raw) ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes: > I spent this afternoon (when not talking to students) taking the > integration example and beefing it up to the point where it would > plausibly take a reasonable amount of time. I produced three > versions: [now four, using two C compilers] Lang Time Size How compiled Ada 18 94 3.04 gnatmake -gnatp -cargs -O4 Pascal 18 57 SPARCompiler 4.0 pc -s -native -O4 C 20 92 2.7.2 gcc -O4 C 13 92 SPARCompiler 4.0 cc -fsimple -native -fast -xO4 Scheme 6 40 stalin -copt "-O4" -d -On -dc Scheme 5 40 stalin -cc cc -copt "-native -xO4" -d -On Seconds Lines [All of these were double precision; single precision trimmed 1 second off the time for C and Pascal, made no apparent change for Ada, and had yet to be tried at the time of reposting for Scheme.] rogoff@sccm.Stanford.EDU (Brian Rogoff) writes: >Note that the Pascal compiler was not any better than GNAT on this. The C code simulates a model where top level procedures do not have a static link, but nested procedures do (a realistic implementation model). The C times bracket the Ada/Pascal times. The really interesting thing was that the Ada, Pascal, and Scheme versions worked the first time they got through the compiler, while the C version crashed. (lclint pointed me to an uninitialised variable...) >The data >does suggest that the nested procedure approach may have performance >advantages in addition to its general advantages as a simple programming >construct. What is stalin doing? Is it dependent on any simplifying >assumptions about the code? The -d option says "inexact numbers are C doubles". The -On option says "do not check for exact integer overflow", which I put in to make the comparison fair. The -dc option says "yes you can use alloca"; as you see from the last line, leaving it out didn't make much difference. Does Stalin make any simplifying assumptions about the code? Well, it doesn't support bignums or rationals (neither do Ada, Pascal, or C). It doesn't support complex arithmetic (neither does C, and neither does SPARCompiler Pascal, even though it's in the current standard.) It doesn't support DELAY/FORCE (nor do Ada, Pascal, or C). It doesn't support LOAD (adding new code at run time, or replacing existing code). Neither do Ada, Pascal, or C. Stalin makes *no* other assumptions about the program. Even CAR and CDR receive no special magic treatment. It just does a really thorough job of static analysis and optimisation. Jeff Siskind has put a *lot* of work into the algorithms in this compiler. It's a one-man show; he is the only one working on it, and his latest grant proposal to do more work on it was turned down, so it is also by a rather large margin the slowest of the compilers tested. This is a pity, because while a lot of the methods in Stalin are related to dynamically typed languages, "Stalin also does global static life-time analysis for all allocated data. This allows much temporary allocated storage to be reclaimed without garbage collection. Finally, Stalin has very efficient strategies for compiling closures." Of course, when you introduce OOP, dynamic typing joins the party, so it's not that clear that Stalin has nothing to contribute to the art of Ada compilation. >A shared generic passes in some way a pointer to a data area identifying the >generic, and containing its local objects. I see. This is like "type classes" as found in Mercury and Haskell. I note that Haskell manages to combine this with unrestricted closures; I don't know how the Glasgow Haskell Compiler handles it, but I don't _think_ it involves run-time code generation. >The result that that eliminating the restrictions on 'Access would make some >code easy to write, but would force the junking of existing code sharing >algorithms, or make the cost of access-to-subprogram substantially higher than >in competing languages. Those both are very bad ideas. Ah *hah*. This is *not* an argument against procedure parameters, it is an argument against identifying them with procedure *pointers*. The force of the integration example is that even though current Ada "has" procedure parameters they can't be *used* for the things that people have historically wanted to use them for, Now I understand why it was thought that the maximum size of the display mattered: people wanted to know how much stuff to put in a procedure pointer, and a procedure pointer of a type declared at lexlevel N needs N+c pointers, and a pointer declared who-knows-where needs who-knows-how-many pointers. Fine, but NONE of this is a problem with procedure parameters, only with bodging them up Borland-style as procedure pointers. >How much are upward funargs used in day to day functional programming? I >think Bob Duff is still looking for a compelling example of why they are >so much better than the explicitly simulated closure via an instance of a >tagged type. Whenever you simulate any mechanism, - you lose clarity This is demonstrated by the line numbers. - you introduce the risk of error The Scheme and Pascal versions didn't have to "simulate" anything. They worked, as soon as the compiler was happy with them. The C version crashed, precisely *because* having to simulate the feature added complexity, and I slipped, even though I was transcribing code, not rewriting from scratch. All I had to worry about was how to simulate the feature, in < 100 lines of code, and I got it wrong. - you lose efficiency. The compiler doesn't understand the feature. It compiles your simulation using general methods. In this example, even when I told the SPARCompiler C compiler (there is no redundancy there; that's it's name) to in-line some crucial functions, it didn't improve the speed. The fact that Stalin really thoroughly understands procedures does pay off in this small example where procedure calling is a major cost factor. One might as well say, "why have direct language support for OOP? You can always simulate it!" And in fact Scheme programmers have often said this, because a language that takes procedures really seriously makes it dead simple to simulate OOP with procedures. -- Fifty years of programming language research, and we end up with C++ ??? Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Jon S Anthony ` (7 preceding siblings ...) 1996-07-29 0:00 ` Richard A. O'Keefe @ 1996-07-30 0:00 ` Jon S Anthony 8 siblings, 0 replies; 133+ messages in thread From: Jon S Anthony @ 1996-07-30 0:00 UTC (permalink / raw) In article <4tha38$1p@goanna.cs.rmit.edu.au> ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes: [...] > simulate in Ada 83, can demonstrably be implemented efficiently by a > compiler (5 seconds for the program in Scheme compiled by Stalin into C > then into SPARC code by SPARCompiler C SC4.0, compared with 18 seconds for > the program in Ada compiled by GNAT 3.04 GCC 2.7.2), was expected for > Ada 95, but arrived in an unusable fashion because that feature was > confounded with another feature, namely access-to-procedure. [...] > > The point is, you don't *have* to tangle them up, and the restrictions > that are necessary for the one (procedure pointers) if you don't want > to support full closures are NOT necessary for the other (procedures > as parameters). Exactly so. What is more, this particular scheme was in fact considered: access to procedure parameters. It would have fit fairly well with the language (maybe even rather well) in this area. But it seems that certain of those involved becamed "obsessed" with the view that the only way to achieve the effect was with some sort of access-to-procedure _type_ (the so called limited access type in particular). > Not only that, you *can* tangle them up in a different way from the > Ada 95 way: you say that the lexical level of a procedure parameter > is the lexical level of the procedure in whose header it appears, > and forbid (copies) of that parameter outliving the callee. Meaning simply that only procedures at or below the lex level of the procedure P with the parameter could be legally supplied in a call of P. I suppose in this context (still involving an access type) the access to subprogram type to which the procedure access would belong would also have to be at or below P (which would effectively cover the stuff in the first sentence...) > So it would have been possible to have both procedure pointers with a > lexical level restriction (thus permitting an implementation in which > library level pointers are fully compatible with C) *and* unrestricted > passing of nested procedures as parameters. Certainly sounds right. So, what are the gotchas?... /Jon -- Jon Anthony Organon Motives, Inc. 1 Williston Road, Suite 4 Belmont, MA 02178 617.484.3383 jsa@organon.com ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 ` Robert A Duff 1996-07-02 0:00 ` Robert Dewar 1996-07-03 0:00 ` Jon S Anthony @ 1996-07-03 0:00 ` Fergus Henderson 1996-07-03 0:00 ` Robert A Duff 1996-07-05 0:00 ` Jon S Anthony ` (13 subsequent siblings) 16 siblings, 1 reply; 133+ messages in thread From: Fergus Henderson @ 1996-07-03 0:00 UTC (permalink / raw) bobduff@world.std.com (Robert A Duff) writes: >During the design of Ada 9X, we proposed a SAFE way of taking 'Access of >more-deeply-nesting subprograms. To this day, I remain astonished and >sad that this particular feature didn't make it into Ada 95. What was the safe way that you proposed? -- Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit" PGP: finger fjh@128.250.37.3 | -- the last words of T. S. Garp. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Fergus Henderson @ 1996-07-03 0:00 ` Robert A Duff 1996-07-03 0:00 ` Robert Dewar 1996-07-03 0:00 ` Adam Beneschan 0 siblings, 2 replies; 133+ messages in thread From: Robert A Duff @ 1996-07-03 0:00 UTC (permalink / raw) In article <4rd5lu$q4@mulga.cs.mu.OZ.AU>, Fergus Henderson <fjh@mundook.cs.mu.OZ.AU> wrote: >What was the safe way that you proposed? There were two variations, actually. 1. Limited access types. You would say: type T is limited access procedure(...); T would be limited, meaning no assignment. Without assignment, you can't create dangling pointers to procedures. You could pass values of type T into subprograms, but all the subprogram could do is call through that value, or pass it on -- not copy it into a global variable. 2. Access-to-subprogram parameters. You would say: procedure Foo(X: Integer; Y: access procedure(B: Boolean)); This syntax is reminiscent of Pascal's. There would be a run-time accessibility check on various operations on Y, just like the access parameters that DO exist in the language (e.g. "Y: access Integer"). This would allow you to pass procedures around, and call them, as in option (1). You could also copy them to *local* variables (that is, inside Foo, you could say "Local := Local_Access_Type(Y)), but any attempt to copy to a global variable would require some sort of type_conversion or whatever that would fail the run-time check. I preferred option (1) at the time. Now, GNAT has gone and provided the same capability, using an implementation-defined attribute (Unrestricted_Access), but unfortunately, this attribute allows dangling pointers to subprograms, unlike either of the above options. - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Robert A Duff @ 1996-07-03 0:00 ` Robert Dewar 1996-07-03 0:00 ` Adam Beneschan 1 sibling, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-03 0:00 UTC (permalink / raw) Bob Duff said "Now, GNAT has gone and provided the same capability, using an implementation-defined attribute (Unrestricted_Access), but unfortunately, this attribute allows dangling pointers to subprograms, unlike either of the above options." But unfortunately, virtually all the useful uses of Unrestricted_Access, at least in my experience are cases where your limited mechanisms would have been insufficient, since we definitely need to be able to assign these values. So we would probably have put the attribute in even if the language had the safe cases. Note that the two safe cases that Bob mentions are in fact cases where the work arounds required in the current language are pretty straightforward, so the limited form of the feature proposed in Bob's note is not very convincing since it provides rather limited capabilities and no significant increase in expressive power. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Robert A Duff 1996-07-03 0:00 ` Robert Dewar @ 1996-07-03 0:00 ` Adam Beneschan 1996-07-03 0:00 ` Robert Dewar ` (2 more replies) 1 sibling, 3 replies; 133+ messages in thread From: Adam Beneschan @ 1996-07-03 0:00 UTC (permalink / raw) It should be noted that the new object-oriented features of Ada 95 should make subprogram accesses less necessary than before. Abstract types inherently possess subprogram pointers, so it should be possible to take advantage of this feature as an alternative to explicit subprogram accesses. In Ada 83, I missed being able to do things like this: with Pack1; procedure P1 is Error_File : Text_IO.File_Type; procedure Report_Error (Message : string) is begin Text_IO.Put_Line (Error_File, Message); end Report_Error; begin Text_IO.Create (Error_File, ... ... Pack1.Do_Some_Big_Procedure_That_Can_Report_Errors (Report_Error); -- some people would fire me for using a name like this :) ... end P1; The purpose is to call a procedure that can generate error messages, and to tell it what I want done with those error messages. Things can't be done this way in Ada 83. The problem can be solved using generics in Ada 83, but I've always thought of this as a strange reason for using generics, and it can get hairy (suppose, for example, that the big procedure calls another procedure that also reports errors; now that procedure has to be turned into a generic also, and so on). In Ada 95, you can accomplish this with a subprogram access, but you have to make Report_Error global, and therefore Error_File has to be made global also. So doing things this way forces you to give up some of the design advantages of using local variables. (It isn't too big a problem in the above example, but in more complicated situations, making things global can be a real pain.) This is also one of the things I missed when I was programming in C, since C doesn't have nested procedures. Another way to do this is with an abstract type. (PLEASE NOTE: I don't guarantee that my Ada 95 syntax is correct!) You can declare an "error handler" in some global package like this: type Error_Handler is abstract tagged null record; procedure Handle_Error (Handler : in Error_Handler; Message : in string) is abstract; The Do_Some_Big_Procedure_That_Can_Report_Errors can then take an Error_Handler (or Error_Handler'Class?) as a parameter. It calls the Handle_Error routine when it wants to generate an error message. It can pass the Error_Handler object around to other procedures that also report errors. P1 sets things up to use its own error reporting routine as the error handler: procedure P1 is type My_Error_Handler is new Error_Handler with record Error_File : Text_IO.File_Type; end record; EH : My_Error_Handler; -- variable name chosen to avoid being fired :) procedure Handle_Error (Handler : in My_Error_Handler; Message : in string) is begin Text_IO.Put_Line (Handler.Error_File, Message); end Handle_Error; begin Text_IO.Create (EH.Error_File, ... ... Pack1.Do_Some_Big_Procedure_That_Can_Report_Errors (EH); This mechanism doesn't let you *directly* store an access to a subprogram in a global variable, the way subprogram accesses do; but using accesses to Error_Handler objects should let you accomplish the same thing. Once again, my apologies if my Ada 95 syntax is incorrect. I haven't yet learned all the nuances of Ada 95 programming. Mainly, I wanted to discuss the concepts involved; someone else may need to fill in the programming details. -- Adam ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Adam Beneschan @ 1996-07-03 0:00 ` Robert Dewar 1996-07-03 0:00 ` Robert A Duff 1996-07-09 0:00 ` Thomas Wolff 2 siblings, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-03 0:00 UTC (permalink / raw) Adam said "It should be noted that the new object-oriented features of Ada 95 should make subprogram accesses less necessary than before. Abstract types inherently possess subprogram pointers, so it should be possible to take advantage of this feature as an alternative to explicit subprogram accesses." One nice demonstration of this is to look at the approach taken by Intermetrics in their Ada 95 compiler that generates JBC. Java does not have subprogram pointers, but their Ada 95 compiler can exactly model Ada 95 subprogram pointers by making them correspond to a class with a method that calls through the "pointer". ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Adam Beneschan 1996-07-03 0:00 ` Robert Dewar @ 1996-07-03 0:00 ` Robert A Duff 1996-07-09 0:00 ` Thomas Wolff 2 siblings, 0 replies; 133+ messages in thread From: Robert A Duff @ 1996-07-03 0:00 UTC (permalink / raw) In article <4re8bj$qfk@krusty.irvine.com>, Adam Beneschan <adam@irvine.com> wrote: >It should be noted that the new object-oriented features of Ada 95 >should make subprogram accesses less necessary than before. Abstract >types inherently possess subprogram pointers, so it should be possible >to take advantage of this feature as an alternative to explicit >subprogram accesses. Quite right. The only problem is that it's a bit verbose. > procedure P1 is > > type My_Error_Handler is new Error_Handler with record > Error_File : Text_IO.File_Type; > end record; You need to put: procedure Handle_Error (Handler : in My_Error_Handler; Message : in string); here, to avoid freezing rules rearing their ugly head. > EH : My_Error_Handler; > -- variable name chosen to avoid being fired :) > > procedure Handle_Error (Handler : in My_Error_Handler; > Message : in string) is > begin > Text_IO.Put_Line (Handler.Error_File, Message); > end Handle_Error; > > begin > Text_IO.Create (EH.Error_File, ... > ... > Pack1.Do_Some_Big_Procedure_That_Can_Report_Errors (EH); > >This mechanism doesn't let you *directly* store an access to a >subprogram in a global variable, the way subprogram accesses do; but >using accesses to Error_Handler objects should let you accomplish the >same thing. Right. Quite often, if you think you want a pointer to a procedure, a class-wide object is better. >Once again, my apologies if my Ada 95 syntax is incorrect. I haven't >yet learned all the nuances of Ada 95 programming. Mainly, I wanted >to discuss the concepts involved; someone else may need to fill in the >programming details. You've got the concepts quite right. No need to apologize for violating a freezing rule. ;-) My only objection to this technique is that it's a lot of verbiage for a pretty trivial thing. - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-03 0:00 ` Adam Beneschan 1996-07-03 0:00 ` Robert Dewar 1996-07-03 0:00 ` Robert A Duff @ 1996-07-09 0:00 ` Thomas Wolff 2 siblings, 0 replies; 133+ messages in thread From: Thomas Wolff @ 1996-07-09 0:00 UTC (permalink / raw) Adam Beneschan: >>>Q: access to subprogram : It should be noted that the new object-oriented features of Ada 95 : should make subprogram accesses less necessary than before. Abstract I don't agree with this view, see below. : types inherently possess subprogram pointers, so it should be possible : to take advantage of this feature as an alternative to explicit : subprogram accesses. : : In Ada 83, I missed being able to do things like this: : : with Pack1; : procedure P1 is : Error_File : Text_IO.File_Type; : : procedure Report_Error (Message : string) is : begin : Text_IO.Put_Line (Error_File, Message); : end Report_Error; : : begin : Text_IO.Create (Error_File, ... : ... : Pack1.Do_Some_Big_Procedure_That_Can_Report_Errors (Report_Error); : -- some people would fire me for using a name like this :) : ... : end P1; : : The purpose is to call a procedure that can generate error messages, : and to tell it what I want done with those error messages. Things : can't be done this way in Ada 83. The problem can be solved using : generics in Ada 83, but I've always thought of this as a strange : reason for using generics, and it can get hairy (suppose, for example, : that the big procedure calls another procedure that also reports : errors; now that procedure has to be turned into a generic also, and : so on). Yes, and the same way you think it's a strange way of employing generics, I'd also say it's a strange thing to employ objects (of abstract types) for this simple (!) purpose alone as you propose below. : In Ada 95, you can accomplish this with a subprogram access, but you : have to make Report_Error global, and therefore Error_File has to be : made global also. So doing things this way forces you to give up some : of the design advantages of using local variables. (It isn't too big : a problem in the above example, but in more complicated situations, : making things global can be a real pain.) This is also one of the : things I missed when I was programming in C, since C doesn't have : nested procedures. : : Another way to do this is with an abstract type. (PLEASE NOTE: I : don't guarantee that my Ada 95 syntax is correct!) You can declare an : "error handler" in some global package like this: Compare my other response in this thread for remarks about the implementation of the discussed language feature. Thomas Wolff ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 ` Robert A Duff ` (2 preceding siblings ...) 1996-07-03 0:00 ` Fergus Henderson @ 1996-07-05 0:00 ` Jon S Anthony 1996-07-06 0:00 ` Robert Dewar 1996-07-06 0:00 ` Robert A Duff 1996-07-07 0:00 ` Mark Eichin ` (12 subsequent siblings) 16 siblings, 2 replies; 133+ messages in thread From: Jon S Anthony @ 1996-07-05 0:00 UTC (permalink / raw) In article <4re2ng$t7u@wdl1.wdl.loral.com> mab@dst17.wdl.loral.com (Mark A Biggar) writes: > If I remember right, it was felt that implementing "closures" (which is the > solution to this problem) placed an unacceptable distributed overhead > on programs that didn't use the feature. Also I think that half the then > current Ada implementations were using "static links" and the other half > were using "displays" and implementing "clousers" would have been real > difficult for one of those groups (the "display" bunch I think). I can maybe buy the second bit (about difficulty for display based impls) but the first makes no sense. You wouldn't have to pass displays or whatever in those cases where the feature wasn't being used. Which means that there is _no_ distributed overhead for the 99+% of regular ol' subprogram calls. /Jon -- Jon Anthony Organon Motives, Inc. 1 Williston Road, Suite 4 Belmont, MA 02178 617.484.3383 jsa@organon.com ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-05 0:00 ` Jon S Anthony @ 1996-07-06 0:00 ` Robert Dewar 1996-07-06 0:00 ` Robert A Duff 1 sibling, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-06 0:00 UTC (permalink / raw) Jon said "I can maybe buy the second bit (about difficulty for display based impls) but the first makes no sense. You wouldn't have to pass displays or whatever in those cases where the feature wasn't being used. Which means that there is _no_ distributed overhead for the 99+% of regular ol' subprogram calls." If you buy the second bit, and if you agree that displays are more efficient than static links for Ada programs (which is not gospel, it requires discussion and examination -- I certainly think it is the case), then the first bit is a consequence, since the provision of closures would push you away from using displays, and hence introduce distributed overhead -- that was what was being talked about. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-05 0:00 ` Jon S Anthony 1996-07-06 0:00 ` Robert Dewar @ 1996-07-06 0:00 ` Robert A Duff 1996-07-06 0:00 ` Robert Dewar 1996-07-08 0:00 ` Richard A. O'Keefe 1 sibling, 2 replies; 133+ messages in thread From: Robert A Duff @ 1996-07-06 0:00 UTC (permalink / raw) In article <JSA.96Jul5141249@organon.com>, Jon S Anthony <jsa@organon.com> wrote: >I can maybe buy the second bit (about difficulty for display based >impls) but the first makes no sense. You wouldn't have to pass >displays or whatever in those cases where the feature wasn't being >used. Which means that there is _no_ distributed overhead for the >99+% of regular ol' subprogram calls. I posted a note in this thread saying the same thing. But, having read Robert Dewar's posts, I have to admit that the "distributed overhead" argument is not totally off the wall. The argument is: 1. Displays are too much trouble, in the presence of downward closures. (Or, are they upward closures? You know what I mean -- passing procedures as parameters.) 2. Therefore, if we have that feature, compiler writers are forced to use static links (or are at least sorely tempted to use static links -- it makes things simpler, and as Robert pointed out, the simplicity-vs-complexity we're talking about is towards the back end of the compiler, which is the hardest part to debug, and may be duplicated for numerous kinds of hardware). 3. Displays are clearly faster than static links, for normal direct calls. 4. Therefore, we've got a distributed overhead; QED. This argument makes *some* sense, but I dispute point 3. I'm not really sure, but I think that perhaps static links are faster. I'm quite *sure* of two things: it doesn't make much difference, since most code isn't very deeply nested anyway, and if there *is* a difference, it's not a big difference. Of course, one might wish for some scientific experiment that could tell us once and for all which is better. Unfortunately, I don't think it's that easy. For one thing, you have to write the same compiler both ways, which is expensive. For another, the issue is affected by other optimizations -- for example, a static link implementation will be much better if the compiler is smart enough to do CSE elimination on loads of the static link, or chains therefrom. But a display implementation won't care so much about that particular optimization. For another thing, it depends on the sort of programs you write. Most Ada code I've seen has very few procedures-within-procedures, which is where the difference counts. And five-level nested procedures are very uncommon, I suspect. But some people like to nest more than others. ;-) - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-06 0:00 ` Robert A Duff @ 1996-07-06 0:00 ` Robert Dewar 1996-07-08 0:00 ` Robert A Duff 1996-07-08 0:00 ` Richard A. O'Keefe 1 sibling, 1 reply; 133+ messages in thread From: Robert Dewar @ 1996-07-06 0:00 UTC (permalink / raw) Bob Duff said "sure, but I think that perhaps static links are faster. I'm quite *sure* of two things: it doesn't make much difference, since most code isn't very deeply nested anyway, and if there *is* a difference, it's not a big difference." If there is no nesting, then neither static links nor displays have any overhead at all. If there is nesting, then static links pay a price for calling any routine other than an outer level library routine. If there is nesting, then displays pay a price for calling any routine that contains a nested routine, but there is no price for calling any routine (at library level or nested) if it contains no nested routines. It seems to be evident that the great majority of calls are to routines that do NOT contain nested routines. Consider in particular the case of a big procedure q that contains many tested procedures q1 .. q100. Now for static links, calls to any of q1 .. q100 incur an overhead, but the call to q does not (assuming q is global level). For displays, calls to any of q1 .. q100 (assuming there is no further level of nesting) incur no overhead, only the call to q incurs an overhead. It seems clear to me from these considerations that displays will be faster than static links for most typical programs. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-06 0:00 ` Robert Dewar @ 1996-07-08 0:00 ` Robert A Duff 0 siblings, 0 replies; 133+ messages in thread From: Robert A Duff @ 1996-07-08 0:00 UTC (permalink / raw) In article <dewar.836709438@schonberg>, Robert Dewar <dewar@cs.nyu.edu> wrote: >If there is no nesting, then neither static links nor displays have >any overhead at all. > >If there is nesting,... [lots of good stuff] >It seems clear to me from these considerations that displays will be >faster than static links for most typical programs. But, IMHO, there usually is no nesting. Therefore, the same facts lead me to think, "If there's a difference, it's negligible." Therefore, compilers ought to do what's simplest (IMHO, static links are simpler to implement). Also, you analyzed calls, but you didn't analyze the speed of up-level references. For a display, it's some-offset added to some-display- pointer. For static links, it's some-offset added to chaining-up-the-links. Sure sounds like displays are better. Especially if the display is in registers. But it depends a lot on what optimizations are done. E.g., can the compiler recognize cases where the nested procedure does no up-level refs? Can the compiler recognize cases where the outer procedure's stack frame can be merged with the environment task's stack frame (i.e. static allocation)? Can the compiler notice multiple loads of the same up-level reference? Can the display in fact be stored entirely in registers? These all make a difference, but IMHO they are second-order effects, given that most code isn't nested at all. I haven't seen any studies showing code is not nested. It's just my limited experience. Why would that be? I don't think nesting is necessarily evil. But, in Ada, you need to be at library level to do true separate compilation, so there's a strong incentive to avoid nesting. Subunits allow separate compilation of bodies (in some compilers), but to get separate compilation of specs, you have to use library units. - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-06 0:00 ` Robert A Duff 1996-07-06 0:00 ` Robert Dewar @ 1996-07-08 0:00 ` Richard A. O'Keefe 1996-07-08 0:00 ` Robert Dewar 1996-07-08 0:00 ` Robert A Duff 1 sibling, 2 replies; 133+ messages in thread From: Richard A. O'Keefe @ 1996-07-08 0:00 UTC (permalink / raw) bobduff@world.std.com (Robert A Duff) writes: >1. Displays are too much trouble, in the presence of downward closures. >(Or, are they upward closures? You know what I mean -- passing >procedures as parameters.) This puzzles me mightily. Burroughs Algol for the B6700 used a single global display (actually a dedicated bank of 32 registers; reduced to 16 on later models). In fact, all languages on that machine did, including Fortran, PL/I, and Pascal. Now Algol, Fortran, PL/I, and Pascal all allow procedures to be passed as parameters, and in Algol, PL/I, and Pascal those procedures can be nested. The B6700 hardware took care of this. Techniques for marrying procedure parameters and displays were readily available in the compiler construction literature by the late '70s. A compiler construction class I was a student in explained how to do it (and we had to; we were writing a Pascal->Algol compiler which used a display). What happened? When did everyone forget? 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. >3. Displays are clearly faster than static links, for normal direct calls. >This argument makes *some* sense, but I dispute point 3. I'm not really >sure, but I think that perhaps static links are faster. Displays are a win if you can afford to dedicate some global registers to them. This was beaten to death by the late 70's surely? -- Fifty years of programming language research, and we end up with C++ ??? Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-08 0:00 ` Richard A. O'Keefe @ 1996-07-08 0:00 ` Robert Dewar 1996-07-10 0:00 ` Richard A. O'Keefe 1996-07-08 0:00 ` Robert A Duff 1 sibling, 1 reply; 133+ messages in thread From: Robert Dewar @ 1996-07-08 0:00 UTC (permalink / raw) Richard O'Keefe said "This puzzles me mightily. Burroughs Algol for the B6700 used a single global display (actually a dedicated bank of 32 registers; reduced to 16 on later models). In fact, all languages on that machine did, including Fortran, PL/I, and Pascal. Now Algol, Fortran, PL/I, and Pascal all allow procedures to be passed as parameters, and in Algol, PL/I, and Pascal those procedures can be nested." If it puzzles you, you should probably go back and reread a good book explaining all this. I strongly recommend the (admittedly somewhat obsolete) book by Gries, the treatment of displays is very clear here. The whole point of using a single global display is that you only need to change (at most) one element at a time). The general use of procedure parameters in Pascal or Algol, if done right, clearly violates this, and requires entire sections of displays to be saved and restored. Maybe the 6700 hardware took care of it, but there is no magic, if it was done right, then it requires saving and restoring chunks of displays (or worse still replicating them in stack frames). This is indeed less efficient than static displays. 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 adopted a consequence that allowed most useful uses of procedures as parameters, but did not result in making displays inefficient. By the way, over the years, many Pascal and Algol compilers have cheated. 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. No one has forgotten anything here: this stuff is pretty well understood. The one thing that Gries misses, which is critical for the efficiency of handling displays, is that you do NOT need to modify the display if the procedure you are calling has no nested procedures. This is a common case, and is missed by most (all?) text books and is absolutely critical for efficiency comparisons. 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. The modification is that the invariant adds "that contains nested procedures" after the word procedure in this invariant. (I am also assuming that the frame pointer is separate from the display, as is typical practice). ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-08 0:00 ` Robert Dewar @ 1996-07-10 0:00 ` Richard A. O'Keefe 1996-07-10 0:00 ` Robert Dewar 0 siblings, 1 reply; 133+ messages in thread From: Richard A. O'Keefe @ 1996-07-10 0:00 UTC (permalink / raw) I wrote, apropos of the claim that using displays made it hard to implement procedures as (non-generic) parameters: "This puzzles me mightily. Burroughs Algol for the B6700 used a single global display (actually a dedicated bank of 32 registers; reduced to 16 on later models). In fact, all languages on that machine did, including Fortran, PL/I, and Pascal. Now Algol, Fortran, PL/I, and Pascal all allow procedures to be passed as parameters, and in Algol, PL/I, and Pascal those procedures can be nested." dewar@cs.nyu.edu (Robert Dewar) writes: >If it puzzles you, you should probably go back and reread a good book >explaining all this. I strongly recommend the (admittedly somewhat >obsolete) book by Gries, the treatment of displays is very clear here. I am getting just a little bit tired of insults. I *have* Gries. I've read it. I've even worked on a Pascal compiler (that admittedly was never deployed) that used a display. In fact, getting procedures as (non-generic) parameters right was the show-stopper that prevented the compiler being deployed (by the time we fixed the design, a better *finished* compiler was available). >The whole point of using a single global display is that you only need >to change (at most) one element at a time). The general use of procedure >parameters in Pascal or Algol, if done right, clearly violates this, and >requires entire sections of displays to be saved and restored. Exactly so. *BUT* it can be implemented without any *distributed* cost. The parent of a procedure that will be passed as a parameter keeps a copy of the relevant section of the display; such a child is passed as a pair (pointer to copy of display, pointer to wrapper procedure), and the wrapper procedure saves the current section, resets the display, calls the real child, restores the display, and returns the child's result. If the child is not called directly (the usual case) it can be integrated in the "wrapper". And another minor optimisation turns the "parent is at lex level 1" common case into exactly the same thing as passing a static link. >Maybe the 6700 hardware took care of it, but there is no magic, if it >was done right, then it requires saving and restoring chunks of displays >(or worse still replicating them in stack frames). This is indeed less >efficient than static displays. It can be implemented with distributed overhead (as the B6700 did, if I recall correctly) with a static link as well as a dynamic link and a return address in every (non-leaf) frame. But it can *also* be implemented with "lumped" overhead so that the overhead for programs or procedures NOT using this facility is ZERO. The overhead for a procedure at lexical level N is roughly 6N memory references per indirect call. This is less efficient than the single static link approach, but (a) it can be retrofitted into a single global display system, in such a way that existing library units that do not use the facility generate EXACTLY the same code as before, and (b) doing it this way is INFINITELY more efficient than not doing it at all! In any case, this display resetting is precisely a context switch, and guess what: Ada has tasking, necessitating either a display per task or a display reset per context switch _anyway_. In fact, one of the claimed advantages for the way the B6700 did it was that it unified the treatment of tasks and procedures in an approach that was very simple to use and to generate code for. >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. I am sorely puzzled that I have to say this: procedures as formal parameters *can* be implemented without *distributed* overhead in a static display architecture; the result is less efficient than alternative architectures might have been, but it is MORE efficient than not doing it. >No one has forgotten anything here: this stuff is pretty well understood. Not as well as it might be, apparently. >The one thing that Gries misses, which is critical for the efficiency of >handling displays, is that you do NOT need to modify the display if the >procedure you are calling has no nested procedures. This is a common case, >and is missed by most (all?) text books and is absolutely critical for >efficiency comparisons. I felt so strongly about this issue that I started writing an article on variants of the BCPL and Algol models. I actually wrote some notes about this particular optimisation yesterday, and read your article at 5:40+ today. It's >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. >The modification is that the invariant adds "that contains nested >procedures" after the word procedure in this invariant. >(I am also assuming that the frame pointer is separate from the display, >as is typical practice). What you are describing is what I've called "the hybrid BCPL/display model" in which the value that would have been in D[n] is actually in the L register. To summarise: if an Ada 83 compiler used a simplified single static display model in which every procedure entry/exit changes/restores a single display element, and in which activation records are not threaded with static links, then procedures (and functions) as (non-generic) formal parameters in the style of Fortran, Algol 60, Pascal, PL/I, Simula 67, ... COULD have been implemented with *no* distributed cost; calling the parent of a passed-procedure would have overhead; calling a formal procedure parameter would have overhead; but these overheads would only be incurred in programs using the new feature. This means that the implementation argument against the feature is bogus. -- Fifty years of programming language research, and we end up with C++ ??? Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-10 0:00 ` Richard A. O'Keefe @ 1996-07-10 0:00 ` Robert Dewar 1996-07-19 0:00 ` Richard A. O'Keefe 0 siblings, 1 reply; 133+ messages in thread From: Robert Dewar @ 1996-07-10 0:00 UTC (permalink / raw) "I am getting tired of insults" Sorry, did not mean to insult you, but you seemed not to understand what was being said, and now I understand why from your article. The concern about distributed overhead is not that the new feature per se generates distributed overhead. Yes of course it is trivially true that if you are using displays, you only pay the penalty when you actually use procedure pointers and procedure arguments. As you point out, many real compilers have been written this way. But then, rather than distributed overhead, if you take the approach of using displays, you have two problems - you have greatly increased overhead when the feature is used. Enough increased overhead that almost certainly the proper design approach is to use static links instead. - if you use displays anyway, then the implementation is greatly - complicated. The maximum depth of the display is not known till - link time, so either you take a huge hit in efficiency by using some absurd maximum value (I have seen nesting depths well over ten coming from the use of subunits), or you have to mess at the linker level to determine the maximum, and then all data structures that depend on this maximum become dynamcically sized objects which must be dynamically allocated. It is this second concern about implementation difficulty that lead to the WG9 decision to restrict the feature so that such dynamic concerns would not be necessary, and also to ensure that the display model could be used without introducing undue overhead mentioned as the first concern above. The distributed overhead argument did *not* enter into the discussion. The distributed overhead concern (as expressed in Steelman) comes from a concern that in general static links are less efficient than displays. So if the language is designed so that static links are the right choice, then you have a distributed overhead. Of course this is an arguable point, as you can see from the discussoin, not everyone accepts that static links are less efficient than displays. But anyway, your "mighty puzzlement" arises from a confusion on your part as to the argument that was being made. No one at any point claimed that implementing procedure pointers in the context of a display implementation causes distributed overhead. As you point out, it does not, and everyone agrees with this, and no one has claimed anything to the contrary, and as I point out above, the distributed overhead argument did not enter into the WG9 discussions substantially, except in the following sense. There were people who said things like "well displays are a silly thing to use in any case, so why on earth are we worrying about compilers that make such a silly choice." And the discussion of the viabiliyt of displays in general did come up in that context. Basically the issue boiled down quite simply to a pragmatic issue. If the procedure pointers were made general, would this be too much of an implementation burden for existing implementations usinvg displays? And how does this balance against the increased utility? Answering such questions is always difficult because it fundamentally involves comparing apples and oranges. There is no doubt that it would have resulted in a substantial implementation burden, and here is no doubt that it would have been a useful feature. WG9 decided the former had precedence. Who knows, Richard, maybe you would have agreed to if you had listened to the detalied arguments (this was very extenisvely discussed) -- there were people there who felt as you do now when we started the discussion, but changed their minds. As to whether the decision is right in retrospect? hard to say. So far I have not seen any really convincing examples. Perhaps some will appear. Bob, it would be nice to post the original "safe" design here. Who knows perhaps one day some extensions might be made to GNAT (certainly we are seriously considering, and discussing with Tuck, implementing some variant of his "with type" proposal to deal with the recursive type situation). Note that any such extensions would of course be under a switch to keep them under control :-) ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-10 0:00 ` Robert Dewar @ 1996-07-19 0:00 ` Richard A. O'Keefe 0 siblings, 0 replies; 133+ messages in thread From: Richard A. O'Keefe @ 1996-07-19 0:00 UTC (permalink / raw) dewar@cs.nyu.edu (Robert Dewar) writes: > - if you use displays anyway, then the implementation is greatly > - complicated. The maximum depth of the display is not known till > - link time, so either you take a huge hit in efficiency by using > some absurd maximum value (I have seen nesting depths well over > ten coming from the use of subunits), or you have to mess at > the linker level to determine the maximum, and then all data > structures that depend on this maximum become dynamcically sized > objects which must be dynamically allocated. >It is this second concern about implementation difficulty that lead >to the WG9 decision to restrict the feature so that such dynamic >concerns would not be necessary, and also to ensure that the display >model could be used without introducing undue overhead mentioned as >the first concern above. But (a) the maximum depth of the display is not *relevant* to the code generated for any procedure, with or without procedure parameters. The only depth that is relevant to any one procedure is the depth of that procedure itself and (b) you don't know the maximum depth of the display until link time *anyway*. So I still don't see what the problem is. As for 10, that seems small to me. (The B6700 had 32 display registers, and there were actually Burroughs customers who were rather upset when later models cut that back to 16.) In any reasonable implementation of procedure parameters based on displays (such as is necessary for Algol 60, Pascal, and PL/I) there is NO data structure that cares the slightest tiniest little bit what the maximum display size is, with the unique exception of the display itself. >The distributed overhead argument did *not* enter into the discussion. It did enter into _this_ discussion (thread). >Basically the issue boiled down quite simply to a pragmatic issue. If >the procedure pointers were made general, would this be too much of >an implementation burden for existing implementations usinvg displays? >And how does this balance against the increased utility? We are agreed that there _is_ a burden, but we seem to disagree quite a bit about what exactly that burden is. Space-wise, it can be - N links in the parent of a passed-procedure - N links in the passed-procedure itself - 3N link assignments in a call This is to provide the same level of support for procedure parameters as Pascal; *not* the more general Algol 68 model which I have not been talking about. >Who knows, Richard, maybe you would have agreed to if >you had listened to the detalied arguments (this was very extenisvely >discussed) -- there were people there who felt as you do now when >we started the discussion, but changed their minds. I have found the Ada 9x design documents that I _have_ read (which comes to a stack about 4 feet high) to be *extremely* interesting and valuable for the field of language design. If these detailed arguments have been written up, I would be most interested to read them. Basically, what I've read _here_ boils down to "People who designed Ada implementations on the assumption that procedure calls are not exceptionally important feared that providing a Pascal-like procedure-related feature would be too expensive.", and it seems as if either a much richer feature than I wanted (procedure _pointers_; I just wanted procedure _parameters_) or a much dumber implementation than I have in mind was envisaged. >As to whether the decision is right in retrospect? hard to say. So far >I have not seen any really convincing examples. Self-fulfilling prophecy. It's a better use of my time to figure out how I _can_ accomplish something in Ada 95 (my favourite imperative language) than to construct examples showing what I'd like to do and can't. If I _were_ going to spend time on that, I'd explain why I would like to be able to pass a generic procedure as a generic parameter (not an *instance* of a generic procedure, the generic itself). -- Fifty years of programming language research, and we end up with C++ ??? Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-08 0:00 ` Richard A. O'Keefe 1996-07-08 0:00 ` Robert Dewar @ 1996-07-08 0:00 ` Robert A Duff 1996-07-08 0:00 ` Robert Dewar 1 sibling, 1 reply; 133+ messages in thread From: Robert A Duff @ 1996-07-08 0:00 UTC (permalink / raw) In article <4rqbo9$b02@goanna.cs.rmit.edu.au>, Richard A. O'Keefe <ok@goanna.cs.rmit.edu.au> wrote: >bobduff@world.std.com (Robert A Duff) writes: > >>1. Displays are too much trouble, in the presence of downward closures. >>(Or, are they upward closures? You know what I mean -- passing >>procedures as parameters.) > >This puzzles me mightily. Burroughs Algol for the B6700 used a single >global display (actually a dedicated bank of 32 registers; reduced to >16 on later models). In fact, all languages on that machine did, >including Fortran, PL/I, and Pascal. Now Algol, Fortran, PL/I, and >Pascal all allow procedures to be passed as parameters, and in Algol, >PL/I, and Pascal those procedures can be nested. I didn't mean it's impossible. I just meant that if I were implementing a compiler for a language with downward closures on a typical modern machine, I would choose static links, in part because it seems simpler. On the other hand, I know of compilers that have implemented Pascal using displays. 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. >Displays are a win if you can afford to dedicate some global registers to >them. This was beaten to death by the late 70's surely? Sure, but inconclusively. Just like LR vs. LL parsing has been beaten to death -- it doesn't mean that everybody agrees which one is the right one to use in all situations. As for displays being a big win, suppose I can afford to dedicate those registers on one of my targets, but not on the other? Do I write a back end (or pair of back ends) that can do it both ways? It's an economic decision, at least in part. Suppose I have a very rich customer who desperately needs efficient code, and loves to write 7-level-deep nested procedures. That might make a difference, no? Also, note that it depends on the language. In my experience, Ada programs are less deeply nested than Pascal programs. If you don't use much nesting, then it's clearly not a "big win" either way. - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-08 0:00 ` Robert A Duff @ 1996-07-08 0:00 ` Robert Dewar 0 siblings, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-08 0:00 UTC (permalink / raw) Bob said "Also, note that it depends on the language. In my experience, Ada programs are less deeply nested than Pascal programs. If you don't use much nesting, then it's clearly not a "big win" either way." I disagree, the presence of subunits makes it practical to nest very deeply (the nesting would have to be lexically explicit in Pascal), and it is common practice to nest deeply this way (common does not mean everyone or even a majority does it, just that there are quite a few programs around written that way). Of course an interesting point is that the difference is more extreme for light nesting. Suppose your organization has a main program with lots of procedures nested inside, but no further nesting. The overhead for displays is zero in such a program, but static links would be used all the time. Getting an example the other way round (one that favors static links) is difficult indeed. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 ` Robert A Duff ` (3 preceding siblings ...) 1996-07-05 0:00 ` Jon S Anthony @ 1996-07-07 0:00 ` Mark Eichin 1996-07-08 0:00 ` Richard Kenner 1996-07-07 0:00 ` Ronald Cole ` (11 subsequent siblings) 16 siblings, 1 reply; 133+ messages in thread From: Mark Eichin @ 1996-07-07 0:00 UTC (permalink / raw) > remember them all. that was around the time when Stallman said that > writing what we now know as the bfd libraries would be "hard"). Thus giving it the name :-) If I remember correctly, the other big reason is that reading externally generated rtl or tree structures would make non-Free frontends possible, and that would be a Bad Thing. This way anything that takes advantage of the backend needs to also be Free. _Mark_ <eichin@cygnus.com> Cygnus Support, Eastern USA ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-07 0:00 ` Mark Eichin @ 1996-07-08 0:00 ` Richard Kenner 0 siblings, 0 replies; 133+ messages in thread From: Richard Kenner @ 1996-07-08 0:00 UTC (permalink / raw) In article <xe1enmnmvjn.fsf@maneki-neko.cygnus.com> Mark Eichin <eichin@cygnus.com> writes: >If I remember correctly, the other big reason is that reading >externally generated rtl or tree structures would make non-Free >frontends possible, and that would be a Bad Thing. This way anything >that takes advantage of the backend needs to also be Free. The other big reason for what? What you state is true, but I don't see it having any relevance. The RTL generated is always customized for a machine, so writing RTL would not allow one to split off a backend into a separate program. Tree structures are mostly machine-independent (but not fully, since size information is encoded into them), but GCC does not operate by forming a tree for a function and then compiling it (the interface from the front end to the rest of the compiler is more procedural), so "writing the tree" out is not meaningful since it never exists. Some front-ends to GCC (most notably those for Fortran and Ada) operate by generating a separate tree structure (usually in a different format) for a function or file and then walking that tree by making calls to GCC. In such a case it indeed is somewhat possible to write out such a tree and separate the front end from GCC. I can't speak for Fortran, but can say this is now impractical for Ada. As part of the bootstrap process, this used to be done, but there are now numerous calls from the tree walk routines back into the Ada front end. Also, the tree is not machine-independent because sizes of predefined types are machine-specific. (Aside from the reason given by Mark, it would also be inefficient to do this split due to the amount of I/O required, so this is not only not easy but undesirable.) ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 ` Robert A Duff ` (4 preceding siblings ...) 1996-07-07 0:00 ` Mark Eichin @ 1996-07-07 0:00 ` Ronald Cole 1996-07-07 0:00 ` Richard Kenner 1996-07-07 0:00 ` Robert Dewar 1996-07-08 0:00 ` Brian Rogoff ` (10 subsequent siblings) 16 siblings, 2 replies; 133+ messages in thread From: Ronald Cole @ 1996-07-07 0:00 UTC (permalink / raw) dewar@cs.nyu.edu (Robert Dewar) writes: > not all compilers are like this, GCC has only one back end, but many > compilers do have myultiple backends). Not true. A single instance of GCC doesn't support multiple machine targets (other than the -m options for some processor families). GCC has to be recompiled to support different machine descriptions (that's what the -b and -V options of gcc are for). I consider this as having multiple backends. Many years ago, when asked about why he didn't make GCC read loadable md files, Stallman answered that it would hurt performance (both for the compiler and for the generated code) (there were probably a few other reasons, but it was too long ago for me to remember them all. that was around the time when Stallman said that writing what we now know as the bfd libraries would be "hard"). -- Ronald Cole E-mail: ronald@ridgecrest.ca.us President, CEO zippy@ecst.csuchico.edu Forte International Fax: (619) 384-2346 My PGP fingerprint: E9 A8 E3 68 61 88 EF 43 56 2B CE 3E E9 8F 3F 2B ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-07 0:00 ` Ronald Cole @ 1996-07-07 0:00 ` Richard Kenner 1996-07-07 0:00 ` Robert Dewar 1 sibling, 0 replies; 133+ messages in thread From: Richard Kenner @ 1996-07-07 0:00 UTC (permalink / raw) In article <m291cv99nr.fsf@devo.ridgecrest.ca.us> Ronald Cole <ronald@ridgecrest.ca.us> writes: >Not true. A single instance of GCC doesn't support multiple machine >targets (other than the -m options for some processor families). GCC >has to be recompiled to support different machine descriptions (that's >what the -b and -V options of gcc are for). I consider this as having >multiple backends. I don't think that's what Robert meant. The distinction he was trying to make is that GCC has only one piece that actually generates code (what is normally called the "back end") and that the config files modify what it does. In most compiler technologies, the config files say how to generate code, while in GCC (with some small number of exceptions) they describe the machine. >Many years ago, when asked about why he didn't >make GCC read loadable md files, Stallman answered that it would hurt >performance (both for the compiler and for the generated code) Yes, having loadable MD files would seriously hurt compiler performance, but is at least something that could be contemplated. By contrast, trying to load the tm.h file at runtime seems hopeless. >that was around the time when Stallman said that >writing what we now know as the bfd libraries would be "hard"). Yes, that's the original of the unoffical acronym of "BDF". However, note that this library is indeed far from trivial. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-07 0:00 ` Ronald Cole 1996-07-07 0:00 ` Richard Kenner @ 1996-07-07 0:00 ` Robert Dewar 1996-07-07 0:00 ` Richard Kenner 1996-07-14 0:00 ` Ronald Cole 1 sibling, 2 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-07 0:00 UTC (permalink / raw) Ronald Cole said (commenting on my claim that GCC did not have multiple backends) Not true. A single instance of GCC doesn't support multiple machine targets (other than the -m options for some processor families). GCC has to be recompiled to support different machine descriptions (that's what the -b and -V options of gcc are for). I consider this as having multiple backends. That's not what I meant, yes, of course there are multiple backends at the object level, but not at the source level. If you look back in this thread, you will see that this is the critical issue. If you have a technology where each backend is a completely different source program, separately written (such technoologies are pretty common, most Ada 83 compiler technologies were like this), then the point is that the impact of anything that affects the backend is greatly multiplied, and that is why during the design, we were very cautious about changes that affect the backend. Most Ada technologies have a single front end for all targets (though Ronald Cole would presumably call these multiple front ends too, because there are certanly separate object versions), but again the important thing is that there is only one source program. Thus changes to the front end are potentially less troublesome, since the change only has to be made once. But for technologies like GCC, where there is only one source program for both front end and backend (though in both cases multiple executables), this distinction is not significant. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-07 0:00 ` Robert Dewar @ 1996-07-07 0:00 ` Richard Kenner 1996-07-07 0:00 ` Robert Dewar 1996-07-14 0:00 ` Ronald Cole 1 sibling, 1 reply; 133+ messages in thread From: Richard Kenner @ 1996-07-07 0:00 UTC (permalink / raw) In article <dewar.836776773@schonberg> dewar@cs.nyu.edu (Robert Dewar) writes: >If you have a technology where each backend is a completely different source >program, separately written (such technoologies are pretty common, most Ada 83 >compiler technologies were like this), then the point is that the impact >of anything that affects the backend is greatly multiplied, and that is >why during the design, we were very cautious about changes that affect >the backend. > >But for technologies like GCC, where there is only one source program for >both front end and backend (though in both cases multiple executables), >this distinction is not significant. I'd say it's not *as* significant. However, in GCC we are concerned about things that affect the config files. We try to avoid making changes that affect existing config files if at all possible and then we much prefer changes (such as adding a new parameter to a macro) that can be made "mechanically" to all the config files. But adding new requirements on the config files is something we try to avoid, though the work on folding a "zero-cost" exception handling into GCC is going to require at least some additional work in each config file. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-07 0:00 ` Richard Kenner @ 1996-07-07 0:00 ` Robert Dewar 0 siblings, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-07 0:00 UTC (permalink / raw) Richard Kenner said "But adding new requirements on the config files is something we try to avoid, though the work on folding a "zero-cost" exception handling into GCC is going to require at least some additional work in each config file." Sure, but I don't think any of the Ada 95 changes are at the level that would require config file changes. Yes some config file changes may be needed for Ada (overflow checking, exception handling ...) but these are things that are in Ada 83 anyway. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-07 0:00 ` Robert Dewar 1996-07-07 0:00 ` Richard Kenner @ 1996-07-14 0:00 ` Ronald Cole 1996-07-14 0:00 ` Richard Kenner 1 sibling, 1 reply; 133+ messages in thread From: Ronald Cole @ 1996-07-14 0:00 UTC (permalink / raw) kenner@lab.ultra.nyu.edu (Richard Kenner) writes: > What you are actually counting are thirty distinct configuration files > used to tailor the single backend to a particular target machine. "Tailor"! Yes, my point exactly. The day gcc can read md files directly is the day I agree that it is a single backend. Gcc is really multiple backend with a meta-layer that gives the appearance of a single backend. > So long as you state the definitions you are using, you are free to > use any you want. But whatever words you use, there is a major > distinction between the GCC approach and that used by other > multi-target systems. IMO, the gcc approach lives somewhere between single and multiple backend. You probably remember well the wailing and gnashing of teeth from the CISC-owners when gcc went from version 1 (handled CISC well/RISC not-so-well) to version 2 (handles RISC much better/CISC not-as-well-as-version-1/holds "inbetween architectures" like the Pentium in contempt). But this thread has travelled well off topic for this group and this is my last post on the subject. -- Ronald Cole E-mail: ronald@ridgecrest.ca.us President, CEO zippy@ecst.csuchico.edu Forte International Fax: (619) 384-2346 My PGP fingerprint: E9 A8 E3 68 61 88 EF 43 56 2B CE 3E E9 8F 3F 2B ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-14 0:00 ` Ronald Cole @ 1996-07-14 0:00 ` Richard Kenner 1996-07-15 0:00 ` Fergus Henderson 0 siblings, 1 reply; 133+ messages in thread From: Richard Kenner @ 1996-07-14 0:00 UTC (permalink / raw) In article <m2g26ufuq2.fsf@devo.ridgecrest.ca.us> Ronald Cole <ronald@ridgecrest.ca.us> writes: >You probably remember well the wailing and gnashing of teeth >from the CISC-owners when gcc went from version 1 (handled CISC >well/RISC not-so-well) to version 2 (handles RISC much better/CISC >not-as-well-as-version-1/holds "inbetween architectures" like the >Pentium in contempt). I remember no such thing since it never happened! GCC version 2 added new mechanisms to support RISC processors but had *absolutely no effect whatsoever* on CISC processors. None of the config files for CISC processors had to be changed, nor was there any change in the generated code for these machines. As to the Pentium issue, this is more complex and there were two factors. First, some of the optimizations required for the best-quality code on that CPU are both very unique to it and are very large pieces of code to add to the compiler. Secondly, the group that did add these, and other, Pentium-specific optimizations to GCC did such a bad job that it was not possible to fix their code without rewriting it and nobody wanted to do that without knowing which of the optimizations were the most important (otherwise, you'd risk spending a lot of work on complex optimizations that had a small effect). By the time this was done, the P6 became available. It does not benefit from most of the Pentium-specific optimizations (which I knew a while before it came out), so the issue rapidly became moot. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-14 0:00 ` Richard Kenner @ 1996-07-15 0:00 ` Fergus Henderson 1996-07-15 0:00 ` Robert Dewar 1996-07-16 0:00 ` Richard Kenner 0 siblings, 2 replies; 133+ messages in thread From: Fergus Henderson @ 1996-07-15 0:00 UTC (permalink / raw) kenner@lab.ultra.nyu.edu (Richard Kenner) writes: >As to the Pentium issue, this is more complex and there were two >factors. First, some of the optimizations required for the >best-quality code on that CPU are both very unique to it and are very >large pieces of code to add to the compiler. Secondly, the group that >did add these, and other, Pentium-specific optimizations to GCC did >such a bad job that it was not possible to fix their code without >rewriting it and nobody wanted to do that without knowing which of the >optimizations were the most important (otherwise, you'd risk spending >a lot of work on complex optimizations that had a small effect). By >the time this was done, the P6 became available. It does not benefit >from most of the Pentium-specific optimizations (which I knew a while >before it came out), so the issue rapidly became moot. Well, there's still going to be a lot of Pentiums out there for quite some time -- I wouldn't call the issue entirely moot yet. -- Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit" PGP: finger fjh@128.250.37.3 | -- the last words of T. S. Garp. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-15 0:00 ` Fergus Henderson @ 1996-07-15 0:00 ` Robert Dewar 1996-07-17 0:00 ` Fergus Henderson ` (2 more replies) 1996-07-16 0:00 ` Richard Kenner 1 sibling, 3 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-15 0:00 UTC (permalink / raw) Fergus wrote "Well, there's still going to be a lot of Pentiums out there for quite some time -- I wouldn't call the issue entirely moot yet." moot means arguable and not yet decided -- I would say that's EXACTLY the right description here. Richard was saying that at this stage, the issue will probably stay arguable and undecided, which seems a reasonable assessment. (I suspect you meant MOOT as in "doesn't matter any more", but that is not what the word means in traditional usage, although I agree this US usage is (unfortunately) getting very common) ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-15 0:00 ` Robert Dewar @ 1996-07-17 0:00 ` Fergus Henderson 1996-07-17 0:00 ` Richard Kenner 1996-07-17 0:00 ` Adam Beneschan 1996-07-20 0:00 ` Michael Feldman 2 siblings, 1 reply; 133+ messages in thread From: Fergus Henderson @ 1996-07-17 0:00 UTC (permalink / raw) [Warning: this thread no longer has much relevance to Ada. Apologies in advance.] dewar@cs.nyu.edu (Robert Dewar) writes: >(I suspect you meant MOOT as in "doesn't matter any more", Yes, that's what I meant, moot as in "no longer important in practice, relevant only for hypothetical debate (e.g. at a moot [in law, students' discussion of hypothetical case for practice] ;-)", not moot as in "debatable". I suspect that when Richard Kenner introduced the word in the article to which I was replying, he meant it in the same "doesn't matter any more" sense, rather than in the "debatable" sense that you think he meant. Perhaps Richard could enlighten us? ;-) -- Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit" PGP: finger fjh@128.250.37.3 | -- the last words of T. S. Garp. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-17 0:00 ` Fergus Henderson @ 1996-07-17 0:00 ` Richard Kenner 0 siblings, 0 replies; 133+ messages in thread From: Richard Kenner @ 1996-07-17 0:00 UTC (permalink / raw) In article <4sjbjc$pae@mulga.cs.mu.OZ.AU> fjh@mundook.cs.mu.OZ.AU (Fergus Henderson) writes: >Yes, that's what I meant, moot as in "no longer important in practice, >relevant only for hypothetical debate (e.g. at a moot [in law, >students' discussion of hypothetical case for practice] ;-)", >not moot as in "debatable". >I suspect that when Richard Kenner introduced the word in the article >to which I was replying, he meant it in the same "doesn't matter any >more" sense, rather than in the "debatable" sense that you think he >meant. Perhaps Richard could enlighten us? ;-) Yes, that's correct. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-15 0:00 ` Robert Dewar 1996-07-17 0:00 ` Fergus Henderson @ 1996-07-17 0:00 ` Adam Beneschan 1996-07-20 0:00 ` Michael Feldman 2 siblings, 0 replies; 133+ messages in thread From: Adam Beneschan @ 1996-07-17 0:00 UTC (permalink / raw) In article <dewar.837456126@schonberg> dewar@cs.nyu.edu (Robert Dewar) writes: >Fergus wrote > >"Well, there's still going to be a lot of Pentiums out there for quite >some time -- I wouldn't call the issue entirely moot yet." > >moot means arguable and not yet decided -- I would say that's EXACTLY >the right description here. > >Richard was saying that at this stage, the issue will probably stay >arguable and undecided, which seems a reasonable assessment. > >(I suspect you meant MOOT as in "doesn't matter any more", but that is not >what the word means in traditional usage, although I agree this US usage >is (unfortunately) getting very common) _Webster's Ninth New Collegiate_ (Merriam-Webster, 1984): [3]moot adj. 1 a: open to question: DEBATABLE b: subjected to discussion: DISPUTED 2: deprived of practical significance: made abstract or purely academic So the "doesn't matter any more" meaning is a legitimate meaning. _Dictionary or Problem Words and Expressions_, by Harry Shaw (McGraw-Hill, 1975): This word when used as an adjective means (1) subject to debate, arguable, unresolved; and (2) of only slight importance or significance: "This is a _moot_ question." "Whether the player is black or white is a _moot_ consideration." That is, a "_moot_ question" is debatable; "a _moot_ point" is of no importance. . . . So according to this, both meanings of "moot" are correct, and which meaning is the correct one depends on what it applies to---i.e. whether it's a Question or a Point you're saying is moot. Whether an Issue is more like a Question or a Point is---well, a moot issue. (Heh heh heh.) -- Adam ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-15 0:00 ` Robert Dewar 1996-07-17 0:00 ` Fergus Henderson 1996-07-17 0:00 ` Adam Beneschan @ 1996-07-20 0:00 ` Michael Feldman 1996-07-20 0:00 ` Robert Dewar 2 siblings, 1 reply; 133+ messages in thread From: Michael Feldman @ 1996-07-20 0:00 UTC (permalink / raw) In article <dewar.837456126@schonberg>, Robert Dewar <dewar@cs.nyu.edu> wrote: >(I suspect you meant MOOT as in "doesn't matter any more", but that is not >what the word means in traditional usage, although I agree this US usage >is (unfortunately) getting very common) The English and the Americans are two people separated by a common language. (Shaw?) Actually, the "unfortunate" US usage of "moot" is quite normal in legal circles, and has been for a long time. Courts will use the term to mean a legal issue they don't have to worry about deciding, because the conditions in the suit were overtaken by events, or some other such cause. Law schools have a ritual they call "moot court", which is essentially a simulated courtroom drama, where students debate each other to get practice for doing so in real courtrooms. I think both senses of "moot" apply here - it is a court where things are debated, but it doesn't matter what the outcome is (well, except maybe for a student's grade.:-)) Your 1-man crusade to hold back the tide is (in both senses) moot.:-) Mike Feldman ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-20 0:00 ` Michael Feldman @ 1996-07-20 0:00 ` Robert Dewar 0 siblings, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-20 0:00 UTC (permalink / raw) Micheal said "Actually, the "unfortunate" US usage of "moot" is quite normal in legal circles, and has been for a long time. Courts will use the term to mean a legal issue they don't have to worry about deciding, because the conditions in the suit were overtaken by events, or some other such cause." That's confused -- look up moot in any legal dictionary, and you will find the first definition only -- that is the legal definition. A moot issue is one that is undecided, and hence arguable. When a judge declares an issue moot, he is declaring that the court will not decide the issue. The reasons for this may be many, and sometimes an observer thinking in terms of the second definition will find it consistent, but it is always the first meaning that is operable -- the court will leave the decision undecided! A moot court is one that considers an undecided arguable issue, again, only the first definition applies. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-15 0:00 ` Fergus Henderson 1996-07-15 0:00 ` Robert Dewar @ 1996-07-16 0:00 ` Richard Kenner 1 sibling, 0 replies; 133+ messages in thread From: Richard Kenner @ 1996-07-16 0:00 UTC (permalink / raw) In article <4sdt1i$nqa@mulga.cs.mu.OZ.AU> fjh@mundook.cs.mu.OZ.AU (Fergus Henderson) writes: >Well, there's still going to be a lot of Pentiums out there for quite >some time -- I wouldn't call the issue entirely moot yet. I would because the issue is optimization, not functionality. The people who want every last cycle of performance are now going to be the ones who use a P6, not a Pentium. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 ` Robert A Duff ` (5 preceding siblings ...) 1996-07-07 0:00 ` Ronald Cole @ 1996-07-08 0:00 ` Brian Rogoff 1996-07-11 0:00 ` Norman H. Cohen 1996-07-09 0:00 ` Jon S Anthony ` (9 subsequent siblings) 16 siblings, 1 reply; 133+ messages in thread From: Brian Rogoff @ 1996-07-08 0:00 UTC (permalink / raw) ncohen@watson.ibm.com (Norman H. Cohen) writes: (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.) Could you summarize or provide a reference to Bill Taylor's work? Does it answer the objection that downward closures impose an inefficiency on programs that don't use them? I like closures myself, but I am thinking of the full (upward I guess you'd call them) closures of Lisp, which require garbage collection. Perhaps a "syntactically upwards compatible" Ada dialect supporting closures should be considered, especially since the Java virtual machine already imposes GC on any language that runs on it, and it will be a popular target. -- Brian ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-08 0:00 ` Brian Rogoff @ 1996-07-11 0:00 ` Norman H. Cohen 1996-07-11 0:00 ` Magnus Kempe 0 siblings, 1 reply; 133+ messages in thread From: Norman H. Cohen @ 1996-07-11 0:00 UTC (permalink / raw) In article <ROGOFF.96Jul8155205@sccm.Stanford.EDU>, rogoff@sccm.Stanford.EDU (Brian Rogoff) writes: |> ncohen@watson.ibm.com (Norman H. Cohen) writes: ... |> 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.) |> |> Could you summarize or provide a reference to Bill Taylor's work? Does it |> answer the objection that downward closures impose an inefficiency on programs |> that don't use them? Bill Taylor's contribution was part of an ongoing discussion in the form of comments sent to the Mapping/Revision Team during the design of Ada 9X. All of these comments from June 1992 on are publicly available in the following directory: ftp://sw-eng.falls-church.va.us/public/AdaIC/standards/95com/mrtcomments/ All the comments through April 1994 are in files with names of the form YYMMmrt.zip, where YY and MM are the year and month the comment was received. (Thus all comments from May 1993 are in 9305mrt.zip.) Starting with May 1994, there are individual daily files, such as 94.0501 for all comments received on May 1, 1994. The discussion on downward closures and their impact on display implementations included the following comments: Date Comment ID Author My summary April 29, 1993 93.2622.b Bill Taylor The initial message about iterators mentioned above. May 1, 1993 93-2628.b Robert Duff Says he likes the feature, but Robert Dewar has frightened WG9 members about the cost, and the MRT won't add downward closures until someone convinces WG9 otherwise. Claims the size of a display is not known at compile time. May 3, 1993 93-2634.a Norman Cohen Reply to Duff, asserting that the size of a display IS known at compile time. Foreshadows an identical exchange that will take place on comp.lang.ada in July 1996. :-) May 3, 1993 93-2635.a Robert Duff Reply to Cohen. Size of a display is not known at the site of a call through a pointer. Says he hates arguing against a feature he likes. May 3, 1993 93-2637.a Randy Brukardt Reports that Janus/Ada uses (RR Software) displays. Proposes a workaround involving unchecked conversion. May 3, 1993 93-2638.a Robert Duff Reply to Brukardt, asking him to explain workaround. May 4, 1993 93-2644.a Antoine Bertier Reports that Alsys uses (Alsys) displays for most of its compilers. May 4, 1993 93-2645.a Ted Baker Calls displays an "anachronism", except on register-poor machines. May 4, 1993 93-2646.a Randy Brukardt Reply to Duff, explaining his workaround and conceding that it is not portable to compilers that do NOT use displays. May 5, 1993 93-2647.a Brian Dobbing Also reports that Alsys (Alsys) uses displays, states that Alsys cannot afford any more language changes with such great impact on their compilers, and states that neither the display approach nor the static link approach is always the right choice. May 5, 1993 93-2651.a Bill Taylor Points out that Brukhardt's proposed workaround does not work when the pointed- to procedures reference data in surrounding scopes, as they do in his iterators example. May 5, 1993 93-2655.a Robert Dewar Reply to Baker, defending displays and asserting that they can be quite efficient. May 5, 1993 93-2656.a Robert Eachus Experiments (with a compiler that was altered to send Eachus e-mail every time code was generated for a call on a nested subprogram!) show that calls on nested procedure are rare, so the expense of supporting this feature is not justified. May 6, 1993 93-2661.a Ted Baker Reply to Dewar, claiming that downward closures were important for the kind of applications that justified ANY inclusion of 'Access for nested subprograms in Ada 9X, and worth the cost; but admitting that Brian Dobbing's economic argument might be the deciding consideration. May 11, 1993 93-2676.a Randy Brukardt Reply to Baker. May 11, 1993 93-2676.b Randy Brukardt States that downward closures impose a distributed overhead on all uses of generics when generics are implemented by shared code for all instances, as in Janus/Ada. January 14, 1994 94-3669.a Bjorn Kallberg An eloquent case for the importance of downward closures, pointing out that their omission would create the only case in which Ada is not a functional superset of Pascal. February 15, 1994 LSN 1083 Robert Duff A dispassionate analysis of all sides of the issue, explaining why the MRT decided not to include downward closures in Ada 9X. March 4, 1994 94-3985.a David Tombs An empassioned plea to reconsider this decision. -- Norman H. Cohen ncohen@watson.ibm.com ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-11 0:00 ` Norman H. Cohen @ 1996-07-11 0:00 ` Magnus Kempe 1996-07-11 0:00 ` Robert Dewar 0 siblings, 1 reply; 133+ messages in thread From: Magnus Kempe @ 1996-07-11 0:00 UTC (permalink / raw) ncohen@watson.ibm.com (Norman H. Cohen) writes: : : Bill Taylor's contribution was part of an ongoing discussion in the form : of comments sent to the Mapping/Revision Team during the design of Ada 9X. If I remember correctly, the final decision was based on arguments about displays (Dewar arguing against a more generalized 'Access), alternatives using generics and abstract types (Barnes arguing de facto against a more generalized 'Access), and the bad mistake made in Ada 83 (the lack of access to subprograms, as compared to C, Pascal, etc.). This is not the only decision that was made on the basis of some implementors' fears rather than for the sake of Ada users. For instance, at some point in the revision process child units of generics were rejected; the "solution" was a compromise so that some implementors would not need to make any changes in their linking steps when updating their compiler from Ada 83 to Ada 95. The consequence is that not all non-generic hierarchies of packages can be turned into generic hierarchies (just adding "generic" doesn't work, e.g. if some child unit needs to "with" another child unit in the same hierarchy). As Norm mentioned, most of these issues are documented in the "mrtcomments" available online. I hope the designers of Ada 0Y (oh-why) will read these discussions carefully for the next revision--if there is one--so that they can make a list of the fallacious arguments that will no doubt pop up again. In the meantime, I think it is a very bad idea to try to "fix" such mistakes by the introduction of an ever-increasing number of "hacking" attributes. For one thing, this tends to make Ada programs less portable (from one compiler to another). -- Magnus Kempe "I know not what course others may take, but as Magnus.Kempe@di.epfl.ch for me, Give me Liberty... or give me Death!" http://lglwww.epfl.ch/Team/MK/ -- Patrick Henry ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-11 0:00 ` Magnus Kempe @ 1996-07-11 0:00 ` Robert Dewar 0 siblings, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-11 0:00 UTC (permalink / raw) "As Norm mentioned, most of these issues are documented in the "mrtcomments" available online. I hope the designers of Ada 0Y (oh-why) will read these discussions carefully for the next revision--if there is one--so that they can make a list of the fallacious arguments that will no doubt pop up again." fallacious arguments on either side :-) the same argument of implementability vs functionality will of course arise if the language is revisited, and the view in either case may have changed. On the one hand, implementors may come and say "well in retrospect that is not such a big deal", or "Gosh, this was even more critical than we though that this be left out because xxx", and of course a different cast of implementors and technologies will be around. On the other hand, programmers may come and say "turns out that was not a critical feature after all, so it did not matter that we did not put it in", or they may say "drat! I *really* find the lack of this feature a pain, and it should be fixed now, here are some examples: xxx" Different people will feel different ways (for example I find the lack of in out and out parameters for functions a real pain, and suspect I will continue to do so in the future, and that wasn't even left out befcause of implementation concerns, but rather purity concerns). One thing to notice is that once a feature is put *in*, then it never comes out again, even if programmers arrive ten years from now and say "hmm, we have found that feature useless, it can be removed". I find the obsolescent features Annex in the Ada 95 a useless fantasy, when we revise the language, we will still end up levaing these features in because of compatibility concerns (remember what happened with COBOL 8X and the attempt to remove ALTER). Given that ratchet effect, one prefers to leave features out if you are not absolutely sure they belong in! ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 ` Robert A Duff ` (6 preceding siblings ...) 1996-07-08 0:00 ` Brian Rogoff @ 1996-07-09 0:00 ` Jon S Anthony 1996-07-09 0:00 ` Robert Dewar 1996-07-09 0:00 ` Robert Dewar 1996-07-09 0:00 ` Jon S Anthony ` (8 subsequent siblings) 16 siblings, 2 replies; 133+ messages in thread From: Jon S Anthony @ 1996-07-09 0:00 UTC (permalink / raw) In article <4rr5tu$sap@watnews1.watson.ibm.com> ncohen@watson.ibm.com (Norman H. Cohen) writes: > (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.) While the lack of direct support for recursive types across package boundaries and lack of assertions are more important (IMO) goofs, and while the evinced reasons for the latter one are mind numbingly incomprehensible, this latest example would appear to take the crown for the most stupefying goof. Just amazing... /Jon -- Jon Anthony Organon Motives, Inc. 1 Williston Road, Suite 4 Belmont, MA 02178 617.484.3383 jsa@organon.com ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-09 0:00 ` Jon S Anthony @ 1996-07-09 0:00 ` Robert Dewar 1996-07-09 0:00 ` Robert Dewar 1 sibling, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-09 0:00 UTC (permalink / raw) "While the lack of direct support for recursive types across package boundaries and lack of assertions are more important (IMO) goofs, and while the evinced reasons for the latter one are mind numbingly incomprehensible, this latest example would appear to take the crown for the most stupefying goof." One interesting question to ask is how people are using Unrestricted_Access in GNAT. During the discussion of this issue in WG9, we did have some examples that purported to show the importance of this issue (I am including Bill Taylor's discussion of iterators), but they were unconvincing, since there seemed to be alternative expressions that were quite acceptable (the final vote on this issue was unanimous by delegations as I remember, which means there was no strong advocate for keeping the feature -- there certainly were some energetic arguments over an extended period of time -- but by the end, everyone was convinced. Now the difficulty with arguing by example is that of course you don't know if you have found the critical examples or not. Note that the entertaining thing about Jon labeling this as a stupefuing goof is that in the message *just* before this one, he declared that real programs have no nesting anyway, and of course all this business about closures is irrelevant nonsense in programs that don't have any nesting! So, the intersting question is: are there examples that people are running into, involving nesting of course, since otherwise the issue does not arise, where the use of Unrestricted_Access in GNAT seems really critical. I must say I implemented this attribute because it fell out literally free to do so (the real thing I needed was an access attribute that did not require aliased, but the procedure case just fell out), not because I had a critical use in mind, but I certainly have found some uses for it, none that I would label as critical. But if someone can present some really nice example where the use of Unrestricted_Access is critical, that would be interesting. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-09 0:00 ` Jon S Anthony 1996-07-09 0:00 ` Robert Dewar @ 1996-07-09 0:00 ` Robert Dewar 1 sibling, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-09 0:00 UTC (permalink / raw) Jon says "While the lack of direct support for recursive types across package boundaries and lack of assertions are more important (IMO) goofs, and while the evinced reasons for the latter one are mind numbingly incomprehensible, this latest example would appear to take the crown for the most stupefying goof." Well it is always easy for users to decide that they want everything and don't want to worry about the required resources, but a language design can't be quite that cavalier in balancing requirements. The fact of the matter is that providing for displays to work reasonably easy *has* had value in getting at least some Ada 95 compilers to market more easily than might have otherwise been the case. I think everyone agrees that it is valuable to have several compilers competing, and the balance in features vs implementability was always a tricky one. Note that we did lose one compiler (the DEC Ada compiler), and a large part of the reason for DEC's decision to get out of the Ada compiler business was that they estimated it was too expensive to modify their technology for Ada 95. We have also lost at least one front end (the old Alsys technology, and before that the Systeam technology), and more may dissappear before we are through. At least the Alsys code generators proved largely adaptable to Ada 95. Of course we have gained at least two new front ends (GNAT and Intermetrics, so the front end situation looks healthy, although it is interesting that both of these front ends were "from scratch". One of the key requirements in the design was that Ada 95 not be such a big change that it would be impractical to adapt existing Ada 83 front ends. At some points in the design, some people expressed the opinion that this was impractical, and that we should assume that "from scratch" development was the only practical path, but WG9 insisted on a viewpoint that we should not restrict things in this way. It appears that we at least partially succeeded, since at least two Ada 95 front ends *are* adaptations of Ada 83 frontends. There is certainly no doubt that Ada 95 is close to the limits of acceptable front end complexity. Of course when you look at individual features, it is hard to label any one feature as a back-breaking straw, but that's what that little fable is all about after all :-) ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 ` Robert A Duff ` (7 preceding siblings ...) 1996-07-09 0:00 ` Jon S Anthony @ 1996-07-09 0:00 ` Jon S Anthony 1996-07-09 0:00 ` Robert Dewar 1996-07-10 0:00 ` Ronald Cole ` (7 subsequent siblings) 16 siblings, 1 reply; 133+ messages in thread From: Jon S Anthony @ 1996-07-09 0:00 UTC (permalink / raw) In article <dewar.836627383@schonberg> dewar@cs.nyu.edu (Robert Dewar) writes: > Jon said > > "I can maybe buy the second bit (about difficulty for display based > impls) but the first makes no sense. You wouldn't have to pass > displays or whatever in those cases where the feature wasn't being > used. Which means that there is _no_ distributed overhead for the > 99+% of regular ol' subprogram calls." > > If you buy the second bit, and if you agree that displays are more > efficient than static links for Ada programs (which is not gospel, > it requires discussion and examination -- I certainly think it is > the case), then the first bit is a consequence, since the provision > of closures would push you away from using displays, and hence > introduce distributed overhead -- that was what was being talked about. I don't see how, as most programs will not have _any_ nesting. Period. So displays or static links are irrelevant for nearly all cases. So, the issue is irrelevant to [probably not even hyperbole here] 99+% of subprogram calls. Which means that there really is no distributed overhead (at least not as I understand the term). /Jon -- Jon Anthony Organon Motives, Inc. 1 Williston Road, Suite 4 Belmont, MA 02178 617.484.3383 jsa@organon.com ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-09 0:00 ` Jon S Anthony @ 1996-07-09 0:00 ` Robert Dewar 0 siblings, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-09 0:00 UTC (permalink / raw) Jon Anthony says "I don't see how, as most programs will not have _any_ nesting. Period. So displays or static links are irrelevant for nearly all cases. So, the issue is irrelevant to [probably not even hyperbole here] 99+% of subprogram calls. Which means that there really is no distributed overhead (at least not as I understand the term)." This is wildly overstated. I would say that any large program that has no nested procedures at all is poorly written, and I have seen very few large program (actually none in Ada) that had no nesting at all. On the other hand, I have *quite* often seen programs using nesting *very* extensively, where the program was divided into large procedures, containing many nested procedures, where the majority of calls are to procedures contained within other procedures. I don't believe Jon's figure of 99+% of subprogram calls being to library level subprograms is anywhere near right, and I would guess it is just a rhetorical guess rather than any kind of measurement. Across an admitedly small sample of large programs that I was involved in measuring, we saw over 80% of the calls being to procedures that were nested inside other procedures. Probably the big picture is that some programs use very little nesting, and therefore are insensitive to the display mechanism, and other programs nest heavily, and are potentially sensitive to the mechanism. I will get some statistics on our Ada 95 database when I have chance to find out what we see there. For GNAT itself, there are sections in both styles. For a style where calls to nested procedures are heavy in frequency, see sem_prag.adb for example. Remember that nesting of procedures becomes much more critical in tasking programs, because it is the cheap way of making task local data. One of the problems in making C library routines threadsafe is that they tend to use global variables heavily, which in corresponding Ada programs would typically be local uplevel references. For example, printf is presumably a big nest of functions, and it would not be surprising if there are some global variables around that make it thread unsafe. In Ada, one would nest these subsidiary functions inside the equivalent of printf, and the global variables would become local variables of printf itself, and therefore task specific. In any case, I agree it is probably not a critical point. gcc uses static links for all implementations (and a good thing too, because it is what made pointers to inner procedures possible, something we depend on quite a bit). Most of the Alsys implementations used displays, and to our satisfaction (our = Alsys, I used to work for them :-) our measurements showed that this was clearly more efficient, but in the big picture of things, I doubt the difference was very significant. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 ` Robert A Duff ` (8 preceding siblings ...) 1996-07-09 0:00 ` Jon S Anthony @ 1996-07-10 0:00 ` Ronald Cole 1996-07-11 0:00 ` Robert Dewar 1996-07-11 0:00 ` Richard Kenner 1996-07-11 0:00 ` Jon S Anthony ` (6 subsequent siblings) 16 siblings, 2 replies; 133+ messages in thread From: Ronald Cole @ 1996-07-10 0:00 UTC (permalink / raw) dewar@cs.nyu.edu (Robert Dewar) writes: > Ronald Cole said (commenting on my claim that GCC did not have multiple > backends) > > Not true. A single instance of GCC doesn't support multiple machine > targets (other than the -m options for some processor families). GCC > has to be recompiled to support different machine descriptions (that's > what the -b and -V options of gcc are for). I consider this as having > multiple backends. > > That's not what I meant, yes, of course there are multiple backends at > the object level, but not at the source level. Again not true. Yes, the source contains all the parts for each backend, but all the parts are not used to build the backend. Configure() will determine the correct source files and create links to properly build one target backend. The multiple backends at the source level are kept under the config subdirectory and grouped by architecture. I count thirty distinct backends: 1750a/1750a.md fx80/fx80.md m88k/m88k.md sh/sh.md a29k/a29k.md gmicro/gmicro.md mips/mips.md sparc/sparc.md alpha/alpha.md h8300/h8300.md ns32k/ns32k.md spur/spur.md arm/arm.md i370/i370.md pa/pa.md tahoe/tahoe.md clipper/clipper.md i386/i386.md pdp11/pdp11.md vax/vax.md convex/convex.md i860/i860.md pyr/pyr.md we32k/we32k.md dsp16xx/dsp16xx.md i960/i960.md romp/romp.md elxsi/elxsi.md m68k/m68k.md rs6000/rs6000.md > Most Ada technologies have a single front end for all targets (though > Ronald Cole would presumably call these multiple front ends too, because > there are certanly separate object versions), You presume incorrectly. I consider the frontend to be defined by the language it accepts, not by the host architecture or the number of object files in an implementation. Likewise, I consider the backend to be defined by the object code it produces. > But for technologies like GCC, where there is only one source program for > both front end and backend (though in both cases multiple executables), > this distinction is not significant. But it is. While the union of the sources for each target architecture is the GCC source tree, the difference of the sources for each target architecture is not the null set. -- Ronald Cole E-mail: ronald@ridgecrest.ca.us President, CEO zippy@ecst.csuchico.edu Forte International Fax: (619) 384-2346 My PGP fingerprint: E9 A8 E3 68 61 88 EF 43 56 2B CE 3E E9 8F 3F 2B ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-10 0:00 ` Ronald Cole @ 1996-07-11 0:00 ` Robert Dewar 1996-07-11 0:00 ` Richard Kenner 1 sibling, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-11 0:00 UTC (permalink / raw) Ronald Cole said "Again not true. Yes, the source contains all the parts for each backend, but all the parts are not used to build the backend. Configure() will determine the correct source files and create links to properly build one target backend. The multiple backends at the source level are kept under the config subdirectory and grouped by architecture. I count thirty distinct backends:" Ronald is still missing the point that started this thread. There are two kinds of technologies. In one, the code generators for different target architectures are completely separate programs that may not even have the same overall design, let alone the same souce code. This approach is typical of a number of Ada 83 compiler technologies. The other kind of technology uses a single common source base for all backends. GCC is in this category. Yes, the configuration files differ, but the great majority of the code is common. This is a critical feature of GCC, and is what allows easy porting of the technology. To port to a new architecture, a new configuration file needs to be written, but not a new code generator. In the context of the original point in this thread, the critical thing is that if you have a change to the language which affects the backend, rather than just the front end, then the two technology approaches will be in a very different situation. In one case, you have to change multiple separate programs, in the other, unless the change affects configuration files, you only have to change one program. So far the Ada 95 changes have required zero changes to the configuration files, although eventually we anticipate some minor changes being required (and of course no change to configuration files is really minor, precisely because it has to be done in multiple cases). Ronald's technical comments on the GCC structure, while quite correct (after all I know this technology perfectly well, so we do not disagree on what is there) obscure the central point. There is a BIG difference between single-common-source-code-generator technologies and multiple-code-generator technologies when it comes to language changes that affect the back end. One of the design points in Ada 95 was to minimize changes that would impact backends, precisely because some Ada technologies (those using multiple separate front ends) could have been severely affected by such changes. On the other hand, if you use the GCC approach, the disctinction is not so important, and had we known that *all* Ada technologies used a single common source approach we might have made some design decisions differently, but in fact we knew this definitely was NOT the case. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-10 0:00 ` Ronald Cole 1996-07-11 0:00 ` Robert Dewar @ 1996-07-11 0:00 ` Richard Kenner 1 sibling, 0 replies; 133+ messages in thread From: Richard Kenner @ 1996-07-11 0:00 UTC (permalink / raw) In article <m2u3vfem42.fsf@devo.ridgecrest.ca.us> Ronald Cole <ronald@ridgecrest.ca.us> writes: >Again not true. Yes, the source contains all the parts for each >backend, but all the parts are not used to build the backend. >Configure() will determine the correct source files and create links >to properly build one target backend. The multiple backends at the >source level are kept under the config subdirectory and grouped by >architecture. I count thirty distinct backends: What you are actually counting are thirty distinct configuration files used to tailor the single backend to a particular target machine. >You presume incorrectly. I consider the frontend to be defined by the >language it accepts, not by the host architecture or the number of >object files in an implementation. Likewise, I consider the backend >to be defined by the object code it produces. So long as you state the definitions you are using, you are free to use any you want. But whatever words you use, there is a major distinction between the GCC approach and that used by other multi-target systems. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 ` Robert A Duff ` (9 preceding siblings ...) 1996-07-10 0:00 ` Ronald Cole @ 1996-07-11 0:00 ` Jon S Anthony 1996-07-11 0:00 ` Jon S Anthony ` (5 subsequent siblings) 16 siblings, 0 replies; 133+ messages in thread From: Jon S Anthony @ 1996-07-11 0:00 UTC (permalink / raw) In article <dewar.836962533@schonberg> dewar@cs.nyu.edu (Robert Dewar) writes: > Jon Anthony says > > "I don't see how, as most programs will not have _any_ nesting. > Period. So displays or static links are irrelevant for nearly all > cases. So, the issue is irrelevant to [probably not even hyperbole > here] 99+% of subprogram calls. Which means that there really is no > distributed overhead (at least not as I understand the term)." > > This is wildly overstated. I would say that any large program that has > no nested procedures at all is poorly written, and I have seen very > few large program (actually none in Ada) that had no nesting at all. I can agree with this (even the "wildly" bit :-)) > On the other hand, I have *quite* often seen programs using nesting > *very* extensively, where the program was divided into large procedures, > containing many nested procedures, where the majority of calls are to > procedures contained within other procedures. And I would say that these are examples where "poorly written" would equally apply. > I don't believe Jon's figure of 99+% of subprogram calls being to library > level subprograms is anywhere near right, and I would guess it is just > a rhetorical guess rather than any kind of measurement. Across an Yes, no real data - only anecdotal evidence. Hence the "hyperbole caveat". > admitedly small sample of large programs that I was involved in measuring, > we saw over 80% of the calls being to procedures that were nested inside > other procedures. I find that a little surprising, but facts is facts. I would also say that this is very likely an indication that something has gone wrong. Not in the measurement, but in the programs. > In any case, I agree it is probably not a critical point. gcc uses static Check! /Jon -- Jon Anthony Organon Motives, Inc. 1 Williston Road, Suite 4 Belmont, MA 02178 617.484.3383 jsa@organon.com ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 ` Robert A Duff ` (10 preceding siblings ...) 1996-07-11 0:00 ` Jon S Anthony @ 1996-07-11 0:00 ` Jon S Anthony 1996-07-11 0:00 ` Tucker Taft ` (3 more replies) 1996-07-11 0:00 ` Jon S Anthony ` (4 subsequent siblings) 16 siblings, 4 replies; 133+ messages in thread From: Jon S Anthony @ 1996-07-11 0:00 UTC (permalink / raw) In article <dewar.836964092@schonberg> dewar@cs.nyu.edu (Robert Dewar) writes: > if you have found the critical examples or not. Note that the entertaining > thing about Jon labeling this as a stupefuing goof is that in the message > *just* before this one, he declared that real programs have no nesting > anyway, and of course all this business about closures is irrelevant > nonsense in programs that don't have any nesting! Nah, that's not what's entertaining. What's entertaining is that I failed to make clear that it wasn't the actual leaving out of the proposal that was "stupefying" but rather the purported reasons for doing so. Actually this isn't entertaining either - more like a goof than anything else! Oh, and I did _NOT_ say that closures are irrelevant nonsense (that would just be plain stupid), I said that most programs don't have much nesting and that without nesting no cost is incurred and therefore any argument about distributed cost in the user model as a reason for not having them was nonsense. And that is still just plain true. /Jon -- Jon Anthony Organon Motives, Inc. 1 Williston Road, Suite 4 Belmont, MA 02178 617.484.3383 jsa@organon.com ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-11 0:00 ` Jon S Anthony @ 1996-07-11 0:00 ` Tucker Taft 1996-07-17 0:00 ` Brian Rogoff 1996-07-11 0:00 ` Robert Dewar ` (2 subsequent siblings) 3 siblings, 1 reply; 133+ messages in thread From: Tucker Taft @ 1996-07-11 0:00 UTC (permalink / raw) Jon S Anthony (jsa@organon.com) wrote: : ... What's entertaining is that I : failed to make clear that it wasn't the actual leaving out of the : proposal that was "stupefying" but rather the purported reasons for : doing so. It is generally impossible to fully reconstruct the process by which decisions like this are made. But I will give it a try... We originally proposed a version of access-to-subprograms that would allow for downward closures. These were called "limited access types" because allowing assignment for these types would definitely create the possibility for dangling references. So these kinds of access types would need to disallow assignment, and hence be "limited." At the time of this original proposal (in 1990, I believe), the 9X reviewers were overwhelmed by the number of changes proposed for Ada 9X, and this just seemed like added complexity for less than comensurate gain. This was always the hard question: does the added functionality make up for the added complexity, and is the Ada 9X "complexity" boat reaching the point of sinking completely? We had to make a lot of hard decisions. If you look only at the "margin", taking one decision at a time, you can very frequently convince yourself that just this one more feature would have been a good idea. However, we were defintely struggling with the "overloaded boat" problem. It is also easy to say that you shouldn't worry about compiler implementation, but in fact, many of the problems of Ada 83 (and perhaps Algol 68, and other well-designed languages) were due to the pragmatic realities of getting a sufficient number of high-quality, fully-compliant compilers out the door in a reasonable time-frame. One of our goals was to minimize changes that required modifications to compiler back ends. We achieved this goal to a remarkable extent, in my view. Another sub-goal was to allow existing "C" compiler backends to be used with Ada 95 front ends, without major changes to the backend. Support for downward closures clearly began to run afoul of this goal. Finally, there was already very flexible support for downward closures in the form of generic formal subprograms. Admittedly, generics are more verbose. However, they don't have any of the limitations that would likely be associated with an access-to-subprogram approach. You can pass a predefined operator, an attribute, even an enumeration literal as a subprogram parameter to a generic. Hence, we now have a suggested feature that: 1) Adds semantic complexity (by requiring two kinds of access-to-subprogram types, limited and non-limited); 2) Is largely functionally redundant with an existing feature; 3) May require changes to many backends. Our main "competitors" in the language wars, C, C++, and now Java, have no support for this feature. Is this the feature we should spend our valuable Ada 9X "chips" on? I hope you will at least agree that the answer is not a trivially obvious "yes"... : Jon Anthony : Organon Motives, Inc. : 1 Williston Road, Suite 4 : Belmont, MA 02178 : 617.484.3383 : jsa@organon.com -Tucker Taft stt@inmet.com http://www.inmet.com/~stt/ Intermetrics, Inc. Cambridge, MA USA ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-11 0:00 ` Tucker Taft @ 1996-07-17 0:00 ` Brian Rogoff 0 siblings, 0 replies; 133+ messages in thread From: Brian Rogoff @ 1996-07-17 0:00 UTC (permalink / raw) dewar@cs.nyu.edu (Robert Dewar) writes: <talking about downward closures> Tuck is certainly right that the reason that this originally disappeared was in the general mood of simplification, although some would feel that the restriction here is not a simplification but rather an instance of introducing arbitrary restrictions that make things more complex. I am surprised that anyone would feel that it is not a restriction that makes things more complex for the user. It's not arbitrary, in that there are several implementation oriented arguments favoring the restriction. I can accept the decision as reasonable given the circumstances, and lack of compelling data refuting the implementation arguments or less compelling data about the utility of the feature in similar languages. But the failure of Bill Taylor's arguments with repsect to iterators to succeed in getting the feature in was definitely the above consideration, and as I say, you should read all the articles -- of course the articles only capture a part of the argument -- you should also read Jim's excellent minutes of the Villar's meeting where this issue was discussed and finally decided on. Is this online somewhere? -- Brian ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-11 0:00 ` Jon S Anthony 1996-07-11 0:00 ` Tucker Taft @ 1996-07-11 0:00 ` Robert Dewar 1996-07-15 0:00 ` Mark A Biggar 1996-07-12 0:00 ` Jon S Anthony 1996-07-15 0:00 ` Jon S Anthony 3 siblings, 1 reply; 133+ messages in thread From: Robert Dewar @ 1996-07-11 0:00 UTC (permalink / raw) Jon said "irrelevant nonsense (that would just be plain stupid), I said that most programs don't have much nesting and that without nesting no cost is incurred and therefore any argument about distributed cost in the user model as a reason for not having them was nonsense. And that is still just plain true." Just to be absolutely clear on this, since it seems to have caused a lot of confusion :-) The Steelman (and hence Ada 83) reasoning for not allowing procedure parameters was indeed influenced by concerns about distributed cost of uplevel reference mechanisms (if you read Steelman, you will see that concern expressed in black-and-white). Whether this concern is legitimate or not probably can't be settled without some hard data on existing Ada programs (what you need is dynamic traces that show how many calls are to outer level procedures, and how many calls are to procedures that contain no nested procedures). At least that will allow you to track the cost of display/static-chain handling. If you think uplevel references themselves are a significant factor, as some do in this thread, then you also need dynamic data on the number of such references and how deep they go (by procedure invocation, so that you can factor out optimization effects). As is clear from the thread, Jon and I simply disagree on the bottom line here, but I don't think any more arguments without data can illuminate this discussion further (it is by the way a *very* old discussion). The Ada 95 reasoning for not allowing completely general procedure parameters (that would handle the case where nested procedures are involved in all cases), has NOTHING to do with distributed cost. It had solely to do with concerns about the cost of implementation, and if you want to track Norman's very nice precis of the written discussion on this issue, you will see how the back-and-forth went on this issue. Again, the question of whether the trade-off was made correctly can be discussed. That's more of a subjective issue, but it would be influenced in retrospect by nice examples of things you can't do but would be nice to be able to do, but you can't do in any other convenient way, and one would think that if there are such, some of them might have surfaced by now. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-11 0:00 ` Robert Dewar @ 1996-07-15 0:00 ` Mark A Biggar 1996-07-15 0:00 ` Robert Dewar 0 siblings, 1 reply; 133+ messages in thread From: Mark A Biggar @ 1996-07-15 0:00 UTC (permalink / raw) Does tasking mess the static link vs display trade off in any way. I.E. a procedure nested in a task nested in a procedure and you want to pass the inner most procedure as a parameter. -- Mark Biggar mab@wdl.lmco.com ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-15 0:00 ` Mark A Biggar @ 1996-07-15 0:00 ` Robert Dewar 0 siblings, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-15 0:00 UTC (permalink / raw) Mark says "Does tasking mess the static link vs display trade off in any way. I.E. a procedure nested in a task nested in a procedure and you want to pass the inner most procedure as a parameter." The only effect is that if you are using a single global display, you need to switch displays when you switch tasks, which means that the display has to be per-task data. A common implementation approach is to put the display in the TCB, and then have a register pointing to the TCB. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-11 0:00 ` Jon S Anthony 1996-07-11 0:00 ` Tucker Taft 1996-07-11 0:00 ` Robert Dewar @ 1996-07-12 0:00 ` Jon S Anthony 1996-07-12 0:00 ` Robert Dewar 1996-07-15 0:00 ` Jon S Anthony 3 siblings, 1 reply; 133+ messages in thread From: Jon S Anthony @ 1996-07-12 0:00 UTC (permalink / raw) In article <DuDyus.I8I.0.-s@inmet.camb.inmet.com> stt@henning.camb.inmet.com (Tucker Taft) writes: > Jon S Anthony (jsa@organon.com) wrote: > > : ... What's entertaining is that I > : failed to make clear that it wasn't the actual leaving out of the > : proposal that was "stupefying" but rather the purported reasons for > : doing so. > >...[interesting stuff snipped] > > At the time of this original proposal (in 1990, I believe), the > 9X reviewers were overwhelmed by the number of changes proposed for > Ada 9X, and this just seemed like added complexity for less than > comensurate gain. This was always the hard question: does the added > functionality make up for the added complexity, and is the Ada 9X > "complexity" boat reaching the point of sinking completely? Now, we are on to something. This is the sort of analysis I was hoping was lurking behind the decision, not this emphasis on all the rubbish about static links vs. displays. > We had to make a lot of hard decisions. If you look only at the > "margin", taking one decision at a time, you can very frequently > convince yourself that just this one more feature would have been > a good idea. However, we were defintely struggling with the > "overloaded boat" problem. Makes _perfect_ sense and is completely reasonable. > It is also easy to say that you shouldn't worry about compiler > implementation, but in fact, many of the problems of Ada 83 (and > perhaps Algol 68, and other well-designed languages) were due to the > pragmatic realities of getting a sufficient number of high-quality, > fully-compliant compilers out the door in a reasonable time-frame. This also definitely makes sense - again in the overall picture! Sure, in an individual case you don't want to introduce some wild-6-sigmas-out construct that noone has any experience with in implementing. But other than that, the overall goal (best overall design which can actually be produced) should be primary. > One of our goals was to minimize changes that required modifications > to compiler back ends. We achieved this goal to a remarkable extent, > in my view. Another sub-goal was to allow existing "C" compiler backends > to be used with Ada 95 front ends, without major changes to the backend. > Support for downward closures clearly began to run afoul of this goal. As several have pointed out, this is not particularly convincing. The best evidence indicates that this was a red-herring in this instance. > Hence, we now have a suggested feature that: > > 1) Adds semantic complexity (by requiring two kinds of > access-to-subprogram types, limited and non-limited); > 2) Is largely functionally redundant with an existing feature; > 3) May require changes to many backends. Wow! Here's an analysis that really makes sense - especially in the ranking (hopefully this was not accidental!) Stir in the bits about balancing the "total reasonable amount of things that can go in" and weighing it against something else which is much more important and would have to go if this one got in and _voila_, a perfectly reasonable and probably even correct decision. > Our main "competitors" in the language wars, C, C++, and now Java, > have no support for this feature. Well, now we are back to irrelevant... > I hope you will at least agree that the answer is not a trivially > obvious "yes"... Correct. Thanks, Tucker, for explaining this and showing that the thinking that I was hoping was lurking behind the decision was. /Jon -- Jon Anthony Organon Motives, Inc. 1 Williston Road, Suite 4 Belmont, MA 02178 617.484.3383 jsa@organon.com ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-12 0:00 ` Jon S Anthony @ 1996-07-12 0:00 ` Robert Dewar 0 siblings, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-12 0:00 UTC (permalink / raw) iJon said "As several have pointed out, this is not particularly convincing. The best evidence indicates that this was a red-herring in this instance." Nope, this was not a red herring, it (the concern about backend reimplementation) was the major focus of the argument. Remember that this feature was being discussed very late on. Jon, did you read all the references that Norman pointed to, they will give you a clear picture of the discussion on this issue. The reason it was discussed late on was Bill Taylor's late plea to reexamine this issue in light of the iterator issue (well worth reading, it is the first of Norman's references). This got a lot of people interested again, and in the absence of implementatoin concerns, it is clear that the design would have been revisited. This late discussion was entirely focused on the issue of importance of this functionality vs impact on existing backends Note that, as I have tried to emphasize before, static links vs displays was an irrelevant issue then and now. I suppose someone could ake the position of the original Steelman and worry about the impact on implementations at a conceptual level, but in fact NO ONE took this position that I can remember. The issue was very much focused on the fact that at least two existing Ada technologies depended on displays (you should also carefully look at Randy's concerns about shared generics -- as always Randy was the one defending the shared generic approach, and there are some interesting concerns here). Tuck is certainly right that the reason that this originally disappeared was in the general mood of simplification, although some would feel that the restriction here is not a simplification but rather an instance of introducing arbitrary restrictions that make things more complex. But the failure of Bill Taylor's arguments with repsect to iterators to succeed in getting the feature in was definitely the above consideration, and as I say, you should read all the articles -- of course the articles only capture a part of the argument -- you should also read Jim's excellent minutes of the Villar's meeting where this issue was discussed and finally decided on. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-11 0:00 ` Jon S Anthony ` (2 preceding siblings ...) 1996-07-12 0:00 ` Jon S Anthony @ 1996-07-15 0:00 ` Jon S Anthony 1996-07-15 0:00 ` Robert Dewar 3 siblings, 1 reply; 133+ messages in thread From: Jon S Anthony @ 1996-07-15 0:00 UTC (permalink / raw) In article <dewar.837226494@schonberg> dewar@cs.nyu.edu (Robert Dewar) writes: > iJon said > > "As several have pointed out, this is not particularly convincing. The > best evidence indicates that this was a red-herring in this instance." > > Nope, this was not a red herring, it (the concern about backend > reimplementation) was the major focus of the argument. Remember that I agree that this was the major focus of the argument. My claim is that IMO this was an irrelevant distraction and thus a red herring. /Jon -- Jon Anthony Organon Motives, Inc. 1 Williston Road, Suite 4 Belmont, MA 02178 617.484.3383 jsa@organon.com ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-15 0:00 ` Jon S Anthony @ 1996-07-15 0:00 ` Robert Dewar 0 siblings, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-15 0:00 UTC (permalink / raw) Jon said > Nope, this was not a red herring, it (the concern about backend reimplementation) was the major focus of the argument. "I agree that this was the major focus of the argument. My claim is that IMO this was an irrelevant distraction and thus a red herring." OK, that makes very clear Jon's disagreement. If you take the position that concerns about backend reimplementation were irrelevant, then of course you will disagree with the conclusion. For a contrary view, note that Bevin has several times publically stated that the impact of Ada 95 on the backend was a major factor in DEC's decision to abandon their Ada product and not attempt to move it to Ada 95. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 ` Robert A Duff ` (11 preceding siblings ...) 1996-07-11 0:00 ` Jon S Anthony @ 1996-07-11 0:00 ` Jon S Anthony 1996-07-11 0:00 ` Robert Dewar 1996-07-12 0:00 ` Brian Rogoff ` (3 subsequent siblings) 16 siblings, 1 reply; 133+ messages in thread From: Jon S Anthony @ 1996-07-11 0:00 UTC (permalink / raw) In article <dewar.836963120@schonberg> dewar@cs.nyu.edu (Robert Dewar) writes: > Jon says > > "While the lack of direct support for recursive types across package > boundaries and lack of assertions are more important (IMO) goofs, and > while the evinced reasons for the latter one are mind numbingly > incomprehensible, this latest example would appear to take the crown > for the most stupefying goof." > > Well it is always easy for users to decide that they want everything > and don't want to worry about the required resources, but a language > design can't be quite that cavalier in balancing requirements. We had a couple private exchanges on this point. But just to be clear: I did not mean that I thought the leaving of "partial closures" out _itself_ was "stupefying", rather the purported _reasons_ for doing so are. The reasons for leaving out recursive types across packages definitely make sense, but are just not convincing (pretty much everyone agrees now on this). The ones for leaving out assertions that I've seen here (certain people getting wigged out over possible optimization effects) basically make no sense. Also, I am far from the camp that wants everything. Personally I'd flush various chunks of what eventually got accepted because they fuzz up the focus of the language and require a fair amount of resources to get right. A lot of effort spent on stuff that is on the fringes of where the language will be applied (and thus not see much actual use). The saving grace is that the user's model of Ada is orthogonal enough that they can pretty much be completely ignored. And at the end of the day, it's still, without doubt, the best of the viable options. /Jon -- Jon Anthony Organon Motives, Inc. 1 Williston Road, Suite 4 Belmont, MA 02178 617.484.3383 jsa@organon.com ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-11 0:00 ` Jon S Anthony @ 1996-07-11 0:00 ` Robert Dewar 0 siblings, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-11 0:00 UTC (permalink / raw) Jon said "The reasons for leaving out recursive types across packages definitely make sense, but are just not convincing (pretty much everyone agrees now on this). The ones for leaving out assertions that I've seen here (certain people getting wigged out over possible optimization effects) basically make no sense." OK, so you know from that thread the three separate and quite distinct possible semantics for an assert pragma. Which of these three is "obviously what is wanted" according to you? :-) Just for interest, what areas of the language would you have left out (to leave room for your favorite features!) ? ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 ` Robert A Duff ` (12 preceding siblings ...) 1996-07-11 0:00 ` Jon S Anthony @ 1996-07-12 0:00 ` Brian Rogoff 1996-07-16 0:00 ` Magnus Kempe 1996-07-14 0:00 ` Ronald Cole ` (2 subsequent siblings) 16 siblings, 1 reply; 133+ messages in thread From: Brian Rogoff @ 1996-07-12 0:00 UTC (permalink / raw) Magnus.Kempe@di.epfl.ch (Magnus Kempe) writes: ncohen@watson.ibm.com (Norman H. Cohen) writes: : : Bill Taylor's contribution was part of an ongoing discussion in the form : of comments sent to the Mapping/Revision Team during the design of Ada 9X. First of all, thanks Norman for that clear summary and the pointers. Is there a way I could have found out the location of these messages without asking you or reading all of the MRTcomments? It would be great if all of these arguments were webified and cross referenced so I could look up "closure" or something like it and find out the reasoning that went into the design of the feature. On the down side, I have a bit more sympathy for the "contra-downward-closure" position than I did before :-). I still don't have a good sense of how much faster a display based implementation might be, if at all, and I doubt that anyone will be convinced without experiments. If I remember correctly, the final decision was based on arguments about displays (Dewar arguing against a more generalized 'Access), alternatives using generics and abstract types (Barnes arguing de facto against a more generalized 'Access), and the bad mistake made in Ada 83 (the lack of access to subprograms, as compared to C, Pascal, etc.). I think that the efficiency argument, if correct, is a valid argument not to include the feature given the goals of Ada. The argument about alternatives is rather weak, since the alternatives are so clumsy. A similar discussion has been going on in the Java community, where it appears that full (upward) closures may be added in the near future. Of course you can simulate them with objects and interfaces, but that is a rather heavyweight mechanism. This is not the only decision that was made on the basis of some implementors' fears rather than for the sake of Ada users. For instance, at some point in the revision process child units of generics were rejected; the "solution" was a compromise so that some implementors would not need to make any changes in their linking steps when updating their compiler from Ada 83 to Ada 95. The consequence is that not all non-generic hierarchies of packages can be turned into generic hierarchies (just adding "generic" doesn't work, e.g. if some child unit needs to "with" another child unit in the same hierarchy). Magnus, do you have a list of issues such as this one in which you feel that orthogonality and usability were traded for the comfort of a few implementors? I'd like to hear their arguments too of course. As Norm mentioned, most of these issues are documented in the "mrtcomments" available online. I hope the designers of Ada 0Y (oh-why) will read these discussions carefully for the next revision--if there is one--so that they can make a list of the fallacious arguments that will no doubt pop up again. Indeed. Also, I think Ada 0X is the way I'd refer to it, although I like your humorous jab :-) I also don't like knocking Ada so much, since every ignoramus with a computer seems to think that Ada is awful. Paraphrasing Stroustrup, I think Ada 95 is the best C++ there is! -- Brian ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-12 0:00 ` Brian Rogoff @ 1996-07-16 0:00 ` Magnus Kempe 0 siblings, 0 replies; 133+ messages in thread From: Magnus Kempe @ 1996-07-16 0:00 UTC (permalink / raw) rogoff@sccm.Stanford.EDU (Brian Rogoff) writes: : Magnus, do you have a list of issues such as this one in which you : feel that orthogonality and usability were traded for the comfort of a : few implementors? A list? No. For the most part, Ada 95 is great. I'll submit comments when it is time for Ada 0Y (and/or I'll experiment with the source code of GNAT :-). An interesting research project for academic people would be to add downward closure to GNAT and measure the impact on the compiler and generated code; then do the same on another compiler to compare static vs display effects. Brian, maybe you know someone who would do that? :-) Now that the source code of an Ada compiler is available, where are the academic experiments? I think some improvements that were seen as too expensive or risky this time around would have brought Ada closer to the power of functional languages. In a few years the OO movement will be followed by another one, and it will be interesting to see if Ada can gracefully adapt a second time. In the meantime, our best path is to learn how to use the full power of the language--in order to create many usable, reliable, maintainable, and profitable applications. -- Magnus Kempe "I know not what course others may take, but as Magnus.Kempe@di.epfl.ch for me, Give me Liberty... or give me Death!" http://lglwww.epfl.ch/Team/MK/ -- Patrick Henry The Ada Home is at http://lglwww.epfl.ch/Ada/ ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 ` Robert A Duff ` (13 preceding siblings ...) 1996-07-12 0:00 ` Brian Rogoff @ 1996-07-14 0:00 ` Ronald Cole 1996-07-14 0:00 ` Robert Dewar 1996-07-15 0:00 ` Jon S Anthony 1996-07-16 0:00 ` Brian Rogoff 16 siblings, 1 reply; 133+ messages in thread From: Ronald Cole @ 1996-07-14 0:00 UTC (permalink / raw) dewar@cs.nyu.edu (Robert Dewar) writes: > Ronald is still missing the point that started this thread. You are missing the point that I am solely taking exception to your categorizing gcc as a "single backend" compiler and not the point that started this thread. At a meta level, gcc may look like one; but under close scrutiny, it clearly isn't. > The other kind of technology uses a single common source base for all > backends. GCC is in this category. Yes, the configuration files differ, > but the great majority of the code is common. This is a critical feature > of GCC, and is what allows easy porting of the technology. To port to > a new architecture, a new configuration file needs to be written, but > not a new code generator. If this were true, then gcc could be made to read the md files directly. But since it can't due to some of the code generation shenanigans that go on in an md file; well, I'll let you figure it out... -- Ronald Cole E-mail: ronald@ridgecrest.ca.us President, CEO zippy@ecst.csuchico.edu Forte International Fax: (619) 384-2346 My PGP fingerprint: E9 A8 E3 68 61 88 EF 43 56 2B CE 3E E9 8F 3F 2B ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-14 0:00 ` Ronald Cole @ 1996-07-14 0:00 ` Robert Dewar 0 siblings, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-14 0:00 UTC (permalink / raw) "If this were true, then gcc could be made to read the md files directly. But since it can't due to some of the code generation shenanigans that go on in an md file; well, I'll let you figure it out..." Again, you miss the point (you seem pretty determined to do so). The point is that there is a very important qualitative difference, in terms of the impact of language changes on the backend, between the effect on a technology like GCC, and a technology where the code generators are substantial separate programs for each back end. Since I know you know the GCC technology it is hard for me to believe that you disagree with this! That is the one and only important point that is relevant to the start of this thread (which was talking about the effect of definitions of access-to-subporgram semantics on backend technologies). ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 ` Robert A Duff ` (14 preceding siblings ...) 1996-07-14 0:00 ` Ronald Cole @ 1996-07-15 0:00 ` Jon S Anthony 1996-07-15 0:00 ` Robert Dewar 1996-07-16 0:00 ` Brian Rogoff 16 siblings, 1 reply; 133+ messages in thread From: Jon S Anthony @ 1996-07-15 0:00 UTC (permalink / raw) In article <dewar.837095740@schonberg> dewar@cs.nyu.edu (Robert Dewar) writes: > Whether this concern is legitimate or not probably can't be settled without > some hard data on existing Ada programs (what you need is dynamic traces > that show how many calls are to outer level procedures, and how many >...[sort of data needed] > can factor out optimization effects). As is clear from the thread, Jon > and I simply disagree on the bottom line here, but I don't think any > more arguments without data can illuminate this discussion further (it > is by the way a *very* old discussion). At the risk of starting another branch in this goofy thread, you are quite correct here in that to some extent this aspect of the discussion has been a case of "arguing in a vacuum. I suppose at this point Jay Martin would start blow torching academics for this, but it is curious that this sort of thing is not given much attention despite the fact that it does have real world impact and would appear to be very important. /Jon -- Jon Anthony Organon Motives, Inc. 1 Williston Road, Suite 4 Belmont, MA 02178 617.484.3383 jsa@organon.com ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-15 0:00 ` Jon S Anthony @ 1996-07-15 0:00 ` Robert Dewar 0 siblings, 0 replies; 133+ messages in thread From: Robert Dewar @ 1996-07-15 0:00 UTC (permalink / raw) Jon said "At the risk of starting another branch in this goofy thread, you are quite correct here in that to some extent this aspect of the discussion has been a case of "arguing in a vacuum. I suppose at this point Jay Martin would start blow torching academics for this, but it is curious that this sort of thing is not given much attention despite the fact that it does have real world impact and would appear to be very important." Actually this data DOES exist, but it tends to be proprietary. For example, IBM has *extensive* PL/1 execution traces that would certainly yield this information for a large set of existing PL/1 applications. Similarly you will find that Ada companies have this kind of informatoin available, but do not necessarily share it. I would not blow torch academics here. The trouble is that to get this information, you need widespread acccess to large real-world applications. Such access is usually only available to large companies, and not to universities, and measuremens on small non-typical programs may be worse than useless. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 ` Robert A Duff ` (15 preceding siblings ...) 1996-07-15 0:00 ` Jon S Anthony @ 1996-07-16 0:00 ` Brian Rogoff 16 siblings, 0 replies; 133+ messages in thread From: Brian Rogoff @ 1996-07-16 0:00 UTC (permalink / raw) Magnus.Kempe@di.epfl.ch (Magnus Kempe) writes: rogoff@sccm.Stanford.EDU (Brian Rogoff) writes: : Magnus, do you have a list of issues such as this one in which you : feel that orthogonality and usability were traded for the comfort of a : few implementors? A list? No. For the most part, Ada 95 is great. I'll submit comments when it is time for Ada 0Y (and/or I'll experiment with the source code of GNAT :-). I agree that Ada 95 is great for the most part, which is why I read this newsgroup. However, it is not as good as it could be, for a number of important reasons, some of which are more "economic" than technical, like backwards compatibility. Now, backwards compatibility is very important, so I wouldn't suggest just starting from scratch. However, at some point in Ada's evolution there will have to be an incompatible shift, as that "ratchet effect" that Robert Dewar mentioned will just keep making the language larger. An interesting research project for academic people would be to add downward closure to GNAT and measure the impact on the compiler and generated code; then do the same on another compiler to compare static vs display effects. Brian, maybe you know someone who would do that? :-) Now that the source code of an Ada compiler is available, where are the academic experiments? I'm temporarily out of academia, though I use the account :-). But your question gets to the heart of one part of the discussion. Are displays faster? If so, by how much? On what types of programs? On the other hand, if there were a compiler which supported downward closures, how much would they be used? How often are they used in languages that support them, like Pascal? Lots of questions like this have to be considered, and I don't envy the designers! I went from being a strong supporter of downward closures to being not so sure after I followed Norman's paper trail. The arguments about complicating a shared implementation for generics worried me, though I haven't thought through it carefully enough (I am not a compiler writer) I do appreciate arguments about implementability. From where I was sitting, Stanford, Ada has a long way to go. The languages used in the CS curricula are for the most part (1) C and C++ (by far the most popular) (2) ML among the theoretical CS types (3) Fortran and MATLAB among numerical analysts unlike me and engineers and now Java seems to be gaining popularity. GNAT is nowhere to be seen. How are things in Lausanne? Much better I take it :-). However, this is not a reason for despair. The academic research will come when the language is more widely accepted in industry. Just look at all of the academic work on C++, and now Java. I think it is good that Windows is slowly becoming the primary GNAT environment, as this will hasten that acceptance. I think some improvements that were seen as too expensive or risky this time around would have brought Ada closer to the power of functional languages. In a few years the OO movement will be followed by another one, and it will be interesting to see if Ada can gracefully adapt a second time. It also remains to be seen whether the problems solved by the powerful features are that important. In his excellent paper "Hints for Computer System Design", Butler Lampson says a lot about this, and recommends simple, fast operations are usually "the right thing". So what do you think will follow OO? Functional Constraint Logic Programming? :-) In the meantime, our best path is to learn how to use the full power of the language--in order to create many usable, reliable, maintainable, and profitable applications. Yes! -- Brian ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 tmoran 1996-07-02 0:00 ` Robert A Duff @ 1996-07-24 0:00 ` Jon S Anthony 1996-07-25 0:00 ` Jon S Anthony 1996-07-25 0:00 ` Fergus Henderson 3 siblings, 0 replies; 133+ messages in thread From: Jon S Anthony @ 1996-07-24 0:00 UTC (permalink / raw) In article <Dv0LHw.Jq6@world.std.com> bobduff@world.std.com (Robert A Duff) writes: > In article <ROGOFF.96Jul23093858@sccm.Stanford.EDU>, > Brian Rogoff <rogoff@sccm.stanford.edu> wrote: > >Hi Bob, > > Hi Brian, > > > While this is now straying a bit from Ada 95, > > Indeed. I hope people don't get too annoyed at us for discussing > general language design stuff. I hope not. This is good stuff. There aren't many places on the net where you can find this sort of discussion. > >.. I'm curious as to > >whether you find Pascal style iterators using downward funargs (there, I'm > >using Lisp terminology) superior to CLU/Sather-1.0 style iterators. > > No. When I was a Pascal programmer many years ago, I used > procedures-as-params a lot for iterators. But CLU iterators are clearly > superior. I don't know Sather, but from what I've read, they seem even > more superior. Sather iterators (IMO) are pretty clearly about as kewl as iterators get. They are _extremely_ flexible and can be combined in arbitrary ways (basically allowing you to "snap together" new iterators from the ones you have in your bag - the ones provided in the class definitions). I'd also recommend the Sather Iterator Technical Report paper on the Sather home page: http://http.icsi.berkeley.edu/Sather/ > >how do the Ada 95 alternatives stack up? > > Not very well, I'm afraid. You can use generics, but you end up with a > lot of verbose junk for some simple things. Sigh. Agreed. They are more or less "good enough"... > P.S. I was away for more than a week, so I may have missed some answers > to my question about full closures. Did anybody answer that? I don't recall even seeing it. I've been noticing lately that several posts from various people (including myself) have not "got out"... /Jon -- Jon Anthony Organon Motives, Inc. 1 Williston Road, Suite 4 Belmont, MA 02178 617.484.3383 jsa@organon.com ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 tmoran 1996-07-02 0:00 ` Robert A Duff 1996-07-24 0:00 ` Jon S Anthony @ 1996-07-25 0:00 ` Jon S Anthony 1996-07-25 0:00 ` Fergus Henderson 3 siblings, 0 replies; 133+ messages in thread From: Jon S Anthony @ 1996-07-25 0:00 UTC (permalink / raw) In article <Dv0LHw.Jq6@world.std.com> bobduff@world.std.com (Robert A Duff) writes: > In article <ROGOFF.96Jul23093858@sccm.Stanford.EDU>, > Brian Rogoff <rogoff@sccm.stanford.edu> wrote: > >Hi Bob, > > Hi Brian, > > > While this is now straying a bit from Ada 95, > > Indeed. I hope people don't get too annoyed at us for discussing > general language design stuff. I hope not. This is good stuff. There aren't many places on the net where you can find this sort of discussion. > >.. I'm curious as to > >whether you find Pascal style iterators using downward funargs (there, I'm > >using Lisp terminology) superior to CLU/Sather-1.0 style iterators. > > No. When I was a Pascal programmer many years ago, I used > procedures-as-params a lot for iterators. But CLU iterators are clearly > superior. I don't know Sather, but from what I've read, they seem even > more superior. Sather iterators (IMO) are pretty clearly about as kewl as iterators get. They are _extremely_ flexible and can be combined in arbitrary ways (basically allowing you to "snap together" new iterators from the ones you have in your bag - the ones provided in the class definitions). I'd also recommend the Sather Iterator Technical Report paper on the Sather home page: http://http.icsi.berkeley.edu/Sather/ > >how do the Ada 95 alternatives stack up? > > Not very well, I'm afraid. You can use generics, but you end up with a > lot of verbose junk for some simple things. Sigh. Agreed. They are more or less "good enough"... > P.S. I was away for more than a week, so I may have missed some answers > to my question about full closures. Did anybody answer that? I don't recall even seeing it. I've been noticing lately that several posts from various people (including myself) have not "got out"... /Jon -- Jon Anthony Organon Motives, Inc. 1 Williston Road, Suite 4 Belmont, MA 02178 617.484.3383 jsa@organon.com ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-02 0:00 tmoran ` (2 preceding siblings ...) 1996-07-25 0:00 ` Jon S Anthony @ 1996-07-25 0:00 ` Fergus Henderson 1996-07-25 0:00 ` David Kristola 1996-07-26 0:00 ` Robert A Duff 3 siblings, 2 replies; 133+ messages in thread From: Fergus Henderson @ 1996-07-25 0:00 UTC (permalink / raw) rogoff@sccm.Stanford.EDU (Brian Rogoff) writes: >It was one of the refs in Norman Cohen's precis of the discussion, from >Randy Brukardt at RR Software. Here is the relevant excerpt: > >--------------------------------------------------------------------------- >To put the problem in a nutshell: > >If 'Access is allowed in generic bodies, generic code sharing requires >distributed overhead. (Or compilers have to do body analysis of generics >in order to prevent sharing on them). Having implemented shared generic handling for Mercury, without any distributed overhead as far as I am aware, I'm keen to understand in detail how this problem arises in Ada. >To explain this in detail, I'd have to give a crash course on the construction >of shared generics. However, here is a simplified version of the problem: >A shared generic passes in some way a pointer to a data area identifying the >generic, and containing its local objects. [Note that this exists in any but >the most simplified versions of sharing - any sharing algorithm which allows >data in the generic specification or body would have the problem]. >However, an access-to-subprogram does not know that the routine comes from >a generic, or even which generic. The solution to this problem in the >specification is to construct a 'wrapper' routine at instantiation time, >which knows about the appropriate generic instantiation. I think I follow you so far... >However, a wrapper cannot be built for 'Accesses in the generic body >inside the generic body. Can you explain in a bit more detail when this would be necessary, and why it is not possible? -- Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit" PGP: finger fjh@128.250.37.3 | -- the last words of T. S. Garp. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-25 0:00 ` Fergus Henderson @ 1996-07-25 0:00 ` David Kristola 1996-07-26 0:00 ` Robert A Duff 1996-07-26 0:00 ` Robert A Duff 1 sibling, 1 reply; 133+ messages in thread From: David Kristola @ 1996-07-25 0:00 UTC (permalink / raw) In article cbo@mulga.cs.mu.OZ.AU, fjh@mundook.cs.mu.OZ.AU (Fergus Henderson) writes: >rogoff@sccm.Stanford.EDU (Brian Rogoff) writes: [snip] (I apologize if i am attributing these words to the wrong person, i was not able to locate the original post). >>If 'Access is allowed in generic bodies, generic code sharing requires >>distributed overhead. (Or compilers have to do body analysis of generics >>in order to prevent sharing on them). Maybe i am misunderstanding the meaning of "distributed overhead", but don't all shared generics have some? But anyway... [snip] >>To explain this in detail, I'd have to give a crash course on the construction >>of shared generics. However, here is a simplified version of the problem: >>A shared generic passes in some way a pointer to a data area identifying the >>generic, and containing its local objects. [Note that this exists in any but >>the most simplified versions of sharing - any sharing algorithm which allows >>data in the generic specification or body would have the problem]. >>However, an access-to-subprogram does not know that the routine comes from >>a generic, or even which generic. The solution to this problem in the >>specification is to construct a 'wrapper' routine at instantiation time, >>which knows about the appropriate generic instantiation. > >I think I follow you so far... This is how i understand generics with shared code to work. >>However, a wrapper cannot be built for 'Accesses in the generic body >>inside the generic body. > >Can you explain in a bit more detail when this would be necessary, >and why it is not possible? Maybe a code example here would help (let me know if i have missed the mark): generic ... package Pkg is procedure P; end Pkg; with ... package body Pkg is function F(...) return ... is ... begin ... end F; procedure P is ... begin ... Call_Something(F'Access); ... end P; end Pkg; Since F might depend on the generic parameters to Pkg, F'Access would need to point to a wrapper for F, which is not known inside Pkg at compile time (there may be no instantiations, and therefore no wrappers created). I do not know if F would have it's own wrapper anyway, because it is not visible in the spec of Pkg, and therefore not externally callable. BUT, why not have a wrapper for F, and, include in the instantiation data, the addresses of the wrapper routines (F in this case), so that P could reference the instantiated data passed to it to get the address to resolve F'Access? There is a bit of indirection here, but then that is an everyday part of shared generics. I hope my mostly Ada 83 view of the world has not blinded me to something in Ada that makes this approach fail (or some general blindness to a common feature that i have overlooked). And before i start a flame war, this is just a comment on how such a thing could be done, please do not point out the RM sections that forbid it (that is not the point). >-- >Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit >WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit" >PGP: finger fjh@128.250.37.3 | -- the last words of T. S. Garp. david kristola "maybe i would not see the solution so clearly if i could see all of the problem" Work: davidk@os1.ese.lmsc.lockheed.com Play: DJKristola@aol.com My suggestion for Lockheed Martin's next slogan: "Lockheed Martin, we make things that go BOOM!" ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-25 0:00 ` David Kristola @ 1996-07-26 0:00 ` Robert A Duff 1996-07-30 0:00 ` Thomas Wolff 1996-07-30 0:00 ` David Kristola 0 siblings, 2 replies; 133+ messages in thread From: Robert A Duff @ 1996-07-26 0:00 UTC (permalink / raw) In article <4t8rfo$g71@butch.lmsc.lockheed.com>, David Kristola <davidk@OS2.ifs> wrote: >Maybe i am misunderstanding the meaning of "distributed overhead", but don't >all shared generics have some? But anyway... I think you're misunderstanding "distrib overhead". "Feature X causes distributed overhead" means that your program will have some overhead, caused by the mere existence of feature X in the language, even if you don't use feature X. If feature X is slow, that's just plain old overhead, not "distributed overhead". An example from another thread: tasking causes distributed overhead, because when generating code for a subprogram containing a package-body-subunit, you have to *assume* that the package body will contain a task, and generate some extra task-waiting code in the subunit. So the poor programmer who wants to use subunits, but never used a task in his life is paying some cost for the mere existence of tasking. This is distributed overhead. Of course, this assumes a certain implementation model -- namely that code is generated for the parent subprogram at compile time, when the subunits might not exist yet. It also assumes the user doesn't have a feature saying "I promise not to use tasking." Another example: Text_IO keeps track of line and column numbers, which is an overhead you pay even if you are just sending characters to stdout, and don't care about line and column numbers. (Assuming a straightforward implementation of Text_IO.) Arguments about distributed overhead generally need to have some implementation model in mind (which usually assumes, for example, that fancy optimizations are not done at link time). The case in *this* thread assumes an always-shared generic implementation. Always sharing generics has a *lot* of overhead, but I don't think it has much *distributed* overhead. We're also assuming that you're not allowed to generate code at run time. Distributed overhead is evil. Overhead is not evil, necessarily, because the programmer can choose whether to use the feature (and incur the overhead). Almost any feature causes *some* distributed overhead. The goal is to make it close enough to zero that nobody cares. >generic > ... >package Pkg is > procedure P; >end Pkg; > >with ... >package body Pkg is > function F(...) return ... is > ... > begin > ... > end F; > > procedure P is > ... > begin > ... > Call_Something(F'Access); > ... > end P; >end Pkg; > >Since F might depend on the generic parameters to Pkg, Yes, or perhaps a variable declared in the package body. >... F'Access would need to >point to a wrapper for F, which is not known inside Pkg at compile time (there >may be no instantiations, and therefore no wrappers created). I do not know if >F would have it's own wrapper anyway, because it is not visible in the spec of >Pkg, and therefore not externally callable. Suppose Call_Something were *outside* the generic, and saved F'Access in a global variable. This is illegal, but we're arging about "what if this were legal?" >BUT, why not have a wrapper for F, and, include in the instantiation data, the >addresses of the wrapper routines (F in this case), so that P could reference the >instantiated data passed to it to get the address to resolve F'Access? There is >a bit of indirection here, but then that is an everyday part of shared generics. Because when you compile F, you don't know about the instantiations. And when you compile the instantiations, you don't know about F, because F is declared in the generic *body*. Sure, you could have the compiler take a peek at the generic body, but as Randy pointed out, that defeats the purpose of the always-share model (i.e. to be able to generate code without seeing the body). So this doesn't work. Therefore you have to *always* have this extra generic related info, even if you're not using generics. Hence, distributed overhead. Hence, Ada 9X outlawed the feature. Note that the workaround isn't so bad: declare F in the private part, and then it's legal (and then the compiler knows about it at instantiation time, and can generate the wrapper at that time). - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-26 0:00 ` Robert A Duff @ 1996-07-30 0:00 ` Thomas Wolff 1996-07-30 0:00 ` Robert A Duff 1996-07-30 0:00 ` David Kristola 1 sibling, 1 reply; 133+ messages in thread From: Thomas Wolff @ 1996-07-30 0:00 UTC (permalink / raw) bobduff@world.std.com (Robert A Duff) writes: : In article <4t8rfo$g71@butch.lmsc.lockheed.com>, : David Kristola <davidk@OS2.ifs> wrote: : >Maybe i am misunderstanding the meaning of "distributed overhead", but don't : >all shared generics have some? But anyway... : I think you're misunderstanding "distrib overhead". "Feature X causes : distributed overhead" means that your program will have some overhead, : caused by the mere existence of feature X in the language, even if you : don't use feature X. If feature X is slow, that's just plain old : overhead, not "distributed overhead". Regarding the popularity of distributed systems, the terminology is confusing. Was it invented in this thread or is it common elsewhere? Perhaps something like "propagated overhead" should rather be used. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-30 0:00 ` Thomas Wolff @ 1996-07-30 0:00 ` Robert A Duff 0 siblings, 0 replies; 133+ messages in thread From: Robert A Duff @ 1996-07-30 0:00 UTC (permalink / raw) In article <4tldre$lco@fu-berlin.de>, Thomas Wolff <wolff@inf.fu-berlin.de> wrote: >Regarding the popularity of distributed systems, the terminology is >confusing. Was it invented in this thread or is it common elsewhere? I don't know where the term comes from, but it certainly existed before this thread. It was commonly used, for example, during the Ada 9X design. An accusation of "proposed feature X has distributed overhead" happened many times, and was taken quite seriously. I suspect the term is much older than that. >Perhaps something like "propagated overhead" should rather be used. Shrug. It seems to me that one should be able to tell from context whether you're talking about "distributed overhead" (i.e. overhead distributed across unused features of the language) or "distributed systems" (i.e. programs consisting of partitions distributed across a network of computers). - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-26 0:00 ` Robert A Duff 1996-07-30 0:00 ` Thomas Wolff @ 1996-07-30 0:00 ` David Kristola 1 sibling, 0 replies; 133+ messages in thread From: David Kristola @ 1996-07-30 0:00 UTC (permalink / raw) In article B9F@world.std.com, bobduff@world.std.com (Robert A Duff) writes: >In article <4t8rfo$g71@butch.lmsc.lockheed.com>, >David Kristola <davidk@OS2.ifs> wrote: >>Maybe i am misunderstanding the meaning of "distributed overhead", but don't >>all shared generics have some? But anyway... > >I think you're misunderstanding "distrib overhead". "Feature X causes >distributed overhead" means that your program will have some overhead, >caused by the mere existence of feature X in the language, even if you >don't use feature X. If feature X is slow, that's just plain old >overhead, not "distributed overhead". Yes, i was confused. Thank you. [snip] >Distributed overhead is evil. [snip] >Suppose Call_Something were *outside* the generic, and saved F'Access in >a global variable. This is illegal, but we're arging about "what if >this were legal?" I should have used dot notation to indicate that Call_Something was outside the generic. I also should have used an access-to-subprogram type. I suppose there are still problems, considering that the generic instance could be temporary. Maybe by placing a pointer in the generic data block (actually, in every generic data block) and allocating (on the heap) generic body specific data during elaboration of the generic instance body (but deallocating is now a problem), and filling in the pointer to point to the additional information during the instance body elaboration.... I guess this is all a moot point (i hope i am using "moot" correctly, i skipped the big discussion on that topic :-). [snip] >Note that the workaround isn't so bad: declare F in the private part, >and then it's legal (and then the compiler knows about it at >instantiation time, and can generate the wrapper at that time). Now if i only had a job where i could use Ada95, i could use this ;). >- Bob david kristola Work: davidk@os1.ese.lmsc.lockheed.com Play: DJKristola@aol.com My suggestion for Lockheed Martin's next slogan: "Lockheed Martin, we make things that go BOOM!" ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-25 0:00 ` Fergus Henderson 1996-07-25 0:00 ` David Kristola @ 1996-07-26 0:00 ` Robert A Duff 1996-07-26 0:00 ` Fergus Henderson 1 sibling, 1 reply; 133+ messages in thread From: Robert A Duff @ 1996-07-26 0:00 UTC (permalink / raw) In article <4t7dvt$cbo@mulga.cs.mu.OZ.AU>, Fergus Henderson <fjh@mundook.cs.mu.OZ.AU> wrote: >>However, a wrapper cannot be built for 'Accesses in the generic body >>inside the generic body. > >Can you explain in a bit more detail when this would be necessary, >and why it is not possible? It would be necessary when you say P'Access inside a generic body, and P is in that body (and not declared in the spec), and you then let the pointer escape outside the generic. This is illegal in Ada 95. I believe we're talking about full generic sharing here. Most implemtnations of sharing share *sometimes* and not other times, depending on what sort of generic it is, and what the formals are. But here, we *always* share. Well, when you call through the pointer, the called subprogram needs a pointer to the generic data -- an area of memory where variables declared in the generic package body live. There's one such are per instance. But since you have only one copy of the generic code, that code doesn't know which instance is the current one. You could generate code to do this at run time, as gcc does, but Randy said that doesn't work on some OS's. Generating code to do it at compile time is impossible, since there's only one piece of code, but many instances. If you *always* represent access-to-subprogram values with extra data telling where the generic instance data is, then it can work, but that's distributed overhead for the case where you didn't use generics. Make sense? I know nothing of Mercury, in particular how its version of generics relates to Ada's. Could you outline how you did it, and why you say it has no distributed overhead? - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-26 0:00 ` Robert A Duff @ 1996-07-26 0:00 ` Fergus Henderson 1996-07-28 0:00 ` Robert A Duff 0 siblings, 1 reply; 133+ messages in thread From: Fergus Henderson @ 1996-07-26 0:00 UTC (permalink / raw) bobduff@world.std.com (Robert A Duff) writes: >If you *always* represent access-to-subprogram values with extra data >telling where the generic instance data is, then it can work, but that's >distributed overhead for the case where you didn't use generics. > >Make sense? After much thought -- nope, I'm still confused ;-) Mercury's shared-generics implementation doesn't have any distributed overhead when compared to "Mercury minus generics". I don't think it has any distributed overhead when compared to Pascal either (i.e. I think Pascal could be extended with Mercury-style generics without imposing any distributed overhead.) But there is distributed overhead compared to C, if you're not willing to adopt the GNU C trampoline approach or something along those lines. I'm still confused about whether there is distributed overhead compared to Ada. You can't represent higher-order types (Mercury's equivalent to access-to-subprogram types) using a single code address, you need a data address as well -- presuming you don't use trampolines. But I thought Ada already imposed that requirement, since you can take the address of nested procedures in Ada? (can't you?) The way the Mercury implementation handles taking the address of a generic instance in a shared generic is to package up the generic instance data in basically the same way that the stack frame data in an enclosing procedure is packed up when you take the address of a nested procedure. So as long as you are already committed to being able to take the address of nested procedures, there is no distributed overhead -- I think. -- Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit" PGP: finger fjh@128.250.37.3 | -- the last words of T. S. Garp. ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-26 0:00 ` Fergus Henderson @ 1996-07-28 0:00 ` Robert A Duff 1996-07-28 0:00 ` Fergus Henderson 0 siblings, 1 reply; 133+ messages in thread From: Robert A Duff @ 1996-07-28 0:00 UTC (permalink / raw) In article <4tb4ii$5fc@mulga.cs.mu.OZ.AU>, Fergus Henderson <fjh@mundook.cs.mu.OZ.AU> wrote: >You can't represent higher-order types (Mercury's equivalent to >access-to-subprogram types) using a single code address, you >need a data address as well -- presuming you don't use trampolines. >But I thought Ada already imposed that requirement, since you can >take the address of nested procedures in Ada? (can't you?) Ada's access-to-subprogram types are rather severely restricted. Yes, you can make a pointer-to-nested-proc, but that pointer can't survive longer than the immediately enclosing procedure. Define "level of X" to mean "the number of procedures statically enclosing X", so a procedure in a library package is "level 0", a procedure in that is "level 1", and so on. You also need to count block statements and tasks as levels, but not packages. Now, an access type at level N can have values pointing at procedures of levels less than or equal to N, but not greater. In particular, a level-0 access type can only be used to point to level-0 procedures. Various rules ensure the above property. The special rule for generics ensures that the above property holds without requiring the compiler to see the generic body when compiling an instantiation. For a static-link implementation, a level-0 access-to-proc type can be implemented as a single address (of the procedure's code). This is important, for interfacing to C. (E.g. passing call-back procedures to X windows.) A level-1 access-to-proc can also be implemented as a single address, since there is only one possibility for the static link, assuming the run-time model allows level-0 procedures to sometimes get a static link which they then ignore. Level-2 and deeper access types need the pair of pointers you talked about. A display implementation can always implement access-to-subp as a single address, at all levels. Does this help? >The way the Mercury implementation handles taking the address of a >generic instance in a shared generic is to package up the generic >instance data in basically the same way that the stack frame data in an >enclosing procedure is packed up when you take the address of a nested >procedure. So as long as you are already committed to being able to >take the address of nested procedures, there is no distributed >overhead -- I think. Yes, this makes sense, I think, but doesn't it imply that level-0 access-to-proc types have a static link attached? That would constitute a distributed overhead, would it not, given the stuff I said above? And make the interface to C more painful? - Bob ^ permalink raw reply [flat|nested] 133+ messages in thread
* Re: Q: access to subprogram 1996-07-28 0:00 ` Robert A Duff @ 1996-07-28 0:00 ` Fergus Henderson 0 siblings, 0 replies; 133+ messages in thread From: Fergus Henderson @ 1996-07-28 0:00 UTC (permalink / raw) bobduff@world.std.com (Robert A Duff) writes: >Ada's access-to-subprogram types are rather severely restricted. Yes, >you can make a pointer-to-nested-proc, but that pointer can't survive >longer than the immediately enclosing procedure. [...] >For a static-link implementation, a level-0 access-to-proc type can be >implemented as a single address (of the procedure's code). [...] >A display implementation can always implement access-to-subp as a single >address, at all levels. > >Does this help? Yes, thanks. I think I understand things now. >Fergus Henderson <fjh@mundook.cs.mu.OZ.AU> wrote: >>The way the Mercury implementation handles taking the address of a >>generic instance in a shared generic is to package up the generic >>instance data in basically the same way that the stack frame data in an >>enclosing procedure is packed up when you take the address of a nested >>procedure. So as long as you are already committed to being able to >>take the address of nested procedures, there is no distributed >>overhead -- I think. > >Yes, this makes sense, I think, but doesn't it imply that level-0 >access-to-proc types have a static link attached? That would constitute >a distributed overhead, would it not, given the stuff I said above? And >make the interface to C more painful? Yes, you're correct in all of the above. -- Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit" PGP: finger fjh@128.250.37.3 | -- the last words of T. S. Garp. ^ permalink raw reply [flat|nested] 133+ messages in thread
end of thread, other threads:[~1996-07-30 0:00 UTC | newest] Thread overview: 133+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 1996-07-15 0:00 Q: access to subprogram tmoran 1996-07-15 0:00 ` Robert Dewar -- strict thread matches above, loose matches on Subject: below -- 1996-07-05 0:00 tmoran 1996-07-06 0:00 ` Robert A Duff 1996-07-02 0:00 tmoran 1996-07-02 0:00 ` Robert A Duff 1996-07-02 0:00 ` Robert Dewar 1996-07-03 0:00 ` Jon S Anthony 1996-07-03 0:00 ` Robert Dewar 1996-07-03 0:00 ` Mark A Biggar 1996-07-03 0:00 ` Robert Dewar 1996-07-06 0:00 ` Robert A Duff 1996-07-08 0:00 ` Norman H. Cohen 1996-07-08 0:00 ` Robert Dewar 1996-07-11 0:00 ` Robert A Duff 1996-07-12 0:00 ` Robert A Duff 1996-07-14 0:00 ` Norman H. Cohen 1996-07-03 0:00 ` Robert A Duff 1996-07-03 0:00 ` Robert Dewar 1996-07-09 0:00 ` Thomas Wolff 1996-07-09 0:00 ` Robert Dewar 1996-07-10 0:00 ` Robert A Duff 1996-07-10 0:00 ` Richard A. O'Keefe 1996-07-10 0:00 ` Robert Dewar 1996-07-10 0:00 ` Robert A Duff 1996-07-10 0:00 ` Thomas Wolff 1996-07-10 0:00 ` Robert Dewar 1996-07-10 0:00 ` Robert A Duff 1996-07-03 0:00 ` Robert A Duff 1996-07-08 0:00 ` Norman H. Cohen 1996-07-09 0:00 ` Robert A Duff 1996-07-19 0:00 ` Brian Rogoff 1996-07-22 0:00 ` Richard A. O'Keefe 1996-07-23 0:00 ` Brian Rogoff 1996-07-23 0:00 ` Robert A Duff 1996-07-26 0:00 ` Brian Rogoff 1996-07-28 0:00 ` Robert A Duff 1996-07-22 0:00 ` Brian Rogoff 1996-07-23 0:00 ` Robert A Duff 1996-07-24 0:00 ` Brian Rogoff 1996-07-26 0:00 ` Robert A Duff 1996-07-30 0:00 ` Brian Rogoff 1996-07-24 0:00 ` Richard A. O'Keefe 1996-07-26 0:00 ` Ken Garlington 1996-07-30 0:00 ` Richard A. O'Keefe 1996-07-24 0:00 ` Brian Rogoff 1996-07-26 0:00 ` Richard A. O'Keefe 1996-07-28 0:00 ` Robert A Duff 1996-07-29 0:00 ` Richard A. O'Keefe 1996-07-29 0:00 ` Robert A Duff 1996-07-28 0:00 ` Fergus Henderson 1996-07-29 0:00 ` Richard A. O'Keefe 1996-07-30 0:00 ` Jon S Anthony 1996-07-03 0:00 ` Fergus Henderson 1996-07-03 0:00 ` Robert A Duff 1996-07-03 0:00 ` Robert Dewar 1996-07-03 0:00 ` Adam Beneschan 1996-07-03 0:00 ` Robert Dewar 1996-07-03 0:00 ` Robert A Duff 1996-07-09 0:00 ` Thomas Wolff 1996-07-05 0:00 ` Jon S Anthony 1996-07-06 0:00 ` Robert Dewar 1996-07-06 0:00 ` Robert A Duff 1996-07-06 0:00 ` Robert Dewar 1996-07-08 0:00 ` Robert A Duff 1996-07-08 0:00 ` Richard A. O'Keefe 1996-07-08 0:00 ` Robert Dewar 1996-07-10 0:00 ` Richard A. O'Keefe 1996-07-10 0:00 ` Robert Dewar 1996-07-19 0:00 ` Richard A. O'Keefe 1996-07-08 0:00 ` Robert A Duff 1996-07-08 0:00 ` Robert Dewar 1996-07-07 0:00 ` Mark Eichin 1996-07-08 0:00 ` Richard Kenner 1996-07-07 0:00 ` Ronald Cole 1996-07-07 0:00 ` Richard Kenner 1996-07-07 0:00 ` Robert Dewar 1996-07-07 0:00 ` Richard Kenner 1996-07-07 0:00 ` Robert Dewar 1996-07-14 0:00 ` Ronald Cole 1996-07-14 0:00 ` Richard Kenner 1996-07-15 0:00 ` Fergus Henderson 1996-07-15 0:00 ` Robert Dewar 1996-07-17 0:00 ` Fergus Henderson 1996-07-17 0:00 ` Richard Kenner 1996-07-17 0:00 ` Adam Beneschan 1996-07-20 0:00 ` Michael Feldman 1996-07-20 0:00 ` Robert Dewar 1996-07-16 0:00 ` Richard Kenner 1996-07-08 0:00 ` Brian Rogoff 1996-07-11 0:00 ` Norman H. Cohen 1996-07-11 0:00 ` Magnus Kempe 1996-07-11 0:00 ` Robert Dewar 1996-07-09 0:00 ` Jon S Anthony 1996-07-09 0:00 ` Robert Dewar 1996-07-09 0:00 ` Robert Dewar 1996-07-09 0:00 ` Jon S Anthony 1996-07-09 0:00 ` Robert Dewar 1996-07-10 0:00 ` Ronald Cole 1996-07-11 0:00 ` Robert Dewar 1996-07-11 0:00 ` Richard Kenner 1996-07-11 0:00 ` Jon S Anthony 1996-07-11 0:00 ` Jon S Anthony 1996-07-11 0:00 ` Tucker Taft 1996-07-17 0:00 ` Brian Rogoff 1996-07-11 0:00 ` Robert Dewar 1996-07-15 0:00 ` Mark A Biggar 1996-07-15 0:00 ` Robert Dewar 1996-07-12 0:00 ` Jon S Anthony 1996-07-12 0:00 ` Robert Dewar 1996-07-15 0:00 ` Jon S Anthony 1996-07-15 0:00 ` Robert Dewar 1996-07-11 0:00 ` Jon S Anthony 1996-07-11 0:00 ` Robert Dewar 1996-07-12 0:00 ` Brian Rogoff 1996-07-16 0:00 ` Magnus Kempe 1996-07-14 0:00 ` Ronald Cole 1996-07-14 0:00 ` Robert Dewar 1996-07-15 0:00 ` Jon S Anthony 1996-07-15 0:00 ` Robert Dewar 1996-07-16 0:00 ` Brian Rogoff 1996-07-24 0:00 ` Jon S Anthony 1996-07-25 0:00 ` Jon S Anthony 1996-07-25 0:00 ` Fergus Henderson 1996-07-25 0:00 ` David Kristola 1996-07-26 0:00 ` Robert A Duff 1996-07-30 0:00 ` Thomas Wolff 1996-07-30 0:00 ` Robert A Duff 1996-07-30 0:00 ` David Kristola 1996-07-26 0:00 ` Robert A Duff 1996-07-26 0:00 ` Fergus Henderson 1996-07-28 0:00 ` Robert A Duff 1996-07-28 0:00 ` Fergus Henderson
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox