1Multiple Dispatch as Dispatch on TuplesGary T. LeavensDepartment of Computer Science,Iowa State University,229 Atanasoff Hall, Ames, Iowa, 50011 [email protected]+1 515 294-1580Todd D. MillsteinDepartment of Computer Science and Engineering,University of Washington,Box 352350, Seattle, WA 98195-2350 [email protected]+1 206 543-5118ABSTRACTMany popular object-oriented programming languages, suchas C++, Smalltalk-80, Java, and Eiffel, do not supportmultiple dispatch. Yet without multiple dispatch,programmers find it difficult to express binary methods anddesign patterns such as the “visitor” pattern. We describe anew, simple, and orthogonal way to add multimethods tosingle-dispatch object-oriented languages, without affectingexisting code. The new mechanism also clarifies manydifferences between single and multiple dispatch.KeywordsMultiple dispatch, multimethods, generic functions, typing,single dispatch, binary methods, semantics, language design,Tuple.1 INTRODUCTIONSingle dispatch, as found in C++ [Stroustrup 97], Java[Arnold & Gosling 98, Gosling et al. 96], Smalltalk-80[Goldberg & Robson 83], and Eiffel [Meyer 92, Meyer 97],selects a method using the dynamic class of one object, themessage’s receiver. Multiple dispatch, as found in CLOS[Chapter 28, Steele 90] [Paepcke 93], Dylan [Shalit 97,Feinberg et al. 97], and Cecil [Chambers 92, Chambers 95],generalizes this idea, selecting a method based on thedynamic class of any subset of the message’s arguments.Multiple dispatch is in many ways more expressive andflexible than single dispatch in object-oriented (OO)programming [Bobrow et al. 86, Chambers 92, Castagna 97,Moon 86].In this paper we propose a new, simple, and orthogonal wayof adding multiple dispatch to existing languages with singledispatch. The idea is to add tuples as primitive expressionsand to allow messages to be sent to tuples. Selecting amethod based on the dynamic classes of the elements of thetuple gives multiple dispatch. To illustrate the idea, we havedesigned a simple class-based OO language called Tuple*.While perhaps not as elegant as a language built directly withmultiple dispatch, we claim the following advantages for ourmechanism:1. It can be added to existing single dispatch languages,such as C++ and Java, without affecting either (a) thesemantics or (b) the typing of existing programs writtenin these languages.2. It retains the encapsulation mechanisms of single-dispatch languages.3. It is simple enough to be easily understood andremembered, we believe, by programmers familiar withstandard single dispatch.4. It is more uniform than previous approaches ofincorporating multiple dispatch within a single-dispatching framework.To argue for the first two claims, we present the semantics ofthe language in two layers. The first layer is a small, class-based single-dispatching language, SDCore, of no interest initself. The second layer, Tuple proper, includes SDCore andadds multiple dispatch by allowing messages to be sent totuples.Our support for the third claim is the simplicity of themechanism itself. If, even now, you think the idea of sendingmessages to tuples is clearly equivalent to multiple dispatch,then you agree. To support the fourth claim, we argue belowthat our mechanism has advantages over others that solve thesame problem of incorporating multiple dispatch intoexisting single-dispatching languages.The rest of this paper is organized as follows. In Section 2 wedescribe the single-dispatching core of Tuple; this is neededonly to show how our mechanism can be added to such alanguage. In Section 3 we describe the additions to thesingle- dispatching core that make up our mechanism andsupport our first three claims. Section 4 supports the fourthclaim by comparison with related work. In Section 5 we offerAppears in the OOPSLA ‘98 Conference Proceedings,Conference on Object-Oriented Programming, Systems, andApplications, Vancouver, British Columbia, Canada, October 18-22, 1998, pp. 374-387.*With apologies to Bruce et al., whose TOOPLE language [Bruce et al. 93]is pronounced the same way.2some conclusions. In Appendix A we give the concretesyntax of Tuple, and in Appendix B we give the language’sformal typing rules.2 SDCORE, THE SINGLE-DISPATCHING CORE OFTUPLEIn this section, we introduce the syntax and semantics ofSDCore by example.2.1 Syntax and SemanticsThe single-dispatching core of Tuple is a class-basedlanguage that is similar in spirit to conventional OOlanguages like C++ and Java. Integer and boolean values,along with standard operations on these values, are built intothe language. Figure 1 illustrates SDCore with the well-known Point/ColorPoint example. The Point classcontains two fields, representing an x and y coordinaterespectively. Each point instance contains its own values forthese fields, supplied when the instance is created. Forexample, the expression new Point(3,4) returns a freshpoint instance with xval and yval set to 3 and 4respectively. The Point class also contains methods forretrieving the values of these two fields and for calculatingthe distance from the point to some line. (We assume theLine class is defined elsewhere.)For ease of presentation, SDCore’s encapsulation model isextremely simple. An instance’s fields are only accessible inmethods where the instance is the receiver argument. Aninstance may contain inherited fields, which this rule allowsto be accessed directly; this is similar to the protected notionin C++ and Java.The ColorPoint class is a simple subclass of the Pointclass, augmenting that definition with a colorval fieldand a method to retrieve the color. (We assume that a classColor is defined elsewhere.) The ColorPoint classinherits all of the Point class’s fields and methods. Tocreate an instance of a subclass, one gives initial values forinherited fields first and then the fields declared in thesubclass. For example, one would write newColorPoint(3,5,red). As usual, subclasses can alsooverride inherited methods. To simplify the language,SDCore has only single inheritance. (However, multipleinheritance causes no problems with respect to the new ideaswe are advocating.)We use a standard syntax for message sends. For example, ifp1 is an instance of Point or a subclass, then theexpression p1.distanceFrom(ln2) invokes theinstance’s distanceFrom method with the argumentln2. Within the method body, the keyword self refers tothe receiver of the message, in this case p1.Dynamic