Complexity Analysis of Late Binding in Dynamic Object-Oriented Languages
Enrico Pontelli, Desh Ranjan, Gopal Gupta · 1999
We study the algorithmic complexity of supporting late binding in dynamic object-oriented programming languages. Dynamic object-oriented languages (such as most Prototype-based languages and systems like CLOS) allow creation of new class definitions at runtime. Late binding means that procedure-call name resolution, i.e., mapping of procedure calls to method definitions, is done at run-time, rather than compile-time. Late binding is an essential feature of object-oriented programming and is present in most object-oriented languages, e.g., Java, CLOS, Smalltalk, C++ (virtual functions), etc. Name resolution for late binding is easily solved for static languages such as Java and C++; for dynamic languages, however, it is a complex problem. We propose an abstraction of the late binding problem for dynamic object-oriented languages in terms of operations on dynamic trees, and prove a time lower bound of OMEGA(lg N) per operation, ...