Re: breadth-first search through multiple inheritance hierarchy??

[Rici Lake <lua@...>]

On 26-Sep-06, at 10:22 AM, Leo Razoumov wrote:

> Hi Everyone,
> PiL2 as well as PiL1 has a section on multiple inheritance (section
> 16.3) complete with an example on  how to implement multiple
> inheritance in Lua. The problem with this implementation is that the
> inheritance hierarchy is traversed in "depth-first" fashion. This has
> a problem. Let say I have the following hierarchy
>
> T--> M --> B   [ B has "foo"]
>  \-> N             [ N has "foo"]
>
> If I try T.foo it will find B.foo because depth-first search visits
> the whole T->M->B hierarchy before T->N. One gets "foo" from a
> grandparent instead of a direct parent.
>
> More natural way of traversing inheritance hierarchy would be a
> "breadth-first search" when all immediate parents are visited first
> followed by all the grandparents across all the parents and so on.
>
> Is there any simple way to do breadth-first search in this case?
> Conventional wisdom from CS books recommends to deploy a FIFO queue.

Breadth-first may not be what you want, either, but in any event to
implement it you need to bypass the Lua __index mechanism, since you
need an actual tree of inheritances.

However, you might want to look at this paper:

http://www.webcom.com/haahr/dylan/linearization-oopsla96.html

which discusses various algorithms for ordering inheritance orders.
C3 was the algorithm selected for Python, I believe.

Doing this computation dynamically is probably too time-consuming;
either the computation should be done when the class is created, or 
cached
when it is first needed. Since the __index metamethod mechanism needs to
be side-stepped anyway, it would be possible to provide an API for
dynamically changing inheritance relationships, which would void the
caches, but I don't know that such an API would be useful in any
real-life program.