sommar@enea.se (Erland Sommarskog) (12/31/88)
Bob Hathaway (rjh@cs.purdue.edu) writes: >For yet another Ada 9X extension, I propose procedural variables. >... >Procedural variables can >avoid the redundant use of case statements by allowing an operation to be >stored within an Adt. I have stated my view before: a langauge revision should not introduce major changes, but stick to an overview of details that needs refining, like character representation. There is one exception, though: if someone comes up with a fully-fledged extention to give Ada dynamic binding to make it a truly object-oriented langauge, I would whole-heartedily support that proposal. From this it is clear I think Bob Hathaway's idea should be rejected. There are some gains with it, but not suffciently many. We will move some tiny step against the O-O paradigm, but we will not be there. Just for discussion: If we should make Ada an object-oriented langauge, what should we add? Quite obvious seems package types to get classes. If we could create several instances of a package, you have what Bob wanted and more. You have data *and* operations stored together. But this doesn't suffice. This far we have just constructed task types doesn't cost us a context change. We must have inheritance in some way. How tell which other package types we inherit from? The WITH clause is not useful; it merely tells us which types we intend to declare objects of. USE? Maybe. Doing USE on a package type to get all exported operations directly visible is of no interest. We should USE the package variable instead. But for inheritance we want all attributes, also those who do not appear in the specification part (or?), and particulary we probably want to have access to private types internal structure. So best would be a particular INHERIT clause. Multiple inheritance? That doesn't seem to be any problem. Ada already has RENAMES which here could serve to remove clashes. Dynamic binding? We must be able to redefine a inherited operation. There is no current construct for that in Ada so a REDEFINES clause has to be added. (Rather useful is also deferred procedures that inhereting packages *must* define, Ada more or less has this concept.) We are about satisfied by now. Probably we need delaration a la Eiffel, but if we could make all the rest, this would be no problem. Procedure types could be added for completeness, but doesn't feel that necessary with all we added above. Now, it is not as easy as this of course. Many detail rules has to be thought out. And we would get an unnecessary big language. Would we really need the sophisticated system with subtypes and derived types? Well, we can't throw it away. Oh, one we need one more thing if go this way. Yes, you guessed it: Garbage collection. >It also allows individually parameterizable and >reprogrammable Adts since operations can be provided to alter the Adts actions >or structure. Generic subprogram parameters can only allow Adts to be set >once for any instantiation. I use procedural variables and function pointers >in Adts frequently when programming in languages other than Ada and am >convinced they are an elegant way to model Adt actions. With the risk of saying something completely obvious: if you want variable user-provided operations the following example with a tree-traversing illustrates: Generic Type Data_type is limited private; With procedure Assign(A : in out Data_type; B : in Data_type); With function "<"(A, B : Data_type) return boolean is <>; With function ">"(A, B : Data_type) return boolean is <>; Package Binary_trees is Type Tree_type is private; -- A tree with sorted data. Type Node_type is private; -- A node in such a tree. ... Generic With Procedure Treat(Node : in Node_type; Data : in out Data_type); Procedure Traverse_forward(Tree : Tree_type); (By the way, an example like the one above should be added to the validation suite if it's not already there. A PC compiler I played with choked on the code above, and I believe it is/was validated.) -- Erland Sommarskog ENEA Data, Stockholm This signature is not to be quoted. sommar@enea.se
rjh@cs.purdue.edu (Bob Hathaway) (01/01/89)
Newsgroups: comp.lang.ada Subject: Procedure types and dynamic binding Message-ID: <4204@enea.se> Date: 30 Dec 88 21:42:42 GMT Organization: ENEA DATA AB, Sweden Lines: 84 From Erland Sommarskog: >Bob Hathaway (rjh@cs.purdue.edu) writes: >>For yet another Ada 9X extension, I propose procedural variables. >>... >>Procedural variables can >>avoid the redundant use of case statements by allowing an operation to be >>stored within an Adt. >I have stated my view before: a language revision should not introduce >major changes, but stick to an overview of details that needs refining, >like character representation. There is one exception, though: if someone I disagree. While it's not difficult to design new languages with powerful constructs and methodologies it is difficult to get them standardized and accepted. Validated Ada compilers are available on almost every machine and extending Ada with more modern constructs will at least provide one commonly available modern programming language, even if only for designing better ones ;-) >comes up with a fully-fledged extension to give Ada dynamic binding to >make it a truly object-oriented language, I would whole-heartedily >support that proposal. In "Concurrency and Programming Languages" by David Harland, as sited by Bill, dynamic and static binding are provided as a module option. I think this is an excellent idea since most of the literature gives a mind set of one type of binding or the other, with the obvious general solution being to provide both. Another issue is the level of encapsulation in Ada dynamic binding should be provided. Dynamic binding of procedures and functions within a package is possible, but so is dynamic binding of packages. Which did you mean? >From this it is clear I think Bob Hathaway's idea should be rejected. >There are some gains with it, but not suffciently many. We will move >some tiny step against the O-O paradigm, but we will not be there. Procedural variables are orthogonal to "O-O" programming, they can be used for a number of purposes. Some typical uses are tables of procedural variables with generator functions and configuring device driver tables. Array aggregates are easier to modify than in-line code and initializing tables of procedural variables with aggregates using named associations would make programs easy to read. While tables do not always provide the best interface to programmers, I think some circumstances justify their use. >Just for discussion: If we should make Ada an object-oriented langauge, >what should we add? Quite obvious seems package types to get classes. >If we could create several instances of a package, you have what Bob >wanted and more. You have data *and* operations stored together. Yes, this is the "Completion of the Adt paradigm" Bill mentioned earlier. In a compilers class at Purdue, I implemented a class type structure which contained its data and operations including initialization code, and termination code would have been easy to provide as well. But these operations were hardwired into the declaration and a general facility to change Adt operations is desirable. For example, I might want an instance to output data in one way but under other circumstances output data in another. If an output operation is implemented as a procedural variable, I could provide a change_output operation which changes the output operation in the Adt. Thereafter, the new print routine would be in effect whenever the output operation is invoked. [ More about the virtues of inheritance... ] >Now, it is not as easy as this of course. Many detail rules has to >be thought out. And we would get an unnecessary big language. Would >we really need the sophisticated system with subtypes and derived >types? Well, we can't throw it away. I don't think procedural variables or class structures will make Ada much bigger. Procedural variables are not complicated in Modula and from my experience class type structures are not difficult to implement and do not complicate the language. They would, however, provide an incremental improvement in data abstraction. >With the risk of saying something completely obvious: if you want variable >user-provided operations the following example with a tree-traversing >illustrates: > > Generic > Type Data_type is limited private; > With procedure Assign(A : in out Data_type; B : in Data_type); > With function "<"(A, B : Data_type) return boolean is <>; > With function ">"(A, B : Data_type) return boolean is <>; > Package Binary_trees is > Type Tree_type is private; -- A tree with sorted data. > Type Node_type is private; -- A node in such a tree. > ... > Generic > With Procedure Treat(Node : in Node_type; > Data : in out Data_type); > Procedure Traverse_forward(Tree : Tree_type); > This isn't what I had in mind. What if variables of type Tree_Type should be traversed in different ways depending on context? As above, a case statement is needed to choose the routine to parameterize Traverse_forward whenever traversal is invoked. A scheme is needed to allow Tree_Type Adts to be programmed with different traversal routines after its declaration has been elaborated and without the need for case statements. If Traverse_forward invoked a procedural variable stored within Tree_Type then instances of a Tree_Type Adt could be reprogrammed to traverse the tree however desired and a simple call to Traverse_forward would produce the desired result. I think this is in harmony with 'O-O' programming, which I usually refer to as Adt programming, since the operation is stored in the Adt as a procedural variable. Bob Hathaway rjh@purdue.edu
billwolf@hubcap.clemson.edu (William Thomas Wolfe,2847,) (01/05/89)
From article <4204@enea.se>, by sommar@enea.se (Erland Sommarskog): > Just for discussion: If we should make Ada an object-oriented langauge, > what should we add? Quite obvious seems package types to get classes. I'd think classes would be defined a bit differently! A package could contain declarations of variables, and we certainly don't want variables included in a class definition (where class is defined as an abstraction over types, e.g., FRUIT as an abstraction over APPLEs, ORANGEs, etc.). A class of types would consist of the name of the class, in conjunction with a set of operations which must be available over a given type in order for it to be considered a member of the class. Then the use of generics would be reduced substantially; we could simply write function MAKE_JUICE (OUT_OF : in out FRUIT) return JUICE; and this would operate on any type of object (APPLEs, ORANGEs, etc.) which satisfied the definition of a FRUIT. There would still be a need for generics in situations where values or objects are required as generic parameters. (BTW, the above example is also an example of why the stupid rule about functions having only "in" parameters needs to be repealed...) > But for inheritance we want all attributes, also those who do not > appear in the specification part (or?), and particulary we probably > want to have access to private types internal structure. ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ One of the most fundamental aspects of the ADT paradigm is that an object is known to the outside world only as a type definition and a set of predefined operations. This provides the independence which allows us to compile specifications and implementations separately. Access to the internal structure of a private type violates the entire concept of a "private" type. To achieve this effect, one can simply declare the type in question as a visible type rather than a private type. In other words, simply avoid using private types. Be warned, however, that terrible compilation dependencies will result, and you will lose the freedom to replace one implementation with another; in short, the method is NOT recommended for serious use, and is presented only as a theoretical means of achieving what you seek (in my view, misguidedly). > Probably we need delaration a la Eiffel, [...] Gee, why don't we just make "Ada" an alias for "Eiffel"? :-) :-( Seriously though, there *is* a comp.lang.eiffel. Perhaps you would feel more at home there rather than in comp.lang.ada. > With the risk of saying something completely obvious: if you want variable > user-provided operations the following example with a tree-traversing > illustrates: > > Generic > Type Data_type is limited private; > With procedure Assign(A : in out Data_type; B : in Data_type); > With function "<"(A, B : Data_type) return boolean is <>; > With function ">"(A, B : Data_type) return boolean is <>; > Package Binary_trees is > Type Tree_type is private; -- A tree with sorted data. > Type Node_type is private; -- A node in such a tree. > ... > Generic > With Procedure Treat(Node : in Node_type; > Data : in out Data_type); > Procedure Traverse_forward(Tree : Tree_type); > > (By the way, an example like the one above should be added to the validation > suite if it's not already there. A PC compiler I played with choked on the > code above, and I believe it is/was validated.) Why does Node need to be a parameter of Treat? All you need is something that will treat Data once Traverse_Forward has extracted it from the Node. Once you've removed the unnecessary parameter, your package should compile perfectly. Bill Wolfe wtwolfe@hubcap.clemson.edu
billwolf@hubcap.clemson.edu (William Thomas Wolfe,2847,) (01/05/89)
From article <5753@medusa.cs.purdue.edu>, by rjh@cs.purdue.edu (Bob Hathaway): > Erland writes: >>I have stated my view before: a language revision should not introduce >>major changes, but stick to an overview of details that needs refining, >>like character representation. There is one exception, though: if someone > > I disagree. While it's not difficult to design new languages with powerful > constructs and methodologies it is difficult to get them standardized > and accepted. Validated Ada compilers are available on almost every machine > and extending Ada with more modern constructs will at least provide one > commonly available modern programming language, even if only for designing > better ones ;-) I have to agree with Bob. Since old Ada and new Ada would be fairly similar, automatic translators would probably be highly effective should the need arise. >>comes up with a fully-fledged extension to give Ada dynamic binding to >>make it a truly object-oriented language, I would whole-heartedily >>support that proposal. > > In "Concurrency and Programming Languages" by David Harland, as sited by > Bill, dynamic and static binding are provided as a module option. I think > this is an excellent idea since most of the literature gives a mind set of > one type of binding or the other, with the obvious general solution being to > provide both. Um, hold on there. I cited Harland primarily as an example of extreme steps which would provide maximum support for abstraction, and I support Harland's view that departures from the state of maximum expressiveness must bear the burden of proof, but I also noted that there are certain situations in which I think a convincing case can be made in this direction. Most languages, though, go much too far in their restriction of expressiveness, including Ada. (Still, Ada is the best language available, all things considered.) As far as dynamic binding goes, I think there is a need to provide the ability to have a program edit (or generate) a piece of source code, compile that code (including any necessary recompilations), dump any necessary local knowledge for its successor to load in, initiate its successor, and finally kill itself off, but I see no need to go any farther than that. Harland gives a rather eloquent statement of why systems must be self-modifying, and this argument is convincing. But dynamic binding (as I understand the term) is "too changeable", like the uncontrolled change which occurs in some inheritance-oriented languages. Ada's compilation control facilities enable controlled change; they provide firewalls against modification which serve to require that all aspects of the propagating change(s) are considered throughout the system, and this is a very good thing which we should not dispense with lightly. Even the scheme I've described should be applied only with extreme caution. > [...] a general facility to change Adt operations is desirable. For > example, I might want an instance to output data in one way but under > other circumstances output data in another. If an output operation is > implemented as a procedural variable, I could provide a change_output > operation which changes the output operation in the Adt. Thereafter, > the new print routine would be in effect whenever the output operation > is invoked. Other than doing things as I've described above, another way would be (assuming that New Ada expands the idea of a specification to include any accesses to externally defined objects/definitions) to have the output procedure examine its environment to decide what to do. > I don't think procedural variables or class structures will make Ada > much bigger. Procedural variables are not complicated in Modula [...] But Modula doesn't have generics. Using the combination of generics and the class abstraction outlined in my earlier article, I think we'll get more power, with better readability. > This isn't what I had in mind. What if variables of type Tree_Type should > be traversed in different ways depending on context? Just make basic traversal operations a part of your abstraction. Bill Wolfe wtwolfe@hubcap.clemson.edu
sommar@enea.se (Erland Sommarskog) (01/07/89)
Bill Wolfe writes: > I'd think classes would be defined a bit differently! A package > could contain declarations of variables, and we certainly don't want > variables included in a class definition (where class is defined as This is half-true. Thus, we don't want them to be modifyable, but we want them to be readable. As far as I am concerned, writeable variable in packages should be prohibited today, but, alas, wouldn't be a change to rhyme with backwards compability. It should be avoided anyway. >> But for inheritance we want all attributes, also those who do not >> appear in the specification part (or?), and particulary we probably >> want to have access to private types internal structure. > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ > > One of the most fundamental aspects of the ADT paradigm is that > an object is known to the outside world only as a type definition > and a set of predefined operations. This provides the independence > which allows us to compile specifications and implementations separately. > Access to the internal structure of a private type violates the entire > concept of a "private" type. But can you as ADT designer always find out exactly what I want? Say you hand me a linked-list package. I discover that I need to reverse a list, but does not have such an operation. With Ada today I have three possibilies: 1) Write Reverse_list using the existing primitives and place it in my own package. 2) Write my own extended list package, which calls yours and adds my own Reverse_list. 3) Re-hack your package, which gives me the possiblility to write a more efficient version. 1) has the disadvantge that my code contains something that does not belong there. 2) Causes redundancy and duplicated declarations. 3) is maybe not available for various reasons. It resides in a library I cannot write to, and you are holiday. Besides other users would have a lot of recompilation triggered just before deliverance and get mad. With inheritance there is a fourth possibility. I can write my extended list package to solely inherit all from yours and then add Reverse_list. Depending if I want to be saved from changes, or need efficiency I use your primitives, or the implementation. For more info on this, the "open-closed principle", I once again refer to Bertrand Meyer's "Object-Oriented Software Construction" where he discusses these ideas. > Seriously though, there *is* a comp.lang.eiffel. Perhaps you > would feel more at home there rather than in comp.lang.ada. I feel at home both here and there. Wouldn't say I found that comment very serious, :-) >> Generic >>... >> Package Binary_trees is >> ... >> Generic >> With Procedure Treat(Node : in Node_type; >> Data : in out Data_type); >> Procedure Traverse_forward(Tree : Tree_type); >> >> (By the way, an example like the one above should be added to the validation >> suite if it's not already there. A PC compiler I played with choked on the >> code above, and I believe it is/was validated.) > > Why does Node need to be a parameter of Treat? All you need is > something that will treat Data once Traverse_Forward has extracted > it from the Node. Once you've removed the unnecessary parameter, > your package should compile perfectly. You shouldn't work as a compiler. Whether Node is anything useful or not could be discussed, but it's certainly perfectly legal Ada. If it is not, tell me why and I write an error report about our Unix compiler that accepts this. (The use for Node is that the user may want a quick reference to some data, which he saves somewhere else.) -- Erland Sommarskog ENEA Data, Stockholm This signature is not to be quoted. sommar@enea.se
rjh@cs.purdue.EDU (Bob Hathaway) (01/08/89)
>> I don't think procedural variables or class structures will make Ada >> much bigger. Procedural variables are not complicated in Modula [...] > [Bill Wolfe responds] > But Modula doesn't have generics. Using the combination of generics > and the class abstraction outlined in my earlier article, I think > we'll get more power, with better readability. > Yes, class structures with generics would provide good data abstraction. This would allow classes to be statically parameterized by types, variables, constants, and subprograms. Generics are good for setting an Adt once, such as a stack which is parameterized by its element type and a print subprogram. But what about dynamic parameterization? For dynamic parameterization of data, polymorphic parameters to Adt operations are needed to allow the greatest expressiveness. An example is a stack of any element type which could be provided by polymorphic parameters to an insert subprogram. For dynamic parameterization of operations, procedural variables are needed. An example is a stack which can change its print operation as described previously. Now, adding polymorphic parameters to Ada would be a sizable extension but adding procedural variables would be almost trivial. Admittedly, Adt designers can provide a plethora of operations and programmers can use case statements to choose among them but this puts greater burden on the programmer since they must now select the correct operation throughout their code. Also, static generic parameterization is desirable in certain cases such as in the stack example above when the element type is known in advance and the type system can statically perform strong typechecking for correctness. But the flexibility of dynamic parameterization allows maximum expressiveness and greater power, and so "the burden of proof" has to be made against dynamically parameterized operations. Since static generics and dynamic parameterization are not mutually exclusive, both could be provided. >> This isn't what I had in mind. What if variables of type Tree_Type should >> be traversed in different ways depending on context? > > Just make basic traversal operations a part of your abstraction. > But this calls for case statements throughout the program to determine which operation to call, as mentioned above. For maximum expressiveness, I might want to set instances with particular traversal operations and then use a single operation invocation at a later point in the program which will invoke the correct operation for all instances, reducing redundant code and allowing maximum expressiveness. Bob Hathaway rjh@purdue.edu
billwolf@hubcap.clemson.edu (William Thomas Wolfe,2847,) (01/08/89)
From article <5790@medusa.cs.purdue.edu>, by rjh@cs.purdue.EDU (Bob Hathaway): > >>> I don't think procedural variables or class structures will make Ada >>> much bigger. Procedural variables are not complicated in Modula [...] >> > [Bill Wolfe responds] >> But Modula doesn't have generics. Using the combination of generics >> and the class abstraction outlined in my earlier article, I think >> we'll get more power, with better readability. >> > Yes, class structures with generics would provide good data abstraction. > This would allow classes to be statically parameterized by types, variables, > constants, and subprograms. Generics are good for setting an Adt once, such as > a stack which is parameterized by its element type and a print subprogram. > But what about dynamic parameterization? For dynamic parameterization of data, > polymorphic parameters to Adt operations are needed to allow the greatest > expressiveness. An example is a stack of any element type which could be > provided by polymorphic parameters to an insert subprogram. For dynamic > parameterization of operations, procedural variables are needed. No, all we need is the ability to have pointers which are not bound to any specific type. Most of the time we want to say "pointer to SPECIFIC_TYPE", but sometimes we just want to say "pointer". Given the ability to specify an unrestricted pointer, we can implement the desired stack (or whatever) of any element type. > Now, adding polymorphic parameters to Ada would be a sizable extension Not true; all we need to do is write procedures which require an arbitrary pointer as a parameter, and we're done. > static generic parameterization is desirable in certain cases such as in the > stack example above when the element type is known in advance and the type > system can statically perform strong typechecking for correctness. Quite true, and pointers should be restricted wherever it is reasonable to do so, just as ranges should be specified whenever appropriate. # But the # flexibility of dynamic parameterization allows maximum expressiveness # and greater power, and so "the burden of proof" has to be made against # dynamically parameterized operations. Since static generics and dynamic # parameterization are not mutually exclusive, both could be provided. Unless, as I have shown above, a simpler mechanism will suffice. #>> What if variables of type Tree_Type should #>> be traversed in different ways depending on context? #> #> Just make basic traversal operations a part of your abstraction. #> # # But this calls for case statements throughout the program to determine which # operation to call, as mentioned above. For maximum expressiveness, I might # want to set instances with particular traversal operations and then use a # single operation invocation at a later point in the program which will invoke # the correct operation for all instances, reducing redundant code and allowing # maximum expressiveness. Using the above mechanism, we've eliminated the case statements. Now set up your abstraction to provide a "current node" concept, along with operations like DESCEND_LEFT, DESCEND_RIGHT, and ASCEND. This can be implemented either via parent pointers or via a secret stack which holds the path of descent used to reach the current node. Bill Wolfe wtwolfe@hubcap.clemson.edu
billwolf@hubcap.clemson.edu (William Thomas Wolfe,2847,) (01/08/89)
From article <4223@enea.se>, by sommar@enea.se (Erland Sommarskog): > But can you as ADT designer always find out exactly what I want? Say > you hand me a linked-list package. I discover that I need to reverse > a list, but does not have such an operation. With Ada today I have > three possibilies: > 1) Write Reverse_list using the existing primitives and place it > in my own package. > 2) Write my own extended list package, which calls yours and adds my own > Reverse_list. > 3) Re-hack your package, which gives me the possiblility to write a more > efficient version. > 1) has the disadvantge that my code contains something that does not belong > there. 2) Causes redundancy and duplicated declarations. 3) is maybe not > available for various reasons. It resides in a library I cannot write to, > and you are holiday. Besides other users would have a lot of recompilation > triggered just before deliverance and get mad. Proceed with either 2) or 3), whichever you prefer, and use it until procedures can be invoked whereby the library is upgraded to satisfy this requirement. Probably there is a mechanism for submitting new requirements, and you can go ahead and submit your workaround along with your request; the workaround's spec will probably be placed into immediate service, perhaps with minor revisions, and the implementation will be updated with an optimized version as time permits. Other users will not have recompilation triggered because they are depending on the version which does not provide list reversal, which remains in the library. If no increase in efficiency is possible as a result of omitting list reversal, then probably a note will be placed in the library saying that programmers should use the new version instead, and eventually all software depending on the old version will be rewritten (shifting to the new version in the process), or abandoned, and the old version will then be removed from the library. If your local installation prefers, they can instead purchase a more powerful version of the ADT, and then apply the same phasing-out procedure if there is no efficiency bonus in the less comprehensive ADT. > With inheritance there is a fourth possibility. I can write my extended > list package to solely inherit all from yours and then add Reverse_list. > Depending if I want to be saved from changes, or need efficiency I > use your primitives, or the implementation. > > For more info on this, the "open-closed principle", I once again refer > to Bertrand Meyer's "Object-Oriented Software Construction" where he > discusses these ideas. I have read about this in Meyer's book, and do not agree with it. We do not first create the abstract concept of FRUIT and then specialize into APPLEs and ORANGEs; it is the other way around!! Additionally, Meyer's approach creates all manner of compilation dependencies and inefficiencies, and is in general a very messy way to go about doing things. Instead, let us proceed along the lines of a synthesis-oriented approach, as I have described. We should describe FRUIT as an abstraction, and the characteristics of FRUIT permit us to decide whether a given real object falls into this class or not. We can then construct packages which operate over the abstraction FRUIT, knowing that our APPLEs and ORANGEs will satisfy the abstraction and therefore be compatible with the package. We can even discover PLUMs at a later date, design the implementing specification to be compatible with the FRUIT abstraction, and then freely insert PLUMs into the stream of FRUIT being handled by our packages. This is a far more natural paradigm; it corresponds much more closely to the natural processes of human thought. >>> Generic >>>... >>> Package Binary_trees is >>> ... >>> Generic >>> With Procedure Treat(Node : in Node_type; >>> Data : in out Data_type); >>> Procedure Traverse_forward(Tree : Tree_type); >>> >>> (By the way, an example like the one above should be added to the validation >>> suite if it's not already there. A PC compiler I played with choked on the >>> code above, and I believe it is/was validated.) >> >> Why does Node need to be a parameter of Treat? All you need is >> something that will treat Data once Traverse_Forward has extracted >> it from the Node. Once you've removed the unnecessary parameter, >> your package should compile perfectly. > > You shouldn't work as a compiler. Whether Node is anything useful or > not could be discussed, but it's certainly perfectly legal Ada. If > it is not, tell me why and I write an error report about our Unix > compiler that accepts this. (The use for Node is that the user > may want a quick reference to some data, which he saves somewhere > else.) But the problem is that Node is not the user's property; it is the property of the generic package. As such, the user is not free to stick arbitrary data in some secret place within the Node. If the user wants to store "a quick reference to some data", then the user can define Data as a record with two fields: one will provide the REAL data, and the other will provide the user's secret cache. Then the procedure Treat which the user writes can access the user's cache freely, and now we see that Node really is a useless parameter. (I'm not concerned with the deficiencies of one compiler or another as much as I am with the goodness of the ADT; I see no reason why the PC should have rejected the code, but I saw a more important question which needed to be taken care of first.) Bill Wolfe wtwolfe@hubcap.clemson.edu
rjh@cs.purdue.EDU (Bob Hathaway) (01/08/89)
>> Yes, class structures with generics would provide good data abstraction. >> This would allow classes to be statically parameterized by types, variables, >> constants, and subprograms. Generics are good for setting an Adt once, >> such as >> a stack which is parameterized by its element type and a print subprogram. >> But what about dynamic parameterization? For dynamic parameterization of >> data, >> polymorphic parameters to Adt operations are needed to allow the greatest >> expressiveness. An example is a stack of any element type which could be >> provided by polymorphic parameters to an insert subprogram. For dynamic >> parameterization of operations, procedural variables are needed. > > No, all we need is the ability to have pointers which are not bound > to any specific type. Most of the time we want to say "pointer to > SPECIFIC_TYPE", but sometimes we just want to say "pointer". Given > the ability to specify an unrestricted pointer, we can implement > the desired stack (or whatever) of any element type. But this assumes no type or error checking at all. By dynamic parameterization I meant with runtime type and error checking. For static typechecking of data we can use a pointer to a tagged variant record to distinguish types. This assumes foreknowledge of the types in the variant but at least allows subprograms to distinguish objects. With unbound pointers, there is no built-in type or error checking mechanism. This covers the case of "pseudo" polymorphic parameters but what about dynamically parameterized operations? Ada has an address type applicable to function and task type addresses but this is implementation dependent and there is no defined typechecking mechanism for the subprogram parameter structure as there is with procedural variables. Unbound pointers to functions have the same consequences. While tasks can allow procedural abstraction, better is a higher order construct such as procedural variables. >> >> Now, adding polymorphic parameters to Ada would be a sizable extension > > Not true; all we need to do is write procedures which require an > arbitrary pointer as a parameter, and we're done. I meant with runtime typechecking and how this should be done is another point. Milner's type system uses static typechecking for polymorphic parameters but doesn't seem to provide the necessary power for arbitrary polymorphism. More powerful is a scheme which invokes operations on arbitrary types at runtime with dynamic type and error checking mechanisms and not just simple statically checked invocation. This requires a more elaborate mechanism but adding polymorphism to Ada's static type system would allow programmers to fully specify types for static checking and efficiency or choose a more powerful parameter passing mechanism for greater expressiveness however polymorphic parameters and variables would entail major changes to the LRM. On dynamically parameterized operations, if incremental improvement is the goal of the Ada-9X standard then simple statically checked dynamically parameterized operations can be provided with procedural variables. Dynamic typechecking of procedural variables is also possible but I was advocating statically checked procedural variables as an extension. ># But the ># flexibility of dynamic parameterization allows maximum expressiveness ># and greater power, and so "the burden of proof" has to be made against ># dynamically parameterized operations. Since static generics and dynamic ># parameterization are not mutually exclusive, both could be provided. > > Unless, as I have shown above, a simpler mechanism will suffice. But this "proof" doesn't apply to dynamically parameterized operations with type and error checking as defined above, could you comment on that also? >#>> What if variables of type Tree_Type should >#>> be traversed in different ways depending on context? >#> >#> Just make basic traversal operations a part of your abstraction. >#> > > But this calls for case statements throughout the program to determine which ># operation to call, as mentioned above. For maximum expressiveness, I might ># want to set instances with particular traversal operations and then use a ># single operation invocation at a later point in the program which will invoke ># the correct operation for all instances, reducing redundant code and allowing ># maximum expressiveness. > > Using the above mechanism, we've eliminated the case statements. > I'm not sure what this means. With pointers to functions there should be typechecking of parameter structures and this is the essence of procedural variables. > Now set up your abstraction to provide a "current node" concept, > along with operations like DESCEND_LEFT, DESCEND_RIGHT, and ASCEND. > This can be implemented either via parent pointers or via a secret > stack which holds the path of descent used to reach the current node. > Yes this would work, but leaves programmers to build their own traversal routines. My idea was to provide a mechanism allowing programmers to specify a procedural invocation in a single, simple statement and have the Adt select and carry out the operation implicitly. Bob Hathaway rjh@purdue.edu
billwolf@hubcap.clemson.edu (William Thomas Wolfe,2847,) (01/09/89)
From article <5793@medusa.cs.purdue.edu>, by rjh@cs.purdue.EDU (Bob Hathaway): >> all we need is the ability to have pointers which are not bound >> to any specific type. Most of the time we want to say "pointer to >> SPECIFIC_TYPE", but sometimes we just want to say "pointer". Given >> the ability to specify an unrestricted pointer, we can implement >> the desired stack (or whatever) of any element type. > > But this assumes no type or error checking at all. By dynamic > parameterization I meant with runtime type and error checking. The same runtime type and error checking will occur with the unrestricted pointers. When an operation is applied to the object pointed to, the type of that object will be used to determine which code to invoke or to prove the existence of a run-time error. Now I see no reason why we can't say "pointer to TYPE_1 or TYPE_2 (etc.)", thus introducing a new form of restricted pointer, but what we are dealing with here is the need to store any type of object whatsoever. Clearly, unrestricted pointers, with their associated run-time costs, should only be used when their power is absolutely necessary. > For static typechecking of data we can use a pointer to a tagged variant > record to distinguish types. This assumes foreknowledge of the types in > the variant but at least allows subprograms to distinguish objects. What you describe is a hack which would provide (less cleanly) the power provided by the form of restricted pointer described above. This is inappropriate to the problem under discussion, which assumes the need to program a polymorphic stack without foreknowledge of the types of objects to be stacked. > but what about dynamically parameterized operations? Ada has an address > type applicable to function and task type addresses but this is > implementation dependent and there is no defined typechecking mechanism > for the subprogram parameter structure as there is with procedural > variables. Unbound pointers to functions have the same consequences. > While tasks can allow procedural abstraction, better is a higher order > construct such as procedural variables. I have described in earlier articles mechanisms by which the desired effects can be achieved in a more intuitive manner. Please provide a concrete example in which the provided mechanisms would prove inadequate. >> Now set up your abstraction to provide a "current node" concept, >> along with operations like DESCEND_LEFT, DESCEND_RIGHT, and ASCEND. >> This can be implemented either via parent pointers or via a secret >> stack which holds the path of descent used to reach the current node. > > Yes this would work, but leaves programmers to build their own traversal > routines. My idea was to provide a mechanism allowing programmers to specify > a procedural invocation in a single, simple statement and have the Adt > select and carry out the operation implicitly. But wasn't the basis of your argument the claim that the usual preorder, postorder, and inorder traversal schemes may not be enough? The solution to this question is clearly to proceed as I have described. Perhaps you could clarify the problem under consideration and the precise nature of your solution... Bill Wolfe wtwolfe@hubcap.clemson.edu
rjh@cs.purdue.EDU (Bob Hathaway) (01/09/89)
> > But this assumes no type or error checking at all. By dynamic > parameterization I meant with runtime type and error checking. > > The same runtime type and error checking will occur with > the unrestricted pointers. When an operation is applied > to the object pointed to, the type of that object will > be used to determine which code to invoke or to prove > the existence of a run-time error. Now I see no reason > why we can't say "pointer to TYPE_1 or TYPE_2 (etc.)", > thus introducing a new form of restricted pointer, but > what we are dealing with here is the need to store > any type of object whatsoever. Clearly, unrestricted > pointers, with their associated run-time costs, should > only be used when their power is absolutely necessary. I'm still not sure what this means. Do you mean passing unrestricted pointers to procedures and then selecting the procedure via overloading (ad-hoc polymorphism) at runtime? I meant allowing polymorphic parameters to a particular subprogram, such as procedure test (parameter : polymorphic; ...) is ... which defeats static typechecking of parameter and uses a type attribute in the body of test. This also brings up the issue of name vs. structural equivalence of runtime typechecking in both cases, but the usual Ada rules could apply. Either approach allows considerable power but adding runtime typechecking is not a trivial extension, as discussed earlier. But I agree a more powerful parameter passing mechanism is highly desirable. >> For static typechecking of data we can use a pointer to a tagged variant >> record to distinguish types. This assumes foreknowledge of the types in >> the variant but at least allows subprograms to distinguish objects. > > What you describe is a hack which would provide (less cleanly) the > power provided by the form of restricted pointer described above. > > This is inappropriate to the problem under discussion, which > assumes the need to program a polymorphic stack without foreknowledge > of the types of objects to be stacked. I agree, I thought you were talking about unbound pointers; insufficient semantics of unrestricted pointers was given. >> but what about dynamically parameterized operations? Ada has an address >> type applicable to function and task type addresses but this is >> implementation dependent and there is no defined typechecking mechanism >> for the subprogram parameter structure as there is with procedural >> variables. Unbound pointers to functions have the same consequences. >> While tasks can allow procedural abstraction, better is a higher order >> construct such as procedural variables. > > I have described in earlier articles mechanisms by which the > desired effects can be achieved in a more intuitive manner. > > Please provide a concrete example in which the provided > mechanisms would prove inadequate. Ok. Here is an (uncommented fast prototype) example which could easily apply to Ada Adts as well. This is similar to a project I once worked on here and similar constructs have appeared throughout the literature. This does not however, give away any trade secrets. There are many possibilities such as type inference of the generic parameters (ML), full static declarations of generics (current Ada), or dynamic checking via arbitrary polymorphism but these are superfluous to procedural variables. For the Ada-9X extension, generic declarations would be used. Now, ignoring interface boundaries below, SHORT_PRINT and LONG_PRINT can be statically typechecked with the declaration of PRINT_ELEMENT, a procedural variable. For an Ada example, parameterize the visible operations with a stack type and add the usual interfaces and declarations. --========================================================================= -- class STACK -- -- Provides a simple example of procedural variables. --========================================================================= class STACK (ELEMENT_TYPE, FCFS, LCLS, SHORT_PRINT, LONG_PRINT) is procedure INSERT (ELEMENT : ELEMENT_TYPE); -- INSERT (ELEMENT : polymorphic); procedure POP () return ELEMENT_TYPE; procedure MAKE_SHORT_PRINT (); procedure MAKE_LONG_PRINT (); procedure PRINT (); procedure MAKE_fCFS ()... ... on entry ... -- called at block entry. on exit ... -- called at block exit. exception ... private ... end STACK; class body STACK is -- -- PRINT_PROCEDURE_TYPE -- -- A procedural type used to implement the print operation. -- These could be in the private part of the class. -- type PRINT_PROCEDURE_TYPE is procedure (ELEMENT : ELEMENT_TYPE) := SHORT_PRINT; -- -- PRINT_ELEMENT -- -- A procedural variable invoked by the PRINT operation. -- PRINT_ELEMENT : PRINT_PROCEDURE_TYPE; type INTERNAL_STACK_TYPE is record BODY : array ... of ELEMENT_TYPE; TOP : NATURAL; end record; INTERNAL_STACK : INTERNAL_STACK_TYPE; procedure PRINT is begin -- -- For each element in the stack -- print element -- for INDEX in INTERNAL_STACK .BODY'FIRST .. INTERNAL_STACK .TOP loop PRINT_ELEMENT (INTERNAL_STACK .BODY (INDEX)); end loop; end insert; -- -- MAKE_SHORT_PRINT -- -- Set procedural instance variable PRINT_ELEMENT to parameter -- SHORT_PRINT so subsequent calls to PRINT by this instance -- will invoke SHORT_PRINT. Could also use a generic -- subprogram parameter to supply a new print routine, or ... -- Parameters SHORT_PRINT and LONG_PRINT will have to be assignment -- compatible with type PRINT_PROCEDURE_TYPE; -- procedure MAKE_SHORT_PRINT is begin PRINT_ELEMENT := SHORT_PRINT; end MAKE_SHORT_PRINT; procedure MAKE_LONG_PRINT is begin PRINT_ELEMENT := LONG_PRINT; end MAKE_SHORT_PRINT; ... end STACK; Now, a call to print an instance of this class will at first result in invocation of the SHORT_PRINT parameter. But programmers can make subsequent calls to PRINT for this instance use long_print through a call to MAKE_LONG_PRINT. Each instance can parameterize its print subprogram to output its data as desired. Other tricks could be used but this method avoids the use of case statements and is a simple use of procedural variables. It also provides static typechecking of the print operation since only procedures with the same parameter structure as PRINT_ELEMENT will match. In more complicated examples parameterizable operations for each Adt instance could simplify the program considerably, such as by avoiding nested case statements. >> Now set up your abstraction to provide a "current node" concept, >> along with operations like DESCEND_LEFT, DESCEND_RIGHT, and ASCEND. >> This can be implemented either via parent pointers or via a secret >> stack which holds the path of descent used to reach the current node. > >> Yes this would work, but leaves programmers to build their own traversal >> routines. My idea was to provide a mechanism allowing programmers to specify >> a procedural invocation in a single, simple statement and have the Adt >> select and carry out the operation implicitly. > > But wasn't the basis of your argument the claim that the usual > preorder, postorder, and inorder traversal schemes may not be > enough? The solution to this question is clearly to proceed > as I have described. Perhaps you could clarify the problem > under consideration and the precise nature of your solution... > I hope the example above clarified the idea. On the subject of classes, another construct to change operations could be invented but procedural variables provide a simple mechanism. Bob Hathaway rjh@purdue.edu
billwolf@hubcap.clemson.edu (William Thomas Wolfe,2847,) (01/09/89)
From article <5796@medusa.cs.purdue.edu>, by rjh@cs.purdue.EDU (Bob Hathaway): >> [Discussion of unrestricted pointers] > > Do you mean passing unrestricted pointers to procedures and then > selecting the procedure via overloading (ad-hoc polymorphism) at runtime? > I meant allowing polymorphic parameters to a particular subprogram, > such as > procedure test (parameter : polymorphic; ...) is ... Yes, that's what I had in mind, although I would also provide procedure INSERT_ITEM (TARGETED_STACK : in out STACK; NEW_ITEM : in OBJECT); to avoid making the user set up a pointer just to get a parameter passed. The resulting situation would be the same as if an unrestricted pointer had been used and POINTER.all had been made to serve the same function. > [An extended example of toggling between two print procedures] > > procedure MAKE_SHORT_PRINT (); -- sets PRINT up to call SHORT_PRINT, > -- a user-supplied generic parameter > > procedure MAKE_LONG_PRINT (); -- sets PRINT up to call LONG_PRINT, > -- a user-supplied generic parameter > > procedure PRINT (); -- a service provided to the user > Now, a call to print an instance of this class will at first result in > invocation of the SHORT_PRINT parameter. But programmers can make > subsequent calls to PRINT for this instance use long_print > through a call to MAKE_LONG_PRINT. Each instance can parameterize > its print subprogram to output its data as desired. Other tricks > could be used but this method avoids the use of case statements and > is a simple use of procedural variables. > In more complicated examples parameterizable operations for each Adt > instance could simplify the program considerably, such as by avoiding > nested case statements. But you've designed your ADT to handle only two types of printing situations: SHORT_PRINT and LONG_PRINT (or at least this would seem to be the case to anyone who takes your generic parameter structure at face value). What we REALLY want is for ANY type of printing operation to occur, depending on the user's needs, which we cannot forecast in advance. But now look at the trap we've walked into: we must provide MAKE_*_PRINT, where * represents an indefinite set of cases. We now see that our old friend, the case statement, is not gone; it has simply taken on a new form. Verdict: a bad ADT design idea. Now let us step back for a moment and consider our situation. We wish to accept a PRINT procedure from our user, which we will use in the course of printing out the contents of the stack. But how do we know that the method we choose for encapsulating the stacked objects in the printout will make our user happy? Perhaps our idea is to print each object, separated by a blank line, but our user wants to see each object surrounded by a rectangular box of :-)s... We now see that our entire approach to the problem is wrong. We must provide a method whereby our user can access his/her stacked objects, and allow the user to implement any arbitrary print procedure. But, you object, the user must be given some sort of standard print procedure which can be used as a default! And so he/she must; we achieve this by supplying in a utilities package the following: with TEXT_IO; generic type DATA_STRUCTURE is limited private; type STORED_OBJECT is limited private; with procedure NEXT_POSITION (STRUCTURE : in out DATA_STRUCTURE); with function GET_CURRENT_ITEM (STRUCTURE : in DATA_STRUCTURE) return STORED_OBJECT; with procedure PRINT (TO_FILE : in TEXT_IO.FILE_TYPE; THE_ITEM : in STORED_OBJECT ); procedure STANDARD_PRINT_ROUTINE (INTO_FILE : in TEXT_IO.FILE_TYPE; STRUCTURE : in DATA_STRUCTURE); Our user is now provided with maximal power and convenience. Note that the above utility applies to any class of structures for which the user can construct a procedure to sequentially access every stored object in some user-defined order. Still waiting for a situation in which procedural variables should be used in order to formulate an intuitively natural solution... Bill Wolfe wtwolfe@hubcap.clemson.edu
rjh@cs.purdue.EDU (Bob Hathaway) (01/10/89)
> In more complicated examples parameterizable operations for each Adt > instance could simplify the program considerably, such as by avoiding > nested case statements. > Bill Wolfe responds: > But you've designed your ADT to handle only two types of printing > situations: SHORT_PRINT and LONG_PRINT (or at least this would seem > to be the case to anyone who takes your generic parameter structure > at face value). What we REALLY want is for ANY type of printing > operation to occur, depending on the user's needs, which we cannot > forecast in advance. But now look at the trap we've walked into: > we must provide MAKE_*_PRINT, where * represents an indefinite set > of cases. We now see that our old friend, the case statement, is > not gone; it has simply taken on a new form. > This is not entirely correct, since I commented another more general solution. It is possible to parameterize the Adt with a generic MAKE_PRINT_PROCEDURE as described in the comment which I'll repeat below. This is accomplished with a nested generic subprogram declaration in the visible part of the package specification allowing any visible type compatible procedure to be passed to a "MAKE_PRINT_PROCEDURE". This satisfies the constraint above by dynamically assigning the generic parameter to the internal procedural variable, if desired. -- -- MAKE_SHORT_PRINT -- -- Set procedural instance variable PRINT_ELEMENT to parameter -- SHORT_PRINT so subsequent calls to PRINT by this instance ** Please Note *** -- will invoke SHORT_PRINT. Could also use a generic -- subprogram parameter to supply a new print routine, or ... *** *** -- Parameters SHORT_PRINT and LONG_PRINT will have to be assignment -- compatible with type PRINT_PROCEDURE_TYPE; -- Also, it appears unrestricted pointers to subprograms, if thats what you propose, would provide dynamically checked operations at runtime. This mechanism is more powerful than statically checked procedural variables. Analogous to the use of generics and arbitrary polymorphism where generics should be used whenever applicable and arbitrary polymorphism with care, procedural variables should be used whenever applicable and unrestricted pointers with care. Since the previous example used generics, corresponding procedural variables are applicable and provide an elegant general solution. I'll let Harland, if we're lucky enough to have him read this, provide an example with arbitrary polymorphism and unrestricted pointers:-) Mats Weber writes: >I think there is one good reason why procedure types should not be included in >the Ada language: A secure implementation of procedure types must restrict >their use to global procedures (that is, procedures that are not nested in >other procedures or tasks), as is the case in Modula-2. > >Such a rule would violate the uniformity of the language (in Ada 83, anything >can be declared in any declarative region, no matter how deeply nested the >region is). I'm aware of this argument but after several years of Modula-2 programming this simply doesn't cause concern. This is like the "else" construct argument where disambiguating rules must be applied to allow if-then-else constructs. It is not consequential that rules must be applied to grammars, as with the else construct, or that semantic rules must be applied to objects, as with procedural variables. As a programmer, the only procedures I would assign to a procedural variable are top-level procedures and since the nested case doesn't occur, I don't see a problem. I agree constraints restricting orthogonality should only be applied when necessary but procedural variables present such a case in a stack based-model since assignment could allow access to inactive environments global to a procedure and the assignment restriction to top-level procedures is safe, appropriate, and general. Also, the rule for disallowing procedural variable assignment to nested subprograms which are passed as generic subprogram parameters must still be statically checked. Bill Wolfe writes: > We now see that our entire approach to the problem is wrong. We must > provide a method whereby our user can access his/her stacked objects, > and allow the user to implement any arbitrary print procedure. But, > you object, the user must be given some sort of standard print procedure > which can be used as a default! And so he/she must; we achieve this > by supplying in a utilities package the following: > But this is the old scheme again since the Adt cannot be parameterized at any point in the program and allow a single subsequent operation to invoke the desired subprogram. This sheme requires the work of writing an output procedure inline. Yes, the user can call MY_PRINT (STACK .POP ...) for maximum flexibility as they can with the presented example but this was not desired. The output example was kept simple to abstract the desired method and real applications are easy to construct, as shown below. > Still waiting for a situation in which procedural variables should > be used in order to formulate an intuitively natural solution... Graphical environments provide one example where dynamically parameterizable objects can be of great assistance. One could parameterize graphical objects with operations for displaying output, windows, etc., with each instance using the correct subprogram to implement its display operations. Bob Hathaway rjh@purdue.edu
billwolf@hubcap.clemson.edu (William Thomas Wolfe,2847,) (01/10/89)
From article <5804@medusa.cs.purdue.edu>, by rjh@cs.purdue.EDU (Bob Hathaway): >> In more complicated examples parameterizable operations for each Adt >> instance could simplify the program considerably, such as by avoiding >> nested case statements. >> >>> [...] we must provide MAKE_*_PRINT, where * represents an indefinite set >>> of cases. We now see that our old friend, the case statement, is >>> not gone; it has simply taken on a new form. > > This is not entirely correct, since I commented another more general solution. Then let's have a concrete example of this other, more general solution. Be generous with the comments. % Also, it appears unrestricted pointers to subprograms, if thats what % you propose, would provide dynamically checked operations at runtime. % This mechanism is more powerful than statically checked procedural % variables. No, I haven't yet been convinced that subprograms should constitute a separate type; my current position is that subprograms should only be a means by which ADTs and tasks (think of a "main program" as an isolated task...) can be specified. If you can convince us that there is a legitimate need for a subprogram type, then variables of the type and pointers to objects of the type will follow automatically. > Mats Weber writes: >>I think there is one good reason why procedure types should not be included in >>the Ada language: A secure implementation of procedure types must restrict >>their use to global procedures (that is, procedures that are not nested in >>other procedures or tasks), as is the case in Modula-2. Quick question: assuming the idea of a specification is expanded to include all externally accessible objects, what is the source of the insecurity? % Graphical environments provide one example where dynamically parameterizable % objects can be of great assistance. One could parameterize graphical objects % with operations for displaying output, windows, etc., with each instance using % the correct subprogram to implement its display operations. Specific examples, please... Bill Wolfe wtwolfe@hubcap.clemson.edu
rjh@cs.purdue.EDU (Bob Hathaway) (01/10/89)
Another more direct way to parameterize a change operation is
to use a procedural variable as a parameter. Such as:
generic
type ELEMENT_TYPE is private;
package ...
type PRINT_PROCEDURE is procedure (ELEMENT : in ELEMENT_TYPE);
procedure CHANGE_PRINT_OPERATION (PRINT_OPERATION : in PRINT_PROCEDURE);
This allows dynamic specification of statically checked print procedures per
instance while the previous example assumed the user knew all allowable
procedures during instantiation.
Bob Hathaway
rjh@purdue.edubillwolf@hubcap.clemson.edu (William Thomas Wolfe,2847,) (01/11/89)
From article <5806@medusa.cs.purdue.edu>, by rjh@cs.purdue.EDU (Bob Hathaway): > > Another more direct way to parameterize a change operation is > to use a procedural variable as a parameter. Such as: > > generic > type ELEMENT_TYPE is private; > package ... > type PRINT_PROCEDURE is procedure (ELEMENT : in ELEMENT_TYPE); > procedure CHANGE_PRINT_OPERATION (PRINT_OPERATION : in PRINT_PROCEDURE); > > This allows dynamic specification of statically checked print procedures per > instance while the previous example assumed the user knew all allowable > procedures during instantiation. But now we have a highly changeable system. What I am asking is, "Is there any reason we need this extremely high level of changeability?" We are essentially getting into the realm of programs which modify themselves, and I tend to think that this power requires extraordinary regulation due to the ease with which such a program could modify itself to the point that nobody can figure out how it got there in less than omega (Ackermann's function) time, much less how to fix it. I've suggested earlier that programs should theoretically be able to edit source files, cause a recompilation, dump their local knowledge into a transition file, invoke the successor on the local knowledge, and finally commit suicide, but that this should be done with extreme caution. Is there any reason why we need procedural variables in addition to this? Bill Wolfe wtwolfe@hubcap.clemson.edu
rjh@cs.purdue.EDU (Bob Hathaway) (01/11/89)
> Another more direct way to parameterize a change operation is > to use a procedural variable as a parameter. Such as: > > generic > type ELEMENT_TYPE is private; > package ... > type PRINT_PROCEDURE is procedure (ELEMENT : in ELEMENT_TYPE); > procedure CHANGE_PRINT_OPERATION (PRINT_OPERATION : in PRINT_PROCEDURE); > > This allows dynamic specification of statically checked print procedures per > instance while the previous example assumed the user knew all allowable > procedures during instantiation. > But now we have a highly changeable system. What I am asking is, > "Is there any reason we need this extremely high level of changeability?" > I think the answer is yes, and I'll provide a summary of the method under discussion instead of another example. As I mentioned to Bill about a month ago, I have been working on a generic class structure for about a year. Other simpler languages have emerged and provided classes but I am not aware of any extending the idea with generics. If Ada is to continue remaining viable as a state-of-the-art programming language then incremental extensions such as procedural variables and generic classes are necessary. Ada is often considered a general purpose programming language, a systems programming language, and an object-oriented programming language and its use has far surpassed its original intention. Grady Booch has presented an elegant object-oriented design strategy for Ada and since most programmers are using this style of programming, Ada should be extended to provide first class constructs supporting this methodology. Classes provide an incremental improvement in abstract data types and together with procedural variables they provide an elegant solution to parameterized operations. I owe some credit to Chris Torek, who posted a method for "the right way to do object oriented programming in C" (his words as I remember) by storing data and operations together. I extended his idea with dynamically parameterized operations in Adts as the need arose and am sure one "right way to do this" is in Ada with generics. Again, the presented example of procedural variables allows abstract data types to dynamically (at runtime) alter thier operations so each instance can be individually parameterized with an appropriate subprogram to perform that operation. Previous postings presented other uses as well. The first posted example used type inference and provided a method to specify all allowable subprogram invocations per instance during instantiation. This method insures controlled operations during and after instantiation and the Adt state will not be hard to trace. The second method allows Adt operations to be dynamically parameterized during and after instantiation and can be used as the need arises. A history can be kept within the Adt for mission critical applications or complex debugging. I will let the method stand on its own merits and it has been my experience that parameterized operations are frequently an appropriate solution. Here is a simple example of parameterization via procedural variables using a single operation Adt: generic type ELEMENT_TYPE is limited private; package STACK is type ADT is limited private; type OPERATION_TYPE is procedure (ELEMENT : in out ELEMENT_TYPE); procedure OPERATION (INSTANCE : in out ADT; ELEMENT : in out ELEMENT_TYPE); procedure CHANGE_OPERATION (INSTANCE : in out ADT; NEW_OPERATION : in OPERATION_TYPE); end STACK; or generic type ELEMENT_TYPE is limited private; package STACK is type ADT is limited private; procedure OPERATION (INSTANCE : in out ADT; ELEMENT : in out ELEMENT_TYPE); generic with procedure NEW_OPERATION (ELEMENT : in out ELEMENT_TYPE); procedure CHANGE_OPERATION (INSTANCE : in out ADT); end STACK; Here is a recommended class based approach: generic type ELEMENT_TYPE is limited private; class type OPERATION_TYPE is procedure (ELEMENT : in out ELEMENT_TYPE); procedure OPERATION (ELEMENT : in out ELEMENT_TYPE); procedure CHANGE_OPERATION (NEW_OPERATION : in OPERATION_TYPE); procedure INITIALIZE; -- These can be dynamically parameterized, if desired procedure FINISH; -- or declared in the private part. -- exception declarations -- private pragma NO_ENTRY; -- If Bill wants to call these explicitly pragma NO_EXIT; on entry INITIALIZE; on exit FINISH; end STACK; The reader is referred to previous articles for discussions on more powerful parameter passing mechanisms which require a runtime type system. Here is an example within a class construct: class STACK is type OPERATION_TYPE is procedure (ELEMENT : polymorphic); procedure OPERATION (ELEMENT : in polymorphic); procedure CHANGE_OPERATION (NEW_OPERATION : OPERATION_TYPE); function GET_OBJECT return polymorphic; end STACK; class body STACK -- see previous class example. end STACK; And here is an example of Bill's proposal with unrestricted pointers (*If* unrestricted pointers can to apply to subprograms): class STACK is type OPERATION_TYPE is procedure; procedure OPERATION (ELEMENT : in polymorphic;...); procedure CHANGE_OPERATION (NEW_OPERATION : OPERATION_TYPE); function GET_OBJECT return polymorphic; end STACK; But this last method requires considerable thought. I'll assume any procedure can be passed to CHANGE_OPERATION and calls to OPERATION will require runtime elaboration. All packages assign the new operation to an internal procedural variable. As shown above, generics co-exist with procedural variables. Another issue is default parameters; what if the supplied procedure doesn't have the same default parameters? The simplist solution is to enforce a new rule, such as during assignment of a subprogram to a procedural variable any default parameters in the procedural variables parameter structure must be matched by corresponding default parameters in the supplied subprogram. But for now I'll assume assignment is legal as long as subsequent invocations of the procedural variable don't reference default parameters not supplied by the subprogram. Such cases should be avoided, however. I will let the idea stand on its own merits for now since there is time for consideration before the next extension. Is there any way to get feedback or proposal information for the Ada 9X extension? I think there have been several worthwhile ideas presented so far. Bob Hathaway rjh@apurdue.edu
rjh@cs.purdue.EDU (Bob Hathaway) (01/11/89)
> We are essentially getting into the realm of programs which modify > themselves, and I tend to think that this power requires extraordinary > regulation due to the ease with which such a program could modify itself > to the point that nobody can figure out how it got there in less than > omega (Ackermann's function) time, much less how to fix it. > > I've suggested earlier that programs should theoretically be able to > edit source files, cause a recompilation, dump their local knowledge > into a transition file, invoke the successor on the local knowledge, > and finally commit suicide, but that this should be done with extreme > caution. > > Is there any reason why we need procedural variables in addition to this? This method is not unusual and can be accomplished by providing an operating system dependent package with the necessary operations. Your suggestion would move this operation into the higher-order domain and could be useful in AI and program generation applications. Retargetable compilers are a case in point. And, speaking of letting proposals stand on their own merits, could we please put the garbage collection issue to rest. Each party could state a final summary of their position, and leave time for consideration before Ada 9X. Thanks, Bob Hathaway rjh@purdue.edu
billwolf@hubcap.clemson.edu (William Thomas Wolfe,2847,) (01/11/89)
From article <5816@medusa.cs.purdue.edu>, by rjh@cs.purdue.EDU (Bob Hathaway): > [much verbiage deleted...] > > class STACK is > type OPERATION_TYPE is procedure; > procedure OPERATION (ELEMENT : in polymorphic;...); > procedure CHANGE_OPERATION (NEW_OPERATION : OPERATION_TYPE); > function GET_OBJECT return polymorphic; > end STACK; First, let's clarify the terminology: a STACK is an example of a type. A class is a group of related types. Thus, APPLE and ORANGE are types, and FRUIT is a class of types. OBJECT is the class of all possible types. Despite the request that you be generous with the comments, no indication was given as to what OPERATION has to do with the stack. Let's assume that it is some operation that one wishes to apply to every item in the stack. Then we encounter problems in that OPERATION has only an "in" parameter, and therefore cannot modify its parameter. But we'll overlook this too, and ask: If we're looking at objects which need to be modified, 1) what are they doing hidden away inside a stack? 2) why can't we just have a stack of pointers, and write a procedure which will serially read the stacked objects and update what they point to? and 3) what if the user wants to keep N different operations which could be applied to all items in the stack, without the bother of continuously invoking CHANGE_OPERATION? The mechanism whereby a program could edit source files, cause a rec recompilation, transfer its local knowledge to its successor, and then destroy itself is appropriate to an environment where code modifications are infrequent; the system transitions from one well-defined state to another, and the source code always represents the current state of the system. Additionally, optimized code can be generated. Procedural variables would encourage excessive rates of change, and would greatly complicate the problem of code optimization. The idea of modifying the display routine of a graphical object through procedural variables has no merit. What should be modified is a standardized data structure such as a bit-map or list of endpoints. This is analogous to the inappropriate use of recursion (vs. iteration). > If Ada is to continue remaining viable as a state-of-the-art programming > language then incremental extensions such as procedural variables [...] Ada is a state-of-the-art applications programming language, not a state-of-the-art research language. Perhaps a more appropriate approach to procedural variables would be to incorporate them into a research language and look for a) efficient implementations, including code optimization, and b) realistic situations in which the use of procedural variables is effectively not optional. Bill Wolfe wtwolfe@hubcap.clemson.edu
barmar@think.COM (Barry Margolin) (01/12/89)
In article <4062@hubcap.UUCP> wtwolfe@hubcap.clemson.edu writes: > Ada is a state-of-the-art applications programming language, not > a state-of-the-art research language. Perhaps a more appropriate > approach to procedural variables would be to incorporate them into > a research language and look for a) efficient implementations, > including code optimization, and b) realistic situations in which > the use of procedural variables is effectively not optional. I'm really beginning to wonder what universe you're coming from. :-) Procedure variables are hardly a research topic these days. They've been in production use for decades. And I can't think of any reason why any decent compiler implementor wouldn't be able to implement them efficiently (the only inefficiency I know of is minor - procedures assigned to variables must get their own stack frame, rather than being able to share its parent block's stack frame - and does not exist if procedure assignment is restricted to top-level procedures). They've been in use in the Lisp programming world for years. They are great for AI applications in which objects must have highly variable active properties. Simple object-oriented systems can be implemented using either "upward closures" (functions that remember the lexical environment from which they were returned) or structures that contain data and a procedure object. They are used quite effectively on Multics, which has extended PL/I to support procedure variables. The most obvious use is in the device-independent I/O library. The structure that represents an I/O stream mostly contains procedure objects that implement the device-specific portion of each I/O operation. When you call the device-independent routines they dispatch through the appropriate component of the stream structure. The components that represent operations that are not appropriate (either because of the type of device or the state of the stream) can be filled in with procedures that return appropriate error indications. But all of the above can be done with extra flags in the structure and CASE statements. Where it really comes in handy is when you allow new device drivers to be linked in on the fly (Multics has been doing dynamic linking for over twenty years, and there's a system call to explicitly invoke the dynamic linking mechanism and return a procedure object). I guess this doesn't provide any more fundamental capabilities than the runtime recompilation mechanism you've mentioned. But I sure wouldn't want to use a system that implemented dynamic linking by automatic editing, recompilation, linking and invocation of the application. True dynamic linking is often criticized as being too slow, but it must be several orders of magnitude than the most well-optimized recompilation scheme. Algol-68 (or was it Algol-60?) had procedure variables, at least in the form of call-by-name parameters. And there are many good uses for them in C, such as the parameter to the signal() subroutine, which associates a procedure with a software interrupt. I could probably go on and on. Procedure variables are an elegant way to reduce the complexity of an enormous number of programs. When I first saw Ada I noticed two things: 1) the syntax is excessively verbose and contorted (I really hate the way the verb "IS" is used, for some reason even I don't understand), and 2) no procedure variables. Barry Margolin Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
billwolf@hubcap.clemson.edu (William Thomas Wolfe,2847,) (01/12/89)
From article <35339@think.UUCP>, by barmar@think.COM (Barry Margolin): > Procedure variables are hardly a research topic these days. They've > been in production use for decades. The Rationale for the Design of Ada lists it as a research topic which was not sufficiently well-understood at the time (particularly in terms of efficient implementations) to be acceptable for inclusion. Additionally, Paul N. Hilfinger, one of the designers of Ada, discussed procedural variables in his ACM Distinguished Dissertation; last I heard, dissertations were considered research. I haven't done an extended investigation of the literature, but procedural variables in Algol-family languages would appear to be a research topic, or at least would seem to have recently been such a topic. Bill Wolfe wtwolfe@hubcap.clemson.edu
billwolf@hubcap.clemson.edu (William Thomas Wolfe,2847,) (01/12/89)
From article <35339@think.UUCP>, by barmar@think.COM (Barry Margolin): > > [Procedural variables] are great for AI applications in which objects > must have highly variable active properties. Could you expand on these situations? I'll be happy to support procedural variables if you can describe a general class of applications in which they are intuitively natural and necessary... Bill Wolfe wtwolfe@hubcap.clemson.edu
barmar@think.COM (Barry Margolin) (01/12/89)
In article <4072@hubcap.UUCP> billwolf@hubcap.clemson.edu writes: >From article <35339@think.UUCP>, by barmar@think.COM (Barry Margolin): >> [Procedural variables] are great for AI applications in which objects >> must have highly variable active properties. > Could you expand on these situations? I'll be happy to support > procedural variables if you can describe a general class of applications > in which they are intuitively natural and necessary... Unfortunately, I'm not an AI programmer, so I don't have concrete examples. I merely imagined that paradigms such as message-passing and actors would be implemented using procedure objects. Barry Margolin Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
firth@sei.cmu.edu (Robert Firth) (01/12/89)
In article <4071@hubcap.UUCP> billwolf@hubcap.clemson.edu writes: > I haven't done an extended investigation of the literature, but > procedural variables in Algol-family languages would appear to > be a research topic I hardly think so. Procedure variables have been around for over 20 years, and the implementation issues are pretty well understood. As for Algol, when I had to write an Algol-60 compiler in the late '70s, the only "research" required was reading the literature from the early '60s that told me how to do it. My most valued source was the early volumes of "Annual Reviews in Automatic Programming", supplemented by Hopgood's old monograph "Compiler Construction". There is just one problem with procxedure variables that has not quite been completely solved. It is illustrated by this: type proc_type is procedure; procvar : proc_type; procedure outer is X : integer; procedure inner; begin X := X+1; end; begin procvar := inner; end; outer; procvar; The final statement invokes the value of procvar, which is, of course, "inner". The call of inner references the variable X declared in outer, which no longer exists. This is the equivalent of the "dangling reference" problem when the address of a local variable is assigned to a global pointer. Many solutions have been proposed; the cleanest in my opinion is that of Modula-2, which does not allow an "inner" procedure to be assigned to a variable. If that were combined with reasonable visibility rules (so that a procedure could be unnested without perforce being made visible), I think it would be a definitive solution.
billwolf@hubcap.clemson.edu (William Thomas Wolfe,2847,) (01/13/89)
From article <8178@aw.sei.cmu.edu>, by firth@sei.cmu.edu (Robert Firth): > There is just one problem with procxedure variables that has not > quite been completely solved. It is illustrated by this: > > type proc_type is procedure; > > procvar : proc_type; > > procedure outer is > X : integer; > > procedure inner; > begin > X := X+1; % end; % % begin % procvar := inner; % end; % % outer; % procvar; % % The final statement invokes the value of procvar, which is, of course, % "inner". The call of inner references the variable X declared in outer, % which no longer exists. This is the equivalent of the "dangling reference" % problem when the address of a local variable is assigned to a global % pointer. % % Many solutions have been proposed; the cleanest in my opinion is that of % Modula-2, which does not allow an "inner" procedure to be assigned to a % variable. If that were combined with reasonable visibility rules (so % that a procedure could be unnested without perforce being made visible), % I think it would be a definitive solution. Why not something along the lines of the "restricted" clause present in Preliminary Ada? Then inner's specification would require that an integer named X be visible in the environment; the attempt to call procvar would then result in an error which would be similar to a "missing parameters" situation. This would have the added benefit of completing the idea of a specification such that ALL interactions between a procedure and its environment are fully documented (and compiler-enforced) in the specification, considerably simplifying program debugging and maintenance. Also, since Barry was unable to give an answer, for what situations would the use of procedural variables be intuitively natural and necessary? Just some example of a realistic applications program for which current Ada would prove inadequate, some motivating reason for wanting to have procedural variables which would justify such a change. By the way, would this extend also to packages? Package variables? Bill Wolfe wtwolfe@hubcap.clemson.edu
scott@shuksan.UUCP (Scott Moody) (01/14/89)
> > > I haven't done an extended investigation of the literature, but > > procedural variables in Algol-family languages would appear to > > be a research topic > <code not included> > > The final statement invokes the value of procvar, which is, of course, > "inner". The call of inner references the variable X declared in outer, > which no longer exists. This is the equivalent of the "dangling reference" > problem when the address of a local variable is assigned to a global > pointer. > The C language solves this problem by not allowing 'inner' procedures at all. Of course in C any address could be used and called, but it might not point to anything meaningful. I would thing the bigger problems with procedure parameters is in the parameters to those procedures; especially in Ada where there might be overloaded procedures with very complex arguments. The syntax for specifying - and then checking at runtime that the user supplies the arguments correctly can get very complex. I think Ada's solution of requiring procedures to be supplied to generics is a good compromise between allowing a users code to suddenly jump to somewhere (hopefully not hitting any stars), and not having them at all. I for one wouldn't mind procedure parameters and varaiables, ala C, but I can see that they go against the non goto rational behind Ada. -- scott
billwolf@hubcap.clemson.edu (William Thomas Wolfe,2847,) (01/16/89)
From article <1089@shuksan.UUCP>, by scott@shuksan.UUCP (Scott Moody): > I for one wouldn't mind procedure parameters and varaiables, > ala C, but I can see that they go against the non goto rational behind Ada. Speaking of the non-goto rationale behind Ada, can anyone tell me why Ada has a goto statement?? (See LRM 5.9...) The Rationale for the Design of Ada conveniently fails to discuss it. Bill Wolfe wtwolfe@hubcap.clemson.edu
stachour@umn-cs.CS.UMN.EDU (Paul Stachour) (01/24/89)
In article <1089@shuksan.UUCP> scott@shuksan.UUCP (Scott Moody) writes: >> >> > I haven't done an extended investigation of the literature, but >> > procedural variables in Algol-family languages would appear to >> > be a research topic >> <code not included> >> >> The final statement invokes the value of procvar, which is, of course, >> "inner". The call of inner references the variable X declared in outer, >> which no longer exists. This is the equivalent of the "dangling reference" >> problem when the address of a local variable is assigned to a global >> pointer. >> > In the Multics Implementation of PL/I, an procedure variable was (not unsuprisingly) two items. One was a pointer to the code which was the procedure. The 2nd was the "environment" of the procedure at the point of the assignment. Note that this allows: 1) The code will thus update the correct "X" at any time, even when called from a highly-nested point, as it can find its "stack" and thus the "right x" to update. 2) The code given in its original form to "detect" that there is no-such "X" to update, since there is no longer the version of "inner" that is "procvar" on the stack. Detection of this stack-mismatch is easy in the example given, it is merely the fact that the stack is now "below" what it was at the point when the assignment "had effect". Of course, in the general case, where there may have been many calls in between, such a simple check would not work. However, the simple matter of "gravestones", as used to detect dangling references, could be used with procedure-variables just as with naturals, or strings, or ... ...Paul