Multiple dispatch in practice

ABSTRACT

Multiple dispatch uses the run time types of more than one argument to a method call to determine which method body to run. While several languages over the last 20 years have provided multiple dispatch, most object-oriented languages still support only single dispatch forcing programmers to implement multiple dispatch manually when required. This paper presents an empirical study of the use of multiple dispatch in practice, considering six languages that support multiple dispatch, and also investigating the potential for multiple dispatch in Java programs. We hope that this study will help programmers understand the uses and abuses of multiple dispatch; virtual machine implementors optimise multiple dispatch; and language designers to evaluate the choice of providing multiple dispatch in new programming languages.

REFERENCES

• 1: Gareth Baxter , Marcus Frean , James Noble , Mark Rickerby , Hayden Smith , Matt Visser , Hayden Melton , Ewan Tempero, Understanding the shape of Java software, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 2: Daniel G. Bobrow. The LOOPS Manual. Xerox Parc, 1983.
• 3: Daniel G. Bobrow , Kenneth Kahn , Gregor Kiczales , Larry Masinter , Mark Stefik , Frank Zdybel, CommonLoops: merging Lisp and object-oriented programming, ACM SIGPLAN Notices, v.21 n.11, p.17-29, Nov. 1986
• 4: Daniel G. Bobrow , Linda G. DeMichiel , Richard P. Gabriel , Sonya E. Keene , Gregor Kiczales , David A. Moon, Common Lisp Object System specification, ACM SIGPLAN Notices, v.23 n.SI, p.1-142, September 1988 [doi>10.1145/885631.885632]
• 5: Daniel Bonniot, Bryn Keller, and Francis Barber. The Nice user's manual, 2008. URL http://nice.sourceforge.net/ manual.html.
• 6: John Boyland , Giuseppe Castagna, Parasitic methods: an implementation of multi-methods for Java, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.66-76, October 05-09, 1997, Atlanta, Georgia, United States
• 7: Kim Bruce , Luca Cardelli , Giuseppe Castagna , Gary T. Leavens , Benjamin Pierce, On binary methods, Theory and Practice of Object Systems, v.1 n.3, p.221-242, Fall 1995
• 8: Bruno Cabral and Paulo Marques. Exception Handling: A field study in Java and .NET. In ECOOP, volume 4609, pages 151--175. Springer-Verlag, 2007.
• 9: Patrice Chalin and Perry R. James. Non-null references by default in Java: Alleviating the nullity annotation burden. In ECOOP, volume 4609, pages 227--247. Springer-Verlag, 2007.
• 10: Craig Chambers. The Diesel Language, specification and rationale, 2006. URL http://www.cs.washington.edu/research/projects/cecil/www/Release/doc-diesel-lang/diesel-spec.pdf.
• 11: Craig Chambers, Object-Oriented Multi-Methods in Cecil, Proceedings of the European Conference on Object-Oriented Programming, p.33-56, June 29-July 03, 1992
• 12: Craig Chambers , Weimin Chen, Efficient multiple and predicated dispatching, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.238-255, November 01-05, 1999, Denver, Colorado, United States
• 13: Curtis Clifton , Gary T. Leavens , Craig Chambers , Todd Millstein, MultiJava: modular open classes and symmetric multiple dispatch for Java, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.130-145, October 2000, Minneapolis, Minnesota, United States
• 14: Curtis Clifton , Todd Millstein , Gary T. Leavens , Craig Chambers, MultiJava: Design rationale, compiler implementation, and applications, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.3, p.517-575, May 2006 [doi>10.1145/1133651.1133655]
• 15: Antonio Cunei , Jan Vitek, PolyD: a flexible dispatching framework, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 16: Edsger W. Dijkstra, Letters to the editor: go to statement considered harmful, Communications of the ACM, v.11 n.3, p.147-148, March 1968 [doi>10.1145/362929.362947]
• 17: Christopher Dutchyn , Paul Lu , Duane Szafron , Steven Bromling , Wade Holst, Multi-dispatch in the Java virtual machine: design and implementation, Proceedings of the 6th conference on USENIX Conference on Object-Oriented Technologies and Systems, p.6-6, January 29-February 02, 2001, San Antonio, Texas
• 18: Johan Fabry and Tom Mens. Language-independent detection of object-oriented design patterns. Computer Languages, Systems and Structures, 30(1--2):21--33, 2004.
• 19: Neal Feinberg , Sonya E. Keene , Robert O. Mathews , P. Tucker Withington, Dylan programming: an object-oriented and dynamic language, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1996
• 20: Brian Foote, Ralph E. Johnson, and James Noble. Efficient multimethods in a single dispatch language. In ECOOP, volume 3586, pages 337--361. Springer-Verlag, 2005.
• 21: Erich Gamma, Richard Helm, Ralph E. Johnson, and John Vlissides. Design Patterns. AW, 1994.
• 22: Joseph (Yossi) Gil , Itay Maman, Micro patterns in Java code, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 23: Jeffrey Hightower , Barry Brumitt , Gaetano Borriello, The Location Stack: A Layered Model for Location in Ubiquitous Computing, Proceedings of the Fourth IEEE Workshop on Mobile Computing Systems and Applications, p.22, June 20-21, 2002
• 24: David Hume. A Treatise of Human Nature. Printed for John Noon, London, 1739.
• 25: Daniel H. H. Ingalls, A simple technique for handling multiple polymorphism, Conference proceedings on Object-oriented programming systems, languages and applications, p.347-349, September 29-October 02, 1986, Portland, Oregon, United States
• 26: Warwick Irwin. Understanding and Improving Object-Oriented Software Through Static Software Analysis. PhD thesis, University of Canterbury, Christchurch, New Zealand, 2007.
• 27: James Kempf , Warren Harris , Roy D'Souza , Alan Snyder, Experience with CommonLoops, Conference proceedings on Object-oriented programming systems, languages and applications, p.214-226, October 04-08, 1987, Orlando, Florida, United States
• 28: Gregor Kiczales, John Lamping, Anurag Mendhekar, Chris Maeda, Cristina Lopes, Jean-Marc Loingtier, and John Irwin. Aspectoriented programming. In ECOOP, volume 1241, pages 220--242. Springer-Verlag, 1997.
• 29: Gregor Kiczales , Erik Hilsdale , Jim Hugunin , Mik Kersten , Jeffrey Palm , William G. Griswold, An Overview of AspectJ, Proceedings of the 15th European Conference on Object-Oriented Programming, p.327-353, June 18-22, 2001
• 30: Eric Kidd, Efficient Compression of Generic Function Dispatch Tables, Dartmouth College, Hanover, NH, 2001
• 31: David B. Lamkins and Richard P. Gabriel. Successful Lisp: How to Understand and Use Common Lisp. bookfix.com, 2005.
• 32: Gary T. Leavens , Todd D. Millstein, Multiple dispatch as dispatch on Tuples, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.374-387, October 18-22, 1998, Vancouver, British Columbia, Canada
• 33: Kin-Keung Ma , Jeffrey S. Foster, Inferring aliasing and encapsulation properties for java, Proceedings of the 22nd annual ACM SIGPLAN conference on Object oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
• 34: Scott McKay and William York. Common Lisp Interface Manager: CLIM II Specification, 2001.
• 35: Hayden Melton , Ewan Tempero, An empirical study of cycles among classes in Java, Empirical Software Engineering, v.12 n.4, p.389-415, August 2007 [doi>10.1007/s10664-006-9033-1]
• 36: Warwick B. Mugridge , John Hamer , John G. Hosking, Multi-Methods in a Statically-Typed Programming Language, Proceedings of the European Conference on Object-Oriented Programming, p.307-324, July 15-19, 1991
• 37: Jens Palsberg and J. Van Drunen. Visitor-oriented programming. In FOOL, Venice, Italy, 2004.
• 38: Alex Potanin , James Noble , Marcus Frean , Robert Biddle, Scale-free geometry in OO programs, Communications of the ACM, v.48 n.5, p.99-103, May 2005 [doi>10.1145/1060710.1060716]
• 39: Qualitas Research Group. Qualitas corpus release 20080603. http://www.cs.auckland.ac.nz/Üewan/corpus/ The University of Auckland, June 2008.
• 40: Lee Salzman and Jonathan Aldrich. Prototypes with multiple dispatch: An expressive and dynamic object model. In ECOOP, volume 3586, pages 312--336, Glasgow, Scotland, 2005. Springer-Verlag.
• 41: Christopher Unkel , Monica S. Lam, Automatic inference of stationary fields: a generalization of java's final fields, Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 07-12, 2008, San Francisco, California, USA
• 42: Philip Wadler. The expression problem. Discussion on the Java-Genericity mailing list (see 12 November 1998 post), November 1998.
• 43: Matthias Zenger and Martin Odersky. Independently extensible solutions to the expression problem. In FOOL, San Diego, USA, October 2005. Also available as Technical Report IC/2004/109, EPFL, Switzerland, December 2004.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.0 General

General Terms:
Design, Experimentation, Languages, Measurement

Keywords:
double dispatch, empirical software engineering, instanceof, multimethods, multiple dispatch