!standard 03.10 (11) 02-01-23 AI95-00254/02 !class amendment 00-12-06 !status work item 01-08-29 !status received 00-12-06 !priority Low !difficulty Hard !subject Downward closures for access to subprogram types !summary Access-to-subprogram parameters are introduced which enable an access to a subprogram at any level to be passed as actual parameter. !problem Despite the improvements introduced in Ada 95, there is no still no convenient way to perform certain general operations such as integration, minimization, iteration etc where the operation has to be parameterized by a subprogram. This functionality was provided in Algol 60 and Pascal and it is surprising that it is not in Ada. !proposal Access-to-subprogram parameters are introduced as a further form of subprogram parameter. The changes to the syntax are as follows parameter_specification ::= defining_identifier_list: mode subtype_mark [:= default_expression] | defining_identifier_list: access_definition [:= default_expression] | defining_identifier_list: access_to_subprogram_definition [:= default_expression] The actual subprogram must be an access value designating a subprogram which is subtype conformant to the formal profile. The actual parameter must not be null. The only operations permitted on such a formal subprogram parameter are a) to call it, and b) to pass it as an actual parameter to another subprogram call. (This simple semantics avoids many implementation problems and parallels the functionality of the corresponding construction in languages such as Pascal.) Type conversions on such parameters are forbidden and since they are of anonymous type like access-to-object parameters this implies that assignment of them is forbidden. The accessibility level of such parameters is considered to be infinite and this prevents the writing of P.all'Access which could otherwise create a hidden type conversion. (These restrictions again avoid a number of potential implementation difficulties.) Accessibility checks are never required and so such parameters do not need to carry an accessibility level with them. Access-to-subprogram values may not be used as access discriminants. The option of being protected does not apply to access-to-subprogram parameters. An access to a protected operation may not be passed to such parameters. (Are we happy with this?) Default parameters are permitted for access-to-subprogram parameters with the semantics of renaming. The default must not be null. !discussion There are two basic uses for what might loosely be called pointers to subprograms. One use is as parameters to other subprograms where the parameter defines the activity to be performed; examples are routines for integration, iteration and so on. The other use is where the subprogram is provided for return communication purposes (usually known as callback); the pointer is passed to some other program which later calls back to the client by calling the subprogram whose address was handed over. The first usage was familiar in older languages such as Algol and Pascal. The second usage was provided in newer languages such as C and Modula. Ada 83 was unhelpful in both areas and workarounds had to be used. Ada 95 solved the callback problem through the introduction of general access-to- object types. However, the functional parameterization problem in its general form still remains. LSN 1083, a condensed version of which is at the end of this discussion section, outlined the problem and identified two possible solutions, namely, the introduction of limited access to subprogram types or, alternatively, access to subprogram parameters. It concluded that it would have been inappropriate to include either at the time of the design of Ada 9X largely because of implementation difficulties for display-based implementations and for those with shared generics. It should be noted that it was recognised that there were workarounds involving generics and/or the new tagged types. The example in LSN 1083 concerns iterators. An example from the field of numerical analysis is presented after this discussion. The workarounds provided in Ada 95 essentially involve polymorphism of some form - either dynamic polymorphism using tagged types or static polymorphism using generics. The workaround using tagged types is verbose and unnatural. And that involving generics lacks generality because of the static nature of generic instantiation. With hindsight, it is clear that the tagged workaround is so unnatural as to not be a workaround at all in the mind of the potential user. The generic workaround for numerical applications can lean on the excuse that standard routines should be generic anyway because of the desire to parameterize the floating type. However, such parameterization has perhaps been a lost cause because most users just use Float or Long_Float anyway. The other objection concerned implementation difficulty with display based models. However, it is now clear that, given appropriate restrictions on the details of the feature, the implementation difficulties are not so severe as once thought. As mentioned above, the ability to pass access to subprogram parameters with full scope environment intact was a standard feature of Algol 60 and widely used by numerical applications some 40 years ago. The feature was also present in Algol 68 and Pascal. It was not part of Ada 83 because it was claimed that it violated one of the Steelman requirements for predictability; the objection was that it allowed dynamic binding of procedure calls and thus it was not possible in general to predict which actual subprogram was called in certain circumstances. With hindsight this was a foolish objection because predictability for safety-critical programs is marred by many other dynamic features and in any event a particular program does not have to use the feature. The workaround provided by Ada 83 was of course the generic mechanism. If Ada claims to be a general purpose language then it ought to provide the full range of *useful* standard techniques that have evolved over the years. It is concluded (see the example) that the workarounds are not satisfactory and that Ada 0y should include the feature. LSN 1083 suggested two mechanisms: limited access-to-subprogram types and access-to-subprogram-parameters. Of these, the second is preferred because (a) it is close to the techniques in Algol 60 and Pascal, and (b) it fits in with the existing access parameters. This mechanism is thus proposed here. The example discussed below shows the access-to-subprogram profile in situ thus package Integrate is function Do_It(Fn: access function(X: Float) return Float; Lo, Hi: Float); end; If this syntax (which follows that of Pascal) is felt to be undesirably convoluted then given the introduction of "named subtypes of anonymous access types" we might recast this as package Integrate is subtype Integrand is access function(X: Float) return Float; function Do_It(Fn: Integrand; Lo, Hi: Float); end; (This problem did not arise with Algol 60 which just omitted the details of the formal profile and left the compiler to figure it out at its leisure.) It some ways it could be argued that Ada 95 made the situation seem worse. In Ada 83, one had to use generics and just put up with it. Ada 95 introduced access-to-subprogram types which work for simple situations; however, this perhaps led to the expectation that access-to-subprogram types would work for all situations. It is rather frustrating to find that it does not. This lack of natural extensibility is unfortunate. Ada 83 had just one workaround. Ada 95 has at least three different workarounds, two use generics and one uses tagged types - none is satisfactory. There now follows a somewhat condensed form of LSN 1083 which was written during the design of Ada 9X. It concluded by recommending that downward closures not be supported for three reasons: a) it is a burden for some implementations, b) workarounds exist, c) it is too big a change at this stage (Ada 9x time). Addressing these three reasons: a) the proposal given here disallows all assignment of access-to-subprogram parameters thereby greatly reducing the implementation burden, b) the workarounds are horrid and a continual embarrassment in a general purpose language , c) seemingly much bigger changes are being formulated for Ada 0y and it would not seem that much of a change to users but a relief. ============== LSN 1083 (slightly condensed extracts) 1 Background to Downward Closures: Ada's access-to-subprogram types represent assignable subprogram values. They support the ability to create data structures containing the identities of subprograms. They support callbacks, where one software component declares a subprogram and hands its identity to another software component, which can then "call back" the first software component at a later time. These types do not support downward closures, where the identity of a more nested subprogram can be passed to a less nested subprogram. Downward closures can be used, for example, to implement iterators, like this: package P is type Integer_Set is private; ... -- various operations type Integer_Action is access procedure(I: Integer); procedure Iterate(S: Integer_Set; Action: Integer_Action); -- Call Action on each member of S. end P; function Count(S: Integer_Set) return Natural is Result: Natural := 0; procedure Increment(I: Integer) is begin Result := Result + 1; end Increment; begin Iterate(S, Increment'Access); -- Illegal! return Result; end Count; Increment'Access above is illegal, because Increment is more nested than type Integer_Action. It would be bad to have to make Increment global, because that would require making the variable Result global. It is a bad idea to force the use of global variables in a language that has tasks -- in this example, Count would not be reentrant if Result were global. Note that this situation is typical of iterators and similar things -- in typical use, the action passed to an iterator will often need visibility upon a variable declared in the caller of the iterator, in order to accumulate some sort of result. The reason for the restriction is that access-to-subprogram types allow assignment. At the point where Iterate is called, we don't know if the body of Iterate is going to save the access value in a global variable. We disallow passing the nested Increment procedure because Iterate *might* save a pointer to it, and call it later, after Increment (and the variable Result) no longer exist. ... 2 Implementation Issues: In a language (like Ada) with nested subprograms, each subprogram needs some way to access its environment -- that is, the variables declared outside it. There are two common methods for representing this environment: static links, and displays. Most Ada compilers use static links, but some use displays. One key difference between the two methods is that static links have a compile-time-known size (32 bits, on a typical machine), whereas the size of a display depends on the maximum nesting depth throughout the partition. In an implementation with static links, an access-to-subprogram value is generally represented as a pair of addresses -- the address of the subprogram's code, and the static link. However, given the current Ada 9X rules, an access-to-subprogram type that is declared at library level does not need the static link -- it can be represented as just a code address. This is nice, because it is efficient, and it allows the representation to easily match C's typical representation of function pointers. Access-to-subprogram types declared one level deeper than library level can also be represented as just a code address. However, two or more levels deeper requires the static link. In an implementation with displays, given the current rules, an access-to-subprogram value can be represented as just a code address -- it is not necessary to attach a display to each access value. This also has the nice interoperability-with-C property. It has been suggested that downward closures be supported by allowing the Unchecked_Access attribute on subprograms. This is rejected because it would be unsafe and it would be uncomfortable to introduce erroneousness to a high-level feature like downward closures. It would also require every access-to-subprogram value to carry a static link or display, because the nesting level of the designated subprogram would no longer be restricted at compile time. This would break the interoperability-with-C property, and would be less efficient. 3 Possible implementations: There are two ways to support downward closures that we would recommend, if downward closures are to be supported. Both ways recognize the fact that downward closures really need a separate feature from the callback style of access-to-subprograms: - Limited access-to-subprogram types. - Access-to-subprogram parameters. Limited access types were in an earlier version of Ada 9X. Since they would be limited, assignment would be disallowed, so downward-closure-style parameter passing could be allowed, and would be safe. The compiler would implement limited access-to-subprogram types with a static link or display. Non-limited ones would retain the interoperability-with-C property. The syntax would be something like this: type Integer_Action is limited access procedure(I: Integer); -- ^^^^^^^ procedure Iterate(S: Integer_Set; Action: Integer_Action); -- Call Action on each member of S. Type conversion from limited to non-limited would be illegal. Access-to-subprogram parameters would be an extension to access parameters (not to be confused with parameters of a named access type). The syntax would be something like this: procedure Iterate(S: Integer_Set; Action: access procedure(I: Integer)); -- Call Action on each member of S. This is quite similar to the syntax used in Pascal. As for any access parameter, the access type would be anonymous. Parameter type matching would be based on the designated profile. Access parameters already use run-time accessibility checks -- this new kind would do likewise. Thus, assignment would be allowed, but the accessibility checks would prevent dangling pointers. In our iterator example, if Iterate were to try to copy Action to a global variable (during the call to Iterate from Count), then Constraint_Error would be raised, because Count.Increment is too deeply nested. The value of an access-to-subprogram parameter would need to have a static link or display. Library-level access types could retain the interoperability-with-C property. Of the two workable methods outlined above, the access-to-subprogram parameters method would be somewhat simpler in Reference Manual terms, because it would be able to piggyback on the existing access parameters feature for its rules and semantics. The implementation complexity seems equivalent. Efficiency of the limited access types method would be slightly better, because it would not be necessary to pass in information needed for the run-time accessibility checks. Limited access types would be the first elementary limited types; we would have to reword the parameter passing rules to avoid a contradictory requirement to pass by copy and by reference. (It doesn't really matter which is done, actually.) For implementations with static links, the implementation of either method is straightforward. Such implementations already need to include a static link in at least some access-to-subprogram values, and the downward-closure ones would be the same. However, for implementations with displays, either method is an implementation burden, because: - The current rules do not require carrying the display with the access-to-subprogram value, whereas the new rules would. - The size of the display is not easily known at compile time. Its size can be calculated at run time, or a maximum possible size can be known if there is a restriction on nesting depth. Either way, managing the passing of the unknown size display causes complexity. ... It should also be noted that an implementation with displays would be less efficient than one with static links, because an indirect call would require copying the entire display. It's not that big of a deal, however -- it just means copying several words of memory, and there would be no *distributed* overhead. ... 4 Conclusion We (reluctantly) recommend not supporting downward closures, because: - An implementation burden exists for display-based implementations. - Workarounds exist. - It seems like too big a change to make to the language at this late date. I say "reluctantly" recommend, because it is clear to me that the functionality is desirable, and if we were designing Ada 9X from scratch, we would support downward closures. ================ End of condensed form of LSN 1083 !example Consider the problem of integrating a function Fn of one variable X between limits Lo and Hi. The specification of a function to do this might be package Integrate is type Integrand is access function(X: Float) return Float; function Do_It(Fn: Integrand; Lo, Hi: Float) return Float; end; If the function to be integrated is a simple pure mathematical function such as Sqrt, with specification function Sqrt(X: Float) return Float; and which is declared at library level, then in order to integrate it between limits of 0 and 1, we simply write Result := Integrate.Do_It(Sqrt'Access, 0.0, 1.0); Suppose, however, that the function to be integrated is more complex such that its value is not given just by the single parameter X but that auxiliary information has to be supplied as well. Because of the need to match the type Integrand, this can only be done via variables global to the function and difficulties are then encountered. A good practical example is provided by a double integral where the function to be integrated is itself the result of an integration. Supose we wish to compute the integral of the product xy over the square region [0, 1],[0, 1]. We can pose this as the result of integrating the function G(x) between 0 and 1 where the value of G(x) is the result of integrating the function F(y) between 0 and 1 where F(y) is in fact xy and thus depends upon x as well as upon y. (The astute reader will instantly see that the answer is 1/4 and so there is no point in this silly example; such a reader can imagine a double elliptic function substituted for the humble product and allow us mere mortals to continue with our simplest of examples.) The answer is given by Result := Integrate.Do_It(G'Access, 0.0, 1.0); The essence of G is function G(X: Float) return Float is begin return Integrate.Do_It(F'Access, 0.0, 1.0); end G; where the function F is function F(Y: Float) return Float is begin return X*Y; end F; The natural way to arrange this is as follows with Integrate; procedure Main is function G(X: Float) return Float is function F(Y: Float) return Float is begin return X*Y; end F; begin return Integrate.Do_It(F'Access, 0.0, 1.0); -- illegal end G; Result: Float; begin Result := Integrate.Do_It(G'Access, 0.0, 1.0); -- illegal ... end Main; The function F is declared inside G so that it can access X. However, this is illegal in Ada 95 because we cannot apply Access to a subprogram declared at an inner level to the access type concerned (in this case the access type is Integrate.Integrand). Thus both F'Access and G'Access are illegal. We can of course move G to the top level without too much trouble thus with Integrate; function G(X: Float) return Float is function F(Y: Float) return Float is begin return X*Y; end F; begin return Integrate.Do_It(F'Access, 0.0, 1.0); -- illegal end G; with Integrate; with G; procedure Main is Result: Float; begin Result := Integrate.Do_It(G'Access, 0.0, 1.0); -- OK ... end Main; But the trouble remains with F'Access. We could of course move F to the top level as well and use a global variable to copy the value of X thus package Nasty is Variable: Float; end Nasty; with Nasty; function F(Y: Float) return Float is begin return Nasty.Variable*Y; end F; with Integrate; with F; with Nasty; function G(X: Float) return Float is begin Nasty.Variable := X; return Integrate.Do_It(F'Access, 0.0, 1.0); end G; with Integrate; with G; procedure Main is Result: Float; begin Result := Integrate.Do_It(G'Access, 0.0, 1.0); ... end Main; Apart from being nasty programming, it does not work in a multi-tasking situation. This therefore has to be rejected as a general approach. There are two almost respectable workarounds. The first uses generics. We rewrite the integrate package as a generic thus generic package Generic_Integrate is type Integrand is access function(X: Float) return Float; function Do_It(Fn: Integrand; Lo, Hi: Float) return Float; end; and then we instantiate this at the level concerned. We now go back to the original example and obtain with Integrate; procedure Main is function G(X: Float) return Float is function F(Y: Float) return Float is begin return X*Y; end F; package F_Integrate is new Generic_Integrate; begin return F_Integrate.Do_It(F'Access, 0.0, 1.0); end G; package G_Integrate is new Generic_Integrate; Result: Float; begin Result := G_Integrate.Do_It(G'Access, 0.0, 1.0); ... end Main; Note that the instantiation has to be done at the inner level in order to avoid the accessibility problem. This means that it has to be done twice unless we use the Nasty.Variable trick. This workaround is unnatural in that it introduces the genericity sledgehammer where there is no real genericity in the problem. Another workaround uses tagged types. The integrate package then becomes package Integrate is type Integrator is abstract tagged null record; function Integrand(X: Float; Int: Integrator) return Float is abstract; function Do_It(Fn: Integrator'Class; Lo, Hi: Float) return Float; end; Inside the body of Do_It there will be dispatching calls on Integrand and the correct integrand is thus chosen according to the tag of Fn. This contrasts with the situation using access types where within the body of Do_It the choice of integrand was determined by the access-to-subprogram parameter in which case the actual parameter was simply called by dereferencing. The idea is that we now extend the type Integrator as necessary to enable it to pass any auxiliary data such as the nonlocal variable X. with Integrate; procedure Main is type G_Integrator is new Integrate.Integrator with null record; Int_G: G_Integrator; function Integrand(X: Float: Int: G_Integrator) return Float is type F_Integrator is new Integrate.Integrator with record X_Copy: Float; end record; Int_F: F_Integrator; function Integrand(Y: Float: Int: F_Integrator) return Float is begin return Int.X_Copy*Y; end F; begin Int_F.X_Copy := X; return Integrate.Do_It(Int_F, 0.0, 1.0); end G; Result: Float; begin Result := Integrate.Do_It(Int_G, 0.0, 1.0); ... end Main; The above will work and is flexible and does not involve generics. However, by no stretch of the imagination can it be considered natural or elegant. It is probably the case that typical programmers can only use this technique by copying an example from a textbook. It therefore fails as an acceptable workaround. The proposed solution using access-to-subprogram parameters is as follows. The integrate package now becomes package Integrate is function Do_It(Fn: access function(X: Float) return Float; Lo, Hi: Float); end; Note that the function Do_It now has an access-to-subprogram parameter. The program becomes with Integrate; procedure Main is function G(X: Float) return Float is function F(Y: Float) return Float is begin return X*Y; end F; begin return Integrate.Do_It(F'Access, 0.0, 1.0); end G; Result: Float; begin Result := Integrate.Do_It(G'Access, 0.0, 1.0); ... end Main; Note that this is precisely how we originally tried to write it. There are no longer any problems with accessibility because the accessibility of the parameter type is deemed to be infinite. An alternative proposal might be to mirror more closely the procedure parameter facility of Pascal and so sweep the access mechanism under the rug. This would mean that the calls of Integrate.Do_It would have actual parameters of just F and G rather than F'Access and G'Access. Although this might be more natural if starting from scratch, nevertheless given the existence of access-to-subprogram types for callback etc, it seems more natural to make the notations uniform. Finally, it should be noted that neither of the above workarounds were applicable to Ada 83 which did not have access-to-subprogram types. Instead a generic formal parameter had to be used in order to pass the function to be integrated. The integration function might be generic with function Fn(X: Float) return Float; function Generic_Integrate(Lo, Hi: Float) return Float; The program then becomes with Integrate; procedure Main is function G(X: Float) return Float is function F(Y: Float) return Float is begin return X*Y; end F; function F_Integrate is new Generic_Integrate(F); begin return F_Integrate(0.0, 1.0); end G; function G_Integrate is new Generic_Integrate(G); Result: Float; begin Result := G_Integrate(0.0, 1.0); ... end Main; Again two instantiations are required; this time because each instantiation applies to a different function to be integrated. Some variations are possible such as making Lo and Hi generic parameters as well. It could be argued that using generics is always the best way since we should really parameterize with the floating type as well. However, if multiple instantiations are to be avoided then we still have to use access-to- subprogram parameters. !ACATS test !appendix From: Robert A Duff Sent: Friday, November 03, 2000 7:56 AM Here's more mailbox stuffing... I guess it's better than ballot box stuffing. Not as good as turkey stuffing. Erhard says: > We don't have an AI for that. It was a proposal for an Enhancement > ('Unrestricted_Access) discussed at the Westboro Mtg, 9/99. At the > time, the argument against it was a technical difficulty in supporting > it for subprograms within generics. There was supposed to be some old > MRT documentation, exploring this issue (an LSN ?), in addition to > Randy's Prototyping report. > Your action item is to do some archeology to see whether you can > retrieve and distribute this LSN or whatever. (It was not an action > item to rethink the issue in the absence of such documentation.) OK, I dug up the original LSN on the subject of downward closures. ================ !topic LSN on General Access Types !key LSN-1083 on General Access Types !reference RM9X-3.10.2;4.0 !reference RM9X-3.10.2(16);4.0 !reference AARM-12.3(12.p,12.q);4.0 !reference LSN-1042 on Accessibility Checks in Generics !from Bob Duff $Date: 2002/01/24 04:54:12 $ $Revision: 1.3 $ !discussion Two issues related to access types and the accessibility rules came up again at the recent DR/XRG meeting in the UK: - The rules prevent "downward closures". - The rules are applied in an assume-the-worst manner in generic bodies. These issues keep coming up, because they represent clearly-desirable functionality, but with a substantial implementation cost (at least for some implementations). It is difficult to make the trade-off. We recommend not supporting downward closures, but solving the generic problem by going over to run-time accessibility checks in generics. Below, we discuss the issues, and the reasons for our recommendation. LSN-1042, published in October, 1992, discusses in general the relationship between accessibility checks and the generic contract model. ---------------- Downward Closures: Ada's access-to-subprogram types represent assignable subprogram values. They support the ability to create data structures containing the identities of subprograms. They support callbacks, where one software component declares a subprogram and hands its identity to another software component, which can then "call back" the first software component at a later time. These types do not support downward closures, where the identity of a more nested subprogram can be passed to a less nested subprogram. Downward closures can be used, for example, to implement iterators, like this: package P is type Integer_Set is private; ... -- various operations type Integer_Action is access procedure(I: Integer); procedure Iterate(S: Integer_Set; Action: Integer_Action); -- Call Action on each member of S. end P; function Count(S: Integer_Set) return Natural is Result: Natural := 0; procedure Increment(I: Integer) is begin Result := Result + 1; end Increment; begin Iterate(S, Increment'Access); -- Illegal! return Result; end Count; Increment'Access above is illegal, because Increment is more nested than type Integer_Action. It would be bad to have to make Increment global, because that would require making the variable Result global. It is a bad idea to force the use of global variables in a language that has tasks -- in this example, Count would not be reentrant if Result were global. Note that this situation is typical of iterators and similar things -- in typical use, the action passed to an iterator will often need visibility upon a variable declared in the caller of the iterator, in order to accumulate some sort of result. The reason for the restriction is that access-to-subprogram types allow assignment. At the point where Iterate is called, we don't know if the body of Iterate is going to save the access value in a global variable. We disallow passing the nested Increment procedure because Iterate *might* save a pointer to it, and call it later, after Increment (and the variable Result) no longer exist. Pascal supports downward closures, but it does not support Ada's callback style, because the identity of a subprogram being passed as a parameter cannot be copied. Modula-2 supports the callback style, but not the downward closure style. Languages like Lisp support a much more general form of closure, which is not of interest to us, since it requires "stack frames" to be heap allocated -- "heap frames", really, in the general case. C supports the callback style, but since there are no nested functions, the question of downward closures does not arise. There are no tasks, either, in C, so making variables global (or C's "static") does not cause as much trouble as in Ada. (Supporting threads in C presents some interesting problems!) Implementation Issues: In a language (like Ada) with nested subprograms, each subprogram needs some way to access its environment -- that is, the variables declared outside it. There are two common methods for representing this environment: static links, and displays. Most Ada compilers use static links, but some use displays. One key difference between the two methods is that static links have a compile-time-known size (32 bits, on a typical machine), whereas the size of a display depends on the maximum nesting depth throughout the partition. In an implementation with static links, an access-to-subprogram value is generally represented as a pair of addresses -- the address of the subprogram's code, and the static link. However, given the current Ada 9X rules, an access-to-subprogram type that is declared at library level does not need the static link -- it can be represented as just a code address. This is nice, because it is efficient, and it allows the representation to easily match C's typical representation of function pointers. Access-to-subprogram types declared one level deeper than library level can also be represented as just a code address. However, two or more levels deeper requires the static link. In an implementation with displays, given the current rules, an access-to-subprogram value can be represented as just a code address -- it is not necessary to attach a display to each access value. This also has the nice interoperability-with-C property. It has been suggested that downward closures be supported by allowing the Unchecked_Access attribute on subprograms. (It is currently allowed only on objects.) The semantics would presumably be that the access value returned is valid (the designated subprogram can be called) so long as the designated subprogram (and it's containing stack frame) still exist. If it doesn't exist, a dereference would be erroneous. We do not recommend this method for these reasons: - It would be unsafe -- it is uncomfortable to introduce erroneousness to a high-level feature like downward closures. - It would require every access-to-subprogram value to carry a static link or display, because the nesting level of the designated subprogram would no longer be restricted at compile time. This would break the interoperability-with-C property, and would be less efficient. (One could imagine an implementation using a different representation when the Convention is C, but that adds complexity, and doesn't solve the efficiency problem in the Ada-only case.) There are two ways to support downward closures that we would recommend, if downward closures are to be supported. Both ways recognize the fact that downward closures really need a separate feature from the callback style of access-to-subprograms: - Limited access-to-subprogram types. - Access-to-subprogram parameters. Limited access types were in an earlier version of Ada 9X. Since they would be limited, assignment would be disallowed, so downward-closure-style parameter passing could be allowed, and would be safe. The compiler would implement limited access-to-subprogram types with a static link or display. Non-limited ones would retain the interoperability-with-C property. The syntax would be something like this: type Integer_Action is limited access procedure(I: Integer); -- ^^^^^^^ procedure Iterate(S: Integer_Set; Action: Integer_Action); -- Call Action on each member of S. Type conversion from limited to non-limited would be illegal. Access-to-subprogram parameters would be an extension to access parameters (not to be confused with parameters of a named access type). The syntax would be something like this: procedure Iterate(S: Integer_Set; Action: access procedure(I: Integer)); -- Call Action on each member of S. This is quite similar to the syntax used in Pascal. As for any access parameter, the access type would be anonymous. Parameter type matching would be based on the designated profile. Access parameters already use run-time accessibility checks -- this new kind would do likewise. Thus, assignment would be allowed, but the accessibility checks would prevent dangling pointers. In our iterator example, if Iterate were to try to copy Action to a global variable (during the call to Iterate from Count), then Constraint_Error would be raised, because Count.Increment is too deeply nested. The value of an access-to-subprogram parameter would need to have a static link or display. Library-level access types could retain the interoperability-with-C property. Of the two workable methods outlined above, the access-to-subprogram parameters method would be somewhat simpler in Reference Manual terms, because it would be able to piggyback on the existing access parameters feature for its rules and semantics. The implementation complexity seems equivalent. Efficiency of the limited access types method would be slightly better, because it would not be necessary to pass in information needed for the run-time accessibility checks. Limited access types would be the first elementary limited types; we would have to reword the parameter passing rules to avoid a contradictory requirement to pass by copy and by reference. (It doesn't really matter which is done, actually.) For implementations with static links, the implementation of either method is straightforward. Such implementations already need to include a static link in at least some access-to-subprogram values, and the downward-closure ones would be the same. However, for implementations with displays, either method is an implementation burden, because: - The current rules do not require carrying the display with the access-to-subprogram value, whereas the new rules would. - The size of the display is not easily known at compile time. It's size can be calculated at run time, or a maximum possible size can be known if there is a restriction on nesting depth. Either way, managing the passing of the unknown size display causes complexity. It is certainly *possible* to implement: I know of at least one Pascal compiler that used displays, and implemented downward closures. Gnu C supports nesting of functions as an extension, and supports pointers to them. And Ada has other features that require the management of unknown-sized data structures. Nonetheless, the implementation is not trivial. It should also be noted that an implementation with displays would be less efficient than one with static links, because an indirect call would require copying the entire display. It's not that big of a deal, however -- it just means copying several words of memory, and there would be no *distributed* overhead. Note also that there are workarounds: Subprograms can be passed as generic formal parameters, so an iterator can often be implemented as a generic formal parameter. However, that prevents recursion, and is more verbose. A closure can also be represented as an access-to-class-wide value. In the iterator example, whatever state is needed by the Action procedure would be encapsulated in a type extension. However, this method is even more verbose. One possibility would be to not support downward closures directly as access-to-subprogram types, but to make the workaround a bit easier. In particular, we could allow limited tagged types to be extended in a more nested place than the parent type. (The accessibility rule would remain as is for non-limited type extensions.) Instead, a rule would be needed for allocators, similar to the current rule for types with access discriminants. This relaxation is possible for limited types, because they have no assignment, and hence cannot be copied to a place where the object lives longer than its type. This would allow the following: package P is type Integer_Set is private; ... -- various operations type Closure is tagged limited null record; procedure Action(C: Closure; I Integer); procedure Iterate(S: Integer_Set; C: Closure); -- Call Do_It(Action, M) for each member M of S. end P; function Count(S: Integer_Set) return Natural is type My_Closure_Type is new Closure with null record; -- Illegal! Result: Natural := 0; procedure Action(C: Closure; I: Integer) is begin Result := Result + 1; end Action; My_Closure: My_Closure_Type; begin Iterate(S, My_Closure); return Result; end Count; The above is less verbose than the current workaround, and has the advantage that My_Closure_Type can be declared where it arguably belongs -- inside Count. The implementation could store the static link or display in each object of a limited type extension that was declared at a more-nested level than its parent. Code would be added to each potentially primitive subprogram of such a type, to move the static link or display from the parameter object to its proper location. Note that no change to the call sites is necessary. Nonetheless, there is some implementation burden, because extra compiler work is needed for declaring these objects, and in the bodies of the potentially primitive subprograms. (The reason I say "potentially" primitive is that because of renaming, we don't know in general while compiling a given subprogram that it will be primitive. Potentially primitive subprograms are essentially the ones declared at the same nesting level, and that take a parameter of the type.) We (reluctantly) recommend not supporting downward closures, because: - An implementation burden exists for display-based implementations. - Workarounds exist. - It seems like too big a change to make to the language at this late date. I say "reluctantly" recommend, because it is clear to me that the functionality is desirable, and if we were designing Ada 9X from scratch, we would support downward closures. ---------------- Generic Bodies: Currently, accessibility rules are checked in generic bodies in an assume-the-worst manner (see 3.10.2(16) and 12.3(12.p,12.q)). This means that such rules are checked assuming the instantiation will be more nested than the generic unit. This is unfortunate, since most of the time, the instance will be at the same nesting level as the generic unit; the rules are therefore more pessimistic than is usually necessary. In many cases, it is possible to work around the problem by moving something from the generic body up to the private part. For example, suppose P is a subprogram declared in a generic body, and the body wishes to do P'Access, of an access type declared outside the generic unit. This is illegal, but one can move the declaration of the subprogram to the private part of the generic, and declare a constant, also in the private part: P_Access: constant Global_Access_To_Subprogram_Type := P'Access; Similarly, type extensions can be declared in the private part of the generic when they are illegal in the body. For the Access attribute for objects, a different workaround is possible -- use Unchecked_Access instead. Unfortunately, this throws away all the benefit of the accessibility checks, and can lead to erroneous execution if one is not careful. Another case is for type conversion of an access type declared in the generic unit (spec or body) to a type global to the generic unit. This is currently illegal. A possible workaround is to add a conversion function to the generic body: function Convert(Ptr: access ...) return Global_Access_Type is begin return Global_Access_Type(Ptr); end Convert; Then, if X is of the inner access type, Convert(X) will do a run-time check, which will fail if and only if the current instance is more nested than the generic unit. All of the above workarounds are annoying, because they cause trouble when converting a package into a generic package -- one has to apply the above workarounds after having written and tested the non-generic package. One possible solution to the above problems is to define some extra syntax, or a pragma that means "this generic unit will be instantiated only at the same nesting level". However, extra syntax for a small issue seems like too big a change at this point. And a pragma with such a heavy semantic effect seems ugly. Perhaps a better solution would be to say that all accessibility rules are checked at run time in instance bodies. (Doing things at run time is one way of getting around generic contract model problems in general, and it would work here.) An implementation that does macro expansion for generic instantiations could always detect these "run-time" errors at macro-expansion time. An implementation that does code sharing would have to generate code to do the run-time checks. One problem with either solution is that there is a substantial implementation burden for implementations that do universal generic code sharing. For such implementions, when a subprogram declared inside the generic unit is called, it needs to be implicitly passed an extra parameter that represents the current instance. This extra parameter is used by the subprogram to address variables declared in the generic body. Since such subprograms have a different calling convention, if one allows access values pointing at them to escape outside the generic, then one has a problem. We recommend using the run-time accessibility checking solution. However, because of the implementation problem, we recommend using this solution only for access-to-object types, and not solving the problem for access-to-subprogram types. The implementation problem mentioned above does not exist for access-to-object types. This solution is not entirely consistent, but note that it is already the case that access-to-subprogram types are different: there are no anonymous access-to-subprogram types, and there is no Unchecked_Access attribute for these types. ---------------- SUMMARY: Downward closures can be sensibly supported, and are quite desirable, but cause implementation difficulties for display-based implementations. Therefore, we recommend not solving this problem. Removing the accessibility restrictions on generic bodies can also be sensibly supported, and is also desirable, but (for access-to-subprogram types) presents severe implementation difficulties for implementations that do universal sharing of generic bodies. We recommend solving the problem for access-to-object types by using run-time checks. We recommend not solving the problem for access-to-subprogram types. **************************************************************** From: Robert A Duff Sent: Friday, November 03, 2000 7:58 AM I wrote: > OK, I dug up the original LSN on the subject of downward closures. Since LSN-1083 refers to LSN-1042, I'll send that along, too, though I'm not sure how relevant it is. ================ !topic LSN on Accessibility Checks in Generics !key LSN-1042 on Accessibility Checks in Generics !reference MS-12;4.6 !from Bob Duff $Date: 2002/01/24 04:54:12 $ $Revision: 1.3 $ !discussion This Language Study Note discusses accessibility checks, and their relationship to the Ada 9X version of the generic contract model. Ada 83 originally intended to support a "contract model" of generics, in which the generic specification forms a contract between clients of the generic and the body of the generic. However, there were certain holes in the contract model. The Ada 9X requirements document directs us to address these problems. Requirement R4.4-B(1), "Dependence of Instantiations on Bodies" states that "A user must have the ability to compile a generic instantiation before compiling the corresponding generic body." Study Topic S4.4-B(2), "Tighten the Contract Model" states that "Ada 9X should ensure that compatibility of a generic instantiation with the corresponding generic body is based solely on the compatibility of each with the generic specification." Although this is a study topic, we see no way of achieving R4.4-B(1) without also achieving S4.4-B(2). Therefore, we have tried to ensure that there are no holes in the Ada 9X generic contract model. We have patched the holes of Ada 83, and avoided adding new ones related to new Ada 9X features. We agree with the Requirements document -- it is essential to have an air-tight contract model. One might think that the generic formal part would contain all the information that is necessary to determine whether an instantiation is legal. However, we have found that to be infeasible. Therefore, we have extended the contract model to include the entire specification of the generic, including the private part, if any. This means that compile-time rules are checked in the instance specification. On the other hand, compile-time rules are not checked in the instance body; instead, they are checked in an "assume the worst" manner in the generic body. Assume the worst means that we ensure that ANY instance body will be legal. In MS;4.6, certain "scope checking" rules were defined. We are now calling these "accessibility rules". These rules are intended to prevent dangling references. Here's how the Ada 9X generic contract model relates to the accessibility rules. Within a generic body, we must "assume the worst", which in this case means that we must assume that the generic will be instantiated at a place that is more nested than the generic declaration. This implies, for example, that one cannot declare a type extension in a generic body. (Type extensions must be declared at the same level as the parent type.) However, within the specification of the generic, we defer the check until instantiation time, when we know the actual nesting level. This means that if a type extension appears in a generic spec, an instantiation that appears at the same level as the generic declaration will be legal, whereas a more nested instantiation will be illegal. (Remember that the "nesting" we're talking about here does not include nesting within a package.) Here's an example: package Library_Pack_1 is generic type T is tagged private; package G is -- Note to clients: You must instantiate this at library -- level. ... private type T2 is new T with ...; end G; end Library_Pack_1; package Library_Pack_2 is ... end Library_Pack_2; package body Library_Pack_2 is package Instance is new G(...); -- Legal. procedure Nested is package Bad_Instance is new G(...); -- Illegal! begin ... end Nested; end Library_Pack_2; The programmer really wanted to declare type T2 in the body of G. However, that would be illegal. But at least there is a workaround: T2 can be declared in the private part of G. This may not be ideal, but it is the only way we have found to preserve the contract model. In practice, the restrictions are not a problem, since most instantiations can be placed at library level without difficulty. It might seem more consistent to treat the spec of G in the same way as the body. However, that would remove an important set of capabilities. Since bodies generally assume the worst, one needs a way to get around various rules -- that way is to put declarations in the private part of the generic. Given the contract model that we have chosen, it would be strange to do the accessibility checks in a different way. **************************************************************** From: Randy Brukardt Sent: Friday, November 03, 2000 11:40 AM Thanks, Bob, now I don't have to try to find this stuff. I have one quibble with this LSN: > One problem with either solution is that there is a substantial > implementation burden for implementations that do universal generic > code sharing. For such implementions, when a subprogram declared > inside the generic unit is called, it needs to be implicitly passed > an extra parameter that represents the current instance. This extra > parameter is used by the subprogram to address variables declared in > the generic body. This really is misleading, in that it identifies the problem as one that occurs only with universal sharing. If that was the case (and given that RR is the only compiler that does this), a reasonable result would be to say "universal sharing isn't worth it, let's have this feature anyway". However, the problem is actually much broader. It occurs with any implementation of sharing that doesn't look in the body (i.e. one that shares based on the contract of the specification). Unless the implementation knows for sure that there aren't any variables in the body, it will have to somehow provide a method of instancing those variables. That means somehow passing an instance pointer into the subprogram (as described above). Thus, relaxing this rule makes not only universal sharing impossible, but as well any version of sharing based only on the contract. Essentially, with a relaxed rule, sharing is only possible if the body does not contain a subprogram 'Access or doesn't contain any local objects. (I would expect that implementations wouldn't bother with both cases if they did any sharing at all; the second case almost never would happen, given it would require both no objects and instantiations that are virtually identical.) This would render moot the discussions about contract enhancing pragmas and the DEC patent. It also means that an implementation which supported any kind of sharing could not make a decision about how to generate a generic at the instantiation site, as the body would control whether or not sharing was possible. Personally, I think this would prevent any implementations from bothering with sharing at all. **************************************************************** From: Dan Eilers Sent: Friday, November 03, 2000 2:33 PM Randy wrote: > This really is misleading, in that it identifies the problem as one that > occurs only with universal sharing. If that was the case (and given that RR > is the only compiler that does this), a reasonable result would be to say > "universal sharing isn't worth it, let's have this feature anyway". The RR compiler is of course _not_ the only compiler that does universal sharing of generics. **************************************************************** From: Dan Eilers Sent: Friday, November 03, 2000 2:20 PM Motivation for adding downward closures to Ada includes the bad press Ada gets for not supporting this programming paradigm, such as the paper: "Using Procedural Parameters and Continuations in Combinatorial Searches" in Software - Practice and Experience, Volume 24, 1994, pp 377-386, by Wen-Ping Hwang and Ching-Lin Wang. The conclusion of this paper states: "Although the code is given in Pascal, the technique is applicable in other imperative languages such as Modula-2, and impurely functional languages such as ML and Scheme that allow side-effects. However, it is not applicable in C, since functions may not be defined within other functions, and Ada, since recursive instantiations of generic subprograms are disallowed." **************************************************************** From: Robert A Duff Sent: Monday, November 06, 2000 8:06 AM Thanks for the info, Dan. > The conclusion of this paper states: > > "Although the code is given in Pascal, the technique is applicable in other > imperative languages such as Modula-2, and impurely functional languages ^^^^^^^^ > such as ML and Scheme that allow side-effects. However, it is not > applicable in C, since functions may not be defined within other functions, > and Ada, since recursive instantiations of generic subprograms are disallowed." The part about Modula-2 sounds fishy to me. Modula-2 does not have downward (inward?) closures. I found this a disappointment when moving from Pascal to Modula-2, because I had thought that Modula-2 was Wirth's "Better Pascal" (which in many other respects it is). Modula-2 has pointer-to-procedure types, but they can't point to nested procedures. This is essentially the same restriction we have in Ada with the acessibility rules: you can't pass a nested procedure as a parameter to an outer procedure. I haven't read the paper, so I don't know if their technique requires downward closures. **************************************************************** From: Robert Dewar Sent: Monday, November 06, 2000 9:43 AM I suppose we could dig up the old proposals in this area. I must say that if the strongest argument is alledged "bad press" I find that very weak. What would be convincing would be real customer experience. We have not had any demands in the GNAT community, but that may be deceptive because of the availability of Urestricted_Access in GNAT -- which indeed is very usefiul, and which we use ourselves and find critically important. **************************************************************** From: Robert Dewar Sent: Wednesday, August 29, 2001 7:34 AM <> Are you sure? I was under the impressoin that *all* Aonix compilers still used displays. Now I am the first to say that if you take all users of GNAT into use including the public version, then probably the statement is strictly true, and that Aonix users are in the minority, but this is a pretty big minority to simply write off this way. Furthermore, are we really sure that DDC-I, Rational, OCS, GHS, and any others that I have forgotten to mention are using static links at this stage? **************************************************************** From: Pascal Leroy Sent: Wednesday, August 29, 2001 7:55 AM > Are you sure? I was under the impressoin that *all* Aonix compilers still > used displays. The old (Ada 83) Aonix technology surely used displays, but I thought that the new one uses static links > Furthermore, are we really sure that DDC-I, Rational, OCS, GHS, and any > others that I have forgotten to mention are using static links at this stage? My understanding was that Janus is the only compiler which still uses static links. (Well, not sure about Irvine.) **************************************************************** From: Robert Dewar Sent: Wednesday, August 29, 2001 9:17 AM <> That's not what I was told when I enquired, because they were using much the same runtime with the new Aonix technology as with the old, but perhaps this was false information. Anyway, to the extent that our decisions are guided by current technology let's make sure we know what we are talking about. So far, we have clear information on GNAT uses static links (and implements 'Unrestricted_Access :-) Rational uses static links Janus uses displays I still think incidentally that displays are the more efficient choice for Ada, assuming you do the appropriate optimizations, since you only pay an overhead for calls to procedures that contain nested procedures, so still from a theoretical point of view it is good to retain this possibility, but pragmatically if no one does it, why bother. (the reason GNAT uses static links is not because of a careful design decision, but rather GNAT just inherits the gcc decision here). **************************************************************** From: Tucker Taft Sent: Wednesday, August 29, 2001 8:57 AM > > Are you sure? I was under the impressoin that *all* Aonix compilers still > > used displays. > > The old (Ada 83) Aonix technology surely used displays, but I thought that > the new one uses static links I believe it depends on the target. I think the x86 target still uses displays, while the RISC targets use static links. Ben, do you recall? > > Furthermore, are we really sure that DDC-I, Rational, OCS, GHS, and any > > others that I have forgotten to mention are using static links at this > > stage? > > My understanding was that Janus is the only compiler which still uses static > links. (Well, not sure about Irvine.) I presume both of the above paragraphs should read "displays" where they say "static links"... **************************************************************** From: Dan Eilers Sent: Wednesday, August 29, 2001 11:45 AM Irvine uses static links for all targets. TLD may still be using displays. Irvine does implement shared-body generics (allowing users to select on a per-generic basis whether the generic should always be implemented as shared-body or macro-expanded). The !discussion notes potential problems with shared-body generics, without any further discussion (except in attached email) as to how to resolve such problems. I don't know if the difficulties with shared-body generics are unique to RR's implementation model, or are common to all potential implementations of shared-body generics. I am in favor of supporting downward closures, even at the expense of giving up shared-body generics, but if the proposal is to jettison shared-body generics, (rather than accommodating them somehow), then that should be explicitly stated. And if so, various other accommodations in the language for shared-body generics should probably be be eliminated, and class-wide untagged types should probably be added in lieu of shared-body generics. **************************************************************** From: Robert Dewar Sent: Wednesday, August 29, 2001 11:53 AM <> I don't understand the connection here? **************************************************************** From: Dan Eilers Sent: Wednesday, August 29, 2001 12:14 PM As noted in the Ada83 Rationale, shared-body generics are intended to be used for utility routines that you don't want replicated n times just because you have n different type derivations. For example, you don't want 10 identical copies of the generated code for generic_elementary_functions just because you have 10 different types derived from float. Class-wide untagged types would serve the same purpose. **************************************************************** From: Robert Dewar Sent: Wednesday, August 29, 2001 12:35 PM I still don't see the connection. It is always possible to share generics in some limited circumstances, and the cases where class-wide untagged types would help are precisely those in which generics can be shared. I don't think it makes sense at this time to add class-wide untagged types. This is too large a change, without sufficient justification from real customer apps. **************************************************************** From: Robert Duff Sent: Wednesday, August 29, 2001 1:47 PM These two features can do some of the same things. For example, if Text_IO had a Put procedure that takes a parameter of type root_integer'Class, then we wouldn't need the generic package Integer_IO. The implementation issue is separate: you can have shared or not-shared generic bodies, and you have the same choice for untagged class-wide types (duplicate the above-mentioned imaginary Put for each type, or not). I don't remember about the implementation difficulties, but I think I wrote an LSN about it some years ago -- anybody who's interested could try looking that up. **************************************************************** From: Dan Eilers Sent: Wednesday, August 29, 2001 1:58 PM I guess the issue boils down to this: Is generic code sharing the best (long-term) mechanism for addressing the issue of how to write utility functions that depend only on the representation of a type? In Ada83, generic code sharing served multiple purposes, and was accommodated by the language design, and expected to be implemented, as noted in the Rationale, and was in fact reasonably widely implemented, (DEC, Rational, RR, ICC, TLD, others??). In Ada95, generics are not well accommodated by the language design, and are less often needed in cases where code replication is an issue. In particular, linked lists and other polymorphic container classes can be created with tagged types instead of generics, avoiding the code replication issue. Subprograms can be passed as parameters without using generics, again avoiding the code replication issue. This Ada95 functionality has two advantages: it assures that the generated code will not be replicated, and it simplifies the source code by eliminating instantiations. However, the case remains that utility functions needing only the properties of the base type, are not well supported in Ada95 (except of course for the predefined operators and attribute functions). My contention is that it would be much easier for implementations to support such utility functions by extending the language to allow user-defined operations on untagged class-wide types, than it would be for implementations to support shared-body generics. Implementations already support untagged class-wide types--for the predefined operators and attributes. Even the implementations currently supporting shared-body generics would likely jettison that support, since the reasons for it would have essentially all been eliminated, given the maintenance difficulties of shared-body generics. And it would be more convenient for the users as well, since instantiations would be avoided. **************************************************************** From: Robert Duff Sent: Wednesday, August 29, 2001 2:23 PM > I don't think it makes sense at this time to add class-wide untagged types. Well, if I recall, you never thought it made sense at *any* time. ;-) > This is too large a change, without sufficient justification from real > customer apps. I agree that it doesn't make sense at this time. **************************************************************** From: Robert Dewar Sent: Wednesday, August 29, 2001 3:11 PM True, but my point was that we discussed this issue at length at that time, and I don't see anything significant to change the decision at this stage. There are lots more valuable things that can be done (like making it possible to use Annex E with CORBA :-) **************************************************************** From: Robert Dewar Sent: Wednesday, August 29, 2001 2:57 PM Well we have seen almost no demand for shared generic implementation. It would not be at all hard to do in the simple cases, but we don't see it as a significant requirement from our customers point of view, and so to the extent that untagged class-wide types are solving the same problem, this feature is not of interest to us (and I doubt we would implement this extension to the language at the current time). **************************************************************** From: Tucker Taft Sent: Wednesday, August 29, 2001 5:35 PM Dan Eilers wrote: > ... > In Ada83, generic code sharing served multiple purposes, and was accommodated > by the language design, and expected to be implemented, as noted in the > Rationale, and was in fact reasonably widely implemented, (DEC, Rational, > RR, ICC, TLD, others??). > > In Ada95, generics are not well accommodated by the language design, > ... Can you clarify "not well accommodated"? Does it relate to it being harder to implement shared generics? Both you and Randy have mentioned that sharing generics is harder in Ada 95 than Ada 83, but I can never remember what feature it is that makes that true. I thought we had actually tried to make it *easier* to share, by firming up the contract model. In what way did we miss the target? (I realize you or Randy may have already answered this question in the past.) **************************************************************** From: Dan Eilers Sent: Wednesday, August 29, 2001 11:34 PM > In Ada95, generics are not well accommodated by the language design, There is a typo here. As you deduced, I intended to say "shared generics" rather than generics in general. One example of a change in Ada95 that makes shared generics more difficult (although not impossible) is the rule that the choice in a variant record in a generic spec can be of a generic formal type. Formal discrete types can now be modular, which complicates things, since you can't do all discrete arithmetic with 32-bit signed ints. Something that would have helped, but which wasn't included in Ada95, was a mechanism for finer control of generic formal types, such as size clauses to restrict all actual parameters to a particular size. And of course it would have helped to have a way to indicate that a generic is intended to be shared (besides pragma optimize). **************************************************************** From: Randy Brukardt Sent: Thursday, August 30, 2001 9:40 PM Dan said, responding to Tucker: > > In Ada95, generics are not well accommodated by the language design, > > There is a typo here. As you deduced, I intended to say "shared generics" > rather than generics in general. > > One example of a change in Ada95 that makes shared generics > more difficult (although not impossible) is the rule that > the choice in a variant record in a generic spec can be > of a generic formal type. > > Formal discrete types can now be modular, which complicates things, > since you can't do all discrete arithmetic with 32-bit signed ints. To abstract a bit, the contract model was a help, but all of the new features in Ada 95 hurt, a lot in some cases. To add to the list: The fact that decimal fixed types match ordinary fixed point formals means that arithmetic on formal fixed types has to be thunked. The fact that 'Access can be used to pass an access to a object of a formal type outside of a generic eliminates the possibility for the representation tricks that made sharing in Ada 83 efficient. The "assume-the-best" rules in a generic spec. means that many more items have to be constructed at instantiation time and passed to the body. The generic derived types for untagged types means that actuals can have vastly different representations in ways that the body can see. This is especially a problem for record types. And its annoying, because it is very rare that anyone actually takes advantage of this capability (different representations for derived record types) much less pass them into a generic unit. I could probably find more. None of these are insurmountable, but the effect of all of them is that sharing is supported only in a couple of compilers where the implementor couldn't justify the cost of getting rid of it. :-) **************************************************************** From: Randy Brukardt Sent: Thursday, August 30, 2001 10:37 PM Having read this proposed AI, I'm not really sure what the proposal is. (I purposely did not reread the LSN -- the AI has to stand on its own without any of the appendix information.) The AI essentially gives only the syntax, while it is the semantics of the proposal (especially in converting to other types) that will make or break the proposal. Additionally, the AI spends a lot of time taking potshots at implementations using displays (as the implementor in question, I especially resent that). That especially silly when there is no implementation problem at all with displays in this context. It merely is a matter of how fat is an access to subprogram parameter. (Since it needs to carry a static link in such implementations, it clearly is going to be fatter than a "normal" (C-like) access-to-subprogram pointer in any case. (Peeking at the LSN, it makes this point clearly -- so why so much emphasis on an obvious red herring???) The AI is also full of cheerleading language which has no place in a rational technical discussion. "It is time now to do the job properly." Pleeze! And, of course, it completely ignores the generic sharing issue, the one that kept this feature out of Ada 95 in the first place. Without tackling the tough issue, (and without enough details to evaluate it), this AI is hardly worth discussing at all. All of that said, the main issue here is whether or not we continue to work to allow the use of generic sharing. An unrestricted version of downward closures (in this proposal, where access-to-subprogram parameters are freely convertible to "regular" access-to-subprogram types) would certainly mean that no practical generic body sharing is possible. (It could only be done by examining the actual body before sharing, and then would have to be undone if the body changes. A source-based implementation like GNAT might be able to work within those restrictions, but a traditional library-based implementation would find it impossible.) However, if the restrictions on 'Access for subprograms in a generic unit are preserved, and apply to any conversions from an access-to-subprogram parameter to a regular access-to-subprogram type, I think it would be possible to implement these for shared generic bodies. It wouldn't be pretty (it would require an even fatter pointer), but I think it would work. The idea is that the access-to-subprogram parameter would have to carry the address of the subprogram, the static link or display, and the generic instance information. Each call to an access-to-subprogram parameter would inspect the pointer, and pass the generic instance information if necessary in whatever the standard format for that compiler is. (For Janus/Ada, these parameters are passed first, in front for the "real" parameters. We would only have a store a count and list of parameters). This would complicate the calls a bit, but it would work fine. The problem comes if this fat pointer was converted to a "regular" access-to-subprogram type, which does not carry any of this information (and cannot, in order to be compatible with C). After such a conversion, the parameter information is no longer available, so a correct call cannot be made. Thus, it is critical that the access-to-subprogram that allows downward closures is syntactically separate from "regular" access-to-subprogram types (which this proposal does), and that conversions of these types (at least those derived from a generic) to "regular" access-to-subprogram types be disallowed. (The proposal is completely silent on this issue, and it is the critical one.) The LSN implies a runtime check, which could easily be extended to include whether the access came from a generic. I have no choice but to fight every step of the way any proposal to completely eliminate generic sharing as a possibility (to fail to do so would open me to action by RR's many outside shareholders). So I hope that we can find a solution which gives the needed functionality without having to rescind an important design goal of Ada 83. **************************************************************** From: Tucker Taft Sent: Friday, August 31, 2001 12:09 AM Thanks for reminding me of the problems. The formal derived untagged type does seem nasty. The need to support 'Succ and 'Pred on discrete types that might be modular I can see also is a new challenge. On the other hand, I think you have misremembered the rule about decimal fixed point -- they don't match ordinary fixed point. I suppose one approach would be to create a single "typical" shared body that works for all "well-behaved" actuals, and do a macro expansion for the rare ill-behaved instantiations. Of course that means you need to support both sharing and macro expanding, which doubles the work and the possibilities for bugs... **************************************************************** From: David Emery Sent: Thursday, August 30, 2001 9:12 AM >Well we have seen almost no demand for shared generic implementation. It >would not be at all hard to do in the simple cases, but we don't see it >as a significant requirement from our customers point of view, and so to >the extent that untagged class-wide types are solving the same problem, this >feature is not of interest to us (and I doubt we would implement >this extension to the language at the current time). I certainly cannot speak for what GNAT users want. But I will point out that I spent about 4 months on CAATS to take a generic and 'hand-share it' (using every dirty trick I knew :-) The rationale for this effort was clear. There were about 350 instantiations of this generic, and each instantiation used about 250kb of memory. Since we had a requirement for the entire application to be resident in RAM, all of these instantiations added up to an additional RAM chip in each workstation, at a cost of about $1m, if I remember right... I was able to get the per-instantiation load down to about 20kb/instantiation. I've been in other situations where we made heavy use of generics and were significantly disappointed when we didn't get this optimization. But CAATS is the one case where I could quantify both the size impact and the resulting cost of not having this optimization. (p.s. I asked for but did not get a salary award on the basis of saving the company so much money :-) :-) Redesigning was not an option, as this was one of the key parts of the design. (It connected all of the application logic to all of the user interface, and changes to this component would have touched about 1/3 of the total system, running into 750k sloc...) Granted this was Ada83, but as has been pointed out, many Ada83 compilers provided support for shared generic instantiations. With 20-20 hindsight and the new features of Ada95, we probably could have come up with an alternative design that did not make use of generics (and did not have this memory cost...) There are a few Ada optmizations that can have substantial impact on how you design your software. Code sharing on generics and passive task optimizations are two that come to mind. Without such optimizations, designers would probably change their approach, due to implementation costs of these features. More classic optimizations (e.g. loop invariants) don't strike me as having -design level- impacts. dave p.s. I have to admit that it was a lot of fun to take a generic and "hand share it". And I freely admit that the result was not guaranteed to be portable, although I had a lot of confidence that the code would port to "most reasonable Ada compilers". Basically what I did was generate "dope" for each instantiation with pointers to both data structures and subprograms via address attributes and mechanisms to invoke subprograms specified by address. **************************************************************** From: Robert Dewar Sent: Friday, August 31, 2001 7:02 AM Of course the interesting thing in such a specific case (as Dave describes for CAATS) is to know exactly what the generic profile looks like, to get an idea of a) how easy it would be to avoid the use of a generic in such a case b) Whether indeed this would be one of the easy cases to share I must say that 350 instantiations of a single generic is a bit mind boggling in any case, were these really independent instantiations? **************************************************************** From: David Emery Sent: Friday, August 31, 2001 8:26 AM It was pretty "ugly", as I recall. Enumeration type, access to array type, several subprograms. Instantiation of the outer generic contained an inner generic, which also had many different kinds of parameters. It would have been extremely nice to have code sharing, but it was clear to me that this would have been very difficult to implement. But it would have matched the Ada95 notion of generic package parameters very nicely. >I must say that 350 instantiations of a single generic is a bit mind >boggling in any case, were these really independent instantiations? Absolutely. There was an instantiation of the outer generic for each window/display on the system. (The system had 350 different 'windows', where each window consisted of a bunch of related X widgets to implement a specific piece of functionality.) There was an instantiation of the inner generic for each widget in the window. If you're really interested in the details, look for the paper by P. Kruchten, et.al. in IEEE Computer from about 5 years ago. (I don't have the exact reference in front of me...) You can argue the design, particularly in Ada95, but the absolute fact of the matter was that was what it was... In fact, I didn't design the component. Rather, I was the first maintainer of the component, and rewrote it twice, once for time (changing data structures) and the second time for space (reducing instantiation footprint.) **************************************************************** From: Pascal Leroy Sent: Friday, August 31, 2001 3:20 AM > The problem comes if this fat pointer was converted to a "regular" > access-to-subprogram type, which does not carry any of this information (and > cannot, in order to be compatible with C). After such a conversion, the > parameter information is no longer available, so a correct call cannot be > made. I do not understand the parenthetical comment about compatibility with C. My understanding (but I agree that it should spelled out in the AI) was that anonymous access-to-subprogram types have convention Ada; that they can be converted to named access-to-subprogram types only under the condition of subtype conformance; meaning that an anonymous access-to-subprogram type cannot be converted to a convention C named access-to-subprogram type. This implies that pretty much any access-to-subprogram type with convention Ada has to be fat, that those with convention C can be simple code addresses, and that you probably have to disallow convention C on nested subprograms. That doesn't seem unreasonable to me. **************************************************************** From: Robert Dewar Sent: Friday, August 31, 2001 8:22 AM Well GNU-C most certainly allows access to nested procedures using trampolines, so of course GNAT needs to follow that rule (and always has). So most certainly in GNAT we allow convention C on nested subprograms, but then we are not using displays -- most certainly it is *permissible* to disallow convention C on nested subprograms :-) **************************************************************** From: Randy Brukardt Sent: Friday, August 31, 2001 2:34 PM It comes from the LSN, which dismisses 'Unchecked_Access on subprograms with the following: - It would require every access-to-subprogram value to carry a static link or display, because the nesting level of the designated subprogram would no longer be restricted at compile time. This would break the interoperability-with-C property, and would be less efficient. (One could imagine an implementation using a different representation when the Convention is C, but that adds complexity, and doesn't solve the efficiency problem in the Ada-only case.) > My understanding (but I agree that it should spelled out in the AI) was that > anonymous access-to-subprogram types have convention Ada; that they can be > converted to named access-to-subprogram types only under the condition of > subtype conformance; meaning that an anonymous access-to-subprogram type > cannot be converted to a convention C named access-to-subprogram type. > > This implies that pretty much any access-to-subprogram type with convention > Ada has to be fat, that those with convention C can be simple code > addresses, and that you probably have to disallow convention C on nested > subprograms. That doesn't seem unreasonable to me. I think we have to be really careful about passing rules which require existing implementations to change the representation of existing types. Rules that required that in Ada 95 caused no end of trouble. I've been trying to look at this (and most other proposals) from the perspective that existing types should not be forced to change representations to support it. **************************************************************** From: Tucker Taft Sent: Friday, August 31, 2001 9:54 AM > This implies that pretty much any access-to-subprogram type with convention > Ada has to be fat, I presume you mean "has to be fat in the presence of universal generic sharing"... > ... that those with convention C can be simple code > addresses, and that you probably have to disallow convention C on nested > subprograms. That doesn't seem unreasonable to me. ... for an implementation that uses universal generic sharing, I presume you mean. **************************************************************** From: Pascal Leroy Sent: Friday, August 31, 2001 10:29 AM No I didn't, but then I have a very shallow understanding of these issues, so feel free to educate me. We seem to have established that an anonymous access-to-subprogram type has to be fat (either it contains a static link, or (part of) the display at the time when the access is created). If we can freely convert between anonymous and named access-to-subprogram types (modulo the usual accessibility checks) then it seems to me that named access types also need to come with a static link or display. This is irrespective of generic sharing. But again, I may be completely confused... **************************************************************** From: Tucker Taft Sent: Friday, August 31, 2001 1:03 PM A named access-to-subprogram type, unlike the proposed anonymous ones, is only allowed to point to subprograms declared at the same level as the type, or further out. In our implementation, this allows us to use "slim" pointers for values of a library-level (level "zero") access-to-subp type (since the static link is effectively zero) and for level one access-to-subp type, because the static link can be set when a call through the pointer is made to equal the current level one frame pointer, since that is either the correct value or the static link is going to be ignored. I don't think the ability to convert to or from an anonymous access-to-subp type has any impact on this. When you convert to the anonymous type, you need to synthesize the same static link you would synthesize when you currently make a call. When you convert from the anonymous type to a level zero or level one named type, you need to verify that the value of the static link is either null or matches that associated with the target type. **************************************************************** From: Gary Dismukes Sent: Friday, August 31, 2001 5:16 PM That's an interesting optimization (the level one case), but how do you deal with the potential for blowing the stack on indirect calls to global subprograms (e.g., if the calls occur within a loop)? **************************************************************** From: Tucker Taft Sent: Tuesday, September 4, 2001 10:25 AM You have lost me. We pass the static link as a separate parameter. There is no extra stack space involved. Perhaps you mean that the called routine gets one extra parameter, and doesn't pop the stack sufficiently after the call? I presume that stack is popped by the caller, since we are using "C"-like calling conventions. **************************************************************** From: Robert Dewar Sent: Tuesday, September 4, 2001 11:23 AM If indeed stack is consumed at all for the parameter, which is not the case in most architectures. **************************************************************** From: Gary Dismukes Sent: Tuesday, September 4, 2001 1:54 PM Yes, that's what I was alluding to (passing an extra parameter which might not get popped). I would have thought that it would be target-dependent whether the callee or caller has to pop stack arguments, but certainly if the caller pops them then there's no problem. (I didn't realize that C calling conventions required the caller to do this, surely there are architectures that don't easily conform to that?) **************************************************************** From: Robert Dewar Sent: Tuesday, September 4, 2001 1:59 AM In traditional C, the caller has to pop, because only the caller knows the number of arguments in the call, which does not have to match the number of arguments defined in the function, so yes, on all targets that I am aware of (which is a lot), the caller always pops. **************************************************************** From: Gary Dismukes Sent: Tuesday, September 4, 2001 2:32 PM OK. Btw, it's not true on the JVM (admittedly a non-C machine :-) nor on Rockwell's AAMP (I'm not sure how they handle such C arguments there, but it's probably not pretty). **************************************************************** From: Tucker Taft Sent: Tuesday, September 4, 2001 2:55 PM The JVM is a very special case, since they don't directly support calling through a pointer. Almost certainly an access-to-subp value for the JVM will need to be an object with a "call-me" method, of a class constructed at the point of the 'Access or access subp conversion. And of course you have garbage collection... On the AAMP, I presume they would end up passing a pointer to a parameter block, or some such thing, to accommodate unknown length parameter lists, for something like printf. **************************************************************** From: Robert Dewar Sent: Friday, August 31, 2001 9:52 AM I really think that universal generic sharing is a lost cause, and not one that is worth spending time on at this stage. **************************************************************** From: Dan Eilers Sent: Friday, August 31, 2001 12:08 PM It is certainly true that there are many generics for which it makes no sense to share all instantiations. However, it is equally true that there are many generics for which it makes no sense to expand all instantiations, especially when the actual types have common representation, and the body of the generic does not depend on any properties of the formal type other than its representation. The predefined Ada95 libraries are full of such examples (I/O, string processing, math functions, etc.) **************************************************************** From: Robert Dewar Sent: Friday, August 31, 2001 1:14 PM Absolutely, I don't think anyone would disagree with this assessment. **************************************************************** From: Randy Brukardt Sent: Friday, August 31, 2001 3:35 PM > I really think that universal generic sharing is a lost cause, and not one > that is worth spending time on at this stage. Keep in mind that we are not talking about just "universal" sharing, but any sharing based on the contract (specification) alone. I don't think that sharing based on body inspection is worthwhile (among other things, it means that the advantage of not having to recompile instantiations when bodies change is lost), so I believe that to throw out "universal" sharing essentially means that we are throwing out all language support for any sort of sharing. (If that is done, I agree with Dan that all of the rules to support sharing should be junked -- any implementation that wanted to do any sharing would have to stand on its head anyway, so why bother to give them any help?) **************************************************************** From: Robert Dewar Sent: Friday, August 31, 2001 6:54 PM I disagree that it is a significant advantage to avoid recompilaion when bodies change. The motivation for generic sharing that is convincing is saving space. Speeding up compilation is an entirely secondary concern. **************************************************************** From: Randy Brukardt Sent: Friday, August 31, 2001 7:34 PM Well, the original reason we adopted it was because it made compilation possible (there simply wasn't enough RAM on MS-DOS machines to implement a macro-type scheme; we were pretty much out of RAM as it was). We also expected space savings -- but those are largely illusory. The overhead of the shared data area (indirect access to objects, indirect access to ranges, etc.) and the loss of optimization opportunities mean that you need a lot of instantiations to break even. (Dave Emery's app probably would have come out better; poorly designed generics with lots of code in them that doesn't depend on the formal parameters probably would come out better as well. But there isn't much of that around.) Technically, I'd prefer to abandon sharing. Making it work takes just too much effort, and Ada 95 is rather hostile to it. But it simply does not make business sense. For an investment of only $500,000, our customers get: -- Loads of new bugs; -- Much slower binding times; -- Slower runtimes (because our runtime is tuned for shared generics); -- Customers that actually get a benefit from sharing lose that benefit. I cannot imagine a circumstance where it would make economic sense to make that investment (short of winning the lottery)! **************************************************************** From: Robert Dewar Sent: Friday, August 31, 2001 7:40 PM Sure it is always a strong argument that you are already doing things one particular way. That's why we left out downward closures :-) But I still think that general sharing makes little sense, but limited sharing, e.g. when representations are really the same, can in fact save a lot of room, e.g. lots of instantiations of integer_io for 32 bit integers. **************************************************************** From: Randy Brukardt Sent: Friday, August 31, 2001 7:56 PM My understanding is that that would infringe on the DEC patent. (Even though the technique is obvious.) **************************************************************** From: Robert Dewar Sent: Friday, August 31, 2001 8:13 PM Hard to say if it would infringe or not, there is prior art and as long as you are very careful to copy the prior art exactly, you should be fine. Also what's the date on the DEC patent, it must be close to running out. **************************************************************** From: Randy Brukardt Sent: Friday, August 31, 2001 8:25 PM The abstract Dan Eilers posted was dated "January 18, 1994". I think they last longer than 7 years... (Ed note: That is in AC-00003.) **************************************************************** From: Robert Dewar Sent: Friday, August 31, 2001 9:14 PM As I say, there is clear prior art on the DEC patent. That does not mean the DEC patent is invalid, you have to look very carefully to see if the prior art really teaches everything in the claims, but if you stick to what the prior art *does* teach, then you will be safe. **************************************************************** From: Robert Dewar Sent: Friday, August 31, 2001 6:45 AM <> Indeed, as I mentioned in my previous note, displays are clearly technically superior to the use of static links for Ada 83 and Ada 95 as they are defined right now. It is possible that this new AI tips the balance, and if so, that is a serious technical issue that should be seriously examined in the AI. **************************************************************** From: Robert Dewar Sent: Friday, August 31, 2001 6:49 AM <> In practice, I suspect that an accurate generic sharing implementation has no choice but to use multiple bodies in some cases. It is too hard to do things, or involves too much thunking otherwise. In particular, the fact that floating-point can be more than one size is rather deadly (I believe that RR "cheats" by doing everything in maximum precision, but this is really unpleasant since a) it gives annoying extra precision, which, while allowed by the language is a really deadly nuisance in numeric work, as we know from the ia32 disaster of always using 80 bits. b) it causes problems with unchecked conversions at least ) **************************************************************** From: Dan Eilers Sent: Friday, August 31, 2001 12:08 PM ICC also uses a maximum precision floating point in a single body in shared-body mode. Any user who finds this a nuisance can specify macro-expanded mode for the generic. **************************************************************** From: Robert Dewar Sent: Friday, August 31, 2001 1:18 PM That's reasonable, it means that for strict conformance you need to specify macro expansion (if one is being very technical, it should be the case that you can specify this with a command line switch). But switches are definitely allowed to make changes in behavior :-) **************************************************************** From: Randy Brukardt Sent: Friday, August 31, 2001 2:31 PM Robert said: > In practice, I suspect that an accurate generic sharing implementation > has no choice but to use multiple bodies in some cases. It is too hard > to do things, or involves too much thunking otherwise. In particular, > the fact that floating-point can be more than one size is rather deadly > (I believe that RR "cheats" by doing everything in maximum precision, > but this is really unpleasant since.. For the record, Janus/Ada 95 does not "do everything" in maximum precision. Janus/Ada 83 did do that, but the representation of items in memory in Ada 95 have to be as of the actual, or 'Access does not work. We do use maximum precision for intermediate results of calculations, but we do that for ALL real operations (in or out of a generic); that's really all that makes sense on the Intel Pentium family processors. **************************************************************** From: Robert Dewar Sent: Friday, August 31, 2001 6:48 PM <> So how do you handle floating-point generic parameters? <> That's far from true, because it results in non-IEEE compliant results (because of double rounding for one thing). For extensive discussions, see recent thread on gcc mailing list on relaxed math mode. **************************************************************** From: Randy Brukardt Sent: Friday, August 31, 2001 7:06 PM > < Janus/Ada 83 did do that, but the representation of items in memory in Ada > 95 have to be as of the actual, or 'Access does not work.>> > > So how do you handle floating-point generic parameters? With read and write thunks. (Barf!) If an object needs to be allocated, it uses the largest possible size, but the extra bits (if the actual is smaller than the largest) are never used. > < do that for ALL real operations (in or out of a generic); that's really all > that makes sense on the Intel Pentium family processors.>> > > That's far from true, because it results in non-IEEE compliant results > (because of double rounding for one thing). For extensive discussions, > see recent thread on gcc mailing list on relaxed math mode. That's pretty much a "don't care" here. We don't implement Annex G, and we don't have customers with strict numeric requirements. It would take far more code (and time) to not use extra precision in intermediate results (essentially a store to memory between every operation) and it's perfectly legal in Ada. So I stand by my statement. YMMV. **************************************************************** From: Robert Dewar Sent: Friday, August 31, 2001 7:12 PM <> Yes, OK, but that's a huge hit in efficiency. I think you really *have* to specialize by floating-point size for any reasonable performance. <> That's a long cru from "that's really all that makes sense on the Intel Pentium family processors", since that seemed to be an absolute statement, not qualified by "if you don't care about strict numeric requirements". **************************************************************** From: Randy Brukardt Sent: Friday, August 31, 2001 7:42 PM Well, it's actually not much a time hit (at least on the Pentium). I was quite surprised by how little it matters. The main cost is that it costs in space, which makes it less likely that the sharing will save anything. But there really wasn't any choice. That change was the only way to get some of the ACVC's to pass. **************************************************************** From: Tucker Taft Sent: Friday, August 31, 2001 9:52 AM Randy Brukardt wrote: > All of that said, the main issue here is whether or not we continue to work > to allow the use of generic sharing. An unrestricted version of downward > closures (in this proposal, where access-to-subprogram parameters are freely > convertible to "regular" access-to-subprogram types) would certainly mean > that no practical generic body sharing is possible. (It could only be done > by examining the actual body before sharing, and then would have to be > undone if the body changes. A source-based implementation like GNAT might be > able to work within those restrictions, but a traditional library-based > implementation would find it impossible.) Actually that is not true, for what it is worth. There were several library-based implementations that did partial sharing which depended on the body. The design for this was published back in 1983, I believe, by Gary Bray of Intermetrics, and essentially the same design was patented by DEC a decade later (;-). In any case, clearly part of the problem is that there are few people on earth who understand the impliciations of doing "universal" generic sharing, and when the AI author is not one of those few people, attempts to analyze the impact on universal generic sharing are difficult if not impossible. > > However, if the restrictions on 'Access for subprograms in a generic unit > are preserved, and apply to any conversions from an access-to-subprogram > parameter to a regular access-to-subprogram type, I think it would be > possible to implement these for shared generic bodies. It wouldn't be pretty > (it would require an even fatter pointer), but I think it would work. > > The idea is that the access-to-subprogram parameter would have to carry the > address of the subprogram, the static link or display, and the generic > instance information. Each call to an access-to-subprogram parameter would > inspect the pointer, and pass the generic instance information if necessary > in whatever the standard format for that compiler is. (For Janus/Ada, these > parameters are passed first, in front for the "real" parameters. We would > only have a store a count and list of parameters). This would complicate the > calls a bit, but it would work fine. > > The problem comes if this fat pointer was converted to a "regular" > access-to-subprogram type, which does not carry any of this information (and > cannot, in order to be compatible with C). After such a conversion, the > parameter information is no longer available, so a correct call cannot be > made. > > Thus, it is critical that the access-to-subprogram that allows downward > closures is syntactically separate from "regular" access-to-subprogram types > (which this proposal does), and that conversions of these types (at least > those derived from a generic) to "regular" access-to-subprogram types be > disallowed. (The proposal is completely silent on this issue, and it is the > critical one.) The LSN implies a runtime check, which could easily be > extended to include whether the access came from a generic. I think you will need to help define what the rule should be, keeping in mind it shouldn't feel unnecessarily restrictive for non-shared-generic users. > I have no choice but to fight every step of the way any proposal to > completely eliminate generic sharing as a possibility (to fail to do so > would open me to action by RR's many outside shareholders). So I hope that > we can find a solution which gives the needed functionality without having > to rescind an important design goal of Ada 83. I don't think you need to be strident. As I indicated above, the most common problem is that we don't really understand the sharing problems. Please enlighten us. No need to get your dander up ;-). **************************************************************** From: Randy Brukardt Sent: Friday, August 31, 2001 2:58 PM > I think you will need to help define what the rule should be, keeping in > mind it shouldn't feel unnecessarily restrictive for non-shared-generic > users. The rule should essentially be the same as the (revised in AI-229) rule for 'Access. That is, if an explicit 'Access (to a regular access-to-subprogram [A2S]) would be illegal, then a conversion from an anon A2S to a regular A2S also would be disallowed (by a runtime check). Essentially, if the subprogram designated by an anon A2S is declared in a generic and the 'Access is in the same generic, the value cannot be converted to a regular A2S unless that regular A2S is declared in the same generic. (I think the latter part would be too hard to check for most implementations, because a runtime indication of the generic would be needed.) The examples of uses of anon A2Ss in the AI never do any conversions, so it appears that the capability to convert is not very important. **************************************************************** From: John Barnes Sent: Tuesday, September 4, 2001 8:17 AM I see that my attempt at AI-254 has stirred a lot of discussion. It was not in any sense meant to be a completed job but simply to lay out the problem with one coherent example and to outline what I believe is the best solution. And I had no intention of making unpleasant remarks aimed at any implementations and if I have given offence, I am sorry. I also apologise if my British sense of humour is not appreciated. I feel quite strongly about this topic in a somewhat philosophical vein. One of my earliest jobs (around 1962) was to estimate parameters describing chemical reactions. We had various data points from experiments measuring conditions at different points in time and space. We also had models describing the chemistry but with various unknown rate constants and similar parameters. The technique was to integrate the equations with estimated values of the parameters and then to compare the computed data points with the measured values. Some measure of the error (typically weighted sum of squares) was then minimized with respect to the parameters and this gave an estimate of the parameters. Everything was hopelessly non- linear and could only be solved by iterative and often heuristic algorithms. I coded the general algorithms in Algol 60 in order to provide a general library for myself and co-workers. The specific equations to be minimized or integrated were defined via procedure parameters. It all worked fine and it seemed a natural and logical that the routines should be nested as in the example in the AI. Indeed triple nesting often occurred because multiple integrals coupled with minimization were common. I don't know how one does this sensibly in a flat language like Fortran. I assume that one cannot and has to use nasty tricks with global common in order to pass the auxiliary information. I never did like Fortran. I only ever wrote one program in Fortran on an IBM 1401 and I never got it to work because the compiler was riddled with errors. Still one shouldn't condemn a language because of lousy compilers but it is often done as we know. So procedure parameters and full block structure were a natural tool in my earliest programming days. And they carried through into Algol 68 and Pascal. I assumed that they were part of the given infrastructure for any modern language. In the Strawman to Steelman days, I really couldn't believe that David Fisher was demanding a language without procedure parameters and that Jean was going along with it. I thought that the requirements were substantially flawed in failing to meet this, to me, obvious requirement. Of course we were cajoled or whatever into accepting the generic solution. It was said to be good for us because we needed to parameterize by the type anyway. Well each language generation becomes bemused by the latest fad and generics seemed to be the thing. So the poor community was lumbered with having to pretend that the optimization of generic sharing was a sensible solution and we have suffered ever since. Of course generic sharing is appropriate for handling types if you must have several types all derived from Float but it seems to me to be a daft way to do procedure parameters. I think there is a strong analogy with the foolishness over tasking (which I went along with I seem to remember). It was equally mad to pretend that the rendezvous and dynamic tasks would solve everything and then have to introduce passive tasks as an optimization. Optimizations should be just that in my view, neat improvements of a modest kind and not distortions pretending to introduce features that are missing in order to give orders of magnitude of improvement. So in Ada 95 we put right the tasking mess by introducing protected objects. This doesn't seem to have been such a terrible burden on implementers because the structural implications were restricted to a smallish part of the implementation. As we know, the introduction of tagged types does enable downward closures to be simulated without recourse to heavy optimizations such as generic sharing. I was originally happy with this (it made an interesting exercise in my book) but latterly I have felt that it is really a bizarre approach. It seems unnatural and, as I hope the example in the AI demonstrates, the distortion is now placed on the user which in many ways is worse since it forces all users to visibly distort their prograsm whereas with optimizations it is partly hidden by the implementation. It is of course unfortunate that the original absence of full procedure parameters enabled and maybe encouraged implementations to use techniques which in many cases are difficult to adapt to meet the features of the AI. I don't really care about the implementation details since I wrote the AI from the point of view of the user. My own compilers for block structured languages always used displays so I am not against displays per se except inasmuch that it had seemed to become the view that displays stood in the way of doing downward closures and hence my remarks. Clearly the AI is not complete and fine detail like convention needs to be added. I could also of course, move the copy of the LSN on which it leans from the appendix into the discussion but that is merely a detail and not of the essence of the matter. Finally, I don't think it matters if all implementations cannot do new features such as downward closures. We are now in a more pragmatic world and clearly they do not matter for many users. Maybe they could go in the Numerics annex or maybe we should have a Hard annex. But I would like to see the feature accepted so that the language is rounded out properly to meet my expectations of 25 years ago. **************************************************************** From: Robert Dewar Sent: Tuesday, September 4, 2001 11:29 AM <> Speakoing for GNAT, the implementation of protected types was a major development effort, and it is by no means complete, in terms of specialized optimizations that we would like to do. So if the judgment is that downward closures are anythying like that big a hit, I would judge the addition out of the question. **************************************************************** From: Ted Baker Sent: Tuesday, September 4, 2001 5:09 PM As one of the implementors for whom Robert speaks, I'd like to affirm that protected types were a major development effort and not "restricted to a smallish part of the implementation". There are complex interactions with tagged types, initialization and finalization, exception propagation, and of course tasking. And, by the way, most of the complexities were not predicted by the published reports on early prototype implementations. They seemed simple, because they did not implement the full language, with all the potential interplays of features, and they were not held to any validation, stress, or performance testing. As usual "the devil is in the details". **************************************************************** From: Dan Eilers Sent: Tuesday, September 4, 2001 6:29 PM Would you go so far as to contend that protected types are more problematic than equivalent passive task optimizations? I agree with the analogy John makes, that the original Ada definition contemplated the need for passive tasks, subprograms as parameters, (and, I would add, untagged class-wide programming), but mistakenly relied on heroic optimizations (passivating tasks and sharing generic bodies) to meet such needs. Such optimizations go against the important principle of programming by contract, since they involve inspection of the task or generic body. Instead, protected types were (properly) made a distinct feature from tasks, and downward closures are (properly) proposed to be distinct from generics. Even if protected types and/or downward closures are problematic, they are presumably not more problematic than the equivalent heroic optimizations. And the user benefits by not having to wonder whether a task passivation optimization or generic body sharing optimization will actually be performed. **************************************************************** From: Robert Dewar Sent: Tuesday, September 4, 2001 8:03 PM <> Absolutely! It would have been far less effort to do passive task optimizations. This is the point that Paul Hilfinger made during the design process. After all several vendors implemented passive task optimizations quite effectively, and indeed we find several customers who really miss passive task optimziations, and find protected types only a partially satisfactory substitute. **************************************************************** From: Ted Baker Sent: Wednesday, September 5, 2001 9:43 AM | Would you go so far as to contend that protected types are more | problematic than equivalent passive task optimizations? No, PT's are not more problematic than passive tasks. It is just that they turned out to be more complicated than first appeared, due to the piling-on of requirements for their use in combination with other language features. Passive tasks had a different problem. They created a design problem for users. ... but I don't want to get trapped into rehashing the whole story. Ironically, some of the complications with protected objects are there because of a recurrence of the reasoning that in Ada 83 made people believe that passive task optimizations were the answer. For example, we knew that allowing 'Count in barrier expressions would require up to three evaluations of the barrier for a protected entry call (before queueing, after queuing, and after completion of the protected body), but it was argued that optimizations would eliminate this overhead in important cases. Similarly with the need to wrap the barrier evaluation with an exception handler, the need to allow for queue reordering with priority changes, etc. We found out that protected objects were not quite so lean and mean as originally conceived, so long as the compiler and runtime system have to handle the worst-case semantics, that there is a practical limit to the number of cases one can optimize for, and that vendors may differ on where they draw the lines for optimizations. Fortunately, even the most general case of a protected object is much lighter weight than an active task, and the simplest form of protected objects (with no entries) is easy enough to optimize that performance there should be uniformly pretty good across all implementations. I just hope that in future language changes we can remember these lessons: 1) Don't believe arguments that rely on complex "smart" optimizations to excuse adding in features that obviously can have high overhead in the general case. 2) Don't believe arguments about a feature being obviously independent of the rest of the language. Think through all the ramifications and interactions with other language features. Don't assume that somebody (implementors, ARG) else will work out the ugly details in a satisfactory way later. **************************************************************** From: David Emery Sent: Wednesday, September 5, 2001 10:14 AM I'd like to add a third (first) lesson: 0) Pay attention to arguments about how features are likely to be used, particularly at the design/pattern level, to determine how sensitive applications will be to the efficient performance of "critical" language features. Ada has both strengths and weaknesses in its support for what we now call 'patterns'. The great strength is Ada's ability to define and abstract away the implementation of a pattern. Ada's weakness is that some of the patterns that looked very attractive at design-time turn out to have significant potential performance problems. **************************************************************** From: Tucker Taft Sent: Tuesday, September 4, 2001 3:07 PM I haven't heard anything which will make this AI particularly complicated from a run-time point of view for those implementations that do use static links. For those that use displays and/or shared generics, we need to be sensitive to what limitations they require to keep the implementation effort appropriate to the benefit. It sounds like Randy has a pretty good idea what limitations he needs, and I would hope that someone with a connection with Aonix would at least be involved enough to feel comfortable with the implementability. I think the big decision is between anonymous access-to-subp and named, limited access-to-subp. I am personally quite comfortable with the choice of anonymous access-to-subp, as that seems the most straightforward and most familiar from other languages like Pascal. Can we at least decide whether we generally agree with the anonymous access-to-subp direction, and then work with Randy and an Aonix rep to make sure we have the right restrictions? Alternatively, perhaps we should take John's idea of restricting it to the Numerics Annex seriously, though that does strike me as a bit out of character with the annexes in general. **************************************************************** From: Robert Dewar Sent: Tuesday, September 4, 2001 3:52 PM There is no good argument for restricting this to the Numerics annex, there is no special argument that this is a place most likely to use this feature (for my own taste, most often the generic solution is quite fine in numeric cases, it is in non-numeric cases that it is likely to be more irritating). **************************************************************** From: Pascal Leroy Sent: Wednesday, September 5, 2001 4:23 AM As I recall, during the 9X process there was the decision that there should be no new syntax in the annexes. Of course we could decide to change that, but I see no good reason for doing so. Moreover, the issue of downward closures exists in applications that don't make use of numerics. So I think it should go into the core language. **************************************************************** From: Randy Brukardt Sent: Wednesday, September 5, 2001 9:48 PM > It sounds like Randy has a pretty good idea > what limitations he needs, and I would hope > that someone with a connection with Aonix would > at least be involved enough to feel comfortable > with the implementability. For what it's worth, I'm in favor of the feature if it can be designed to not force changes in the implementation of existing types (and of course generics). It seems to me (after thinking it over this weekend) that Pascal was correct that allowing conversions from anon A2S to normal A2S would require carrying static links or displays in the objects for nested A2S types. This is not true in Ada 95 (certainly it is not necessary to carry a display, and there seems to be no reason that static links are different here -- it is certainly possible to figure out the appropriate link at the point of the call). > I think the big decision is between anonymous access-to-subp > and named, limited access-to-subp. I am personally quite > comfortable with the choice of anonymous access-to-subp, > as that seems the most straightforward and most familiar > from other languages like Pascal. > > Can we at least decide whether we generally agree with > the anonymous access-to-subp direction, and then work > with Randy and an Aonix rep to make sure we have the > right restrictions? I really dislike the anon A2S syntax. However, allowing them to be named (as John proposed in the AI) would open up another whole can or worms, because we would have to enforce some accessibility to insure that the subprogram would not disappear while the pointer still existed, while truly anon A2S need no checks. (This is the same problem that caused the named anon A2O to crash and burn in Leuven.) So I very reluctantly go along with that syntax. I prefer the limited access type idea, except that it suffers from the same accessibility problem that a named anon A2S has. Perhaps a runtime lifetime check would fix that (although it would be hard to define). > Alternatively, perhaps we should take John's idea of > restricting it to the Numerics Annex seriously, though > that does strike me as a bit out of character with > the annexes in general. Bad idea. I run into this periodically (with iterators, typically), and the Claw Builder doesn't have anything to do with numerics. **************************************************************** From: Robert Duff Sent: Friday, September 7, 2001 6:41 PM I am in favor of going forward with downward closures. I agree with John's point that Ada oughtn't to be weaker than Pascal in this rather important way. (Algol, too, I suppose, although my knowledge of Algol is purely academic -- I've never written a line of it.) I think this is the *only* feature that exists in Pascal but not in Ada. Am I right? Every Ada 95 program I have written, including the one I'm working on now, and probably most Ada 83 ones I worked on, could have made use of better support for iterators. I've written code that used the workarounds (eg the generic iterator), thus cluttering the code and namespace with irrelevant rubbage, and increasing compile times intolerably. And I've written code where the workarounds were so intolerable that I decided to expose the data structure and write "for I in Blah'Range..." or "X := X.Next" or whatever, scattered all over. I hate having to make that tradeoff -- surely the language design should make encapsulation and information hiding easier than the alternatives! I've also written code that uses 'Unrestricted_Access in GNAT. I shouldn't have to use a non-portable and unsafe feature, when the "right" feature has existed for decades in other languages. > LSN 1083 suggested two mechanisms: limited access-to-subprogram types > and access-to-subprogram-parameters. Of these, the second is preferred > because (a) it is close to the techniques in Algol 60 and Pascal, and > (b) it fits in with the existing access parameters. This mechanism is > thus proposed here. The acc-to-subp idea is closer to Pascal syntactically, but I think the limited types idea is closer semantically. Would it make sense to use the syntax of acc-to-subp, but the semantics of limited access types? The main advantage of the acc-to-subp syntax is that there is no need for a type name. That's a good thing, since the type name just clutters the namespace (as do most access type names). I wish we didn't need a name for the procedure being passed, either -- in the iterator case, that's the body of the loop. Loop bodies are not normally named; requiring a name clutters the namespace. I suppose this feature is too much to ask for, though. I see no point in allowing type conversions from anonymous acc-to-subp things to named acc-to-subp types. The only reason to convert to a named type is to save the thing in some data structure, but the accessibility rules require that data structure to be local, which isn't much use. Furthermore, the possibility of the conversions causes inefficiency by requiring an accessibility level to be passed. Downward closures are really a completely separate feature from callbacks (callbacks being the existing acc-to-subp feature in Ada 95). Why allow conversions between them? I am in favor of retaining whatever capabilities Ada 95 has with respect to generic body sharing. Although universal sharing is pretty hard -- as pointed out by Randy and Dan (and results in pretty inefficient code), more limited sharing is a good idea. Note that one way to implement it is to let the user choose when to share (just like users can choose when to inline calls). I'm not sure, but I suspect that this would avoid violating the DEC patent. (And, as others have pointed out, the DEC patent is at least arguably bogus because of prior art. I would testify in court that it's "obvious", too, but nobody has asked me to. ;-) I would think the mere fact that it was independently invented by two different people would be evidence in that direction -- but I'm not a patent lawyer!) Surely Randy and Dan can state the appropriate restrictions (I think somebody already did), so that we don't make generic body sharing any worse than it already is. I don't think we need to give up on downward closures for that reason. The AI talks about static links and displays. I think it should at least mention the trampoline method, as implemented in gcc (and therefore GNAT). The trampoline method is too bizarre for my taste, and it sounds inefficient (to do P'Access), but I've never measured it. Anyway, it is a viable technique. I am against putting the downward closures feature in an optional annex. **************************************************************** From: Robert Dewar Sent: Friday, September 7, 2001 6:41 PM <> The use of trampolines is orthogonal to whether displays or static links are used, although in practice it would be pretty gruesome to have a trampoline that loaded a display, so in practice trampolines are used with static links. But in no sense do they someone represent a third method. The point of a trampoline is simply to avoid the use of a fat pointer. There are two gains from the use of trampolines 1. Subprogram pointers are only one word long, which tends to be an assumption in C. 2. You do not pay for loading a static link in the normal case where the pointer points to a global procedure. **************************************************************** From: John Barnes Sent: Tuesday, January 22, 2002 10:13 AM I just sent a new version of AI-254 on downward closures to Randy so I guess it will be on the net soon. I felt that you might like to hear a further moan from me on the topic. Over Christmas I needed to solve a pair of non-linear algebraic equations. I turned to Ada, my favourite language for hacking such things. I quickly knocked up a general Newton-Raphson thing hoping that it would be simple enough to pass the functions to be solved as as access-to-function taking a vector and returning a vector. But I immediately fell into the downward closures pit. I had to make a lot of stuff global that shouldn't have been. In fact I ended up with a package named Variables and context clauses saying with Variables; use Variables; everywhere. Disgusting. Clearly I should have called the package F_Global_Common. I am permanently amazed that what I did so easily in 1962 using Algol 60 is beyond Ada 95 without introducing various steamhammers. End of moan. **************************************************************** From: Robert Dewar Sent: Tuesday, January 22, 2002 6:53 AM I am a little surprised that this particular problem was not trivially solved using a generic procedure. ****************************************************************