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

["Leo Razoumov" <slonik.az@...>]

On 9/26/06, Rici Lake <lua@ricilake.net> wrote:
> [..snip..]
> 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.

I am planning to do memoizing, i.e. after first successful search in
the hierarchy the element found (or method or whatever) is added to
the metatable of the calling object so that next time one does not
need to traverse the entire inheritance tree again.

--Leo--