Method lookup search

[dje@scs.carleton.ca (Danny Jared Epstein)]

I've been thinking about your suggestion that a breadth-first search
be used to find inherited slots, rather than the existing depth-first
priority scheme.  Here are my ideas about how to improve the method
lookup search.  I'm going to use an example in which a data parent is
used to inherit representation:

                        traits a
                       A/      \B
                 traits b      prototype a
                       C\      /D
                      prototype b

If you make the D link higher priority than the C link, then prototype
b will inherit from traits a with more "force" than from traits b.
This means that traits b can't override methods in traits a which is
clearly wrong.

If you make the D link lower priority than the C link, then if there
is a slot in both traits a and in prototype a, then prototype b will
inherit the one from traits a rather than the one from prototype a.
Although prototype a can override traits a, prototype b wont inherit
the override.  This is clearly undesirable.

If you make the D link the same priority as the C link, then the above
case would cause an ambiguity.  Although prototype a can override
traits a, prototype b will inherit both slots rather than just the one
in prototype a.

No matter what priorities you use, you can't get it to work right.
You end up having to put slots in prototype b which do directed
resends.  The search orders (expressed as a list of sets) for the
three cases are as follows:

   D > C: ({prototype a}, {traits a}, {traits b})
   D < C: ({traits b}, {traits a}, {prototype b})
   D = C: ({traits a, traits b, prototype a})

A breadth-first order would search a level at a time, presumably
causing an ambiguity if several slots are found at a given level.  If
there is a slot in both traits b and in prototype a, then prototype b
will inherit both, making it ambiguous.  Maybe this is acceptable, but
I think the programmer should be able to specify that the D link is
higher priority than the C link to avoid this ambiguity.

It seems to me that you want the ancestors to be searched in an order
which conforms to the partial ordering derived from the inheritance
hierarchy (normally a directed acyclic graph (DAG)):

   If a inherits from b, then search a before b.

The breadth-first obeys this rule, but the existing depth-first
priority scheme could be modified to enforce the above rule as well.
This would have the following effect on the search orders:

   D > C: ({prototype b}, {prototype a}, {traits b}, {traits a})
   D < C: ({prototype b}, {traits b}, {prototype a}, {traits a})
   D = C: ({traits b, prototype a}, {traits a})

All of these orders are reasonable and potentially useful.  I'm not
sure how this would work in a cyclic inheritance hierarchy, but I
suspect that it would break down completely, because it would require
you to search in two conflicting orders.  Also, the existing search
order may have some advantages that I am unaware of.

Do I understand your idea for using a breadth-first search?  My
understanding is that you eliminate priorities in this scheme.

Comments anyone?

- Danny Epstein
  dje@scs.carleton.ca