Subject: Re> Multiple Inheritance

From: Byron Montgomerie <[email-masked]>
Date: Sun, 28 Mar 1993 09:03:40 -0800

With regard to the problem incountered with two parents having the same verbs,
here are a few thoughts:

  Don't allow multiple parents with conflicting verbs or properties.
  Conflicting defined as parents that have the same verb name which is defined
  on parents which not in common between the two.
      
               #-1          Object #1
		 \         /    \    \
	      Parent1 Parent2 Parent3 Parent4
                  \   /      \   |   /
	         Parent5      Parent6 
		       \     /
		       Object

  So, if Parent 1 and 3 had a verb/prop with the same name/args/etc then
  attempts to create an object with parents 5 and 6 would fail. If 5 and 6
  have matching verbs not defined on 2 then object can't have those parents.
  If parent 1 has properties in conflict with Object #1 then fail.

  So if an object has a bunch of parents that all have unique (defined on only
  one object) verbs and properties then there would be no conflict problems to
  have to deal with.  

  With this type of system, adding verbs to objects would have to pass checks
  to make sure that adding such a verb would not conflict with the inheritance
  of it's children. Also, all this checking could be quite time-consuming and
  perhaps complex.

  Another way, perhaps simpler, would be to have ordered parents, if a verb is
  found on the first parent in an objects list then it would be as if that verb
  did not exist on the rest of the parents.  This could get tricky with
  the functionality of the parents perhaps.  

Byron...
 __________________________________________________________________________
| __  ///    "Byron Montgomerie"  Internet: [email-masked]   __  /// |
| \\\///      "Does anybody here remember Vera Lynn?               \\\///  |
|  \XX/        How she said that we would meet again,               \XX/   |
|  Amiga       some sunny day..." -- Pink Floyd --                 Amiga   |
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

---

From: [email-masked] (Erik Ostrom)
Date: Sun, 28 Mar 1993 11:02:47 -0800

>Date: 	Sun, 28 Mar 1993 09:03:40 PST
>From: Byron Montgomerie <[email-masked]>

>  Don't allow multiple parents with conflicting verbs or properties.

In a many-programmer environment, I think this is going to be too
limiting (as it stands).  The problem is that sooner or later you're
going to want to create an object that inherits from two parents which
use the same verb name for different things, or even for the same
thing but in (slightly) different ways.

I originally wrote a long thing here about Eiffel, but I realized that
Eiffel's inheritance rules would make people absolutely miserable in a
classless system--each useful method added to an object would have to
be added separately to each of its descendants.

Anyway, the other point I wanted to talk about was conflicting
properties.  I think, since we're talking about massive, db-breaking
changes to MOO, that properties should be dealt with in such a way
that conflict is impossible.  Specifically, I'd like to see MOO take
something like COOLMUD's approach.

In COOLMUD, objects don't have properties; instead, each object may
have variables that are visible _only_ from within the methods of that
object.  What this means for inheritance is that, if I have a variable
called "key" on the generic room, then it can be referred to by any
method on the generic room (e.g., :is_unlocked_for), but not by any
method on its descendants.  If you want descendants to be able to
refer to or set their key variables, you have to provide, say,
:get_key and :set_key methods.

This means that I can have as many conflicting "properties" as I
want--if I want an object that's a combination of $thing and $room, I
can do that.  Of course, I still have to deal with verb conflicts; if
both $thing and $room have :get_key methods, I still have trouble.

(I think inheriting from $thing and $room would be a terrible design,
but in an environment like LambdaMOO it seems inevitable that
something like this would come along.)

I was going to start rambling about abstract data types and
lightweight, garbage-collected objects here, but this message is long
enough for now.

-JoeFeedback/Erik

---

From: Greg Hudson <[email-masked]>
Date: Sun, 28 Mar 1993 11:49:03 -0800

The two strategies I've seen proposed for dealing with method searches
(and presumably variable searches) are:

	* A depth-first search on the parents graph
	* Disallowing conflicting verb definitions

The first strategy, without any restrictions, leads to a number of
problems.  Suppose I have the digraph (on all of my diagrams, all
edges are directed upwards):

	Root object
	  /	\
	a	  b
	  \	/
	     c

If b and the root object both define a verb, then presumably we'd
rather use b's override than the root object's definition; but a
depth-first search on the parents tree finds the root object's
definition first.

Disallowing conflicting verb definitions doesn't alleviate this
problem.  We still have to figure out how to find the verb definition
on b before the one on the root object.

A breadth-first search only partiall solves the problem.  Consider the
digraph:

	Root object
	  /	\
	a	  |
	|	  |
	b	  d
	|	  |
	c	  |
	  \	/
	     e

Special-casing the root object is no help at all; the same arguments
apply to any common ancestor.  Unless we disallow common ancestors
completely, so that the parents digraph becomes a tree, we will always
have the problem of two (or more) parents with a common ancestor, with
a verb on the common ancestor overridden on a parent other than the
first, or on an ancestor of such a parent.

I dealt with this in Coolmud and in Coldmud by maintaining an ancestor
precedence list on each object.  This is somewhat storage-intensive,
but not terribly so, and both are disk-based servers anyway.  The
ancestor precedence list is ordered on a left-to-right, up-to-join
basis.  The ordering looks like a depth-first enumeration until it
reaches a common ancestor.  However, enumeration stops at a common
ancestor unless we reached it through the last possible path.  As an
example, consider the digraph:

			   r
			  / \
		  _______/   \
		 /	      \
		a	       \
	       / \		\
	      /   \		 \
	     /	   \		  \
	    c	    d		  |
	     \	   / \		  |
	      \   /   \		  |
	       \ /     \	  |
		e	\______   |
	       /|	       \  |
	      / |		\ |
	     /	|		 \|
	    f	g		  h
	     \	|		  |
	      \ | ________________/
	       \|/
		i

