Re: Inheritance Tree

David Chase <>
12 Dec 1997 14:54:26 -0500

          From comp.compilers

Related articles
Inheritance Tree (Gu Jian) (1997-11-29)
Re: Inheritance Tree (David Chase) (1997-12-12)
Re: Inheritance Tree (Chris F Clark) (1997-12-13)
| List of all articles for this month |

From: David Chase <>
Newsgroups: comp.compilers
Date: 12 Dec 1997 14:54:26 -0500
Organization: Natural Bridge LLC
References: 97-11-154
Keywords: analysis, optimize

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,

Post a followup to this message

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