[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: breadth-first search through multiple inheritance hierarchy??
- From: Rici Lake <lua@...>
- Date: Tue, 26 Sep 2006 14:39:00 -0500
On 26-Sep-06, at 10:22 AM, Leo Razoumov wrote:
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:
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
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