billwolf%hazel.cs.clemson.edu@hubcap.clemson.edu (William Thomas Wolfe, 2847 ) (10/22/89)
[For those people in newsgroups other than comp.lang.ada who are also seeing this article: this thread arose in the context of a discussion in comp.lang.ada regarding the addition of multiple inheritance to Ada as part of the current Ada 9X revision process.] From chase@Ozona.orc.olivetti.com (David Chase): > I'm not well-versed in Ada, but people I've talked to ensure me that > Ada has something similar to the "opaque types" of Modula-2 and > Modula-3. Combining opaque types and multiple inheritance can lead > to some nasty problems. I don't have a solution; just a problem. OK, first I'll rephrase the problem in a way that Ada people will find easier to follow. David assumes that there are two uses for inheritance; the first is specialization, in which one would take the abstraction "vehicle" and provide additional operations in order to define abstractions such as "car" or "truck". The second is derivation, in which one would take an existing abstraction and shape it into a new abstraction, using the implementations provided by the old abstraction as appropriate and overriding operations with new implementations as necessary. > It's the second case, and overriding of existing message-method > bindings in general, that causes the problem. The overriding of the current implementation for only certain operations of a type does cause problems in that in general, a good implementation for a given data abstraction will take maximum advantage of the relationships between the various operations, thus creating an implementation in which the data structures and algorithms involved depend strongly on the fact that exactly that set of operations is to be supported. For example, a standard queue abstraction might be implemented by a singly-linked list structure in conjunction with a descriptor which points to the first and last elements in the list, in order to efficiently support only the operations Enqueue and Dequeue. But now suppose that we wish to support a priority queue instead, and we wanted to override the existing Dequeue operation with a new one. The new operation would scan the entire list in order to find the element having the highest priority, and then dequeue that element. Unfortunately, this is an O (n) algorithm, which is quite inefficient relative to the O (log n) algorithms which could be used if the new abstraction was supported by a binomial forest rather than a linked list. This represents the result of a tradeoff. By using inheritance in conjunction with the implementation of the old abstraction, we have traded off implementation quality in exchange for speed of implementation. The priority queue implementation obtained via the overriding of inherited operations is of very low quality, but this may or may not be an important consideration relative to the cost of providing a high-quality implementation. It has long been recognized that the time to worry about product efficiency is AFTER the product has been developed and put through a profiler to determine where the bottlenecks are in the system, since in this way the high cost of maximizing efficiency can be directed to the points at which it will do the most good. This principle extends to our derived priority queue implementation; if the profiler indicates that a software system is running with unacceptably slow speed due primarily to the time required to do priority queue operations, then a more sophisticated implementation of the priority queue which takes maximum advantage of the relationships between the set of required operations is probably a good idea. We then apply economic principles once again and try to find a software components supplier which will sell us a high-performance priority queue implementation, complete with formal specifications for each operation and timing results for typical workloads. In general, the components supplier will even be able to offer a number of different implementations, some of which will emphasize the particular operations which are most crucial to your system at the expense of others which are not as important. Now back to the problem under consideration... :-) > Suppose I have a type T1, and it has a message-method binding [...] Rephrasing, here is the problem: package Example is -- this is the specification type T2 is limited private; -- can't know or use the details procedure DO_SOMETHING_WITH (Parameter : in out T2); end Example; package body Example is -- this is the implementation -- type T1 has the operation OP1, and implementation IMP1. -- type T2 inherits operation OP1 and implementation IMP1 from T1. end Example; -- Now the user of package Example declares a new type, T3, -- which is_a T1 and also is_a T2. The user then specifies -- a new implementation, IMP2, for OP1. > I claim that (1) this should be legal, because the programmer has > no way of knowing that it should be illegal (information hiding, > right?) (2) An object O of type T3 should have the binding [OP1-IMP2] > where it is visible that O is a T3 (because that's what the programmer > said) (3) An object O of type T3 should have the binding [OP1-IMP1] > whenever it is in a context where it is known to be a T2, but not > known to be a T3 (because the programmer should not be able to > invalidate the correctness of a module if the internals of the > module are hidden). [In other words, if procedure DO_SOMETHING_WITH > is called, which expects a parameter of type T2, then IMP1 should be > used for the object of type T3 because it is expected to perform as > a T2 in that context.] [... C]hanges to the [implementation] bindings > for T1 by a subtype T3 *must not* change the behavior of T3 when > considered as a T2; any proofs about the behavior of a T2 would > thus go out the window (and the programmer would be clueless, because > the dependence of T2 on T1's [specification-implementation] bindings > is hidden). [...] > > I am *not* arguing that this should be the case if T2 is not opaque; > in that case everything is in the clear, and either an error message > or a change in T2's behavior is allowed. This nasty situation could > be avoided by creative prohibition (objects cannot be opaquely > exported -- yuck; opaque types cannot be inherited -- yuck; no > multiple inheritance -- many people say yuck, but that's what we live > with in Modula-3), but I'd be even happier if I could figure it out. First, let me give a reference to an important tutorial regarding the "synthesis of typing systems", as found in "Ada, an advanced language incorporating extensive support for various forms of abstraction", with "the powerful and flexible capabilities of OOP [object-oriented-programming]", which is entitled "Type Theories and Object-Oriented Programming" and can be found in ACM Computing Surveys, Vol. 20, No. 1, March 1988. Actual progress toward this objective is described by Wilf R. LaLonde in "Designing Families of Data Types Using Exemplars" (ACM Transactions on Programming Languages and Systems, Vol. 11, No. 2, April 1989), who argues that "designing families of data types is a programming-in-the- large problem", that "class-based systems need the notion of private types if they are to surmount their current limitations", and that "an advanced system should support the programming maxim that designers can switch implementations as they choose without impacting users. We show, using the implementation technique that we call programming by exemplars, that conventional class-based systems cannot help but violate the maxim. Exemplar-based systems support it easily.". Finally, I agree with each of your claims (1), (2), and (3), and in my opinion they are a natural consequence of the information hiding concept. As far as T3 is concerned, T2 does not HAVE any operations other than procedure DO_SOMETHING_WITH. Therefore, there can be no conflict between T3's inheritance of OP1 from T1, T3's provision of IMP2 for OP1, and T3's status as a T2 having the single operation DO_SOMETHING_WITH. The fact that T2 was declared internally to be an object having the operation OP1 as inherited from T1 is hidden from T3, and therefore is only of consequence within the package body which provides an implementation of T2 and its associated operation. Within that operation, we know that the parameter is of type T2, and therefore this "view" of T3 as a T2 will be supported. The T2 capabilities are visible to procedures such as DO_SOMETHING_WITH which have the needed authorization to view T2s, while also being hidden from T3 and from anything else which is external to the T2 implementation. Bill Wolfe, wtwolfe@hubcap.clemson.edu P.S. I will be in Pittsburgh during the week of October 23-27 for the Tri-Ada '89 conference, and therefore will not be able to respond to any followups until at least October 30th.
grover%brahmand@Sun.COM (Vinod Grover) (10/22/89)
In article <6845@hubcap.clemson.edu> billwolf%hazel.cs.clemson.edu@hubcap.clemson.edu writes: > It has long been recognized that the time to worry about product > efficiency is AFTER the product has been developed and put through > a profiler to determine where the bottlenecks are in the system, > since in this way the high cost of maximizing efficiency can be > directed to the points at which it will do the most good. For those of us without profilers, I suppose, there is no hope. Or perhaps we should worry about efficiency before the product has been developed, or perhaps not to worry about efficiency at all.
barmar@kulla (Barry Margolin) (10/23/89)
In article <126675@sun.Eng.Sun.COM> grover@sun.UUCP (Vinod Grover) writes: >For those of us without profilers, I suppose, there is no hope. Or perhaps >we should worry about efficiency before the product has been developed, or >perhaps not to worry about efficiency at all. Making a program efficient without a profiler is like making a program work without a debugger. Sure, you can manually sprinkle your code with print statements and timing statements, but it's not an efficient way to do it. Barry Margolin, Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
dick@ucsfccb..ucsf.edu (Dick Karpinski) (10/27/89)
In article <126675@sun.Eng.Sun.COM> grover@sun.UUCP (Vinod Grover) writes: >In article <6845@hubcap.clemson.edu> billwolf%hazel.cs.clemson.edu@hubcap.clemson.edu writes: >> It has long been recognized that the time to worry about product >> efficiency is AFTER the product has been developed and put through >> a profiler to determine where the bottlenecks are in the system, >> since in this way the high cost of maximizing efficiency can be >> directed to the points at which it will do the most good. > >For those of us without profilers, I suppose, there is no hope. Or perhaps >we should worry about efficiency before the product has been developed, or >perhaps not to worry about efficiency at all. It seems obvious to me that such of us that have that problem should fix it by making a profiler. Failing sufficient interest to do that job well, I have a simple technique for making inserted timing probes do the necessary work. My approach installs numbered probes into the application to collect timing information from the system and build a RAM table which is dumped in human readable form at end of run. In extreme cases (such as no clock) human keystrokes can be used to fake the clock. Remember, we only need crude information to detect which components are using most of the time. I'll happily tutor folks who need to do this by phone or email. Dick Dick Karpinski Manager of Minicomputer Services, UCSF Computer Center Domain: dick@cca.ucsf.edu (415) 476-4529 (11-7) BITNET: dick@ucsfcca or dick@ucsfvm (415) 658-6803 (Home) USPS: U-76 UCSF, San Francisco, CA 94143-0704 (415) 658-3797 (ans)