brucec@phoebus.phoebus.labs.tek.com (Bruce Cohen;;50-662;LP=A;) (09/12/90)
I've just been reading the Self papers, and it occurred to me that using
prototypes for inheritance could solve a problem which has been annoying me
for quite some time. Maybe some of you out there coould comment on the
theory and/or practice of the idea.
Consider an object-oriented graphic drawing system, in which there's a
general shape object, a polygon object, a rectangle object, a circle
object, and an ellipse object. One way you could arrange class inheritance
for such objects is like this:
Shape
|
------------
| |
Polygon Ellipse
| |
Rectangle Circle
That is, the root class is an abstract shape class, and it's subclasses are
the most general concrete classes, with more specific (i.e., degenerate case)
classes inheriting from them. Well that's fine from a static viewpoint,
but consider that one reason to build a system like this is that it may
be (and usually is) cheaper both to draw and to store a rectangle than a
general polygon, and a circle than an ellipse. OK, so we can create
rectangles when we know that a polygon has 4 sides, or circles when we know
that the foci of an ellipse are coincident.
But what happens when objects can change over time? How do we dynamically
mutate a rectangle to a polygon and back again while retaining the cost
savings of the more refined object? In a class-based system, either you
use a message like become: otherObject in Smalltalk, which is really a
system utility, and implies that there is a global object table or some
other centralized means of insuring that references to the old object get
update, or you have to have creation/conversion methods for objects which
can be called when a mutator method discovers a degeneracy (this is the
technique you would have to use in C++). The mutator would create (e.g.) a
new degenerate object, copy the relevant part of the state of the
non-degenerate one, then install the new one in the right place and
manually update references to the old object.
Suppose instead that the objects inherited from prototypes, and the mutator
merely changed the appropriate parent pointers to (e.g.) remove a
degenerate object's redundant slots and change it's behavior to the less
costly method. Consider the ellipse being converted to a circle (warning:
Self notation):
Ellipse Circle:
------ -------
parent:-----------> traits circle parent:-----------> traits ellipse
focus1 -----------> 0@0 <------------ center
focus2 -----------> 0@0
focus1: <-
focus2: <- focus2: <-
major radius -----> 1 <------------ radius
minor radius -----> 1
major radius: <-
minor radius: <-
This seems significantly cleaner than becomes, and perhaps less work than
the hand-crafted mutator in the class-based approach. Anyone have any
comments?
--
---------------------------------------------------------------------------
NOTE: USE THIS ADDRESS TO REPLY, REPLY-TO IN HEADER MAY BE BROKEN!
Bruce Cohen, Computer Research Lab email: brucec@tekcrl.labs.tek.com
Tektronix Laboratories, Tektronix, Inc. phone: (503)627-5241
M/S 50-662, P.O. Box 500, Beaverton, OR 97077boissier@irisa.irisa.fr (franck boissiere,externes ) (09/13/90)
From article <BRUCEC.90Sep11141457@phoebus.phoebus.labs.tek.com>, by brucec@phoebus.phoebus.labs.tek.com (Bruce Cohen;;50-662;LP=A;): > I've just been reading the Self papers, and it occurred to me that using > prototypes for inheritance could solve a problem which has been annoying me > for quite some time. Maybe some of you out there coould comment on the > theory and/or practice of the idea. > > > Ellipse Circle: > ------ ------- > parent:-----------> traits circle parent:-----------> traits ellipse > focus1 -----------> 0@0 <------------ center > focus2 -----------> 0@0 > focus1: <- > focus2: <- focus2: <- > major radius -----> 1 <------------ radius > minor radius -----> 1 > major radius: <- > minor radius: <- > > This seems significantly cleaner than becomes, and perhaps less work than > the hand-crafted mutator in the class-based approach. Anyone have any > comments? > > -- It is not always needed nor desirable to have object mutating in a system, but this is not exactly the point you make. Object coercion is implemented without invoking becomes: and I feel this is what you need. I don't really see what your example in Self does better compared to the "asSUCH" methods of Smalltalk. I may be missing something. -- Franck BOISSIERE boissier@irisa.irisa.fr Prototyping Lab Manager boissier@ccettix.UUCP C.C.E.T.T. B.P. 59 boissier%irisa.irisa.fr@uunet.uu.net 35512 CESSON SEVIGNE CEDEX FRANCE
pcg@cs.aber.ac.uk (Piercarlo Grandi) (09/13/90)
On 11 Sep 90 21:14:57 GMT, brucec@phoebus.phoebus.labs.tek.com (Bruce Cohen) said: brucec> I've just been reading the Self papers, and it occurred to me brucec> that using prototypes for inheritance could solve a problem brucec> which has been annoying me for quite some time. Maybe some of brucec> you out there coould comment on the theory and/or practice of brucec> the idea. brucec> Consider an object-oriented graphic drawing system, in which brucec> there's a general shape object, a polygon object, a rectangle brucec> object, a circle object, and an ellipse object. One way you brucec> could arrange class inheritance for such objects is like this: [ ... describing the problem where an object's class semantics are a derivative of its parent's, but is implementation need not be ... ] This is the age old problem, which I never tire to describe, that you want to reuse interface, semantics, implementation separately. In your case you want to reuse the interface and semantics of Shape for Polygon, and again for Rectangle, but you don't want to reuse the implementation of Polygon for Rectangle. [ ... describing substituing an object implementation for another, either with an in-built become:, or with a manually implemented version ... ] Your two alternatives, incidentally, are exactly the same; when you reject become:, you propose an alternative that is equivalent to manually implementing become: itself. brucec> Suppose instead that the objects inherited from prototypes, and brucec> the mutator merely changed the appropriate parent pointers to brucec> (e.g.) remove a degenerate object's redundant slots and change brucec> it's behavior to the less costly method. Consider the ellipse brucec> being converted to a circle (warning: Self notation): brucec> Ellipse Circle: brucec> ------ ------- brucec> parent:-----------> traits circle parent:-------> traits ellipse brucec> focus1 -----------> 0@0 <------------ center brucec> focus2 -----------> 0@0 brucec> focus1: <- brucec> focus2: <- focus2: <- brucec> major radius -----> 1 <------------ radius brucec> minor radius -----> 1 brucec> major radius: <- brucec> minor radius: <- This is OK -- what you do is to redefine inheritance so that you inherit protocol but not implementation. This can be done in CLOS, as well. brucec> This seems significantly cleaner than becomes, and perhaps less brucec> work than the hand-crafted mutator in the class-based approach. brucec> Anyone have any comments? If done at run time it requires an interpreter or a runtime compiler, because you are changing dynamically the layout in memory of slots and the access algorithms to them. This may be available for Common Lisp and Self, but not for simpler languages. And it is not that different from become: really; it is an in-place version of become:, where you also twiddle the parent pointer. Bah. I think that become: is clean enough, can be implemented easily, and is more flexible. It merely requires runtime diaptching of methods, not runtime compilation. -- Piercarlo "Peter" 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) (09/14/90)
I think there's some confusion about dynamic inheritance in Self. In the circle-mutating-into-ellipse example, there would be a *child* object of either a circle object or an ellipse object, and other objects would point to this child. This child would act just like either a circle or an ellipse, because of normal object inheritance (the state and behavior of the parent is inherited, and accessible transparently to clients who can't tell there's an extra child object serving as mediator). Before: circle A | | -----> child change child's parent to turn into an ellipse After: ellipse A | | -----> child To mutate a circle into an ellipse, a new ellipse object would be created with the appropriate state, and the parent of the child object would be redirected to the ellipse object from the circle object. All clients still point to the child, and so the child appears to have "become" an ellipse (or at least its external behavior has changed so that its two foci are no longer the same point). But no weird operations (like mutating the formats of objects or redirecting all external pointers) are happening, just a single assignment to a single (parent) slot. Dynamic inheritance is *much* more structured and clean than become:. We use dynamic inheritance in a structured way in our Self programming. One common example occurs when an object may be in one of several "behavior modes." The canonical example is a window that may be displayed either open or iconified. The window object has an assignable parent pointer that either inherits from normal window behavior or from icon behavior, and can shift from one to the other dynamically as the user iconifies and un-iconifies his windows. The resulting code is simpler to understand and extend since the open and iconified cases are separated (just as object-oriented programming improved procedural programming by factoring out different cases into separate routines selected using dynamic method dispatching). Another use for dynamic inheritance is to implement self-reorganizing data structures. For example, a table might be implemented as a list of associations if it's small, but as it grows it might choose to change itself into a hash table for better performance. This could be implemented most easily by having the user's handle on the collection be a child of either a list object or a hash table object, depending on the representation. The circle-vs-ellipse example is similar in flavor. This class of example is useful where the interface to the object doesn't change, but its internal representation and internal algorithms do change. To sum up, being able to support different representations of the same abstraction (such as polygons vs. rectangles vs. squares) is important, and some languages (like Self, Trellis/Owl, and probably CLOS but not like Smalltalk, C++, or Eiffel) support subclasses whose representation is different from their superclasses'. But it is also important to allow objects to change their implementation or inheritance dynamically to best implement their current behavior. This is an implementation decision that is perfectly reasonable in supporting the object's interface. This is where languages with object inheritance that can change at run-time provide additional "clean" power over class-based languages, whose inheritance patterns are static (in every language I know about) and can only solve this problem using hacks like become: or changing an instance's class. -- Craig Chambers
jml@wally.altair.fr (Jean Marie Larcheveque) (09/14/90)
In article <1990Sep13.235832.23454@Neon.Stanford.EDU> craig@Neon.Stanford.EDU (Craig D. Chambers) writes: > >I think there's some confusion about dynamic inheritance in Self. In >the circle-mutating-into-ellipse example, there would be a *child* >object of either a circle object or an ellipse object, and other >objects would point to this child. This child would act just like >either a circle or an ellipse, because of normal object inheritance >(the state and behavior of the parent is inherited, and accessible >transparently to clients who can't tell there's an extra child object >serving as mediator). The decisive decision here is not the use of dynamic inheritance, but the creation of an extra link (an empty child, inheriting behavior *and* state) to avoid having to update external links when the representation changes. The same scheme could be implemented for example in C++, with something like class ellipse { concrete_ellipse state_holder; // ... } with concrete_ellipse a subclass of ellipse and a superclass of circle. -- Jean-Marie Larcheveque <jml@bdblues.altair.fr> or <jml@nuri.inria.fr>
brucec@phoebus.phoebus.labs.tek.com (Bruce Cohen;;50-662;LP=A;) (09/15/90)
In article <1608@seti.inria.fr> jml@wally.altair.fr (Jean Marie Larcheveque) writes: > > In article <1990Sep13.235832.23454@Neon.Stanford.EDU> craig@Neon.Stanford.EDU (Craig D. Chambers) writes: >> > The same scheme could be implemented for example in C++, > with something like > > class ellipse { > concrete_ellipse state_holder; > // ... > } > with concrete_ellipse a subclass of ellipse and a > superclass of circle. > But then don't you have to add a set of delegation functions to ellipse so an instance of it can pass on calls to it's instance of concrete_ellipse? Also (a nit), I think that state_holder has to be a pointer to concrete_ellipse, because, concrete_ellipse being subclass of ellipse, there's no way to forward-reference its type for the layout of the structure to be determined. -- --------------------------------------------------------------------------- NOTE: USE THIS ADDRESS TO REPLY, REPLY-TO IN HEADER MAY BE BROKEN! Bruce Cohen, Computer Research Lab email: brucec@tekcrl.labs.tek.com Tektronix Laboratories, Tektronix, Inc. phone: (503)627-5241 M/S 50-662, P.O. Box 500, Beaverton, OR 97077
sakkinen@tukki.jyu.fi (Markku Sakkinen) (09/16/90)
In article <BRUCEC.90Sep11141457@phoebus.phoebus.labs.tek.com> brucec@phoebus.phoebus.labs.tek.com (Bruce Cohen;;50-662;LP=A;) writes: >I've just been reading the Self papers, and it occurred to me that using >prototypes for inheritance could solve a problem which has been annoying me >for quite some time. Maybe some of you out there coould comment on the >theory and/or practice of the idea. I don't think that the core of your problem is dependent on whether the object model is based on classes or prototypes. I'll try to explain why. >Consider an object-oriented graphic drawing system, in which there's a >general shape object, a polygon object, a rectangle object, a circle >object, and an ellipse object. One way you could arrange class inheritance >for such objects is like this: > Shape > | > ------------ > | | > Polygon Ellipse > | | > Rectangle Circle >That is, the root class is an abstract shape class, and it's subclasses are >the most general concrete classes, with more specific (i.e., degenerate case) >classes inheriting from them. [...] > ... >But what happens when objects can change over time? How do we dynamically >mutate a rectangle to a polygon and back again while retaining the cost >savings of the more refined object? [...] > [...](this is the >technique you would have to use in C++). The mutator would create (e.g.) a >new degenerate object, copy the relevant part of the state of the >non-degenerate one, then install the new one in the right place and >manually update references to the old object. Unfortunately this idea does not quite work at least in C++: there is no way to find all references and pointers to a given object. A more fundamental problem is that inheritance in almost all OOPL's binds together the interface and the implementation of classes. This problem has often been discussed in the literature (e.g. by Alan Snyder). If Circle is defined as a subclass of Ellipse, then every Circle object must contain at least all instance variables of Ellipse, although it would actually need less. Note that Circle is not strictly a subtype of Ellipse but only a "read-only subtype": we can modify the axis ratio of an ellipse, but if we try to do that to a circle, it ceases to be a circle. There are two main ways to look at the subclasses of each most general concrete class: either we want them to be very visible to clients and have an enhanced interface (e.g. additional operations applicable to rectangles but not to other polygons), or we want them to be merely more efficient implementations of special cases and have exactly the same interface as their superclasses. It seems from the preceding paragraph of the original posting that your goal is the latter, so I'll first propose a solution to that. (In fact I'll postpone the discussion of the former case to a later posting, to keep this one at a reasonable size.) Advertise only the classes Polygon and Ellipse to potential clients, but define for them perhaps only one instance variable, which will simply reference an object of an "implementation class" that is utilised behind the scenes. All operations requested by clients from a Polygon or Circle object are simply forwarded to the implementation object. For the small example given we need as implementation classes: GeneralPolygon, Rectangle, GeneralEllipse, Circle. These shall _not_ be subclasses of the "front end" classes Polygon and Ellipse, but it could very well be expedient to make GeneralEllipse a subclass of Circle! (Yes, the inheritance hierarchy of implementation classes often gets inverted.) The main functions that a "front end" object must then fulfill are: - to create the implementation object after its own creation (this goes easily in C++ and other languages that have constructors); - to exchange the current implementation object into one of another class when needed; - to delete the implementation object in conjunction with its own deletion if there is no garbage collection (thus e.g. in C++, where this is fortunately easy to implement with destructors). >Suppose instead that the objects inherited from prototypes, and the mutator >merely changed the appropriate parent pointers to (e.g.) remove a >degenerate object's redundant slots and change it's behavior to the less >costly method. [...] This reasoning seems to me to be incomplete. If the programming technique (in a prototype-based language like Self) is such that the parent objects (Shape, Ellipse, Circle, ...) contain the methods and the instance objects only the data, then the _behaviour_ can of course be changes by changing the parent pointer. But that does not magically remove the now superfluous instance variables from the object! If that is wanted, the object itself must somehow be modified just as in the class-based case. In the opposite situation that a circle needs to become an ellipse it is _necessary_ (and not just a matter of efficiency) that the additional fields be added to the object. In this style of programming, Shape, Ellipse, etc. are simply classes in disguise. A clear disadvantage to real class-based programming is that one can connect a child to a parent even if the child has not got all those instance variables that the parent's methods presuppose. > ... In article <1990Sep13.235832.23454@Neon.Stanford.EDU> craig@Neon.Stanford.EDU (Craig D. Chambers) replies: > ... >To mutate a circle into an ellipse, a new ellipse object would be >created with the appropriate state, and the parent of the child object >would be redirected to the ellipse object from the circle object. All >clients still point to the child, and so the child appears to have >"become" an ellipse (or at least its external behavior has changed so >that its two foci are no longer the same point). But no weird >operations (like mutating the formats of objects or redirecting all >external pointers) are happening, just a single assignment to a single >(parent) slot. Dynamic inheritance is *much* more structured and >clean than become:. The main reason for having a Circle class at all was to have a compact and effective representation for an important special case. According to this suggestion, when a circle becomes a general ellipse, there will be _both_ a circle object _and_ an ellipse object. And when an ellipse becomes a circle, there are no storage savings; at best, the parent objects can be defined so that creating a new circle object (!) is not necessary. Markku Sakkinen Department of Computer Science and Information Systems University of Jyvaskyla (a's with umlauts) Seminaarinkatu 15 SF-40100 Jyvaskyla (umlauts again) Finland SAKKINEN@FINJYU.bitnet (alternative network address)
brucec@phoebus.phoebus.labs.tek.com (Bruce Cohen;;50-662;LP=A;) (09/18/90)
I don't have time just now to reply to Markku Sakkinen's posting in detail, but I did want to make a few comments about areas where I think we're not talking about quite the same things. The posting is quite clear on the problems of a class-based implementation for the problem I described: in general, inheriting objects may not remove behavior or state variables, they can only override them. This is just why I looked for another solution. I don't think that we're in as good agreement on the nature of the prototype-based solution: In article <1990Sep16.083629.10936@tukki.jyu.fi> sakkinen@tukki.jyu.fi (Markku Sakkinen) writes: I wrote: >>Suppose instead that the objects inherited from prototypes, and the mutator >>merely changed the appropriate parent pointers to (e.g.) remove a >>degenerate object's redundant slots and change it's behavior to the less >>costly method. [...] > > This reasoning seems to me to be incomplete. > If the programming technique (in a prototype-based language like Self) > is such that the parent objects (Shape, Ellipse, Circle, ...) contain > the methods and the instance objects only the data, then the _behaviour_ > can of course be changes by changing the parent pointer. > But that does not magically remove the now superfluous instance variables > from the object! If that is wanted, the object itself must somehow be > modified just as in the class-based case. No, the data slots are also inherited, and need not be inherited from the same object the behavior is inherited from. There is a good example of just what I wanted to do that explains how data representation can be used in Self, in the paper "Organizing Programs without Classes" by Ungar, Chambers, Chang, and Holze, in the Self papers. In section 2.4, "Beyond Representation Sharing", they show polygon and rectangle classes which have different data representations but share the appropriate common behavior. > > The main reason for having a Circle class at all was to have a compact > and effective representation for an important special case. > According to this suggestion, when a circle becomes a general ellipse, > there will be _both_ a circle object _and_ an ellipse object. > And when an ellipse becomes a circle, there are no storage savings; > at best, the parent objects can be defined so that creating a new > circle object (!) is not necessary. There may be both a circle and an ellipse prototype, but if the instances in use are modified in place, there only needs to be one instance of each object, which might behave like (and have the data representation of) a circle at one time, and an ellipse at another. -- --------------------------------------------------------------------------- NOTE: USE THIS ADDRESS TO REPLY, REPLY-TO IN HEADER MAY BE BROKEN! Bruce Cohen, Computer Research Lab email: brucec@tekcrl.labs.tek.com Tektronix Laboratories, Tektronix, Inc. phone: (503)627-5241 M/S 50-662, P.O. Box 500, Beaverton, OR 97077
sakkinen@tukki.jyu.fi (Markku Sakkinen) (09/18/90)
In article <BRUCEC.90Sep17111337@phoebus.phoebus.labs.tek.com> brucec@phoebus.phoebus.labs.tek.com (Bruce Cohen;;50-662;LP=A;) writes: >I don't have time just now to reply to Markku Sakkinen's posting in detail, >but I did want to make a few comments about areas where I think we're not >talking about quite the same things. [...] > >In article <1990Sep16.083629.10936@tukki.jyu.fi> sakkinen@tukki.jyu.fi (Markku Sakkinen) writes: >> [...] then the _behaviour_ >> can of course be changes by changing the parent pointer. >> But that does not magically remove the now superfluous instance variables >> from the object! If that is wanted, the object itself must somehow be >> modified just as in the class-based case. > >No, the data slots are also inherited, and need not be inherited from the >same object the behavior is inherited from. There is a good example of >just what I wanted to do that explains how data representation can be used >in Self, in the paper "Organizing Programs without Classes" by Ungar, >Chambers, Chang, and Holze, in the Self papers. In section 2.4, "Beyond >Representation Sharing", they show polygon and rectangle classes which have >different data representations but share the appropriate common behavior. I am sorry, but there seems to be a little confusion still. In a prototype-based system, "inheriting" a data slot from a parent object means _sharing_ it with the parent. Surely Bruce Cohen's intention was not that when a circle becomes a ellipse, it has to share all the instance variables of some prototype ellipse thenceforth. (I have not read the paper mentioned, but the above is obvious anyway.) BTW, you may have to wait a day or two yet for the continuation posting that I promised in the last one, but it's coming. Markku Sakkinen Department of Computer Science and Information Systems University of Jyvaskyla (a's with umlauts) Seminaarinkatu 15 SF-40100 Jyvaskyla (umlauts again) Finland SAKKINEN@FINJYU.bitnet (alternative network address)
hoelzle@Neon.Stanford.EDU (Urs Hoelzle) (09/18/90)
sakkinen@tukki.jyu.fi (Markku Sakkinen) writes: >>[ explanation how circles / ellipses can change representations in a >> prototype-based system like Self ] >I am sorry, but there seems to be a little confusion still. >In a prototype-based system, "inheriting" a data slot from a parent object >means _sharing_ it with the parent. Surely Bruce Cohen's intention was not >that when a circle becomes a ellipse, it has to share all the instance >variables of some prototype ellipse thenceforth. >(I have not read the paper mentioned, but the above is obvious anyway.) I am sorry, but there seems to be a little confusion still... ;-) The parent object is a *clone* of the {circle,ellipse} prototype, not the prototype itself. Every circle has its own "data parent" holding its state, and all circles have a common parent holding common behavior (and possibly common state, if needed). With object-based inheritance, an object can inherit from any other object - there's nothing special about the prototype. But I think the above is obvious anyway ;-) >Markku Sakkinen
jml@wally.altair.fr (Jean Marie Larcheveque) (09/19/90)
I earlier suggested that the circle-to-ellipse mutation could be
handled without using dynamic inheritance, with something like
class ellipse {
concrete_ellipse *state_holder;
// ...
}
where concrete_ellipse is a superclass of circle.
However, I made things rather confusing by further suggesting
that concrete_ellipse should be a subclass of ellipse and leaving
out the * in front of "state_holder", and Bruce Cohen rightly
objected:
>But then don't you have to add a set of delegation functions to ellipse so
>an instance of it can pass on calls to it's instance of concrete_ellipse?
Yes indeed! Since we are using composition instead of inheritance
to forward the behavior, we have to make this explicit, so it is
not so neat as in Self, as we program an ad hoc mechanism instead
of using generic mechanisms. However, the fact remains that,
whether we dynamically act on inheritance links or create ad hoc
links to allow switching between 2 types of behavior, this
possibility has to be specified before any object is created. In
one case, creation of a mutable object involves creating both an
identity-holder and a parent behavior-holder, while in the other,
the class definition has to specify behavior delegation. My
knowledge of Smalltalk is insufficient to tell whether become:
leaves the object identifier unmodified; but if such is the case,
it is by far the best solution, as it allows objects to change
classes even when this was not anticipated at the time of their
creation.
--
Jean-Marie Larcheveque <jml@bdblues.altair.fr> or
<jml@nuri.inria.fr>