Re: Inheritance Tree

Chris F Clark <>
13 Dec 1997 12:01:46 -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: Chris F Clark <>
Newsgroups: comp.compilers
Date: 13 Dec 1997 12:01:46 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 97-11-154 97-12-096
Keywords: OOP, performance

OOPSLA 97 just had an article on this topic--Efficient Type Inclusion
Tests, Jan Vitek, R Nigel Horspool, & Andreas Krall. SIGPLAN Notices
v 32 n 10, Oct 97.

They discuss several alternative representations. The tree numbering
method David Chase method (they called it relative numbering) being
noted for the fact that it only works on inheritance trees, and not
DAGs, which can occur if your language supports multiple inheritance.

Anyway, this got me thinking about relative numbering. It can be
extended to work for DAGs (or even general directed graphs), although
many graphs require more than two numbers to fully disambiguate (and
cyclic graphs, which don't represent any form of inheritance I know of
form an interesting special case). It (relative numbering) turns out
to be related to the dominator problem, which means I may get a chance
to investigate it further (and then I might write it up), as I find
myself solving dominator problems quite often.

Hope this helps,

Chris Clark Internet :
Compiler Resources, Inc. CompuServe : 74252,1375
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)
Web Site in Progress: Web Site :

Post a followup to this message

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