!standard 12.5.2 (00) 00-10-30 AC95-00003/01 !class amendment 00-10-30 !status received no action 00-10-30 !subject Generic formal parameter control for generic sharing !summary !appendix From: Dan Eilers Sent: Thursday, October 19, 2000 11:51 AM !topic floating-point shared generic bodies with unchecked_conversion !from Dan Eilers !discussion The attached email from Robert Dewar mentions an unresolved issue with sharing generic bodies when more than one floating-point type exists. This hole should be fixed (one way or another), so that vendors such as ourselves that do such sharing are not perceived to be "cheating" in any way. Possible fixes (not mutually exclusive) include: 1) noting that unchecked_conversion may not work properly in this case; 2) disallowing unchecked_conversion in this case; 3) strengthening the contract model by providing a mechanism for the user to declare in the generic formal part that all instantiations of the generic will use actual parameters of a particular size, allowing the compiler to generate shared code based on that assumption and reject any other instantiations; 4) providing a way for the user to declare that the compiler should create more than one shared executable version of the body, where the version of the body to be used for a particular instantiation is selected based on user-specified characteristics of the actual generic parameter(s). 5) provide a way for the user to declare more than one source-code version of a body for a generic unit, with the version of the body to be used for a particular instantiation is selected based on user-specified characteristics of the actual generic parameter(s). Note that DEC has a patent that if presumed to be valid prevents other compilers from automatically doing #4, but it does not appear to prevent languages from having mechanisms for user-controlled sharing of generics based on properties of the actual generic parameters. The abstract of the DEC patent is attached below. -- Dan Eilers ======================================================================= To: ARG@acm.org, dan@irvine.com Subject: Re: Draft Agenda, Laurel ARG mtg. Message-Id: <20001017000729.46C4E34D82@nile.gnat.com> Date: Mon, 16 Oct 2000 20:07:29 -0400 (EDT) From: dewar@gnat.com (Robert Dewar) By the way, it seems there are many unresolved issues for full implementation of sharing, especially if you have more than one floating-point type, because then doing unchecked conversion properly in the shared object is really quite complex for example. The only compilers I know of doing generic sharing either had one fpt type (Rational) or cheated and did UC wrong (RR). cheated should of course be in quotes there, indeed it is hard to see how else you could do it except by approximating there. Indeed at one point there was an attempt to change the RM to allow this particular problem to be solved. I suspect there are many other similar problems lurking. ======================================================================= _________________________________________________________________ United States Patent 5,280,617 Brender , et al. January 18, 1994 _________________________________________________________________ Automatic program code generation in a compiler system for an instantiation of a generic program structure and based on formal parameters and characteristics of actual parameters Abstract A compiler maintains a library of sharable program structures generated in response to instantiations of a generic program structure, along with characteristics of parameters which were used in generating the sharable program structure. In response to an instantiation of a generic program structure, the compiler generates information relating to the characteristics and usage of each parameter which are used in connection with the instantiation. The compiler then compares that information to the corresponding information associated with the sharable program structures in the library. If the library contains a sharable program structure whose parameter information compares satisfactorily, that sharable program structure is used in connection with further operations in connection with the instantiation. On the other hand, if the library does not contain such a sharable program structure, one is generated and stored in the library, along with the characteristics of the parameters used in its generation, for use in sharing with later instantiations. In addition, the just-generated sharable program structure is used in further operations in connection with the instantiation. _________________________________________________________________ **************************************************************** From: Tucker Taft Sent: Thursday, October 19, 2000 2:39 PM Unfortunately Robert's email does not provide an example of the problem. Can you include a detailed explanation of the problem for those of us that forget it? For most such sharing problems, I have frequently heard the solution to be simply adding another "thunk" to the instantiation descriptor, though I don't know how realistic that is for unchecked conversion. > Note that DEC has a patent that if presumed to be valid prevents other > compilers from automatically doing #4, This patent is definitely not valid. Intermetrics engineer Gary Bray published (in a SIGPlan conference proceedings) many years before essentially the same algorithm that DEC patented. From a pragmatic point of view, DEC is almost certainly not interested in trying to defend the patent. > ... but it does not appear to prevent > languages from having mechanisms for user-controlled sharing of generics > based on properties of the actual generic parameters. The abstract of > the DEC patent is attached below. In any case, you could certainly provide pragmas that do (3) .. (5) [(1) and (2) sound like a cure that is worse than the disease]. It is not clear that it is worth at this point trying to standardize such pragmas. There was some thought that pragma Optimize(Space) or pragma Optimize(Time) might be used to select shared versus macro-expanded approaches, but I don't know if any vendor followed up on that idea. **************************************************************** From: Randy Brukardt Sent: Thursday, October 19, 2000 3:09 PM > Unfortunately Robert's email does not provide an example > of the problem. Can you include a detailed explanation of > the problem for those of us that forget it? For what it's worth, I don't think that there is any such problem, at least not for generic float types. The problem with Janus/Ada stems from our (self-imposed) rule that the size of both operands of the unchecked conversion match. (We have found that this rule catches a lot of errors, and it also avoids the need to define what happens if there aren't enough bits, or too many bits). In order to avoid contract model problems, we check this rule in generic bodies in an assume-the-worst manner. The result is that most generic formal types can't be converted (because the size isn't known). If we didn't care about that, implementing the conversion would be easy (at least if we don't care about leftover bits). We'd just use the thunk that already exists to handle accesses through general access types, which has to be prepared to read/write in the format of the original type. For example, to go from a GFLT to an Integer, we would just allocate some scratch space in the largest possible size (which is known, of course), use the thunk to write the value to it, cast the address as a ptr to Integer, and go on. And the reverse conversion is about the same. The issue Robert remembers originally came up with the unchecked conversions of generic discrete types to packed arrays of Boolean in the ACVC. That is a somewhat messier case, because both items depend on the generic. In this case, we rejected the conversion because the array of Boolean (which depended on 'Size of the generic discrete type) did not have a static constraint. We've since changed our compiler model which would eliminate that problem (at least if we ever got bit packed arrays to work...); but we still have the assume-the-worst check. I would have been happy if there was a permission for the instantiation (or call) to raise an exception if the sizes don't match. (Note that I'm generally talking about the "Object_Size" [in more-or-less the GNAT sense], not necessarily 'Size.) The Ada 95 RM essentially gives that permission (all of the discussion I think was in the context of Ada 83 which definitely did not have such a permission; in any case we've made no real changes in UC in a long time), so I don't think there is any specific problem that the ARG need discuss here. In all probability, we would make the conversion work if the size matched, and raise Program_Error otherwise. No problem. The more general issue of additional mechanisms to support sharing certainly would be worth discussing in any case. (But of course that is an amendment AI.) **************************************************************** From: Robert Dewar Sent: Friday, October 20, 2000 11:00 AM I do not think this is important enough to fix at this stage. Most certainly the idea of disallowing UC is quite unacceptable, as is the idea of allowing it not to work. Basically my feeling is that we should not modify the language in any restrictive way to accomodate shared generics at this stage. Implementations are free to rig up pragmas etc to restrict things anyway they like, no language change is appropriate. **************************************************************** From: Dan Eilers Sent: Saturday, October 21, 2000 1:08 PM Tuck wrote: > Unfortunately Robert's email does not provide an example > of the problem. Can you include a detailed explanation of > the problem for those of us that forget it? > > For most such sharing problems, I have frequently heard > the solution to be simply adding another "thunk" to the > instantiation descriptor, though I don't know how realistic > that is for unchecked conversion. I think the problem is that such a "thunk" would copy only 32 bits if the instantiation was for short-float, and that this would not copy all 64 bits of variables declared within the generic and implemented as a 64-bit float. Since the representation of 64-bit floats is different from 32-bit floats, copying only the first 32-bits is fatal. > In any case, you could certainly provide pragmas that > do (3) .. (5) [(1) and (2) sound like a cure that is worse > than the disease]. Since facilitating generic code sharing was a formal Ada9x requirement, relying on implementation-defined pragmas doesn't seem to be the right solution to problems that aren't implementation specific. > There was some thought that pragma Optimize(Space) or > pragma Optimize(Time) might be used to select shared > versus macro-expanded approaches, but I don't know if > any vendor followed up on that idea. We didn't. These pragmas don't address the problem of "cluster analysis", identifying groups of instantiations for which the user wants a shared a generic body. **************************************************************** From: Robert Dewar Sent: Saturday, October 21, 2000 7:30 PM <> So what? That's not a justification for upwards incompatible changes this late in the game. My own opinion is that it is not worth spending any more time at this stage modifying the language to further ease generic sharing. **************************************************************** From: Tucker Taft Sent: Sunday, October 22, 2000 9:56 PM Dan Eilers wrote: > I think the problem is that such a "thunk" would copy only 32 bits > if the instantiation was for short-float, and that this would not > copy all 64 bits of variables declared within the generic and > implemented as a 64-bit float. Since the representation of 64-bit > floats is different from 32-bit floats, copying only the first 32-bits > is fatal. I presume the thunk would have to do the "right thing" whatever that might be. So if the short float values are really being represented as longer floats, then the thunk would presumably convert them to the "official" representation expected by unchecked conversion. The "usual" unchecked conversion process could then actually do the conversion/bit copy, and then conceivably a different thunk might be invoked to convert back from the "official" representation to the "shared" representation. > Since facilitating generic code sharing was a formal Ada9x requirement, > relying on implementation-defined pragmas doesn't seem to be the right > solution to problems that aren't implementation specific. What is doable and practical in the way of generic sharing still seems very much dependent on implementation-specific details of an implementation, so it does not seem unreasonable that the pragmas would be implementation-specific. Certainly if there are a group of vendors with a real interest in generic sharing, it might be worth their sharing ideas about generic sharing pragmas. However, there doesn't seem to be enough of a groundswell of interest, nor adequate expertise, probably, in the ARG, to make it seem worthwhile for the ARG to spend energy on this now. A well researched proposal, including information from multiple vendors' implementation approaches, might be of interest. But at the moment, this seems relatively low priority. > > There was some thought that pragma Optimize(Space) or > > pragma Optimize(Time) might be used to select shared > > versus macro-expanded approaches, but I don't know if > > any vendor followed up on that idea. > > We didn't. These pragmas don't address the problem of "cluster analysis", > identifying groups of instantiations for which the user wants a shared > a generic body. For our implementation, we never considered "universal" generic sharing, we only considered the cluster analysis, and so for us, pragma Optimize(Space) would have triggered the cluster analysis. I can see that if you plan to have 3 approaches (macro, universal, and cluster), then pragma Optimize wouldn't give enough flexibility. **************************************************************** From: Robert Dewar Sent: Sunday, October 22, 2000 11:04 PM In any case it seems probably more appropriate to introduce a separate pragma. Note that DEC has already defined pragma Shared_Generic. **************************************************************** From: Dan Eilers Sent: Monday, October 23, 2000 3:26 AM Robert Dewar wrote: > < relying on implementation-defined pragmas doesn't seem to be the right > solution to problems that aren't implementation specific. > >> > > So what? That's not a justification for upwards incompatible changes > this late in the game. My own opinion is that it is not worth spending > any more time at this stage modifying the language to further ease > generic sharing. What is it in my 5 possible suggested fixes that appears upwards incompatible to you, other than perhaps #2, disallowing unchecked_conversion in circumstances where it can't be correctly implemented? I would recommend one of solutions 3..5, for which I see no upward incompatibility problems at all. Paragraph 10 of the Introduction to the RM states: "Every construct of the language was examined in the light of present implementation techniques. Any proposed construct whose implementation was unclear or that required excessive machine resources was rejected." This statement is not true with respect to generics with floating-point formal parameters, such as the predefined generic_elementary_functions package. There is no clear and efficient way to implement this package, or similar packages defined by the user. **************************************************************** From: Robert A Duff Sent: Monday, October 23, 2000 10:45 AM > Paragraph 10 of the Introduction to the RM states: > "Every construct of the language was examined in the light of > present implementation techniques. Any proposed construct whose > implementation was unclear or that required excessive machine > resources was rejected." > > This statement is not true with respect to ... I wish this was the *only* case where paragraph 10 turned out not to be true... ;-) **************************************************************** From: Robert Dewar Sent: Wednesday, October 25, 2000 8:11 AM <> The "perhaps" is rather amazing in the above sentence! **************************************************************** From: Dan Eilers Sent: Monday, October 23, 2000 3:53 AM Tuck wrote: > > I think the problem is that such a "thunk" would copy only 32 bits > > if the instantiation was for short-float, and that this would not > > copy all 64 bits of variables declared within the generic and > > implemented as a 64-bit float. Since the representation of 64-bit > > floats is different from 32-bit floats, copying only the first 32-bits > > is fatal. > > I presume the thunk would have to do the "right thing" whatever > that might be. So if the short float values are really being > represented as longer floats, then the thunk would presumably > convert them to the "official" representation expected by > unchecked conversion. The "usual" unchecked conversion process > could then actually do the conversion/bit copy, and then > conceivably a different thunk might be invoked to convert back > from the "official" representation to the "shared" representation. I don't think there is any way the "thunk" could in general know whether its parameter was a 64-bit object declared within the generic, or a 32-bit object declared outside the generic. So it would be impossible to do the "right thing". > What is doable and practical in the way of generic sharing > still seems very much dependent on implementation-specific > details of an implementation, so it does not seem unreasonable > that the pragmas would be implementation-specific. I would think the difficulties of sharing between instantiations of different object representations would be common to all implementations, and that providing a mechanism to assure that sizes (and alignments) would be the same would make such shared generics relatively straightforward to implement in all implementations. The issues are very similar if not identical to the criteria for efficient implementation of view conversions. **************************************************************** From: Tucker Taft Sent: Monday, October 23, 2000 10:34 AM Dan Eilers wrote: > > Tuck wrote: > ... > > I presume the thunk would have to do the "right thing" whatever > > that might be. So if the short float values are really being > > represented as longer floats, then the thunk would presumably > > convert them to the "official" representation expected by > > unchecked conversion. The "usual" unchecked conversion process > > could then actually do the conversion/bit copy, and then > > conceivably a different thunk might be invoked to convert back > > from the "official" representation to the "shared" representation. > > I don't think there is any way the "thunk" could in general know > whether its parameter was a 64-bit object declared within the generic, > or a 32-bit object declared outside the generic. So it would be > impossible to do the "right thing". I obviously don't know how your compiler works, but I would certainly presume that the compiler knows whether it is dealing with a 32-bit object declared outside the generic, or a 64-bit object that is inside, and it would only generate a call on the thunk when it needed an "extra" conversion to be performed. > > What is doable and practical in the way of generic sharing > > still seems very much dependent on implementation-specific > > details of an implementation, so it does not seem unreasonable > > that the pragmas would be implementation-specific. > > I would think the difficulties of sharing between instantiations > of different object representations would be common to all > implementations, and that providing a mechanism to assure that sizes > (and alignments) would be the same would make such shared generics > relatively straightforward to implement in all implementations. > The issues are very similar if not identical to the criteria for > efficient implementation of view conversions. I've lost track of where we are going with this discussion. Feel free to make a formal proposal, but I don't know if you will find sufficient interest for it to become a high priority standardization issue. It may be better to lead by example in a case like this, that is, implement something that you think others will want to emulate, and then suggest it for standardization at some point. Because we are just talking about a pragma, which is presumably going to be of an advisory nature in any case, it can progress at its own rate as far as standardization, it doesn't need to ride some kind of Ada 2005 train (though I'm not convinced there will be any sort of thing). **************************************************************** From: Robert A Duff Sent: Monday, October 23, 2000 12:53 PM > That's far too expensive, you don't want to pass a UC thunk for every > case where a generic float parameter is involved. But what else can you do, if you want to always-share, and you want UC to work? It seems to me the always-share model involves a LOT of thunk-izing, and many of those thunks are necessarily very inefficient. This isn't the only case. If you choose this model, you're necessarily making a big trade-off for compile-time efficiency at the expense of run-time efficiency. Remember I'm talking *always* share, here. By the way, the thunk-izing of float UC is worse than anyone's mentioned: what about UC of an array of floats, or UC of access to array of floats? I do have a great deal of sympathy with the idea that the language ought to make shared bodies feasible -- as illustrated by some of the AARM quotes Dan Eilers posted. **************************************************************** From: Dan Eilers Sent: Monday, October 23, 2000 2:03 PM Tuck wrote: > > I don't think there is any way the "thunk" could in general know > > whether its parameter was a 64-bit object declared within the generic, > > or a 32-bit object declared outside the generic. So it would be > > impossible to do the "right thing". > > I obviously don't know how your compiler works, but I would > certainly presume that the compiler knows whether it is > dealing with a 32-bit object declared outside the generic, > or a 64-bit object that is inside, and it would only generate > a call on the thunk when it needed an "extra" conversion > to be performed. The way our compiler works, and the way I presume every compiler works, there is never more than one flavor of a subprogram that the compiler must choose between based on the location of its arguments. If the unchecked_conversion function were itself passed as an actual parameter to yet another shared generic, which flavor would you pass, the one that expects 64-bit parameters or the one that expects 32-bit parameters? > I've lost track of where we are going with this discussion. > Feel free to make a formal proposal, but I don't know if > you will find sufficient interest for it to become a high > priority standardization issue. It may be better to lead > by example in a case like this, that is, implement something > that you think others will want to emulate, and then > suggest it for standardization at some point. Because > we are just talking about a pragma, which is presumably going > to be of an advisory nature in any case, it can progress > at its own rate as far as standardization, it doesn't need > to ride some kind of Ada 2005 train (though I'm not convinced > there will be any sort of thing). My proposal would probably _not_ be based on a pragma. Instead, I would probably allow abstract generic units. Such a unit could not be instantiated until it was made concrete, and would not necessarily include a body. It could be made concrete by "constraining" formal parameters, and/or supplying a body, where "constraining" includes restricting the allowable parameters to a single class-wide type. **************************************************************** From: Randy Brukardt Sent: Monday, October 30, 2000 8:41 PM This silliness has gone on long enough. You cannot implement Ada 95 with that model. Period. I tried for years, but gave it up some years ago, faced with too many examples that are unimplementable. You have to implement (universally) shared generics in Ada 95 with the model that (almost) all objects are represented in the representation of the actual type. (You can make an exception for stand-alone non-aliased objects if you want; Janus/Ada does so only for for loop objects). If you try the model of using the largest representation in the body of the generic, you will be finding bugs forever. If I remember right, the example that caused me to give it up looked something like: generic type A_Float is digits <>; type An_Array_of_Float is array (Character) of A_Float; type A_Ptr_at_Array_of_Float is access all An_Array_of_Float; package My_Generic is My_Object : aliased An_Array_of_Float; type Another_Array_of_Float is array (Character) of A_Float; Another_Object : aliased Another_Array_of_Float; function Return_Ptr_at_Array return A_Ptr_at_Array_of_Float; end My_Generic; package body My_Generic is function Return_Ptr_at_Array return A_Ptr_at_Array_of_Float is begin if then return My_Object'Unchecked_Access; else return Another_Object'Unchecked_Access; end if; end Return_Ptr_at_Array; end My_Generic; If A_Float is always represented as a 64-bit float, an instantiation of this with a 32-bit float type would make the array objects have 64-bit components. But, outside of the generic, these components would be referenced as 32-bit objects. Immediate death. You could thunk the generic formal type somehow, but the local object and type could have been implemented in the body, so you can't thunk it. I wasn't able to find anyway around this that was worth bothering with. So I changed to the model that these sorts of things are *allocated* as 64-bits, but that the real representation is used. (This does mean that the 'Component_Size of such arrays is not static inside the generic body, but that is not a major problem - it just means you have to use a multiply always [no "shift" optimizations are possible]). (Note that this wasn't the only problem by any means, it just was the last straw problem.) If you're doing cluster sharing; then the problem doesn't arise: just don't cluster types with different base type representations. > > I've lost track of where we are going with this discussion. > > Feel free to make a formal proposal, but I don't know if > > you will find sufficient interest for it to become a high > > priority standardization issue. It may be better to lead > > by example in a case like this, that is, implement something > > that you think others will want to emulate, and then > > suggest it for standardization at some point. Because > > we are just talking about a pragma, which is presumably going > > to be of an advisory nature in any case, it can progress > > at its own rate as far as standardization, it doesn't need > > to ride some kind of Ada 2005 train (though I'm not convinced > > there will be any sort of thing). > > My proposal would probably _not_ be based on a pragma. > Instead, I would probably allow abstract generic units. > Such a unit could not be instantiated until it was made concrete, > and would not necessarily include a body. It could be made concrete > by "constraining" formal parameters, and/or supplying a body, > where "constraining" includes restricting the allowable parameters > to a single class-wide type. I agree with Tucker in the sense that I don't see a proposal here, just a long discussion about an implementation model that doesn't work. (It *did* work in Ada 83, so some of us used it, and stuck to it long past the point of sanity...) Note that the only effect of not being able to use the "use the largest rep." implementation is simply one of performance; it certainly does not make it any harder to implement shared generics. I could see some performance benefit to having pragmas/syntax to restrict the instantiatably of generic parameters. However, I wonder if any users would actually use something like: generic type A_Float is digits <>; for A_Float'Size use 32; ... Anyway, as editor, I'm not sure what to do with this discussion. There doesn't seem to be a question; the original issue is based on a misconception of how shared generics are implemented. I'd like to save the discussion, but there doesn't seem to be an AI at this point. It looks like an amendment proposal would be in order. **************************************************************** From: Dan Eilers Sent: Wednesday, November 01, 2000 8:03 PM Randy wrote: > You cannot implement Ada 95 with that model. Period. I tried for years, but > gave it up some years ago, faced with too many examples that are > unimplementable. > > You have to implement (universally) shared generics in Ada 95 with the model > that (almost) all objects are represented in the representation of the > actual type. (You can make an exception for stand-alone non-aliased objects > if you want; Janus/Ada does so only for for loop objects). > > If you try the model of using the largest representation in the body of the > generic, you will be finding bugs forever. There is of course absolutely no point in sharing a generic body if the code in the shared body doesn't know what size objects it is dealing with. The resulting shared code would be laughable. > If you're doing cluster sharing; then the problem doesn't arise: just don't > cluster types with different base type representations. We are in violent agreement here. The key to practical shared generics is that the compiler must not be expected to generate code that works simultaneously with different sized objects. I am suggesting that the user should have control in this area, rather than hoping for the best from the compiler, for much the same reasons that the user was given control in Ada95 with protected records, rather than hoping that the compiler could figure out which tasks didn't really need a thread of control. The evidence has shown that compilers can't generally be trusted to do a good job of automatic cluster analysis. ****************************************************************