OMeta: an object-oriented language for pattern matching

ABSTRACT

This paper introduces OMeta, a new object-oriented language for pattern matching. OMeta is based on a variant of Parsing Expression Grammars (PEGs) [5]---a recognition-based foundation for describing syntax---which we have extended to handle arbitrary kinds of data. We show that OMeta's general-purpose pattern matching provides a natural and convenient way for programmers to implement tokenizers, parsers, visitors, and tree transformers, all of which can be extended in interesting ways using familiar object-oriented mechanisms. This makes OMeta particularly well-suited as a medium for experimenting with new designs for programming languages and extensions to existing languages.

REFERENCES

• 1: H. Abelson , R. K. Dybvig , C. T. Haynes , G. J. Rozas , N. I. Adams, IV , D. P. Friedman , E. Kohlbecker , G. L. Steele, Jr. , D. H. Bartley , R. Halstead , D. Oxley , G. J. Sussman , G. Brooks , C. Hanson , K. M. Pitman , M. Wand , William Clinger , Jonathan Rees, Revised report on the algorithmic language scheme, ACM SIGPLAN Lisp Pointers, v.IV n.3, p.1-55, July, 1991 [doi>10.1145/382130.382133]
• 2: ECMA. ECMAScript language specification.
• 3: B. Ford. Pappy: a parser generator for Haskell. http://pdos.csail.mit.edu/<baford/packrat/thesis/.
• 4: Bryan Ford, Packrat parsing:: simple, powerful, lazy, linear time, functional pearl, Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, p.36-47, October 04-06, 2002, Pittsburgh, PA, USA
• 5: Bryan Ford, Parsing expression grammars: a recognition-based syntactic foundation, Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.111-122, January 14-16, 2004, Venice, Italy
• 6: E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns. Addison-Wesley Professional, January 1995.
• 7: Robert Grimm, Better extensibility through modular syntax, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 8: Graham Hutton , Erik Meijer, Monadic parsing in Haskell, Journal of Functional Programming, v.8 n.4, p.437-444, July 1998 [doi>10.1017/S0956796898003050]
• 9: D. Leijen and E. Meijer. Parsec: Direct style monadic parser combinators for the real world. Technical Report Technical Report UU-CS-2001-35, Universiteit Utrecht, 2001.
• 10: Terence J. Parr , Russell W. Quong, Adding Semantic and Syntactic Predicates To LL(k): pred-LL(k), Proceedings of the 5th International Conference on Compiler Construction, p.263-277, April 07-09, 1994
• 11: I. Piumarta. Open, extensible programming systems. Keynote talk, Dynamic Languages Symposium, 2006.
• 12: Guido Rossum, Python reference manual, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1995
• 13: D. J. Salomon , G. V. Cormack, Scannerless NSLR(1) parsing of programming languages, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.170-178, June 19-23, 1989, Portland, Oregon, United States
• 14: D. V. Schorre, META II a syntax-oriented compiler writing language, Proceedings of the 1964 19th ACM national conference, p.41.301-41.3011, January 1964 [doi>10.1145/800257.808896]
• 15: Guy L. Steele, Jr., An overview of COMMON LISP, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.98-107, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802140]
• 16: L. G. Tesler, H. J. Enea, and D. C. Smith. The LISP70 pattern matching system. In Proc. of the 3rd IJCAI, pages 671--676, Stanford, MA, 1973.

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.3 Language Constructs and Features

General Terms:
Design, Languages

Keywords:
metacircular implementation, parsing, pattern matching