Time and space efficient method-lookup for object-oriented programs
Subramanian Muthukrishnan, Martín Müller · 1996
Object-oriented languages (OOLs) are becoming increasingly popular in software development. 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 challenge in implementing the method-lookup, as it turns out, is to use only a reasonable amount of table-space while keeping the query time down. Substantial research has gone into achieving improved space vs time trade-off in practice.