Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!elroy.jpl.nasa.gov!sdd.hp.com!uakari.primate.wisc.edu!aplcen!aplcomm!uunet!mcsun!ukc!dcl-cs!aber-cs!athene!pcg From: pcg@cs.aber.ac.uk (Piercarlo Grandi) Newsgroups: comp.object Subject: Re: Void references Message-ID: Date: 18 Nov 90 16:08:51 GMT References: <454@eiffel.UUCP> <1990Nov15.011702.25087@Neon.Stanford.EDU> <11113@pt.cs.cmu.edu> Sender: aro@aber-cs.UUCP Organization: Coleg Prifysgol Cymru Lines: 137 Nntp-Posting-Host: teachk In-reply-to: ddean@rain.andrew.cmu.edu's message of 15 Nov 90 16:22:19 GMT On 15 Nov 90 16:22:19 GMT, ddean@rain.andrew.cmu.edu (Drew Dean) said: ddean> From a relative neophyte, if a subclass only inherits parts of ddean> its superclass (ie. some subset of the methods and/or variables), ddean> how can an instance of the subclass be used anywhere an instance ddean> of the superclass can be used ? In my (comparably primitive) ddean> understanding of OOP, this is important. Well, this type of polymorphism does not arise in conventional OO languages, where the algebra of interface and implementation reuse is just inheritance via prefixing, and links together both, and only for supersetting, not for subsetting -- often the reason for this is, more or less explicitly, precisely to avoid this problem. But if you look at less restrictive languages you see that the algebras of interface and implementation reuse can be considerably more flexible, and less interlinked; in another article Barry Margolin points out that the problem is... barmar> ... easily solved in class-based languages with multiple barmar> inheritance, such as CLOS. In such languages you can put the barmar> representations in one set of classes and the behavioral barmar> implementations in another set of classes. What he really means is that in CLOS (like in some sense in Smalltalk) you have a functional interface to both methods and attributes, and you can obtain a new class interface by merging the interfaces (or subsets thereof) of one (or more) class that gives you the attributes interface with one (or more) that gives you the methods interface. The problem, for data traits or attributes, is naturally how much of the (name,offset,type) table that describes the components of the state of an object we need to keep at runtime. At one extreme in C and C++ 1.x and similar languages all attributes have characteristics known at compile time, even if their number may change (a subclass of A will have more attributes, but you are forbidden from accessing these, except via virtual functions, which indeed are accessed via a table) With virtual multiple inheritance, as in C++ 2.x (or Eiffel), some attributes have offsets that are variable at run time, so we need to store the offset at run time; in some languages the *type* of an attribute is not known at runtime, as in Smalltalk. In the fully general case the state of an object can be dynamic in all three dimensions; the number of attributes may be variable, their offsets (representations!) may vary, and their types too. Now consider the domain of applicability (or polymorphism) of a method; a method may depend at the very least on the names of the attributes it uses in the object, or also on their offsets (representations!), or also on their types. The most extreme cases can be easily implemented; if the set of attributes of an object are known at compile time and so are their offsets (the C/C++ 1.x case above) we do not need any runtime table; we can match a method against an object by comparing their interfaces in the compiler. If nothing is know at compile time, the solution is equally easy; we associate a full (name,offset,type) table to each object, and we match it with that of the method and its implementation at runtime. A method (or its implementation) can be applied to any object whose interface is 'stronger' than that it has been defined for. Whether it is a mistake to associate a stronger implementation to a weaker method interfaces is largely a matter of taste. On the other hand applying methods with a stronger interface to objects with a weaker one is a partial function, and its validty must be determined at runtime, just as applying a method with a stronger specification to an object with a weaker one. Example of the latter: applying 'factorial' to a numeric object that is not guaranteed positive and integral. Example of the former: applying 'square(int)' to a numeric object that is declared as 'union(int,float)'. The runtime table based solution allows for easy mix and match of interfaces, by mixing and matching the tables; but, especially for attribute access, a table lookup on every use is not attractive, except to AI people, which have been doing this forever (alists, frames, ...), also because in their applications a trait which is an attribute may be *dynamically* reimplemented as a function, or viceversa, and so table/alist based approaches are nearly essential. But in many cases the full generality is not necessary, even if static foreknowledge is not possible either. Implementation techniques for the intermediate cases are being researched. Things like Self and automatically typed Smalltalk are examples of what can be done to reduce the cost of full generality when it can be constrained either statically (at least part of the table for an object can be deduced at compile time) or dynamically (it is expected that the contents of the table do not change frequently). There are other tricks; I am terribly sorry that I do not remember the exact reference, but in some recent 1989 SIGPLAN conference on languages and their implementation there is a paper on laying out different objects types in memory so that subobjects that have the same naem and type in all those object types are at the same offset relative to the object pointer. This naturally means that the access functions to the subobjects are constant and known at compile time and are the same for all those object types. The goal is to minimize holes, of course; we can make the layouts of two classes compatible in the sense of having attributes of the same name and type at the same offset by creating holes, but this is hardly desirable. In the simple inheritance case implemented with prefixing avoiding this is trivial; with multiple prefixing things become more difficult (C++ has to resort to indirection via hidden pointers for virtual base classes). The paper I mention above demonstrates that a fairly simple trick, using postfixing (putting subojects at negative offsets from the object pointer) can solve the problem in many interesting cases with grater efficiency, that is no holes and no extra levels of indirection. ddean> Without this property, what good are abstract classes, which seem ddean> to be a useful organizational tool ? Abstract (deferred) classes are no good of course. They are just a hack to decouple a bit the algebra of interfaces from that of implementations, which are otherwise coupled in inheritance. The best thing sis instead to uncouple them completely, and have different algebras for implementations and interfaces, and to have more general algebras as well, not just supersetting/subsetting. As to this I would like to point you also to some work in the sw engineering reuse field on interface and component description languages, which allow you to describe how to mix and match interfaces (module A has an interface that is the union of those of modules B and C minus that of D). You could contact Bob Gautier (rjg%uk.ac.aber.cs@nsfnet-relay.ac.uk) which has done some work on this issue and on CDL, an interface description language, which I think is interesting. Some other interesting work is being done by the functional language people when they try to define clean type systems. Polymorphism is very important to them, and they have expended a lot of effort into dealing with it. -- 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