Relaxed MultiJava: balancing extensibility and modular typechecking

ABSTRACT

We present the rationale, design, and implementation of Relaxed MultiJava (RMJ), a backward-compatible extension of Java that allows programmers to add new methods to existing classes and to write multimethods. Previous languages supporting these forms of extensibility either restrict their usage to a limited set of programming idioms that can be modularly typechecked (and modularly compiled) or simply forego modular typechecking altogether. In contrast, RMJ supports the new language features in a virtually unrestricted form while still providing mostly-modular static typechecking and fully-modular compilation. In some cases, the RMJ compiler will warn that the potential for a type error exists, but it will still complete compilation. In those cases, a custom class loader transparently performs load-time checking to verify that the potential error is never realized. RMJ's compiler and custom loader cooperate to keep load-time checking costs low. We report on qualitative and quantitative experience with our implementation of RMJ.

REFERENCES

• 1: Proceedings of the 1992 European Conference on Object-Oriented Programming, LNCS 615, Utrecht, The Netherlands, June 1992. Springer-Verlag.
• 2: Jonathan Aldrich , Craig Chambers , David Notkin, Architectural Reasoning in ArchJava, Proceedings of the 16th European Conference on Object-Oriented Programming, p.334-367, June 10-14, 2002
• 3: Egil P. Andersen , Trygve Reenskaug, System Design by Composing Structures of Interacting Objects, Proceedings of the European Conference on Object-Oriented Programming, p.133-152, June 29-July 03, 1992
• 4: Ken Arnold , James Gosling , David Holmes, The Java Programming Language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 5: David F. Bacon , Peter F. Sweeney, Fast static analysis of C++ virtual function calls, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.324-341, October 06-10, 1996, San Jose, California, United States
• 6: G. Baumgartner, M. Jansche, and K. Laufer. Half & half: Multiple dispatch and retroactive abstraction for java. Technical Report OSU-CISRC-5/01-TR08, Department of Computer and Information Science, The Ohio State University, Mar. 2002.
• 7: Daniel G. Bobrow , Kenneth Kahn , Gregor Kiczales , Larry Masinter , Mark Stefik , Frank Zdybel, CommonLoops: merging Lisp and object-oriented programming, Conference proceedings on Object-oriented programming systems, languages and applications, p.17-29, September 29-October 02, 1986, Portland, Oregon, United States
• 8: B. Bokowski and A. Spiegel. Barat -- a front-end for java. Technical Report Technical Report B-98-09, Freie Universitat Berlin, FB Mathematik und Informatik, Dec. 1998.
• 9: 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
• 10: G. Bracha. Personal communication. Jan. 2003.
• 11: Robert Cartwright , Mike Fagan, Soft typing, ACM SIGPLAN Notices, v.26 n.6, p.278-292, June 1991
• 12: 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]
• 13: 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
• 14: C. Chambers. The Cecil language: Specification and rationale. Technical Report UW-CSE-93-03-05, Department of Computer Science and Engineering. University of Washington, Mar. 1993. Revised, March 1997.
• 15: C. Chambers. Towards Diesel, a next-generation OO language after Cecil. Invited talk, the Fifth Workshop of Foundations of Object-Oriented Langauges, San Diego, California, Jan. 1998.
• 16: 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
• 17: C. Clifton. MultiJava: Design, implementation, and evaluation of a Java-compatible language supporting modular open classes and symmetric multiple dispatch. Technical Report 01-10, Department of Computer Science, Iowa State University, Ames, Iowa, 50011, Nov. 2001. Available from multijava.sourceforge.net.
• 18: 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
• 19: Jeffrey Dean , Greg DeFouw , David Grove , Vassily Litvinov , Craig Chambers, Vortex: an optimizing compiler for object-oriented languages, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.83-100, October 06-10, 1996, San Jose, California, United States
• 20: Proceedings of the 1998 European Conference on Object-Oriented Programming, LNCS 1445, Brussels, Belgium, July 1998. Springer-Verlag.
• 21: E. Gamma, R. Helm, R. E. Johnson, and J. Vlissides. Design Patterns. Addison-Wesley, Reading, MA, 1995.
• 22: 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
• 23: C. Grothoff. Walkabout revisited: The runabout. In Proceedings of the 2003 European Conference on Object-Oriented Programming, LNCS 2743, Darmstadt, Germany, July 2003. Springer-Verlag.
• 24: 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
• 25: 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
• 26: 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
• 27: John Lamping, The Role of the Base in Aspect Oriented Programming, Proceedings of the Workshop on Object-Oriented Technology, p.289-291, June 14-18, 1999
• 28: 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
• 29: 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
• 30: 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
• 31: Vassily Litvinov, Constraint-based polymorphism in Cecil: towards a practical and static type system, Addendum to the 1998 proceedings of the conference on Object-oriented programming, systems, languages, and applications (Addendum), January 1998, Vancouver, British Columbia, Canada [doi>10.1145/346852.346948]
• 32: Robert C. Martin, Acyclic visitor, Pattern languages of program design 3, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 33: 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
• 34: Todd D. Millstein , Craig Chambers, Modular Statically Typed Multimethods, Proceedings of the 13th European Conference on Object-Oriented Programming, p.279-303, June 14-18, 1999
• 35: David A. Moon, Object-oriented programming with flavors, Conference proceedings on Object-oriented programming systems, languages and applications, p.1-8, September 29-October 02, 1986, Portland, Oregon, United States
• 36: MultiJava home page. http://multijava.sourceforge.net.
• 37: Martin E. Nordberg, III, Default and extrinsic visitor, Pattern languages of program design 3, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 38: Proceedings of the 1986 ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, Portland, OR, Nov. 1986.
• 39: Proceedings of the 1996 ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, San Jose, CA, Oct. 1996.
• 40: Proceedings of the 1998 ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, Vancouver, Canada, Oct. 1998.
• 41: Harold Ossher , Peri Tarr, Hyper/J: multi-dimensional separation of concerns for Java, Proceedings of the 22nd international conference on Software engineering, p.734-737, June 04-11, 2000, Limerick, Ireland [doi>10.1145/337180.337618]
• 42: Andreas Paepcke, Object-oriented programming: the CLOS perspective, MIT Press, Cambridge, MA, 1993
• 43: 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
• 44: A. Shalit. The Dylan Reference Manual. Addison-Wesley, Reading, MA, 1996.
• 45: Yannis Smaragdakis , Don S. Batory, Implementing Layered Designs with Mixin Layers, Proceedings of the 12th European Conference on Object-Oriented Programming, p.550-570, July 20-24, 1998
• 46: Guy L. Steele, Jr., Common LISP: the language (2nd ed.), Digital Press, Newton, MA, 1990
• 47: Michael VanHilst , David Notkin, Using C++ Templates to Implement Role-Based Designs, Proceedings of the Second JSSST International Symposium on Object Technologies for Advanced Software, p.22-37, March 11-15, 1996
• 48: J. Vlissides. Visitor in frameworks. C++ Report, 11(10):40-- 46, November/December 1999.
• 49: 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

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Classes and objects

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Design, Languages

Keywords:
class loader, external methods, modular typechecking, multimethods, relaxed MultiJava