stt@inmet.inmet.com (12/04/90)
We are looking for a few good examples of multiple inheritance in the programming language (especially C++) arena (as opposed to OODB, OOD, OOA arenas) The examples in Meyer's Eiffel book tend to be used to represent the equivalent of module interdependence (Modula's IMPORT, Ada's WITH). The examples in SigPlan Notices and elsewhere seem weak and relatively easily recast using single inheritance or component structures. We are looking for an example of a C++ class (or Eiffel, Objective C, etc.) which is a "true" sub-class of two (or more) parent classes; that is, it bears the "is-a" relationship to multiple parents. Our hypothesis is that multiple inheritance can rarely be useful unless planned for in advance, which seems to defeat the purpose. If it does require advance planning, then we anticipate that those situations would be amenable to other structures, perhaps, for example, a component with a pointer to its enclosing object. Multiple inheritance seems to add significant overhead to an OOPL even when not being used in a system, so we are looking for convincing examples that it's benefits outweigh the cost. Thanks in advance. S. Tucker Taft Intermetrics, Inc. 733 Concord Avenue Cambridge, MA 02138 stt@inmet.inmet.com ...!uunet!inmet!stt
honda@csl.sony.co.jp (Yasuaki Honda) (12/04/90)
If you want see the real use of multiple inheritance, you should see Symbolics Lisp Machine. There are a lot of classes (flavors) which are defined for mixin. Especially, programs for its window system and network system heavyly use mix-in flavors (as far as I remember). Unfortunately this is written in lisp and not in c++ nor some such. Hope this helps. honda@csl.sony.co.jp -- ************************************** Yasuaki Honda honda@csl.sony.co.jp SONY Computer Science Laboratory Inc. **************************************
dag@control.lth.se (Dag Bruck) (12/04/90)
I have once made good use of MI in C++. The task was to implement a logging window using the AT&T iostream library and the InterViews user interface library. The low-level output of iostream was made by deriving from `streambuf'. The user interface was was derived from an `HBox' in order to combine a `TextDisplay', a scrollbar, etc. I also added functionality so the window de-iconizes itself when new output arrives. Please note that the use of MI in the AT&T iostream library is not involved here -- the `streambuf' is at a lower level. I think this application of MI was sucessful. It was a practical way of combining two class hierarchies, and I think the solution is very clean. This application could easily have been implemented without MI (I drafted such a solution as well), but I guess this would have required writing more code. Dag M. Bruck -- Department of Automatic Control E-mail: dag@control.lth.se Lund Institute of Technology P. O. Box 118 Phone: +46 46-104287 S-221 00 Lund, SWEDEN Fax: +46 46-138118
tom@ssd.csd.harris.com (Tom Horsley) (12/04/90)
>>>>> Regarding Examples of Multiple Inheritance?; stt@inmet.inmet.com adds: stt> We are looking for an example of a C++ class (or Eiffel, Objective C, stt> etc.) which is a "true" sub-class of two (or more) parent classes; stt> that is, it bears the "is-a" relationship to multiple parents. I think the AT&T <iostream.h> implementation may be a good example. It has input streams and output streams and streams that can do both input and output that inherit from both (at least I think it does, I don't actually have AT&T C++ yet). This seems like a fairly natural way to do this sort of thing (although the earlier <stream.h> achieved similar functionality without MI since it was written before MI was implemented in C++). -- ====================================================================== domain: tahorsley@csd.harris.com USMail: Tom Horsley uucp: ...!uunet!hcx1!tahorsley 511 Kingbird Circle Delray Beach, FL 33444 +==== Censorship is the only form of Obscenity ======================+ | (Wait, I forgot government tobacco subsidies...) | +====================================================================+
dlw@odi.com (Dan Weinreb) (12/05/90)
In article <60700005@inmet> stt@inmet.inmet.com writes:
Our hypothesis is that multiple inheritance can rarely be useful
unless planned for in advance, which seems to defeat the purpose.
If it does require advance planning, then we anticipate that those
situations would be amenable to other structures, perhaps, for example,
a component with a pointer to its enclosing object.
This has not been the experience of many years of work with Flavors at
Symbolics. The problem is that it's hard to come up with simple
examples that illustrate why multiple inheritance is important;
multiple inheritance is not needed for any example simple enough to
explain briefly. See Sonya Keene's book "Object-Oriented Programming
in Common Lisp" for the best small examples I've ever seen.
A typical larger example used at Symbolics are the pathname classes,
of which there is one for each format of pathname understood by the
system; typically each operating system that can be talked to over the
network has its own format. Some pathnames are hierarchical and some
are not. Some have a "device" field and some do not. Some are all
upper-case, some all lower-case, some use both cases and distinguish
between case, some use both but don't distinguish, etc. Multiple
inheritance lets you mix and match, making the code more modular.klimas@iccgcc.decnet.ab.com (12/05/90)
In article <60700005@inmet>, stt@inmet.inmet.com writes: > Our hypothesis is that multiple inheritance can rarely be useful > unless planned for in advance, which seems to defeat the purpose. > If it does require advance planning, then we anticipate that those > situations would be amenable to other structures, perhaps, for example, > a component with a pointer to its enclosing object. > > Multiple inheritance seems to add significant overhead to an OOPL even > when not being used in a system, so we are looking for convincing > examples that it's benefits outweigh the cost. A few comments, 1)I have thrown out the same challenge to the Smalltalk community (yes ST-80 once had it and ST /V286 does support MI in the hierarchy via a simple change to Behavior, and there have been 3rd party add on browsers for V/286) for quite a while now, and I have not gotten any substantive examples other than simple mixins to date. 2)This is not a new topic. Per Borning and Engals 1982 "M. I. in ST-80" Proc. of the Ntnl. conf. on AI, "The attempts at MI have not achieved the elegance and simplicity of single inheritance." 3)A lot of people claim that MI is a strength of C++, however a number of companies that are developing in C++ also have internal policies that prohibit the use of MI because of the potential for unmanageable complexity explosions in solutions that are of any size. With MI in C++, the user must now know about how every class and method is used so that if he inserts a class in the hierarchy he won't break it. This goes against the idea of "comprehension avoidance", i.e. for effective programming, limit the amount of stuff a programmer needs to know about a system to interact with it.
ajs@prg.ox.ac.uk (Adolfo Socorro) (12/05/90)
There are lots. How about
Person
/ \
Student Teacher
\ /
Teaching Assistant
or perhaps
Account
/ \
Savings Checking
Account Account
\ /
NOW Account
Adolfo Socorrofranke@lynx.cad.mcc.com (David Franke) (12/05/90)
In article <60700005@inmet> stt@inmet.inmet.com writes: > >We are looking for a few good examples of multiple inheritance >in the programming language (especially C++) arena (as opposed to OODB, >OOD, OOA arenas) > ... >We are looking for an example of a C++ class (or Eiffel, Objective C, >etc.) which is a "true" sub-class of two (or more) parent classes; >that is, it bears the "is-a" relationship to multiple parents. I believe that I can provide such an example. I have been interested in imbedding rule inferencing in CAD tools, have developed an objected-oriented approach, and have implemented this approach in C++. (An article, "Embedding Rule Inferencing in Applications" will appear in Dec. 90 IEEE Expert). The basic idea is that an inference-object class is defined that a tool developer can include (derive from) when creating classes needed for the tool. While the tool views instances of the derived class for its purposes (e.g. schematic editing, timing analysis), the inference engine can view these same instances for its purpose. As you state, this derived class "is-a" tool object and "is-a" inference engine object. >Our hypothesis is that multiple inheritance can rarely be useful >unless planned for in advance, which seems to defeat the purpose. It is certainly true in this case that the multiple inheritance was planned in advance. The primary motivation has been the ability to integrate the inferencing capability into an existing tool (developed in C++) and tools under development with the least possible impact on tools defined classes. Multiple inheritance provides such a mechanism to accomplish this integration. >Multiple inheritance seems to add significant overhead to an OOPL even >when not being used in a system, so we are looking for convincing >examples that it's benefits outweigh the cost. IMO, multiple inheritance solves a significant problem in the application I have described. Specifically, the problem is that not all classes defined by a tool will be of interest in inferencing, and hence need not derive from the inference-object class. If the class hierarchy defined by the tool is very rich, one does not want to reference the inference-object class from one of the most general classes in the hierarchy (i.e. use only single inheritance), since it (the inference- object class) will probably participate in derived classes for which there is no interest with respect to inferencing. Multiple inheritance allows the tool developer to define an inferencing capability for only those objects of interest, avoiding overhead in those objects for which inferencing is not needed. >S. Tucker Taft >Intermetrics, Inc. >733 Concord Avenue >Cambridge, MA 02138 > >stt@inmet.inmet.com ...!uunet!inmet!stt David Franke, MCC CAD Program | ARPA: franke@mcc.com | Phone: [512] 338-3641 UUCP: {uunet,harvard,gatech,pyramid}!cs.utexas.edu!milano!cadillac!franke
dlw@odi.com (Dan Weinreb) (12/06/90)
In article <2277.275bdf0b@iccgcc.decnet.ab.com> klimas@iccgcc.decnet.ab.com writes:
1)I have thrown out the same challenge to the Smalltalk
community (yes ST-80 once had it and ST /V286 does support MI in the
hierarchy via a simple change to Behavior, and there have been 3rd
party add on browsers for V/286) for quite a while now, and I have
not gotten any substantive examples other than simple mixins to date.
Since most Smalltalk users do not have access to a language with
multiple inheritance, it is hardly surprising that they are not a good
source of examples of multiple inheritance.
2)This is not a new topic. Per Borning and Engals 1982 "M. I. in ST-80"
Proc. of the Ntnl. conf. on AI, "The attempts at MI have not achieved
the elegance and simplicity of single inheritance."
That's quite true. But that wasn't the question. The question was
whether multiple inheritance was genuinely useful. Fixed point is a
lot more elegant and simple than floating point, but many people find
floating point useful for certain applications.
3)A lot of people claim that MI is a strength of C++, however a number
of companies that are developing in C++ also have internal policies that
prohibit the use of MI because of the potential for unmanageable
complexity explosions in solutions that are of any size. With MI in
C++, the user must now know about how every class and method is used
so that if he inserts a class in the hierarchy he won't break it. This
goes against the idea of "comprehension avoidance", i.e. for effective
programming, limit the amount of stuff a programmer needs to know
about a system to interact with it.
Instead, when these companies try to model things that are best
described by multiple inheritance, they'll be forced to use something
kludgy and awkward instead, which will end up confusing their
programmers in the long run and making the software harder to
maintain. You cannot eliminate complexity by simply deeming that it
shall not be there. I certainly don't recommend using multiple
inheritance where single inheritance will do just fine. I can even
believe that it's sometimes better to avoid multiple inheritance if
single inheritance plus a small kludge can do almost as well. But
sometimes multiple inheritance is the natural way to model something,
and it should be used in those cases.muller@src.umd.edu (Christophe Muller) (12/06/90)
In article <60700005@inmet> stt@inmet.inmet.com writes: > We are looking for an example of a C++ class (or Eiffel, Objective C, > etc.) which is a "true" sub-class of two (or more) parent classes; > that is, it bears the "is-a" relationship to multiple parents. I read a couple of replies and would like to add the point of view of a modeling engineer (i.e., somebody who builds _models_ of _real_ systems to perform discrete event simulations). If MI is necessary for me, it is because MI exists *everywhere* in reality. Just like lists for example (you don't have 56 employees, you have _a certain number_ of employees that happens to be 56 at current time). I want to add however, that I'm not interested at all by speed issues or compiler implementation issues (everybody has his own problems :-). I want a program that does the job first, then if it can be fast it's even better, but that's not the main goal (I'm this kind of guy that prefers Pascal to C and Eiffel to C++ (and also both last ones to both first ones :-)). So let's take an example for MI. This one is extracted from B. Stroustrup's book (The C++ Programming Language): class temporary { ... }; class employee { ... }; class secretary : employee { ... }; class temporary_secretary : temporary, secretary { ... }; class consultant : temporary : employee { ... }; This example seems perfect to me. temporary_secretary IS-A true temporary worker and also IS-A true secretary.. Now the kind of ADTs that these three classes will define is irrelevant for me. I'm using the language first as a _design_ tool. When I'm writing a model of a factory, I start by identifying the types of objects that I could need for the simulation and the relations that they have between each other, *then* I will be thinking of ADTs (behaviors, attributes, etc..) but at the beginning I have no clue what the heck a grinder or a lathe could be used for and even less what characterizes them! Maybe there will be even *nothing* in the class temporary! (so what's the use of MI here? :-D) But it's important for me to write it down in the design document if I have this information. Now it's true that this design may not guide us to the fastest implementation, but once more I don't think it's a good idea of thinking about optimizations while writing specifications or design documents.. However why not thinking about optimizations *after*? If it's _so_ easy to write a program not using MI that does the same job, why not designing some semantic tools that will translate my slow MI-program to a fast non-MI-one? (Note: I have no idea if it's possible or not.. I leave that to the gurus :-) > Our hypothesis is that multiple inheritance can rarely be useful > unless planned for in advance, which seems to defeat the purpose. > If it does require advance planning, then we anticipate that those > situations would be amenable to other structures, perhaps, for example, > a component with a pointer to its enclosing object. I'm not sure to understand this paragraph. What does "planned for in advance" mean? There are always plenty of different possible programs that will solve a problem, but there is only one best (simplest? more readable? more maintenable? more optimized?) one. That's why OO exists. (from Ed Berard's article: "What is OO ...") << It is important to realize that Kay viewed object-oriented techniques as a means of _simplifying_ computer usage. When you hear people say things like, "object-oriented systems more closely resemble 'real life' than do, for example, functional decomposition systems," they are echoing Kay's original intentions. >> That would be my conclusion. I don't think this aspect of "programs modeling real-life" only applies to discrete event simulations. There are plenty of applications where objects are based on existing ones and not only hash- tables or io-libraries. The temporary_secretary example seems rather "cobolian" to me. So should you use MI in your company? It depends on the type of software you write, it depends if speed is an important issue for you (or if like me you are running your simulations at night :-), and it depends whether a "simplification" of your programs is important or not. Cheers, Christophe. = The C Programming Language -- A language which combines the = = flexibility of assembly language with the power of assembly language. =
schemers@vela.acs.oakland.edu (Roland Schemers III) (12/06/90)
In article <60700005@inmet> stt@inmet.inmet.com writes: >We are looking for an example of a C++ class (or Eiffel, Objective C, >etc.) which is a "true" sub-class of two (or more) parent classes; >that is, it bears the "is-a" relationship to multiple parents. > I have written some C++ classes that use MI extensively. The library is called Transport, and stands for Network Transport. Simply put, a Transport is something that lets you send data from place to another. Here is the layout of the classes: class Transport; class Socket inherit from Transport; class UnixSocket inherit from Socket; class InetSocket inherit Socket; class DECnetSocket inherit from Socket; class TransportStream inherit from Transport; class SocketStream inherit from Socket and TransportStream; class UnixStream inherit from UnixSocket, and SocketStream; class InetStream inherit from InetSocket, and SocketStream; class DECnetStream inherit from DECnetSocket and SocketStream; class TransportDatagram inherit from Transport; class SocketDatagram inherit from Socket, and TransportDatagram; class InetDatagram inherit from InetSocket and SocketDatagram; So a InetStream object is a Transport, Socket, InetSocket, TransportStream, SocketStream, and InetStream object! Roland -- Roland J. Schemers III Systems/Network Manager schemers@vela.acs.oakland.edu (Ultrix) Oakland University schemers@argo.acs.oakland.edu (VMS) Rochester, MI 48309-4401 ~Disclaimer::Disclaimer() { reboot(RB_HALT); } (313)-370-4323
barmar@think.com (Barry Margolin) (12/06/90)
One thing I haven't seen anyone mention in this discussion is that the
utility and elegance of MI is strongly influenced by the quality of the MI
scheme provided by the language. I'm familiar with Flavors and CLOS, and
have a passing knowledge of C++, and C++ doesn't make it nearly as easy to
make use of MI (perhaps Dan Weinreb, who has migrated from Flavors to C++,
could comment on this).
For instance, Flavors' and CLOS's method combination methodology makes a
"mixin" approach to OO very elegant. Specifically, the handling of method
name conflicts among a class and its superclasses strongly affects the
usability of the inheritance mechanism. In Flavors and CLOS a generic
function can be specified to invoke all the methods (perhaps combining the
results in some way), and "before" and "after" methods can be defined so
that a mixin class may easily augment the behavior of an object. In C++,
inherited member name conflicts must be resolved explicitly by the
programmer; if a new parent class is added to a class the programmer must
then update all the conflicting member functions to implement the method
combination.
The result of this is that C++ functions with complex MI schemes end up
with lots of functions that look like:
class Parent1 { public: function(); };
class Parent2 { public: function(); };
class Parent3 { public: function(); };
class Derived : public Parent1, public Parent2, public Parent3
{ public : function(); };
void Derived::function()
{
// encapsulate the ambiguous inherited members
Parent1::function();
Parent2::function();
Parent3::function();
// Now do stuff specific to the Derived class
}
When looking at this one is tempted to say that it would work just as well
if the parents were separate objects, and Derived simply contained them; it
would look like:
class Derived {
public:
function();
protected:
Parent1 p1;
Parent2 p2;
Parent3 p3;
};
void Derived::function()
{
// forward the operation to the "parents"
p1.function();
p2.function();
p3.function();
// Now do stuff specific to the Derived class
}
Of course, the reason not to do this is that this forces Derived to
reimplement *all* the member functions of all its parents, not just the
ones that conflict. C++ multiple inheritance is reasonable when all the
parents provide disjoint pieces of behavior (e.g. iostream inheriting from
istream and ostream), but it's painful when the parents are all
contributing to the same behavior (e.g. in a window system, each parent may
want to modify the way the window is displayed).
--
Barry Margolin, Thinking Machines Corp.
barmar@think.com
{uunet,harvard}!think!barmarbrandis@inf.ethz.ch (Marc Brandis) (12/06/90)
In article <980@culhua.prg.ox.ac.uk> ajs@prg.ox.ac.uk (Adolfo Socorro) writes: >There are lots. How about > > Person > / \ > Student Teacher > \ / > Teaching Assistant > >or perhaps > > Account > / \ > Savings Checking > Account Account > \ / > NOW Account > Sorry, but I think you are missing the point. The fact that there are examples in the real world where a thing has properties of several other things does not imply that you need multiple inheritance in a programming language. Very often, the kind of situations that you are describing can be solved by using references to other objects and just deriving from one class. You may argue that this is not a direct projection of the real world into the program, but this is not needed at all. What would be interesting are some examples where multiple inheritance was useful in writing a large program, which would have been much harder to implement without it. Marc-Michael Brandis Computer Systems Laboratory, Swiss Federal Institute of Technology CH-8092 Zurich, Switzerland email: brandis@inf.ethz.ch
tok@stbimbo.UUCP (Terry Kane) (12/06/90)
Regarding the hypothetical companies which prohibit the use of MI in C++ systems for fear of "complexity entropy": It seems to me (and please forgive me if I'm restating the obvious, not having a reliable news server for some time) that the feared complexity should not arise if a proper class hierarchy is designed. I inferred from the previous postings that the company fears collisions of class properties. E.G. Which nearly equal member function to use? If there are intersections of class then the hierarchy is probably not a good one nor should it be considered OOD, rather it is just "better C", c.f. Booch OODw/a.
pcg@cs.aber.ac.uk (Piercarlo Grandi) (12/07/90)
On 3 Dec 90 20:05:00 GMT, stt@inmet.inmet.com said: stt> We are looking for a few good examples of multiple inheritance stt> in the programming language (especially C++) arena (as opposed to OODB, stt> OOD, OOA arenas) The small book on CLOS, "Object Oriented programming in CL" has I think fairly good ideas and examples about MI. Because they treat it as an algebra of mixing and matching interfaces. Also look at Trellis, and Emerald. Recent issues of OOPSLA and POPL proceedings also have interesting discussions on mixing and matching interfaces, implementations and specifications in a less constrained way than MI. stt> We are looking for an example of a C++ class (or Eiffel, Objective C, stt> etc.) which is a "true" sub-class of two (or more) parent classes; stt> that is, it bears the "is-a" relationship to multiple parents. Haha. So you haven't read my all important, wonderful and revolutionary thoughts on the matter :-). So you don't say which is-a relationship you mean; is-a as interface, as implementation, or as specification? MI in traditional OO languages implements composition of interfaces mainly, and subsidiarily composition of implementations (or viceversa depending on the style of language). Normally (with some exception in Eiffel and a few others) it deals not with composition of semantics. If you read Lippman's book on C++ you get the impression that MI is about (hierarchical) data design (in the database sense). Uhmmmm. I tend to be skeptical :-). Data design is a more serious issue than MI. To confuse data design with reuse seems to be fairly strange. stt> Our hypothesis is that multiple inheritance can rarely be useful stt> unless planned for in advance, which seems to defeat the purpose. stt> If it does require advance planning, then we anticipate that those stt> situations would be amenable to other structures, perhaps, for example, stt> a component with a pointer to its enclosing object. The latter is known as "delegation" if brought to its logical conclusion. Note that inheritance as we commonly know it is actually nothing else than a syntactic device by which fields of fields of a record can be named as if they were fields of that record (e.g. assuming that it is unambiguous, derived.base.field can be abbreviated as derived.field), i.e. union of interfaces. The really interesting bits are overloading and genericity, either static or dynamic. These are good problems even if you don't have "inheritance". These are problems about static or runtime matching of functions with types. They exist and demand a solution even in non OO languages; consider X windows for example. What we need is a nice notation to express the same things that we already do clumsily in Lisp, or C, or Ada (even if it does not have functions as first class objects, and thus no runtime genericity, unless you use access types to tasks). We also need that the notation be a bit supported by the environment, and without crazy limitations (consider the difficulty one has in Ada to provide and let the user choose different bodies for the same package spec, and the _impossibility_ to do viceversa). stt> Multiple inheritance seems to add significant overhead to an OOPL stt> even when not being used in a system, This is *not* true. What adds overhead is dynamic overloading and dynamic genericity (the static varieties are nearly cost free). They are just a bit more expensive under multiple than single inheritance simply because the prefixing trick (which puts base objects at offset zero in the derived one) is not in general possible, so one has to deal with non zero offsets either at compile time (if no virtual bases are involved) or runtime (if virtual bases are involved). stt> so we are looking for convincing examples that it's benefits stt> outweigh the cost. Note that multiple (interface,implementation,specification) composition is a need, and so are dynamic/static overloading/genericity. You can only choose whether to put them in the language as primitives, or to let the programmer simulate them (just like non nested control and environment structures). I think that even if they are rarely used (but they are not! Simply people do not know they are simulating them!) they had better be in the language, because otherwise one needs to do contortions (like using access types to tasks instead of to procedures in Ada...). -- Piercarlo Grandi | ARPA: pcg%uk.ac.aber.cs@nsfnet-relay.ac.uk Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk
dlw@odi.com (Dan Weinreb) (12/07/90)
In article <13688@cadillac.CAD.MCC.COM> franke@lynx.cad.mcc.com (David Franke) writes: >Our hypothesis is that multiple inheritance can rarely be useful >unless planned for in advance, which seems to defeat the purpose. It is certainly true in this case that the multiple inheritance was planned in advance. I don't see anything wrong with planning in advance. Indeed, many people actually think that it is a virtue to design software in advance. :-) The reason for multiple inheritance is not specially to facilitate unplanned ex-post-facto kludges. Seriously, in most cases of multiple inheritance that I know about, it was entirely planned that way from the beginning.
halbert@crl.dec.com (Dan Halbert) (12/07/90)
[reposted with wrapped lines - sorry] The DEC Trellis language provides multiple inheritance. We coded the programming environment for Trellis in Trellis, and found multiple inheritance to be very useful. However, most uses are not of the Teacher/Student type of combination, where two conceptually "equal" types are merged. Instead, we usually use multiple inheritance to guarantee that a certain type will obey some protocol, ancillary in nature. For example, a number of the basic data types provided in the Trellis type library are subtypes of the abstract types Readable and/or Printable, which define operations for reading and writing representations of these types to and from streams. Another common ancillary abstract type is Hashed, which defines an operation that returns an Integer hash value for an object. Integer, for instance is a subtype of both Readable and Hashed (Readable is a subtype of Printable). In our window system code, we also used multiple inheritance. We call widget-like objects "frames". Some frames, in addition to their mainline inheritance, are subtypes of type Selector, which means they display things which can be selected (e.g. text or lists). These ancillary abstract types define operations, but often don't provide implementations for them, or provide a general purpose implementation. If there is no implementation, it is up to the subtypes that inherit them to provide implementations. The Trellis compiler checks that non-abstract types have implementations for all defined operations. --Dan Halbert
johnson@m.cs.uiuc.edu (12/07/90)
>MI in traditional OO languages implements composition of interfaces >mainly, and subsidiarily composition of implementations (or viceversa >depending on the style of language). Normally (with some exception in >Eiffel and a few others) it deals not with composition of semantics. I could argue with this (and will). MI in the Lisp world is primarily composition of implementations. It is clear from Dan Halbert's description of MI in Trellis that MI is used there primarily for composition of interfaces. Thus, MI means different things to different people. Most of you are probably tired of hearing that I think that interface and implementation should be reused by different mechanisms; i.e. I think that types and classes are different, and that subclassing and subtyping should be different as well. MI of interface is important, but I would be happy to live without MI of implementation. In fact, I do! Ralph Johnson -- University of Illinois at Urbana-Champaign
dlw@odi.com (Dan Weinreb) (12/08/90)
In article <1990Dec6.020928.13319@Think.COM> barmar@think.com (Barry Margolin) writes:
and C++ doesn't make it nearly as easy to
make use of MI (perhaps Dan Weinreb, who has migrated from Flavors to C++,
could comment on this).
That's right. In a nutshell, the basic difference is that in CLOS, a
"mixin" flavor can be an independent, reusable module. You can build
new flavors by inheriting from pre-existing mixins, and they all join
together and work, without modification of code. C++ does not have
this concept, and modification of code is needed much more frequently,
because individual classes in C++ have the names of parent classes
textually embedded within them. The fundamental facility of CLOS that
C++ lacks is "call-next-method".
(I bet that another reason that there is presently less experience
than you might expect with C++ MI is that the AT&T-based
implementations still have some implementation problems, particularly
with virtual base classes. This has nothing to do with C++, the
language definition, of course, but it affects its manner of usage in
the short term.)pcg@cs.aber.ac.uk (Piercarlo Grandi) (12/09/90)
On 5 Dec 90 19:19:33 GMT, muller@src.umd.edu (Christophe Muller) said:
muller> So let's take an example for MI. This one is extracted from B.
muller> Stroustrup's book (The C++ Programming Language):
muller> class temporary { ... };
muller> class employee { ... };
muller> class secretary : employee { ... };
muller> class temporary_secretary : temporary, secretary { ... };
muller> class consultant : temporary : employee { ... };
muller> This example seems perfect to me. temporary_secretary IS-A true
muller> temporary worker and also IS-A true secretary..
This is a perfect example of the poverty of the common understanding of
the IS-A relationship instead. In what sense temporary_secretary IS-A
temporary and a secretary? In the sense that the concepts of temporary
and secretary are in some way united in temporary_secretary? Or in the
sense that the records that describe some aspects of those concepts are
somehow merged? Or in the sense that you can invoke on a temporary
secretary value all the operations you can on a temporary or secretary?
Not defining precisely all these nice little details generates fuzzy
warm ffeling and bad engineering. OO programming is more like databases
(data design!) than knowledge bases.
IS-A is just an equivalence relationship. As such it can be used to
build taxonomies. The really interesting questions are:
1) What is the domain of your IS-A equivalence class generator?
2) What kind of precise equivalence definition do you want in that domain?
2) What is the algebra for the generated equivalence classes?
My answers for now are something like that there are at least three
domains or dimensions, specification, protocol, and implementation
(pragmatics is as important but not commonly recognized) over which you
want to build taxonomies (partitioning entities according to the
equivalence of their specification, or of their protocol, or of their
implementation), and that entities you want to classify along those
three dimensions are values and functions.
The goal of this taxonomy business is to devise good (de)composition
criteria for build composite entities in the three dimensions, so that
the resulting composite exhibits "good" structural properties.
Existing mechanisms like inheritance are an an appallingly poor and
misleading technology in this respect; it is both unorthogonal and
incomplete (it is neither orthogonal nor a base in the data design
concept space). This is clearly demonstrated by all the problems in most
OO languages with defining suitable algebras for combining the generated
equivalence classes, which in general are extremely poor, allowing only
for addition, and in the ad hoc devices used to uncouple the three
dimensions, like abstract classes, a lame attempt at decoupling the IS-A
operator on the domain of interfaces from the IS-A operator on the
domain of implementations. And the confusion of these issues with those
of dynamic and static overloding and genericity, which are quite
separate.
CLOS maybe, by leaving the door open for all possible solutions, and by
being oh so very unconstrained and redundant, seems to me the closest to
a suitable solution, only that it is so unstructured. BETA has some very
interesting ideas, and so a few others.
--
Piercarlo Grandi | ARPA: pcg%uk.ac.aber.cs@nsfnet-relay.ac.uk
Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.ukdlw@odi.com (Dan Weinreb) (12/09/90)
In article <77500069@m.cs.uiuc.edu> johnson@m.cs.uiuc.edu writes:
I could argue with this (and will). MI in the Lisp world is primarily
composition of implementations. It is clear from Dan Halbert's
description of MI in Trellis that MI is used there primarily for
composition of interfaces. Thus, MI means different things to
different people.
In my experience with Lisp, it was often used for both purposes.
Most of you are probably tired of hearing that I think that interface
and implementation should be reused by different mechanisms; i.e. I
think that types and classes are different, and that subclassing and
subtyping should be different as well. MI of interface is important,
but I would be happy to live without MI of implementation. In fact,
I do!
Perhaps you do, but "mixin" classes that modify behavior have turned
out, many times, to be an elegant and simple way to express desired
behavior. Of course they're not "necessary"; no programming language
feature is. But they are a useful tool, and once you learn how to use
the tool properly (modularly and tastefully), and when you build large
systems with complex requirements, you often find that it is a good,
appropriate tool.
The question of providing separate concepts of "inheritance of
protocol (specification)" and "inheritance of implementation" is one
that we debated for some time in the design of Flavors. Generally I
was in favor of introducing a separate concept of inheritance of
specification, on the grounds that by forcing the programmer to see
that it was something different, the programmer would end up
understanding things better. Dave Moon, on the other hand, was
opposed to the separation on the grounds that it would make Flavors
more complex and hard to learn and verbose. I liked the idea that two
classes might implement the same protocol, but not actually share any
ancestors, because they might have totally independent
implementations. Moon really didn't like the idea of having two
separate hierarchies, one for protocols and one for implementations,
for the reasons I cited. Another problem with the two-hierarchy
design was that the interactive programming environment tools would
get more numerous and complex. Instead, Moon preferred the idea of a
single hierarchy. If there were multiple independent implementations,
they'd both inherit from a purely-abstract class, that served to
define the hierarchy but did not contribute any implementation.
When CLOS was designed, based on Flavors and CommonLoops, the key
designers (Bobrow, Moon, Kiczales, et. al.) decided against
introducing the distinction. I can't speak for their reasons.
I believe that Dan Halbert once told me that the Trellis designers
spent a lot of time considering the same question, and decided that
separating the two concepts would result in unacceptably excessive
complexity in the language design, and be too hard for programmers to
understand. I believe the idea of having two different hierarchies
was also something they wanted to avoid. Note: I might be expressing
this poorly, since I'm trying to remember a short remark from years
back, and I am by no means a Trellis expert.
C++, of course, is like Flavors too: one hierarchy, and you use an
abstract class that contributes no implementation if you have
independent implementations of a protocol.
I'm also not exactly sure that the two-way decision that you are
talking about is exactly the same as the one that Moon and I debated,
nor the one that the Trellis designers considered. There are a lot of
possible language designs, not just two choices. So I hope I'm not
promulgating any misunderstandings.paj@mrcu (Paul Johnson) (12/10/90)
I think that this debate is missing the point. Neither MI or SI make simple examples easier to code. If you have fully analysed your problem and know what routines are to be called where then you can code in Pascal or C just as easily. The point about inheritance and polymorphism is that they contribute to code flexibility and reuse. When the requirements change (as they always do) then a well designed OO program is far superior because the existing abstract classes (what Meyer terms "deferred" classes) from which the actual classes inherit become the basis for new classes. MI allows the designer to increase the number of abstract classes in the system and thereby increases the flexibility of the system. Paul. -- Paul Johnson UUCP: <world>!mcvax!ukc!gec-mrc!paj --------------------------------!-------------------------|------------------- GEC-Marconi Research is not | Telex: 995016 GECRES G | Tel: +44 245 73331 responsible for my opinions. | Inet: paj@uk.co.gec-mrc | Fax: +44 245 75244
Marc.Herrmann@ec.bull.fr (12/10/90)
> Very often, the kind of situations that you are describing can be > solved by using references to other objects and just deriving from one class. By doing so don't you implement multiple inheritance by using simple inheritance + delegation ? Could you clarify your point? Thanks, Marc ============================== Marc Herrmann Bull S.A. 1, rue de Provence BP 208 38432 Echirolles Cedex, FRANCE email: Marc.Herrmann@ec.bull.fr
weigand@kub.nl (Hans Weigand) (12/11/90)
In article <1990Dec6.185634.24199@crl.dec.com> halbert@crl.dec.com writes: > >The DEC Trellis language provides multiple inheritance. .. > ... However, most uses are not of the >Teacher/Student type of combination, where two conceptually "equal" >types are merged. Just a side remark, but I doubt that even in this case the two concepts merged are equally important. Teacher-assistant is primarily a subtype of Teacher, besides subtypes like professor, assistant-professor etc. On the Student side, there is not such a subcategorization. Hans Weigand weigand@kub.nl Tilburg University
stt@inmet.inmet.com (12/12/90)
Re: Examples of Multiple Inheritance?
Here are my proposals for handling Multiple Inheritance
in programming languages:
There seem to be two relatively distinct ways in which MI
is used: as a mix-in to a known base class, and as a combination
of otherwise unrelated classes. It would seem that if these two
uses were clearly distinguished, then the resulting model
might actually be easier to understand and implement efficiently.
Note that C++ makes effectively this distinction via
the concept of "virtual" base classes, but I find their terminology
confusing, and they don't seem to get any major implementation
or conceptual simplification from this distinction.
MIX-INS
When structuring a system with mix-ins, a base class
tends to be partitioned into independent "aspects" (inventing
terminology here), and a given mix-in is "responsible" for
a particular aspect of the behavior of the class.
For now, let us name these mix-ins as follows:
<base-class>.<aspect>.<mix-in-name>
A given subclass of the base class must select the appropriate
mix-in for each aspect, or accept by default the behavior selected
by its immediate superclass.
A given mix-in should not presume that some other specific
mix-in has been chosen, but it may assume that, for each
aspect of behavior, a mix-in has been chosen to handle it.
This guarantees independence of implementation of mix-ins,
while they may all depend on the interface of the base class.
COMBOS
When building up a class by combining unrelated parent classes,
the goal is to have a single object which can "pretend"
it is an instance of any of the parent classes. Furthermore, in overriding
the behavior of one of the parent classes, the implementation
of a method for the combo class may take advantage of the presence of methods
defined on the other parents. Apparently, each parent is handling
a different "aspect" of the behavior of the combo class.
For now, let us name each parent of a class as:
<combo-class>.<aspect>.<parent-class-name>
MIX-IN COMBOS?
If you compare mix-ins with combos, there is a striking duality.
Combos are effectively creating a "mix-in" situation after the fact.
Two parents of a combo could be considered the default (mix-in)
implementations of two aspects of the behavior of the combo.
Given a combo, it would seem to make sense to extend it
using the mix-in approach, now overriding the default implementation
of each aspect, originally inherited from a parent, with
implementations which may "know" they are mix-ins to the
(base) combo-class.
PARTITIONED INTERFACE
In both of the above approaches, it seems that it is natural
to partition the overall interface of a class into multiple
"aspects." Aspects then become the unit for replacement
on a mix-in basis.
The interface to an "aspect" should
be independent of the interface to any other aspect.
The implementation of an aspect specifies its assumptions,
by identifying which base-class it is based on, which indirectly
indicates what other aspects are supported.
Alternatively, the implementation of an aspect (i.e. a mix-in)
could directly identify which other aspects it depends on, and any base class
which includes implementations for those aspects may select
that mix-in.
ASPECTS = MODULES?
If we treat aspects as modules, then we see a clear resemblance between
the module concept of Modula-2 or the package concept of
Ada, and aspects, with the "import" clause or the "with" clause
indicating the inter-aspect dependence.
However, it is still useful to have higher level encapsulation
constructs like modules or packages, in which sets of related
classes are declared.
STRAWMAN
Here is a strawman proposal which incorporates the above thinking:
-- Define an aspect for use in a class
aspect Fum is
{visible attribute/component}
{visible operation}
end Fum;
-- Define another aspect for use in a class
aspect Foo is
{visible attribute/component}
{visible operation}
end Foo;
-- Define an implementation of the Fum aspect
with Foo; -- Require aspect Foo to be present in class
aspect body Fum.Foozle is
-- Code within here may call operations defined for Foo aspect
{private attribute/component}
{body for private operation}
{body for visible operation}
end Fum.Foozle;
aspect body Foo.Frazzle is
-- Implementation of Foo operations
. . .
end Foo.Frazzle;
-- Define a class which has various aspects
class Combo_Mix_In combines Foo.Frazzle, Fum.Foozle;
. . .
-- Define an instance of the class
X : Combo_Mix_In;
-- Now we can say things like:
X.Fum.<visible Fum operation>(...);
X.Foo.<visible Foo attribute> := 5;
==========================
Any takers?
More ideas later... (I hope!)
S. Tucker Taft stt@inmet.inmet.com ...!uunet!inmet!stt
Intermetrics, Inc.
733 Concord Avenue
Cambridge, MA 02138rick@tetrauk.UUCP (Rick Jones) (12/12/90)
In article <743@puck.mrcu> paj@uk.co.gec-mrc (Paul Johnson) writes: >I think that this debate is missing the point. It is indeed! >Neither MI or SI make >simple examples easier to code. If you have fully analysed your >problem and know what routines are to be called where then you can >code in Pascal or C just as easily. I sometimes wonder if half (most?) the people using OOPLs are simply replacing top-down functional decomposition with top-down object decomposition. The sort of approach which says that "SI is better because it leads to a more structured hierarchy" makes me think that this is what is happening. There are lots of ways to produce a structured solution to a _specific_ problem; object orientation is just one way to do it. But that doesn't make your system more resilient to change, which is the real point. >The point about inheritance and >polymorphism is that they contribute to code flexibility and reuse. >When the requirements change (as they always do) then a well designed >OO program is far superior because the existing abstract classes (what >Meyer terms "deferred" classes) from which the actual classes inherit >become the basis for new classes. MI allows the designer to increase >the number of abstract classes in the system and thereby increases the >flexibility of the system. The most important point about reuse is the ability to reuse something in a way that was not anticipated when it was written. Rigid hierarchies don't stand much chance of letting you do that. In a function oriented system, reuse is provided by function libraries. These work quite well, but we all know that they are limited in scope because of problems of encapsulation and extension. The acclaimed benefit of object oriented methods is better reusability. In a real _class based_ system, reuse comes from class libraries, which are not only better encapsulated (if properly written) but also reusable in two dimensions; either as supplier classes (by creating and using objects of the classes as they are), or by inheritance, allowing controlled but essentially arbitrary extension. The original question can be posed in the reverse: If I wish to reuse components from a class library by inheritance, under what circumstances is it reasonable for me to be restricted to reusing only a single class at a time? Would it be a reasonable restriction of C if a function I wrote were only allowed to call one other sub-function? I feel this concern about MI is all to do with implementation problems of languages which have been (short-sightedly) designed without due consideration for the ultimately essential support of multiple inheritance. That is until someone comes up with a concept which is even better (and there do seem to be some ideas bouncing around). -- Rick Jones Tetra Ltd. Maidenhead, Was it something important? Maybe not Berks, UK What was it you wanted? Tell me again I forgot rick@tetrauk.uucp -- Bob Dylan
tok@stbimbo.UUCP (Terry Kane) (12/13/90)
paj@mrcu (Paul Johnson) writes: > If you have fully analysed your >problem and know what routines are to be called where then you can >code in Pascal or C just as easily. Isn't it funny how many threads in comp.* revolve around (the lack of) proper analysis and design? ...as you nicely allude to, a good analysis encourages a good design in any language. (see my posting in comp.edu)
brandis@inf.ethz.ch (Marc Brandis) (12/13/90)
In article <841@echbull.bull.fr> Marc.Herrmann@ec.bull.fr () writes: >> Very often, the kind of situations that you are describing can be >> solved by using references to other objects and just deriving from one class. > > By doing so don't you implement multiple inheritance by using simple >inheritance + delegation ? Could you clarify your point? > I do not implement (!) multiple inheritance, but instead achieve a similar effect using simple inheritance and delegation. There are several reasons why I think this is advantegeous to implementing multiple inheritance. First, there is no really clean way to solve the naming and consistency conflicts that arise when using multiple inheritance. I do not want to list them here as I think you know them. If one will be found, I have no major objection against multiple inheritance any more. However, I am not sure whether it will ever be found. As long as these conflicts are not resolved, I prefer to see in my code what is going on instead of having to guess what the compiler will do. I know that I may have to write a little more using simple inheritance and delegation, but everything is under complete control of the programmer. Second, multiple inheritance is a rather expensive construct (compared to single inheritance). In C++, you even have to pay some overhead when you are just using single inheritance because multiple inheritance has been added. I do not think that the few places where I could use multiple inheritance instead of some kind of delegation are worth this overhead. Third, as multiple inheritance is a rather powerful construct, which - at least at the moment - requires a lot of rules how conflicts are resolved, I would assume that lots of programmers may not understand all these rules well, so that they may introduce more errors than necessary. Just one note: I do not want to start a flame war on this. This has been discussed by many people before and lots of researchers do not agree on it. It is just that I am one of the people that are not convinced that multiple inheritance is worth the problems it causes. Marc-Michael Brandis Computer Systems Laboratory, ETH-Zentrum (Swiss Federal Institute of Technology) CH-8092 Zurich, Switzerland email: brandis@inf.ethz.ch
jimad@microsoft.UUCP (Jim ADCOCK) (12/13/90)
In article <60700005@inmet> stt@inmet.inmet.com writes: |Multiple inheritance seems to add significant overhead to an OOPL even |when not being used in a system, so we are looking for convincing |examples that it's benefits outweigh the cost. MI need not add overhead when not being used. This simply depends on how its being implemented.
craig@Neon.Stanford.EDU (Craig D. Chambers) (12/13/90)
In article <18090@neptune.inf.ethz.ch> brandis@inf.ethz.ch (Marc Brandis) writes: >First, there is no really clean way to solve the naming and consistency >conflicts that arise when using multiple inheritance. I do not want to list >them here as I think you know them. If one will be found, I have no major >objection against multiple inheritance any more. However, I am not sure >whether it will ever be found. In prototype-based languages, the programmer explicitly constructs an initial (prototypical) instance of each type to go along with a shared behavior object (thus splitting a single class declaration into two cooperating object declarations). All issues about resolving instance variable name clashes are largely moot, since the programmer is already explicitly handling the representation of instances anyway. See the "Organizing Programs without Classes" paper that I've mentioned before (available in postscript form via anonymous ftp from otis.stanford.edu) for a longer discussion. Name clashes among inherited methods are still an issue, of course. >As long as these conflicts are not resolved, I prefer to see in my code >what is going on instead of having to guess what the compiler will do. I >know that I may have to write a little more using simple inheritance and >delegation, but everything is under complete control of the programmer. > >[reordering....] > >Third, as multiple inheritance is a rather powerful construct, which - at >least at the moment - requires a lot of rules how conflicts are resolved, >I would assume that lots of programmers may not understand all these rules >well, so that they may introduce more errors than necessary. I agree that MI rules should be simple enough for programmers to use effectively. I think this requires that the language only resolve *obvious* ambiguities automatically (i.e. silently), such as between a child and its parent; any other ambiguities may be reasonably forwarded to the programmer for explicit resolution. Note that this does not necessarily mean that each name clash must be resolved separately by writing code to handle each name clash; fancier schemes and/or environment tools would allow a more declarative way to resolve whole groups of name clashes in a standard way (such as the mixin combination rules supported in Flavors and CLOS). I believe the programmer should be informed about these potential conflicts, make sure that they are of the "standard variety," and hit a button to have the system automatically do the necessary programming to resolve the ambiguity. Hopefully this approach would lead to more reliable use of MI without sacrificing the ease of programming that is the hallmark of the more automatic, complex, error-prone approaches. >Second, multiple inheritance is a rather expensive construct (compared to >single inheritance). In C++, you even have to pay some overhead when you >are just using single inheritance because multiple inheritance has been added. >I do not think that the few places where I could use multiple inheritance >instead of some kind of delegation are worth this overhead. As others have said, this is an implementation issue, not a language issue. The Self implementation includes MI at virtually no cost, since many performance-critical messages are statically bound at compile-time anyway, therefore leading to zero run-time lookup overhead, and all the rest of the run-time message sends use both in-line caching (pioneered by the Deutsch-Schiffman Smalltalk-80 implementation (i.e. ParcPlace Smalltalk)) and global lookup caching. So run-time lookups only happen if none of the caches contain an entry for the message being sent. These latter two run-time caching techniques are not quite as fast as the standard indirect procedure call implementation of pre-MI C++, but are faster than the same scheme extended to handle dynamically-typed languages with the possibility of lookup errors (which for all intents and purposes includes Eiffel, since Eiffel's static checking doesn't exclude run-time lookup errors). Also, techniques for handling MI in statically-typed languages using a single level of indirection are appearing in the literature as well [see OOPSLA'89 and PLDI'90 for some papers]. If you're really concerned about message send speed, you should be trying to get OO language implementors to include techniques that support more static binding of messages (such as customization, type analysis, and splitting as in the Self compiler). And for those messages that remain dynamically-bound, you could probably afford a little extra compile time (consider it part of the time to optimize programs) to do fancy things to support single-level-of-indirection calls. If you're concerned about space overheads of MI, other implementations of MI than the one in C++ 2.0+ have low space overheads, comparable to pre-MI C++ implementations (i.e. a word or two extra per object). -- Craig Chambers
lins@Apple.COM (Chuck Lins) (12/14/90)
In article <1990Dec13.035418.28040@Neon.Stanford.EDU> craig@Neon.Stanford.EDU (Craig D. Chambers) writes: >If you're concerned about space overheads of MI, other implementations >of MI than the one in C++ 2.0+ have low space overheads, comparable to >pre-MI C++ implementations (i.e. a word or two extra per object). Could you provide some examples or references to papers describing such implementations? For some of us this (oo research) is a part-time endeavor and we don't always have the time to read every single paper. (Our limits, not yours.) Thanks in advance. -- Chuck Lins | "Is this the kind of work you'd like to do?" Apple Computer, Inc. | -- Front 242 20525 Mariani Avenue | Internet: lins@apple.com Mail Stop 37-BD | AppleLink: LINS@applelink.apple.com Cupertino, CA 95014 | "Self-proclaimed Object Oberon Evangelist" The intersection of Apple's ideas and my ideas yields the empty set.
paj@mrcu (Paul Johnson) (12/14/90)
>paj@mrcu [Me] writes: >> If you have fully analysed your >>problem and know what routines are to be called where then you can >>code in Pascal or C just as easily. >Isn't it funny how many threads in comp.* revolve around (the lack of) >proper analysis and design? The point I was trying to make is that in the Real World (TM) a full analysis of the problem is not possible because by the time you finish it is out of date. Hence we need a way of creating systems that are able to absorb the changes that will always occur. Of course, spending some time learning about the system is necessary, but thick tomes full of minutae are largely a waste of time and trees. Paul. -- Paul Johnson UUCP: <world>!mcvax!ukc!gec-mrc!paj --------------------------------!-------------------------|------------------- GEC-Marconi Research is not | Telex: 995016 GECRES G | Tel: +44 245 73331 responsible for my opinions. | Inet: paj@uk.co.gec-mrc | Fax: +44 245 75244
barmar@think.com (Barry Margolin) (12/15/90)
In article <756@puck.mrcu> paj@uk.co.gec-mrc (Paul Johnson) writes: >>Isn't it funny how many threads in comp.* revolve around (the lack of) >>proper analysis and design? >The point I was trying to make is that in the Real World (TM) a full >analysis of the problem is not possible because by the time you finish >it is out of date. Also, if software reusability is a goal, then software components may be used in projects not even conceived at the time they were designed. One justification for OO technology is that it can make it easier to develop reusable software. -- Barry Margolin, Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
dlw@odi.com (Dan Weinreb) (12/15/90)
In article <47353@apple.Apple.COM> lins@Apple.COM (Chuck Lins) writes: >If you're concerned about space overheads of MI, other implementations >of MI than the one in C++ 2.0+ have low space overheads, comparable to >pre-MI C++ implementations (i.e. a word or two extra per object). Could you provide some examples or references to papers describing such implementations? For some of us this (oo research) is a part-time endeavor and we don't always have the time to read every single paper. (Our limits, not yours.) Thanks in advance. The Symbolics CLOS implementation uses one word for each instance variable, plus one word of overhead, no matter how much multiple inheritance is being used. I think that it is described in papers that have been published in OOPSLA. I believe that the portable PCL implementation also has the same property (in fact, I strong suspect that every single extant implementation of CLOS has this property).
craig@Neon.Stanford.EDU (Craig D. Chambers) (12/18/90)
In article <47353@apple.Apple.COM> lins@Apple.COM (Chuck Lins) writes: >In article <1990Dec13.035418.28040@Neon.Stanford.EDU> craig@Neon.Stanford.EDU (Craig D. Chambers) writes: >>If you're concerned about space overheads of MI, other implementations >>of MI than the one in C++ 2.0+ have low space overheads, comparable to >>pre-MI C++ implementations (i.e. a word or two extra per object). > >Could you provide some examples or references to papers describing such >implementations? For some of us this (oo research) is a part-time endeavor >and we don't always have the time to read every single paper. (Our limits, >not yours.) Thanks in advance. Languages based on separate hash tables for message lookup (like Self, Smalltalk, many Lisp-based systems, Trellis/Owl, and (I think) Eiffel) can use one extra word in the beginning of the object to identify the object's run-time type. This could either be a pointer to a class object, an invisible map object as in Self, or a table of defined methods. No extra words per object are needed. C++'s MI implementation is designed to trade away some space per object to get faster message lookup (although in-line caching may be faster than this implementation when the cache hits, especially when combined with customization). I think the Smalltalk Blue Book [Golberg & Robson '83] might talk about this representation towards the back, and the Self implementation is summarized in OOPSLA'89. As far as I know, Trellis[/Owl]'s implementation has only been described in unpublished documents. I don't know if Eiffel's implementation is described anywhere. -- Craig Chambers
pcg@cs.aber.ac.uk (Piercarlo Grandi) (12/22/90)
On 17 Dec 90 22:33:06 GMT, craig@Neon.Stanford.EDU (Craig D. Chambers) said: craig> In article <47353@apple.Apple.COM> lins@Apple.COM (Chuck Lins) writes: lins> In article <1990Dec13.035418.28040@Neon.Stanford.EDU> lins> craig@Neon.Stanford.EDU (Craig D. Chambers) writes: craig> If you're concerned about space overheads of MI, other implementations craig> of MI than the one in C++ 2.0+ have low space overheads, comparable to craig> pre-MI C++ implementations (i.e. a word or two extra per object). This is not strictly true: the space overhead of MI in C++ 2.x when implemented without code thunks is not in the object, but in pointers to virtual member functions for the object's class. Also, multiple virtual inheritance also requires N-1 extra pointer words in the object for each suboject inherited virtually inherited N times. lins> Could you provide some examples or references to papers describing lins> such implementations? For some of us this (oo research) is a lins> part-time endeavor and we don't always have the time to read every lins> single paper. (Our limits, not yours.) Thanks in advance. craig> Languages based on separate hash tables for message lookup (like Self, craig> Smalltalk, many Lisp-based systems, Trellis/Owl, and (I think) Eiffel) craig> can use one extra word in the beginning of the object to identify the craig> object's run-time type. Or they can use a BIBOP system and thus tagging the address space instead of the data space (the tag is contained not in the object's contents but in its location). In other words they would be using hash linking, a little known but useful technique. craig> This could either be a pointer to a class object, an invisible craig> map object as in Self, or a table of defined methods. No extra craig> words per object are needed. So, in a BIBOP implementation, we could have *in theory* zero space overhead multiple inheritance. But this is only because of an illusion, unfortunately. craig> C++'s MI implementation is designed to trade away some space per craig> object to get faster message lookup No, the "problem" is that in C++, but for one case, all components of an object, whether inherited or not, are expanded inline, and functions are not dynamically overloaded by default. In the languages you mention functions are dyncamically overloaded by default and subobjects they are accessed by a very convenient extra level of indirection. The extra overhead of MI is thus absorbed in these two already existing overheads. As Dave Weinreb remarks in another article, there is an overhead of one pointer for every member of a CLOS object, for example. In C++ the one exception is virtual multiple inheritance, which indeed causes problems, because it means that pointers to virtual member functions must be more complex than otherwise even when not necessary. In non C++ languages this extra complexity is not explicitly required for MI because it is already required for other reasons, thus giving rise to the illusion that MI costs relatively less than in C++. -- Piercarlo Grandi | ARPA: pcg%uk.ac.aber.cs@nsfnet-relay.ac.uk Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk
craig@Neon.Stanford.EDU (Craig D. Chambers) (12/23/90)
In article <PCG.90Dec22154707@odin.cs.aber.ac.uk> pcg@cs.aber.ac.uk (Piercarlo Grandi) writes: >On 17 Dec 90 22:33:06 GMT, craig@Neon.Stanford.EDU (Craig D. Chambers) said: > >craig> If you're concerned about space overheads of MI, other implementations >craig> of MI than the one in C++ 2.0+ have low space overheads, comparable to >craig> pre-MI C++ implementations (i.e. a word or two extra per object). > >This is not strictly true: the space overhead of MI in C++ 2.x when >implemented without code thunks is not in the object, but in pointers to >virtual member functions for the object's class. Also, multiple >virtual inheritance also requires N-1 extra pointer words in the object >for each suboject inherited virtually inherited N times. I was talking about per-object space overhead, i.e. extra space in the representation of an object over the representation of its components. There is additional per-class overhead too (in C++, the virtual function pointer arrays; in other languages, message lookup tables); if a class has many instances, then the per-class overhead becomes relatively small. >craig> C++'s MI implementation is designed to trade away some space per >craig> object to get faster message lookup > >No, the "problem" is that in C++, but for one case, all components of an >object, whether inherited or not, are expanded inline, and functions are >not dynamically overloaded by default. > >In the languages you mention functions are dyncamically overloaded by >default and subobjects they are accessed by a very convenient extra >level of indirection. The extra overhead of MI is thus absorbed in these >two already existing overheads. As Dave Weinreb remarks in another >article, there is an overhead of one pointer for every member of a CLOS >object, for example. I think this is a strange viewpoint. C++ allows the programmer to declare that certain things should be implemented more efficiently, with a sacrifice in programming power and language simplicity. One thing you mentioned was allowing components to be referenced either by pointer (what I would consider the normal case, and the only possible case in other higher-level languages) or contained in-line (sacrificing the ability to share the component, as well as making certain other tasks of the run-time system, such as GC, harder to implement efficiently (since you might get interior pointers)). The other thing you mentioned is that C++ allows the programmer to explicitly distinguish virtual from non-virtual functions, with non-virtual functions sacrificing language power in the name of efficiency. In my C++ programming, I rarely use in-line components (almost always using pointers instead) and avoid non-virtual member functions. In these cases, C++ has the same "overhead" as the other languages we talked about as far as 1 word per component for the pointer and extra space to handle the dynamic binding of virtual functions. The programmer can explicitly opt to sacrifice language power to get some space and time efficiency, but I wouldn't compare C++ to other languages by assuming that the C++ programmers always performed these optimizations. Also, all class-based languages I know of embed the representation of their superclasses into the subclass, so there's no overhead here (sharing of the superclass is not an issue). Self, a classless language, forces the programmer to explicitly define how he wants to handle parent prototype objects, by building the appropriate object structures. Our current style uses separate linked objects for each ancestor's prototype (see the "Organizing Programs without Classes" paper for more details), leading to extra space costs, but this is up to the programmer. He could avoid this chaining and manually copy down "instance variable" declarations to save space. We don't normally do this because we aren't concerned that much about the small space overheads involved. The fact still remains, then, ignoring the "overhead" of pointers and dynamically-bound message passing, that other implementations typically use an extra word or two of space *per object*, independent of whether MI is used or even a feature of the language. MI C++, on the other hand, uses more space *per object*. C++ sacrifices this space overhead to make sure that message passing is fast even in the worst case (just an indirect procedure call, plus some extra pointer arithmetic). Other languages save space per object by using a slower message passing implementation in the worst case (e.g. probing hash tables/scanning inheritance graphs); they sometimes rely on other techniques (e.g. in-line caching) to speed message passing in the normal case. Of course, post-MI C++ has more per-class overhead than pre-MI C++. Virtual function pointer arrays are twice as big, and a single class may have more than one of them. But it's hard to compare per-class costs with other systems that have redically different architectures. In caching implementations, for example, the per-class cost can change over time. One final point: per-object overhead is more important that per-class overhead because it affects the time to create new objects. The smaller an object is, the faster it is to create (fewer memory words to initialize). In a GC'd system, smaller objects also lead to less frequent (or faster) GCs, further speeding the system. -- Craig Chambers
pcg@cs.aber.ac.uk (Piercarlo Grandi) (12/30/90)
On 22 Dec 90 22:00:16 GMT, craig@Neon.Stanford.EDU (Craig D. Chambers) said:
craig> In article <PCG.90Dec22154707@odin.cs.aber.ac.uk>
craig> pcg@cs.aber.ac.uk (Piercarlo Grandi) writes:
pcg> On 17 Dec 90 22:33:06 GMT, craig@Neon.Stanford.EDU (Craig D.
pcg> Chambers) said:
craig> If you're concerned about space overheads of MI, other
craig> implementations of MI than the one in C++ 2.0+ have low space
craig> overheads, comparable to pre-MI C++ implementations (i.e. a word
craig> or two extra per object).
pcg> This is not strictly true: the space overhead of MI in C++ 2.x when
pcg> implemented without code thunks is not in the object, but in
pcg> pointers to virtual member functions for the object's class. Also,
pcg> multiple virtual inheritance also requires N-1 extra pointer words
pcg> in the object for each suboject inherited virtually inherited N
pcg> times.
craig> I was talking about per-object space overhead, i.e. extra space
craig> in the representation of an object over the representation of its
craig> components.
I am not aware of any case (except virtual MI as written above) where
inheritance in C++ whether multiple or not requires a per object space
overhead. There is overhead connected to virtual functions, not to
inheritance.
craig> Also, all class-based languages I know of embed the
craig> representation of their superclasses into the subclass, so
craig> there's no overhead here (sharing of the superclass is not an
craig> issue).
C++, again excepted for virtual inheritance, does the same.
craig> The fact still remains, then, ignoring the "overhead" of pointers
craig> and dynamically-bound message passing, that other implementations
craig> typically use an extra word or two of space *per object*,
craig> independent of whether MI is used or even a feature of the
craig> language. MI C++, on the other hand, uses more space *per
craig> object*.
I cannot understand you here. Did you mean to write that MI C++ uses
more space *per pointer* or *per class*? As you said above, if we ignore
the costs of virtual functions/dynamic binding, MI C++ has absolutely no
extra space overhead per object over SI C++. Indeed, if virtual
functions are not defined, there is zero per object overhead.
Maybe you refer to the fact that in C++ there is a separate vtable and
vtable pointer for each class type, and they are not merged with
inheritance, as this would require different offsets. Well, again this
is purely an effect of a common _implementation_ of _virtual functions_,
and of the general requirement that in C++ any component, whether
inherited or not, of an object, can be pointed to and used on its own.
There are other languages that have this property, and they require
special trickery. For example I have read an article in which negative
member offsets were used to get around many cases where otherwise
offsets would have been jumbled around.
It is conceivable that virtual functions in C++ could be implemented too
in quite different ways from how they are implemented in cfront. It is
in no way implied by how MI is defined in C++.
It is a consequence of how virtual functions are realized.
--
Piercarlo Grandi | ARPA: pcg%uk.ac.aber.cs@nsfnet-relay.ac.uk
Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk