|
Abstract : |
Dynamic Object-Oriented languages allows for dynamic definition of new classes, new generic functions and new methods. This paper proposes a single and compact data structure to, at the same time, facilitate the addition of new classes, generic functions or methods, and still ensure a fast method selection. Key words: data structures, programming languages, object-oriented dispatch. Within a dynamic Object-Oriented language, new classes, new generic functions and new methods may be created at run-time. We assume the CLOS model [BDG 88] where a generic function is a dispatching function over a set of methods. When invoked, a generic function executes its most appropriate method based on the class of its arguments. This dispatching process, or method selection, has been well studied [KR90,Ros91,HC92,AGS94,VH94,CT95] and its efficiency is based on the elaboration of a specific dispatch structure; see [VH94] for a detailed comparison. The dynamic character of the language requires the implementation to be able to regenerate the dispatch structure whenever a class, a generic function or a method is added. Our paper proposes to implement the dispatch structure with a decision tree, respecting the inheritance tree thus making easy these additions and yet providing a fast dispatch mechanism based on a specific numbering of classes. While multiple dispatch is addressed in section 5, our solution is particularly useful for languages with single inheritance and singlemethod dispatch: the Smalltalk case [GR83], where the method is selected according to the class of a distinguished argument: the receiver. The examples of the rest of the paper are based on the tree of classes shown on figure 1, |
