Re: Inheritance Tree

Gu Jian wrote:
>
> Can anyone suggest good references for implementing inheritance trees?


Paul Dietz, symposium on theory of computing, 1980 or 81.


The basic trick is to give each node of a tree an IN and OUT number
as you walk the tree in left-to-right or right-to-left order.


IN(ancestor) < IN(any_descendent) < OUT(any_descendent) < OUT(ancestor)


Dietz shows how you can use binary search to perform interesting
lookup operations among a set of nodes (lexical scopes, or type
nodes) in such a tree. Such tricks were proposed for implementation
of TYPECASE in Modula-3, but never (to my knowledge) used there.
They were also proposed but never (to my knowledge) used as a way
of implementing SSA without renaming. There have also been used
to implement efficient "applicative symbol tables" in an attribute
grammar evaluation system sold by Declarative Systems. They probably
have other uses; it is a cute trick.


--
David Chase, chase@world.std.com
--

Return to the comp.compilers page.
Search the comp.compilers archives again.