Pattern matching in an open world
Abstract
Pattern matching is a pervasive and useful feature in functional programming. There have been many attempts to bring similar notions to Object-Oriented Programming (OOP) in the past. However, a key challenge in OOP is how pattern matching can coexist with the open nature of OOP data structures, while at the same time guaranteeing other desirable properties for pattern matching.
This paper discusses several desirable properties for pattern matching in an OOP context and shows how existing approaches are lacking some of these properties. We argue that the traditional semantics of pattern matching, which is based on the order of patterns and adopted by many approaches, is in conflict with the openness of data structures. Therefore we suggest that a more restricted, top-level pattern matching model, where the order of patterns is irrelevant, is worthwhile considering in an OOP context. To compensate for the absence of ordered patterns we propose a complementary mechanism for case analysis with defaults, which can be used when nested and/or multiple case analysis is needed. To illustrate our points we develop Castor: a meta-programming library inScala that adopts both ideas. Castor generates code that uses type-safe extensible visitors, and largely removes boilerplate code typically associated with visitors. We illustrate the applicability of our approach with a case study modularizing the interpreters in the famous book ”Types and Programming Languages”.
References
[1]
Patrick Bahr and Tom Hvitved. 2011. Compositional data types. In Proceedings of the seventh ACM SIGPLAN workshop on Generic programming. ACM, 83–94.
[2]
Eugene Burmako. 2017. Unification of Compile-Time and Runtime Metaprogramming in Scala. Ph.D. Dissertation. EPFL.
[3]
Jacques Carette, Oleg Kiselyov, and Chung-chieh Shan. 2009. Finally tagless, partially evaluated: Tagless staged interpreters for simpler typed languages. Journal of Functional Programming 19, 5 (2009), 509–543.
[4]
Craig Chambers. 1992. Object-oriented multi-methods in Cecil. In European Conference on Object-Oriented Programming.
[5]
Curtis Clifton, Gary T Leavens, Craig Chambers, and Todd Millstein. 2000. MultiJava: Modular open classes and symmetric multiple dispatch for Java. In ACM Sigplan Notices, Vol. 35. ACM, 130–145.
[6]
Burak Emir, Martin Odersky, and John Williams. 2007. Matching objects with patterns. In European Conference on Object-Oriented Programming.
[7]
Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. 1994. Design Patterns : Elements of Reusable Object-Oriented Software. Addisson-Wesley.
[8]
Jacques Garrigue. 1998. Programming with polymorphic variants. In ML Workshop.
[9]
Jacques Garrigue. 2000. Code reuse through polymorphic variants. In Workshop on Foundations of Software Engineering.
[10]
Felix Geller, Robert Hirschfeld, and Gilad Bracha. 2010. Pattern Matching for an object-oriented and dynamically typed programming language. Number 36. Universitätsverlag Potsdam.
[11]
Martin Hirzel, Nathaniel Nystrom, Bard Bloom, and Jan Vitek. 2008. Matchete: Paths through the pattern matching jungle. In International Symposium on Practical Aspects of Declarative Languages.
[12]
Christian Hofer and Klaus Ostermann. 2010. Modular Domain-specific Language Components in Scala. In Proceedings of the Ninth International Conference on Generative Programming and Component Engineering (GPCE ’10).
[13]
Christian Hofer, Klaus Ostermann, Tillmann Rendel, and Adriaan Moors. 2008. Polymorphic Embedding of Dsls. In Proceedings of the 7th International Conference on Generative Programming and Component Engineering (GPCE ’08).
[14]
Michael Homer, James Noble, Kim B. Bruce, Andrew P. Black, and David J. Pearce. 2012. Patterns As Objects in Grace. In Proceedings of the 8th Symposium on Dynamic Languages (DLS ’12). New York, NY, USA, 17–28.
[15]
Pablo Inostroza and Tijs van der Storm. 2015. Modular Interpreters for the Masses: Implicit Context Propagation Using Object Algebras. In Proceedings of the 2015 ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences.
[16]
Chinawat Isradisaikul and Andrew C. Myers. 2013. Reconciling Exhaustive Pattern Matching with Objects. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’13).
[17]
Simon Peyton Jones. 2003. Haskell 98 language and libraries: the revised report. Cambridge University Press.
[18]
Jed Liu and Andrew C Myers. 2003. JMatch: Iterable abstract pattern matching for Java. In PADL.
[19]
Andres Löh and Ralf Hinze. 2006. Open data types and open functions. In Proceedings of the 8th ACM SIGPLAN international conference on Principles and practice of declarative programming.
[20]
Todd Millstein, Colin Bleckner, and Craig Chambers. 2004. Modular Typechecking for Hierarchically Extensible Datatypes and Functions. ACM Trans. Program. Lang. Syst. 26, 5 (Sept. 2004).
[21]
Robin Milner, Mads Tofte, Robert Harper, and David Macqueen. 1997. The Definition of Standard ML-Revised. (1997).
[22]
Martin Odersky, Philippe Altherr, Vincent Cremet, Burak Emir, Sebastian Maneth, Stéphane Micheloud, Nikolay Mihaylov, Michel Schinz, Erik Stenman, and Matthias Zenger. 2004. An overview of the Scala programming language. Technical Report.
[23]
Martin Odersky and Matthias Zenger. 2005. Independently extensible solutions to the expression problem. In The 12th International Workshop on Foundations of Object-Oriented Languages.
[24]
Bruno C. d. S. Oliveira. 2009. Modular Visitor Components. In Proceedings of the 23rd European Conference on Object-Oriented Programming.
[25]
Bruno C. d. S. Oliveira and William R. Cook. 2012. Extensibility for the Masses: Practical Extensibility with Object Algebras. In Proceedings of the 26th European Conference on Object-Oriented Programming.
[26]
Bruno C. d. S. Oliveira, Shin-Cheng Mu, and Shu-Hung You. 2015. Modular Reifiable Matching: A List-of-functors Approach to Twolevel Types. In Proceedings of the 2015 ACM SIGPLAN Symposium on Haskell (Haskell ’15).
[27]
Bruno C. d. S. Oliveira, Tijs van der Storm, Alex Loh, and William R. Cook. 2013. Feature-Oriented Programming with Object Algebras. In Proceedings of the 27th European Conference on Object-Oriented Programming.
[28]
Benjamin C Pierce. 2002. Types and programming languages. MIT press.
[29]
Tillmann Rendel, Jonathan Immanuel Brachthäuser, and Klaus Ostermann. 2014. From Object Algebras to Attribute Grammars. In Proceedings of the 2014 ACM International Conference on Object-Oriented Programming Systems Languages and Applications.
[30]
Tiark Rompf and Martin Odersky. 2010. Lightweight Modular Staging: A Pragmatic Approach to Runtime Code Generation and Compiled DSLs. In In GPCE.
[31]
Sukyoung Ryu, Changhee Park, and Guy L Steele Jr. 2010. Adding pattern matching to existing object-oriented languages. In ACM SIGPLAN Foundations of Object-Oriented Languages Workshop.
[32]
Tim Sheard and Simon Peyton Jones. 2002. Template metaprogramming for Haskell. In Proceedings of the 2002 ACM SIGPLAN workshop on Haskell.
[33]
Yuriy Solodkyy, Gabriel Dos Reis, and Bjarne Stroustrup. 2013. Open Pattern Matching for C++. In Proceedings of the 12th International Conference on Generative Programming: Concepts and Experiences (GPCE ’13).
[34]
Wouter Swierstra. 2008. Data types à la carte. Journal of functional programming 18, 4 (2008), 423–436.
[35]
Philip Wadler. 1998. The Expression Problem. Email. (Nov. 1998). Discussion on the Java Genericity mailing list.
[36]
Hongwei Xi, Chiyan Chen, and Gang Chen. 2003. Guarded Recursive Datatype Constructors. In Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’03).
[37]
Matthias Zenger and Martin Odersky. 2001. Extensible Algebraic Datatypes with Defaults. In Proceedings of the Sixth ACM SIGPLAN International Conference on Functional Programming.
[38]
Weixin Zhang. 2017. Extensible domain-specific languages in objectoriented programming. HKU Theses Online (HKUTO) (2017).
[39]
Weixin Zhang and Bruno C. d. S. Oliveira. 2017. EVF: An Extensible and Expressive Visitor Framework for Programming Language Reuse. In European Conference on Object-Oriented Programming.
Index Terms
- Pattern matching in an open world
Recommendations
Pattern matching in an open world
GPCE 2018: Proceedings of the 17th ACM SIGPLAN International Conference on Generative Programming: Concepts and ExperiencesPattern matching is a pervasive and useful feature in functional programming. There have been many attempts to bring similar notions to Object-Oriented Programming (OOP) in the past. However, a key challenge in OOP is how pattern matching can coexist ...
Open pattern matching for C++
GPCE '13Pattern matching is an abstraction mechanism that can greatly simplify source code. We present functional-style pattern matching for C++ implemented as a library, called Mach71. All the patterns are user-definable, can be stored in variables, passed ...
Open pattern matching for C++
GPCE '13: Proceedings of the 12th international conference on Generative programming: concepts & experiencesPattern matching is an abstraction mechanism that can greatly simplify source code. We present functional-style pattern matching for C++ implemented as a library, called Mach71. All the patterns are user-definable, can be stored in variables, passed ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2018
214 pages
November 2018214 pages
Copyright © 2018 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 07 April 2020
Published in SIGPLAN Volume 53, Issue 9
Check for updates
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 181Total Downloads
- Downloads (Last 12 months)9
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in