Efficient Implementation of Multi-Methods for Statically Typed Languages

Some of the benefits of object-oriented programming such as extensibility and reusability are fundamentally based on inheritance and late binding. Dynamic dispatching is not only time consuming but it also prevents the usage of some optimization techniques such as inlining or interprocedural analysis. The situation is even more severe for languages supporting multi- methods, where dispatching is not only performed based on the type of the receiver, but also based on the types of the arguments. The most efficient way to perform dynamic dispatching is to avoid it as often as possible, without restricting the use of multi-methods. In this paper it is shown how this goal can be achieved through static analysis. We present a technique which discards all method calls which can be statically bound. Furthermore, even if a method cannot be statically bound, we derive information which will at run time speed up the dispatching process considerably.

ICSI Technical Report TR-95-053

Technical Report