Subject: Re> Multiple Inheritance

From: [email-masked] (Jeff Prothero)
Date: Mon, 29 Mar 1993 13:08:34 -0800

I said:

| > For example, a maintainer can no longer assume that it it safe to
| > insert a new superclass in a given hierarchy (in order perhaps to
| > share some code with a newly created class -- a common sort of
| > maintainance programming in an oo system) merely if all pre-existing
| > classes export the same behavior after the change: the maintainer
| > must verify that the change in treedepth of each moved method does
| > not break the behavior of any _user_ of any of the classes by
| > implicitly switching it to another method.

Greg replied:

| I would find this more plausible if I could see a concrete example.

*blush*.  The analysis I had in mind was in fact completely
incorrect.  My apologies!  Greg did have the intellectual
honesty to dig up an example of the sort I had in mind:

|          Root object
|        /     /  \    \
|      d      /    \     e
|        \   /      \  /
|          a         b
|            \     /
|               c
| 
| To be fair, there is one sticky point.  If I reimplement a
| root object verb on d, which has exactly the same behavior
| as the root object method, then a has the same behavior as
| it did before, while c changes behavior.  While this is a
| "smoking gun" example of loss of encapsulation, it's not
| clear to me that this would cause a problem in practice,
| since I don't see *why* you'd want to reimpliment a root
| object verb on d.

Well, we could spin a story:

  Once upon a time there was a subclass B of class A with many
  verbs, among them v:

	   A
	  /
	 /
	/
       /
      B:v

  B got hastily cloned and modified one day by hacker Sloppy
  Joe to produce additional related classes C (with many mostly
  different verbs, but the same verb v) and D (with a
  different implementation v' of v):

	   A
	  /|\
	 / | \
	/  |  \
       /   |   \
      B:v C:v D:v'

  which classes were duly used as parents by by
  Pricillia Precise for her class E:

	   A
	  /|\
	 / | \
	/  |  \
       /   |   \
      B:v C:v D:v'
       \   |   /
	\  |  /
	 \ | /
	  \|/
	   E

  which worked fine until Joe got around to cleaning
  up a bit and moved the common v implementations to
  A to avoid redundancy:

	  A:v
	  /|\
	 / | \
	/  |  \
       /   |   \
      B    C  D:v'
       \   |   /
	\  |  /
	 \ | /
	  \|/
	   E

  At which point E shifted to using v' instead of v and broke,
  despite the exported interfaces of B, C and D remaining
  exactly the same.  This upset Priscillia Precise no end, she
  thought she'd proved the code correct.  Naturally, she wrote
  her own depthfirst message-send which fixed the problem and
  allowed her to live happily ever after *wink*.

However, this sort of situation is likely not nearly as
common as those which I'd originally mistakenly had in mind
as exhibiting this sort of effect.  I think Greg has a least
halfway convinced me.

| One more issue, on efficiency:
| 
| > (Changing updating the parent pointers in an object from an O(1)
| > operation to, worstcase, an O(N) operation in the size of the db, as
| > the coldmud approach appears to do, seems also unappealing,
| > especially in a diskbased system.)
| 
| You have to traverse the children digraph of the object, yes.  This is
| unpleasant, but I think it's fairly rare to change the parent pointers
| on, say, generic room, while the database is large.
| 
| --GBH
| 

I'm not sure I want child pointers: seems to me they can
play havok with garbage collection.  Nor do I have data on
how often the class hierarchy grows at leaf nodes vs
internal nodes.  (I gather you feel it's almost exclusively
at the leaves, or very close to?)

On the other hand, it appears to me one doesn't have to buy
your implementation to get your semantics: one should be
able to get the same result for the price of a full
depth-first search at message-send time, without any static
datastructures of the sort you describe, no?  Assuming the
usual caching of frequently sent messages and/or typically
small parent graphs, the speed difference might not be
significant anyhow.

Maybe we should thoroughly confuse folks and provide both
variants? :)  That's either indecisive or democratic...

CrT

---

From: Greg Hudson <[email-masked]>
Date: Mon, 29 Mar 1993 14:42:43 -0800

A couple of points:

> I'm not sure I want child pointers: seems to me they can play havok
> with garbage collection.

MOO has child pointers.  I can't see how they would play havok with
garbage collection; when you destroy an object or change its parents,
you update the child pointers on the parent object.  In fact, it makes
it easier to deal with destroying objects; you can remove the parent
pointers on the children, thus ensuring that parent pointers are
always valid.  This eliminates the need for type-checking code, both
in the server and (more importantly) in methods which look at parent
pointers.

This reminds me of an issue I never resolved: what happens when you
destroy an object that's not a leaf?  If a child has other parents, I
suppose you can just remove the parent from the list (changing the
behavior of the child completely, of course); if it doesn't, do you
destroy the child object, or let it sit there as a root object?
Alternatively, do you disallow destroying an object with children?
>From a maintainer's point of view, this last option is probably the
best, since it removes the potential for accidentally slaughtering or
disabling large portions of the database, but it does pose some issues
for players (I can't destroy my object because of your child object).

> On the other hand, it appears to me one doesn't have to buy your
> implementation to get your semantics: one should be able to get the
> same result for the price of a full depth-first search at
> message-send time, without any static datastructures of the sort you
> describe, no?  Assuming the usual caching of frequently sent
> messages and/or typically small parent graphs, the speed difference
> might not be significant anyhow.

I hadn't thought about caching frequently-sent messages.  I guess you
might save a lot of object retrievals this way.  Would it be better to
have a global cache or a cache on each object?  The latter
implementation's success would depend heavily on the object-to-disk
cache, I suppose.

At any rate, I'm not exactly sure how you would simulate an LRUJ
system (left-to-right, up-to-join) with a complete depth-first search.
Simply taking the last method you find isn't going to work.  I think
you really have to know what the common ancestors are, which requires
at least an O(n ln n) process on the number of ancestors.  Maybe I'm
missing something, though.

--GBH