Maya: multiple-dispatch syntax extension in Java

ABSTRACT

We have designed and implemented Maya, a version of Java that allows programmers to extend and reinterpret its syntax. Maya generalizes macro systems by treating grammar productions as generic functions, and semantic actions on productions as multimethods on the corresponding generic functions. Programmers can write new generic functions (i.e., grammar productions) and new multimethods (i.e., semantic actions), through which they can extend the grammar of the language and change the semantics of its syntactic constructs, respectively. Maya's multimethods are compile-time metaprograms that transform abstract syntax: they execute at program compile-time, because they are semantic actions executed by the parser. Maya's multimethods can be dispatched on the syntactic structure of the input, as well as the static, source-level types of expressions in the input. In this paper we describe what Maya can do and how it works. We describe how its novel parsing techniques work and how Maya can statically detect certain kinds of errors, such as code that generates references to free variables. Finally, to demonstrate Maya's expressiveness, we describe how Maya can be used to implement the MultiJava language, which was described by Clifton et al. at OOPSLA 2000.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Jonthan Bachrach , Keith Playford, The Java syntactic extender (JSE), Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.31-42, October 14-18, 2001, Tampa Bay, FL, USA
• 3: J. Baker. Macros that play: Migrating from Java to Maya. Master's thesis, University of Utah, Dec. 2001. http://www.cs.utah.edu/~jbaker/maya/thesis.html
• 4: Jason Baker , Wilson Hsieh, Runtime aspect weaving through metaprogramming, Proceedings of the 1st international conference on Aspect-oriented software development, April 22-26, 2002, Enschede, The Netherlands [doi>10.1145/508386.508396]
• 5: D. Batory , B. Lofaso , Y. Smaragdakis, JTS: Tools for Implementing Domain-Specific Languages, Proceedings of the 5th International Conference on Software Reuse, p.143, June 02-05, 1998
• 6: Claus Brabrand , Michael I. Schwartzbach, Growing languages with metamorphic syntax macros, Proceedings of the 2002 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, p.31-40, January 14-15, 2002, Portland, Oregon
• 7: Avi Bryant , Andrew Catton , Kris De Volder , Gail C. Murphy, Explicit programming, Proceedings of the 1st international conference on Aspect-oriented software development, April 22-26, 2002, Enschede, The Netherlands [doi>10.1145/508386.508389]
• 8: L. Cardelli, F. Matthes, and M. Abadi. Extensible syntax with lexical scoping. Technical Report 121, DEC SRC, Feb. 1994
• 9: C. Chambers. The Cecil Language Specification and Rationale: Version 2.0, 1995
• 10: Shigeru Chiba, A metaobject protocol for C++, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.285-299, October 15-19, 1995, Austin, Texas, United States
• 11: C. Clifton. The MultiJava project. http://www.cs.iastate.edu/~cclifton/multijava/index.shtml
• 12: 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
• 13: William Clinger , Jonathan Rees, Macros that work, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.155-162, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99607]
• 14: D. de Rauglaudre. Camlp4 reference manual. http://caml.inria.fr/camlp4/manual/, Jan. 2002
• 15: W. Divoky, C. Forgione, T. Graf, C. Laborde, A. Lemonnier, and E. Wais. The Kopi project. http://www.dms.at/kopi/index.html
• 16: R. Ducournau , M. Habib , M. Huchard , M. L. Mugnier, Monotonic conflict resolution mechanisms for inheritance, conference proceedings on Object-oriented programming systems, languages, and applications, p.16-24, October 18-22, 1992, Vancouver, British Columbia, Canada
• 17: R. Kent Dybvig , Robert Hieb , Carl Bruggeman, Syntactic abstraction in Scheme, Lisp and Symbolic Computation, v.5 n.4, p.295-326, Dec. 1992 [doi>10.1007/BF01806308]
• 18: 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
• 19: 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
• 20: Steven E. Ganz , Amr Sabry , Walid Taha, Macros as multi-stage computations: type-safe, generative, binding macros in MacroML, Proceedings of the sixth ACM SIGPLAN international conference on Functional programming, September 03-05, 2001, Florence, Italy
• 21: R. Kelsey, W. Clinger, and J. Rees (Eds.). The revised report on the algorithmic language Scheme. ACM SIGPLAN Notices, 33(9), Sept. 1998
• 22: Shriram Krishnamurthi , Matthias Felleisen, Linguistic reuse, 2001
• 23: David A. Ladd , J. Christopher Ramming, A": A Language for Implementing Language Processors, IEEE Transactions on Software Engineering, v.21 n.11, p.894-901, November 1995 [doi>10.1109/32.473218]
• 24: W. Maddox. Semantically-sensitive macroprocessing. Master's thesis, University of California, Berkeley, 1989
• 25: Microsoft. C# language specification. http://msdn.microsoft.com/library/dotnet/csspec/vclrfcsharpspec_Start.htm
• 26: Massimiliano Poletto , Wilson C. Hsieh , Dawson R. Engler , M. Frans Kaashoek, C and tcc: a language and compiler for dynamic code generation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.2, p.324-369, March 1999 [doi>10.1145/316686.316697]
• 27: A. Shalit. Dylan Reference Manual. Addison-Wesley, 1996
• 28: Guy L. Steele, Jr., Common LISP: the language (2nd ed.), Digital Press, Newton, MA, 1990
• 29: M. Tatsubori, S. Chiba, M. Killijian, and K. Itano. OpenJava: A class-based macro system for Java. In Proceedings of the OOPSLA '00 Reflection and Software Engineering Workshop, Minneapolis, MN, Oct. 2000
• 30: Daniel Weise , Roger Crew, Programmable syntax macros, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.156-165, June 21-25, 1993, Albuquerque, New Mexico, United States
• 31: Xerox. The AspectJ programming guide. http://www.aspectj.org/doc/dist/progguide/

INDEX TERMS

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

General Terms:
Languages

Keywords:
Java, generative programming, macros, metaprogramming