Time and Space Efficient Method-Lookup for Object-Oriented Programs (Extended Abstract)

) S. Muthukrishnan Martin Muller y DIMACS & Univ. of Warwick University of New Mexico 1 Introduction Object-oriented languages (OOLs) are becoming increasingly popular in software development (See [4, 11, 18, 20] on OOLs). The modular units in such languages are abstract data types called classes, comprising data and functions (or selectors in the OOL parlance); each selector has possibly multiple implementations (or methods in OOL parlance) each in a different class. These languages support reusability of code/functions by allowing a class to inherit methods from its superclass in a hierarchical arrangement of the various classes. Therefore, when a selector s is invoked in a class c, the relevant method for s inherited by c has to be determined. That is the fundamental problem of method-lookup in object-oriented programs. Since nearly every statement of such programs calls for a method-lookup, efficient support of OOLs crucially relies on the method-lookup mechanism. The challen..