Snyder [16] and Liskov [13] have also studied conflicts between data encapsulation and other aspects of object-oriented programming. They discuss problems that arise when subclass operations are given access to superclass data or private operations, and Snyder [16] observes that a class's superclasses cannot be considered an implementation detail of the class in a system that allows multiple inheritance without replicating common superclasses.
Appel [2, Section 4.2], Harrison and Ossher [10], Krishnamurthi, Felleisen, and Friedman [11], and possibly many others have noted the conflict that arises between reuse by inheritance and reuse in a function. There are a number of approaches to resolving this problem, which we discuss in order of increasing familiarity for programmers familiar with C++.
Some techniques for multiple dispatch (also known as multi-methods) [3,9,5,4] could be used to provide dispatch on a parameter other than the receiver of an object, or by including the type needed for dispatch in a new tuple type [12]. However, general multi-method dispatch either requires more than constant time per dispatch or excessively large dispatch tables [1]. However, recent techniques for multimethod dispatch [6] have very low overhead, and we believe they would be at least as efficient as our system for the case of single dispatch (which, as we have noted, is all that is needed to resolve the conflict between different kinds of reuse).
Work on multiple dispatch also differs from ours in that it not focused on the separation of dispatch and access. Cecil explicitly retains the unification of dispatch and access, though a change to this rule would probably not have any impact on performance. We believe the main barrier to the widespread use of these techniques to enable both kinds of reuse is the tendency of programmers to prefer familiar techniques and languages. The other approaches to solving this problem (including ours) focus on techniques or language extensions that can be applied to C++ or Java. General discussions of techniques for multi-method dispatch can be found in [1, Section 3.2] and [6, Section 3.7].
The visitor pattern could be applied to our abstract syntax tree example: Each tree class (such as Plus) would provide a ``visit'' operation that takes a ``visitor'' parameter, and sends the visitor a message that is specific to the tree subclass (e.g. Plus::visit(visitor &v) sends v.visitPlus(this)). This approach still interferes with the addition of new subclasses, since the visitor class must be extended to include a new method for each new subclass. The ``Extended Visitor'' protocol [11] fixes this problem, but still has higher overhead than a single dispatch accessory function, and to some degree shifts the burden of performing dispatch back from the compiler onto the programmer. It thus creates unnecessary opportunities for programmer error, and suffers from limitations due to the lack of compiler support. Krishnamurthi, Felleisen, and Friedman have developed a language named Zodiac to simplify the use of the extended visitor pattern, but it is not clear how quickly it will be adopted by programmers who are familiar with C++ or Java.
Harrison and Ossher [10] proposed the ``Subject-Oriented Programming'' style. This approach, like our accessory functions, can serve as the basis for extension of an existing language like C++ (it is currently available as a preprocessor for C++ in IBM's Visual Age for C++ Version 4). Instead of separating the property of dispatch from presence in a class, subject-oriented programming facilitates the decomposition of a class into different ``subjects'' that can be developed independently and then composed. A subject can correspond to one of our accessory functions, a group of functions, or functions together with associated data (like a class). This approach is more general than ours (though not more general than some of the multimethod systems), and correspondingly raises more new issues for programmers, such as the selection of composition system.
We have focused on providing a resolution to the conflict between reuse by inheritance and reuse in a function, while creating the minimal impact on programmers who are familiar with the traditional object-oriented style. Our extensions can be added to C++ by relaxing a single rule (that dynamic dispatch must be based on the receiver of the message). A preliminary description of accessory functions appeared at MASPLAS '99 [7]. We have also explored the possibility of allowing multiple virtual parameters [8], though this work does not make a significant contribution to the existing literature on multiple dispatch.