MultiJava Modular Open Classes and Symmetric Multiple Dispatch for Java Curtis Clifton Gary T Leavens Craig Chambers and Todd Millstein TR 00 06a April 2000 Revised July 2000 An earlier version of this technical report was titled MultiJava Modular Symmetric Multiple Dispatch and Extensible Classes for Java Keywords Open classes open objects extensible classes extensible external methods external methods multimethods generic functions object oriented programming languages single dispatch multiple dispatch encapsulation modularity static typechecking subtyping inheritance Java language MultiJava language separate compilation 1999 CR Categories D 1 5 Programming Techniques Object oriented programming D 3 2 Programming Languages Language Classifications object oriented languages D 3 3 Programming Languages Language Constructs and Features abstract data types classes and objects control structures inheritance modules packages patterns procedures functions and subroutines D 3 4 Programming Languages Processors compilers D 3 m Programming Languages Miscellaneous open classes multimethods generic functions To appear in OOPSLA 2000 Minneapolis Minnesota October 2000 Copyright ACM 2000 Permission to make digital or hard copies of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page To copy otherwise or republish to post on servers or to redistribute to lists requires prior specific permission and or a fee Department of Computer Science 226 Atanasoff Hall Iowa State University Ames Iowa 50011 1040 USA MultiJava Modular Open Classes and Symmetric Multiple Dispatch for Java Curtis Clifton and Gary T Leavens Craig Chambers and Todd Millstein Department of Computer Science Iowa State University 226 Atanasoff Hall Ames IA 50011 1040 USA 1 515 294 1580 Department of Computer Science and Engineering University of Washington Box 352350 Seattle WA 98195 2350 USA 1 206 685 2094 cclifton leavens cs iastate edu chambers todd cs washington edu ABSTRACT since the existing Visitor infrastructure must be edited to account for the new subclasses Open classes can be used to organize cross cutting operations separately from the classes to which they belong a key feature of aspect oriented programming Kiczales et al 97 With open classes object oriented languages can support the addition of both new subclasses and new methods to existing classes relieving the tension that has been observed by others Cook 90 Odersky Wadler 97 Findler Flatt 98 between these forms of extension We present MultiJava a backward compatible extension to Java supporting open classes and symmetric multiple dispatch Open classes allow one to add to the set of methods that an existing class supports without creating distinct subclasses or editing existing code Unlike the Visitor design pattern open classes do not require advance planning and open classes preserve the ability to add new subclasses modularly and safely Multiple dispatch offers several well known advantages over the single dispatching of conventional object oriented languages including a simple solution to some kinds of binary method problems MultiJava s multiple dispatch retains Java s existing class based encapsulation properties We adapt previous theoretical work to allow compilation units to be statically typechecked modularly and safely ruling out any link time or run time type errors We also present a novel compilation scheme that operates modularly and incurs performance overhead only where open classes or multiple dispatching are actually used Multiple dispatch found in Common Lisp Steele 90 Paepcke 93 Dylan Shalit 97 Feinberg et al 97 and Cecil Chambers 92 Chambers 95 allows the method invoked by a message send to depend on the run time classes of any subset of the argument objects A method that takes advantage of the multiple dispatch mechanism is called a multimethod In contrast single dispatch found in C Smalltalk and Java selects the method invoked by a message send based on the run time class of only the distinguished receiver argument In C and Java the static types of the arguments influence method selection via static overload resolution the dynamic types of the arguments are not involved in method dispatch Multimethods provide a more uniform and expressive approach to overload resolution For example they support safe covariant overriding in the face of subtype polymorphism providing a natural solution to the binary method problem Bruce et al 95 1 INTRODUCTION In this paper we introduce MultiJava a backward compatible extension to Java Gosling et al 00 Arnold Gosling 98 that supports open classes and symmetric multiple dispatch An open class is one to which new methods can be added without editing the class directly Chambers 98 Millstein Chambers 99 An open class allows clients to customize their interface to the needs of the client s application Unlike customization through subclasses inplace extension of classes does not require existing code referencing the class to be changed to use the new subclass instead The Visitor design pattern Gamma et al 95 pp 331 344 also is intended to allow new client specific operations to be added to an existing family of classes but unlike open classes the Visitor pattern requires class implementors to plan ahead and build infrastructure in the class with which clients can indirectly add behavior to the class Moreover unlike open classes use of the Visitor pattern makes it difficult to add new subclasses modularly Multiple dispatch is symmetric if the rules for method lookup treat all dispatched arguments identically Asymmetric multiple dispatch typically uses lexicographic ordering where earlier arguments are more important a variant of this approach selects methods based partly on the textual ordering of their declarations We believe that symmetric multiple dispatch is more intuitive and less error prone reporting possible ambiguities rather than silently resolving them in potentially unexpected ways Symmetric multiple dispatch is used in Cecil Dylan Kea Mugridge et al 91 the calculus Castagna et al 92 Castagna 97 ML Bourdoncle Merz 97 and Tuple Leavens Millstein 98 A major obstacle to adding symmetric multimethods to an existing statically typed programming language has been their modularity problem Cook 90 independently developed modules which typecheck in