MultiJava: Design rationale, compiler implementation, and applications

ABSTRACT

MultiJava is a conservative extension of the Java programming language that adds symmetric multiple dispatch and open classes. Among other benefits, multiple dispatch provides a solution to the binary method problem. Open classes provide a solution to the extensibility problem of object-oriented programming languages, allowing the modular addition of both new types and new operations to an existing type hierarchy. This article illustrates and motivates the design of MultiJava and describes its modular static typechecking and modular compilation strategies. Although MultiJava extends Java, the key ideas of the language design are applicable to other object-oriented languages, such as C# and C++, and even, with some modifications, to functional languages such as ML.This article also discusses the variety of application domains in which MultiJava has been successfully used by others, including pervasive computing, graphical user interfaces, and compilers. MultiJava allows users to express desired programming idioms in a way that is declarative and supports static typechecking, in contrast to the tedious and type-unsafe workarounds required in Java. MultiJava also provides opportunities for new kinds of extensibility that are not easily available in Java.

REFERENCES

• 1: Rakesh Agrawal , Linda G. Demichiel , Bruce G. Lindsay, Static type checking of multi-methods, Conference proceedings on Object-oriented programming systems, languages, and applications, p.113-128, October 06-11, 1991, Phoenix, Arizona, United States
• 2: Davide Ancona , Giovanni Lagorio , Elena Zucca, A Formal Framework for Java Separate Compilation, Proceedings of the 16th European Conference on Object-Oriented Programming, p.609-636, June 10-14, 2002
• 3: Ken Arnold , James Gosling , David Holmes, The Java Programming Language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 4: Larry Arnstein , Chia-Yang Hung , Robert Franza , Qing Hong Zhou , Gaetano Borriello , Sunny Consolvo , Jing Su, Labscape: A Smart Environment for the Cell Biology Laboratory, IEEE Pervasive Computing, v.1 n.3, p.13-21, July 2002 [doi>10.1109/MPRV.2002.1037717]
• 5: AspectJ Team. 2004. The AspectJ programming guide. Available online from http://eclipse.org/aspectj.
• 6: Baumgartner, G., Jansche, M., and Läufer, K. 2002. Half & Half: Multiple dispatch and retroactive abstraction for Java. Tech. rep. OSU-CISRC-5/01-TR08. Department of Computer Science, The Ohio State University. Columbus, OH.
• 7: Bonniot, D. 2003. Using kinds to type partially-polymorphic methods. In Electronic Notes in Theoretical Computer Science, G. Barthe and P. Thiemann, Eds. Vol. 75. Elsevier, New York, NY.
• 8: Bonniot, D. and Keller, B. 2003. The Nice user's manual. Available online at http://nice.sourceforge.net.
• 9: François Bourdoncle , Stephan Merz, Type checking higher-order polymorphic multi-methods, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.302-315, January 15-17, 1997, Paris, France [doi>10.1145/263699.263743]
• 10: 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
• 11: Gilad Bracha , William Cook, Mixin-based inheritance, Proceedings of the European conference on object-oriented programming on Object-oriented programming systems, languages, and applications, p.303-311, September 1990, Ottawa, Canada
• 12: Bridges, S., Figueroa, M., Hsu, D., and Diorio, C. 2003. Field-programmable learning arrays. In Advances in Neural Information Processing Systems 15. MIT Press, Cambridge, MA.
• 13: 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
• 14: Luca Cardelli, A semantics of multiple inheritance, Information and Computation, v.76 n.2-3, p.138-164, February/March 1988 [doi>10.1016/0890-5401(88)90007-7]
• 15: Giuseppe Castagna, Covariance and contravariance: conflict without a cause, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.3, p.431-447, May 1995 [doi>10.1145/203095.203096]
• 16: Giuseppe Castagna, Object-oriented programming: a unified foundation, Birkhauser Boston Inc., Cambridge, MA, 1997
• 17: Giuseppe Castagna , Giorgio Ghelli , Giuseppe Longo, A calculus for overloaded functions with subtyping, Information and Computation, v.117 n.1, p.115-135, Feb. 15, 1995 [doi>10.1006/inco.1995.1033]
• 18: 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
• 19: Chambers, C. 1997. The Cecil language specification and rationale: Version 2.1. Available online from http://www.cs.washington.edu/research/projects/cecil/www/pubs/cecil-spec.html.
• 20: Chambers, C. 1998. Towards Diesel, a next-generation OO language after Cecil. Invited talk. In Proceedings of the Fifth Workshop of Foundations of Object-Oriented Languages (San Diego, CA).
• 21: 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
• 22: Craig Chambers , Gary T. Leavens, Typechecking and modules for multimethods, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.6, p.805-843, Nov. 1995 [doi>10.1145/218570.218571]
• 23: Clifton, C. 2001. MultiJava: Design, implementation, and evaluation of a Java-compatible language supporting modular open classes and symmetric multiple dispatch. Tech. Rep. 01-10. Department of Computer Science, Iowa State University, Ames, IA. The author's masters thesis.
• 24: 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
• 25: William R. Cook, Object-Oriented Programming Versus Abstract Data Types, Proceedings of the REX School/Workshop on Foundations of Object-Oriented Languages, p.151-178, May 28-June 01, 1990
• 26: Sophia Drossopoulou , Susan Eisenbach , David Wragg, A Fragment Calculus Towards a Model of Separate Compilation, Linking and Binary Compatibility, Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science, p.147, July 02-05, 1999
• 27: Dominic Duggan , Constantinos Sourelis, Mixin modules, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.262-273, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 28: Dutchyn, C., Szafron, D., Bromling, S., and Holst, W. 2001. Multi-dispatch in the Java virtual machine: Design and implementation. In Sixth Conference on Object-Oriented Technologies and Systems (COOTS). USENIX, Berkeley, CA.
• 29: Michael Ernst , Craig Kaplan , Craig Chambers, Predicate Dispatching: A Unified Theory of Dispatch, Proceedings of the 12th European Conference on Object-Oriented Programming, p.186-211, July 20-24, 1998
• 30: Manuel Fähndrich , K. Rustan M. Leino, Declaring and checking non-null types in an object-oriented language, ACM SIGPLAN Notices, v.38 n.11, November 2003
• 31: Feinberg, N., Keene, S. E., Mathews, R. O., and Withington., P. T. 1997. The Dylan Programming Book. Addison-Wesley Longman, Reading, MA.
• 32: Robert Bruce Findler , Matthew Flatt, Modular object-oriented programming with units and mixins, Proceedings of the third ACM SIGPLAN international conference on Functional programming, p.94-104, September 26-29, 1998, Baltimore, Maryland, United States
• 33: Matthew Flatt , Matthias Felleisen, Units: cool modules for HOT languages, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.236-248, June 17-19, 1998, Montreal, Quebec, Canada
• 34: Matthew Flatt , Shriram Krishnamurthi , Matthias Felleisen, Classes and mixins, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.171-183, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268961]
• 35: Forax, R., Duris, E., and Roussel, G. 2000. Java multi-method framework. In Proceedings of the International Conference on Technology of Object-Oriented Languages and Systems (TOOLS '00), Sydney, Australia. IEEE Computer Society Press, Los Alamitos, CA.
• 36: Etienne M. Gagnon , Laurie J. Hendren, SableCC, an Object-Oriented Compiler Framework, Proceedings of the Technology of Object-Oriented Languages and Systems, p.140, August 03-07, 1998
• 37: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 38: Garrigue, J. 2000. Code reuse through polymorphic variants. In Proceedings of the Workshop on Foundations of Software Engineering, Sassaguri, Japan. Available online from http://wwwfun.kurims.kyoto-u.ac.jp/~garrigue/papers/fose2000.html.
• 39: Adele Goldberg, SMALLTALK-80: the interactive programming environment, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 40: James Gosling , Bill Joy , Guy Steele , Gilad Bracha, Java Language Specification, Second Edition: The Java Series, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 41: Grimm, R., Davis, J., Lemar, E., MacBeth, A., Swanson, S., Gribble, S., Anderson, T., Bershad, B., Borriello, G., and Wetherall, D. 2001. Programming for pervasive computing environments. Tech. Rep. UW-CSE-01-06-01. Department of Computer Science and Engineering, University of Washington, Seattle, WA.
• 42: Grothoff, C. 2003. Walkabout revisited: The Runabout. In ECOOP 2003---Object-Oriented Programming, 17th European Conference, Darmstadt, Germany, Proceedings, L. Cardelli, Ed. Lecture Notes in Computer Science, vol. 2743. Springer-Verlag, New York, NY, 103--125.
• 43: William Harrison , Harold Ossher, Subject-oriented programming: a critique of pure objects, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.411-428, September 26-October 01, 1993, Washington, D.C., United States
• 44: 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
• 45: 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
• 46: Ralph Keller , Urs Hölzle, Binary Component Adaptation, Proceedings of the 12th European Conference on Object-Oriented Programming, p.307-329, July 20-24, 1998
• 47: 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
• 48: Kiczales, G., Lamping, J., Menhdhekar, A., Maeda, C., Lopes, C., Loingtier, J.-M., and Irwin, J. 1997. Aspect-oriented programming. In ECOOP '97---Object-Oriented Programming 11th European Conference, Jyväskylä, Finland, Proceedings, M. Akşit and S. Matsuoka, Eds. Lecture Notes in Computer Science, vol. 1241. Springer-Verlag, New York, NY, 220--242.
• 49: Kopi 2004. Kopi project home page. Go online to http://www.dms.at/kopi.
• 50: Shriram Krishnamurthi , Matthias Felleisen , Daniel P. Friedman, Synthesizing Object-Oriented and Functional Design to Promote Re-Use, Proceedings of the 12th European Conference on Object-Oriented Programming, p.91-113, July 20-24, 1998
• 51: 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
• 52: Keunwoo Lee , Anthony LaMarca , Craig Chambers, HydroJ: object-oriented pattern matching for evolvable distributed systems, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 53: Sheng Liang , Gilad Bracha, Dynamic class loading in the Java virtual machine, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.36-44, October 18-22, 1998, Vancouver, British Columbia, Canada
• 54: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 55: Vassily Litvinov, Contraint-based polymorphism in Cecil: towards a practical and static type system, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.388-411, October 18-22, 1998, Vancouver, British Columbia, Canada
• 56: Peter Martin, Java, the good, the bad and the ugly, ACM SIGPLAN Notices, v.33 n.4, p.34-39, April 1998 [doi>10.1145/278283.278288]
• 57: Sean McDirmid , Matthew Flatt , Wilson C. Hsieh, Jiazzi: new-age components for old-fasioned Java, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.211-222, October 14-18, 2001, Tampa Bay, FL, USA
• 58: Todd David Millstein , Craig Chambers, Reconciling software extensibility with modular program reasoning, 2003
• 59: Todd Millstein, Practical predicate dispatch, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 60: Todd Millstein , Colin Bleckner , Craig Chambers, Modular typechecking for hierarchically extensible datatypes and functions, Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, p.110-122, October 04-06, 2002, Pittsburgh, PA, USA
• 61: Millstein, T. and Chambers, C. 2002. Modular statically typed multimethods. Inform. Computat. 175, 1 (May), 76--118.
• 62: Todd Millstein , Mark Reay , Craig Chambers, Relaxed MultiJava: balancing extensibility and modular typechecking, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 63: 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
• 64: Martin E. Nordberg, III, Default and extrinsic visitor, Pattern languages of program design 3, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 65: Nystrom, N., Clarkson, M. R., and Myers, A. C. 2003. Polyglot: An extensible compiler framework for java. In Compiler Construction: 12'th International Conference, CC 2003. Vol. 2622. Springer-Verlag, New York, NY, 138--152.
• 66: Odersky, M., Cremet, V., Röckl, C., and Zenger, M. 2003. A nominal theory of objects with dependent types. In ECOOP 2003---Object-Oriented Programming, 17th European Conference, Darmstadt, Germany, Proceedings, L. Cardelli, Ed. Lecture Notes in Computer Science, vol. 2743. Springer-Verlag, New York, NY, 201--224.
• 67: Martin Odersky , Philip Wadler, Pizza into Java: translating theory into practice, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.146-159, January 15-17, 1997, Paris, France [doi>10.1145/263699.263715]
• 68: Harold Ossher , Peri Tarr, Using multidimensional separation of concerns to (re)shape evolving software, Communications of the ACM, v.44 n.10, p.43-50, Oct. 2001 [doi>10.1145/383845.383856]
• 69: Andreas Paepcke, Object-oriented programming: the CLOS perspective, MIT Press, Cambridge, MA, 1993
• 70: Jens Palsberg , C. Barry Jay, The Essence of the Visitor Pattern, Proceedings of the 22nd International Computer Software and Applications Conference, p.9-15, August 19-21, 1998
• 71: D. L. Parnas, On the criteria to be used in decomposing systems into modules, Communications of the ACM, v.15 n.12, p.1053-1058, Dec. 1972 [doi>10.1145/361598.361623]
• 72: David Lorge Parnas, Software Engineering or Methods for the Multi - Person Construction of Multi - Version Programs, Programming Methodology, 4th Informatik Symposium, p.225-235, September 25-27, 1974
• 73: Matthai Philipose , Kenneth P. Fishkin , Mike Perkowitz , Donald J. Patterson , Dieter Fox , Henry Kautz , Dirk Hahnel, Inferring Activities from Interactions with Objects, IEEE Pervasive Computing, v.3 n.4, p.50-57, October 2004 [doi>10.1109/MPRV.2004.7]
• 74: Rain 2004. Rain home page. Go online to http://seattleweb.intel_research.net/projects/rain.
• 75: Reynolds, J. C. 1975. User-defined types and procedural data structures as complementary approaches to type abstraction. In New Directions in Algorithmic Languages, S. A. Schuman, Ed. INRIA, Rocquencourt, France, 157--168.
• 76: John C. Reynolds, Using category theory to design implicit conversions and generic operators, Semantics-Directed Compiler Generation, Proceedings of a Workshop, p.211-258, January 14-18, 1980
• 77: Andrew Shalit, The Dylan reference manual: the definitive guide to the new object-oriented dynamic language, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1996
• 78: Guy L. Steele, Jr., Common LISP: the language (2nd ed.), Digital Press, Newton, MA, 1990
• 79: Bjarne Stroustrup, The C++ Programming Language, Third Edition, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 80: Peri Tarr , Harold Ossher , William Harrison , Stanley M. Sutton, Jr., N degrees of separation: multi-dimensional separation of concerns, Proceedings of the 21st international conference on Software engineering, p.107-119, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302457]
• 81: Torgersen, M. 2004. The expression problem revisited: Four new solutions using generics. In ECOOP 2004---Object-Oriented Programming, 18th European Conference, Oslo, Norway, Proceedings, M. Odersky, Ed. Lecture Notes in Computer Science, vol. 3086. Springer-Verlag, New York, NY, 123--143.
• 82: Andrew Troelsen, C# and the .Net Platform, APress L. P., 2003
• 83: Vlissides, J. 1999. Visitor in frameworks. C++ Rep. 11, 10 (Nov./Dec.), 40--46.
• 84: Matthias Zenger , Martin Odersky, Extensible algebraic datatypes with defaults, Proceedings of the sixth ACM SIGPLAN international conference on Functional programming, September 03-05, 2001, Florence, Italy
• 85: Zenger, M. and Odersky, M. 2005. Independently extensible solutions to the expression problem. In Proceedings of the 12th International Workshop on Foundations of Object-Oriented Languages (FOOL 12, Long Beach, CA). ACM Press, New York, NY.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.5 Object-oriented Programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages
      D.3.3 Language Constructs and Features
          Subjects: Abstract data types; Patterns; Classes and objects; Inheritance; Modules, packages; Control structures; Procedures, functions, and subroutines
      D.3.4 Processors
          Subjects: Compilers
      D.3.m Miscellaneous

General Terms:
Design, Languages

Keywords:
Java language, MultiJava language, Open classes, augmenting method problem, binary method problem, encapsulation, expression problem, extensible classes, extensible external methods, external methods, generic functions, inheritance, method families, modularity, multimethods, multiple dispatch, object-oriented programming languages, open objects, separate compilation, single dispatch, static typechecking, subtyping