We enumerate starting at the first parent, so we write down 'f'.  Now
we've hit a common ancestor 'e', and we're not at the last path, so we
stop, and go onto the next parent.  We write down 'g' and again come
to 'e', this time by the last path.  So we continue and write down
'e', and then 'c', and come to 'a', which is a common ancestor.  We
stop, and go back to the other parent of 'e', which is 'd', also a
common ancestor.  We go all the way back to the third parent of 'i',
which is 'h'.  We come again to 'd', and since we are on the last path
to 'd', we continue onto 'a'.  Again, we are on the last path to that
common ancestor, so we continue to 'r'.  We don't write down 'r' on
this visit, since there is another path to it; instead we go back to
the second parent of 'h', which happens to be 'r' again.  Now we write
it down, completing the list:

	i f g e c h d a r

This enumeration is, in my opinion, the most intuitive.  We never fail
to miss an override; for instance, a verb on 'd' that 'h' overrides
will be found on 'h'.  If there are conflicting verb definitions on
objects that can't be ordered according to one inheriting from the
other (say, on 'c' and 'h'), we can determine which is leftmost in the
digraph; that is, which shows up in a depth-first enumeration.

If we still want to restrict users from putting conflicting verb
definitions on parallel objects like 'c' and 'h', we can, but there's
no reason to; it doesn't make things any harder for us to allow it.
The only restriction that we need to make is that there be no cycles
in the parents digraph, which is a restriction we'd want to make
anyway for sanity reasons.

Having a list on the object requires us to do no checking when we do
the actual search; we simply search for the verb (or variable) on each
ancestor in turn.  The space overhead is significant (if most rooms
inherit from, say, some specialized room, 'generic room', 'generic
container', 'generic described object', 'generic named object', and
the root object, we're looking at five object IDs per room for the
ancestor precedence list, plus some overhead) but not bad.

Readers are no doubt wondering at this point how I propose to
construct such a list when we create an object or modify its parents
or its ancestors' parents.  It may be obvious from looking at the
graph that 'e' is a common ancestor of 'f' and 'g', but it's not at
all obvious from a programmer's point of view, and scanning a children
graph at each point would be intolerable, especially in a disk-based
server (it would require several sweeps through the database).

It turns out that constructing the list is fairly easy if we do it
backwards.  Using pseudo-code, we could define the function
enumerate(node) as:

	if (node has already been written down)
		do nothing
	otherwise
		traverse list of parents in reverse order
			enumerate(parent)
		write down node

This allows us to write down a common ancestor the first time we come
to it, instead of the last time.  Checking if we've already written
down a common ancestor is much easier than checking if we're going to
write it down in the future.

To see how this would work in practice, here is some example code
derived from the Coldmud source.  I've simplified the memory
management somewhat, to make it more understandable.  The code hasn't
been compile-tested or run-tested, but I have implemented and tested
this scheme in Coolmud in a similar manner, so I know that the general
design gives the desired results in practice.

---

/* Declarations for what an object is, how the cache works, what a
 * list is, etc. */

#define ANCTEMP_STARTING_SIZE	16

static long *anctemp;
static int anctemp_size, anctemp_pos;

void init_object(void)
{
    anctemp = (long *) malloc(ANCTEMP_STARTING_SIZE * sizeof(long))
    if (!anctemp)
	panic();
    anctemp_size = ANCTEMP_STARTING_SIZE;
}

void object_construct_ancprec(long dbref)
{
    Object *object;
    int i;

    /* Call the recursive routine to construct the ancestor precedence list in
     * anctemp. */
    anctemp_pos = 0;
    object_construct_ancprec_recurse(dbref);

    /* At this point, the ancestor list in anctemp[] is backwards, and has an
     * extra entry at the end for dbref. */

    object = cache_get(dbref);

    object->ancestors = anctemp_pos - 1;
    object->ancprec = (long *) malloc((anctemp_pos - 1) * sizeof(long));
    if (!object->ancprec)
	panic();

    for (i = 0; i < anctemp_pos; i++)
	object->ancprec[i] = anctemp[anctemp_pos - i - 2];

    cache_put(object, object->dbref);
}

static void object_construct_ancprec_recurse(long dbref)
{
    Object *object;
    List *parents;
    int i;

    /* Check if we've already done this object. */
    for (i = 0; i < anctemp_pos; i++) {
	if (anctemp[i] == dbref)
	    return;
    }

    object = cache_get(dbref);
    parents = object->parents;
    parents->refs++;			/* Hold onto this list. */

    /* Recursively process parents from right to left. */
    for (i = parents->len - 1; i >= 0; i--)
	object_construct_ancprec_recurse(parents->el[i].u.dbref);

    list_discard(parents);

    /* Resize anctemp[] if necessary, and add us to it. */
    if (anctemp_pos == anctemp_size) {
	anctemp_size *= 2;
	anctemp = (long *) realloc(anctemp, anctemp_size * sizeof(long));
	if (!anctemp)
	    panic();
    }

    anctemp[anctemp_pos++] = dbref;
}

--GBH