article

Extensible pattern matching via a lightweight language extension

Authors:

Gregory Neverov,

James MargetsonAuthors Info & Claims

ACM SIGPLAN Notices, Volume 42, Issue 9

Pages 29 - 40

https://doi.org/10.1145/1291220.1291159

Published: 01 October 2007 Publication History

Abstract

Pattern matching of algebraic data types (ADTs) is a standard feature in typed functional programming languages, but it is well known that it interacts poorly with abstraction. While several partial solutions to this problem have been proposed, few have been implemented or used. This paper describes an extension to the .NET language F# called active patterns, which supports pattern matching over abstract representations of generic heterogeneous data such as XML and term structures, including where these are represented via object models in other .NET languages. Our design is the first to incorporate both ad hoc pattern matching functions for partial decompositions and "views" for total decompositions, and yet remains a simple and lightweight extension. We give a description of the language extension along with numerous motivating examples. Finally we describe how this feature would interact with other reasonable and related language extensions: existential types quantified at data discrimination tags, GADTs, and monadic generalizations of pattern matching.

References

[1]

V. Benzaken, G. Castagna, and A. Frisch. CDuce: An XML-centric general purpose language. In Proceedings of 2003 ACM SIGPLAN International Conference on Functional Programming. ACM Press, 2003.

Digital Library

[2]

F. Warren Burton and Robert D. Cameron. Pattern matching with abstract data types. Journal of Functional Programming, 3(2):171--190, 1993.

[3]

Burak Emir and Martin Odersky. Matching Objects with Patterns. In ECOOP '07, 2007. To appear.

Digital Library

[4]

Martin Erwig. Active patterns. In Implementation of Functional Languages. Springer, 1997.

[5]

Martin Erwig and Simon Peyton Jones. Pattern Guards and Transformational Patterns. In Haskell Workshop, 2000.

[6]

Manuel Fähndrich and John Boyland. Statically checkable pattern abstractions. In International Conference on Functional Programming. ACM, 1997.

Digital Library

[7]

Pedro Palao Gostanza, Ricardo Pena, and Manuel Nunez. A new look at pattern matching in abstract data types. In ICFP '96: Proceedings of the first ACM SIGPLAN international conference on Functional programming, pages 110--121, New York, NY, USA, 1996. ACM Press.

Digital Library

[8]

Jim Grundy, Tom Melham, and John O'Leary. A reflective functional language for hardware design and theorem proving. Journal of Functional Programming, 16(2):157--196, 2006.

Digital Library

[9]

Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy. Composable memory transactions. In Principles and Practice of Parallel Programming. ACM, 2005.

Digital Library

[10]

Haruo Hosoya and Benjamin Pierce. Regular expression pattern matching for XML. ACM SIGPLAN Notices, 36(3):67--80, 2001.

Digital Library

[11]

Martin Jambon. Micmatch. martin.jambon.free.fr/micmatch.html, 2007.

[12]

Konstantin Läufer and Martin Odersky. An extension of ML with first class abstract types. In ACM SIGPLAN Workshop on ML and its Applications, San Francisco, California, pages 78--91, June 1992.

[13]

Fabrice Le Fessant and Luc Maranget. Optimizing pattern-matching. In Proceedings of the 2001 International Conference on Functional Programming. ACM Press, 2001.

Digital Library

[14]

Luc Maranget. Warnings for pattern matching. Journal of Functional Programming, 17(3):647--656, 2007.

[15]

Erik Meijer and Brian Beckman. XLinq: XML Programming Refactored. research.microsoft.com/~emeijer, 2006.

[16]

Nemerle. Nemerle website. nemerle.org, 2006.

[17]

Martin Odersky. Scala website. scala.epfl.ch, 2006.

[18]

Martin Odersky and Philip Wadler. Pizza into Java: Translating theory into practice. In Principles of Programming Languages. ACM, 1997.

Digital Library

[19]

Chris Okasaki. Views for Standard ML. In SIGPLAN Workshop on ML, Baltimore, Maryland, USA, pages 14--23, September 1998.

[20]

Simon Peyton Jones. View patterns: lightweight views for Haskell (wiki entry). hackage.haskell.org/trac/ghc/wiki/ViewPatterns, 2007.

[21]

Andreas Rossberg. Generalizing layered patterns to conjunctive patterns. successor-ml.org, 2007a. Search for "Generalizing Layered Patterns".

[22]

Andreas Rossberg. Hamlet S: To Become or Not To Become SuccessorML. www.ps.uni-sb.de/hamlet/hamlet-succ-1.3.0S4.pdf, 2007b. Appendix B.17 and B.19.

[23]

Kevin Scott and Norman Ramsey. When Do Match-compilation Heuristics Matter? Technical Report CS-2000-13, University of Virginia, 2000.

Digital Library

[24]

Don Syme. Active patterns in F#. blogs.msdn.com/dsyme, 2006a.

[25]

Don Syme. Leveraging .NET meta-programming components from F#: Integrated queries and interoperable heterogeneous execution. In Proceedings of the ACM SIGPLAN Workshop on ML and its Applications, 2006b.

Digital Library

[26]

Don Syme and James Margetson. F# website. research.microsoft.com/fsharp, 2006.

[27]

Walid Taha and Tim Sheard. Multi-stage programming with explicit annotations. In Partial Evaluation and Semantics-Based Program Manipulation. ACM, 1997.

Digital Library

[28]

Mark Tullsen. First class patterns. In Practical Aspects of Declarative Languages. Springer, 2000.

Digital Library

[29]

Philip Wadler. Views: A way for pattern matching to cohabit with data abstraction. In Principles of Programming Languages. ACM, 1987.

Digital Library

[30]

Hongwei Xi, Chiyan Chen, and Gang Chen. Guarded recursive datatype constructors. In Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of Programming Languages, pages 224--235, New York, NY, USA, 2003. ACM Press.

Digital Library

Cited By

Chataing NDolan SScherer GYallop J(2024)Unboxed Data Constructors: Or, How cpp Decides a Halting ProblemProceedings of the ACM on Programming Languages10.1145/36328938:POPL(1509-1539)Online publication date: 5-Jan-2024
https://doi.org/10.1145/3632893
Flatt MAllred TAngle NDe Gabrielle SFindler RFirth JGopinathan KGreenman BKasivajhula SKnauth AMcCarthy JPhillips SPorncharoenwase SSøgaard JTobin-Hochstadt S(2023)Rhombus: A New Spin on Macros without All the ParenthesesProceedings of the ACM on Programming Languages10.1145/36228187:OOPSLA2(574-603)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622818
Shaikhha ASchaefer IReichenbach CStorm T(2019)Polymorphic extractors for semantic and portable pattern matching (short paper)Proceedings of the 18th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3357765.3359522(61-67)Online publication date: 21-Oct-2019
https://dl.acm.org/doi/10.1145/3357765.3359522
Show More Cited By

Index Terms

Extensible pattern matching via a lightweight language extension
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features

Recommendations

Extensible pattern matching via a lightweight language extension
ICFP '07: Proceedings of the 12th ACM SIGPLAN international conference on Functional programming

Pattern matching of algebraic data types (ADTs) is a standard feature in typed functional programming languages, but it is well known that it interacts poorly with abstraction. While several partial solutions to this problem have been proposed, few have ...
Formal validation of pattern matching code
PPDP '05: Proceedings of the 7th ACM SIGPLAN international conference on Principles and practice of declarative programming

When addressing the formal validation of generated software, two main alternatives consist either to prove the correctness of compilers or to directly validate the generated code. Here, we focus on directly proving the correctness of compiled code ...
Open pattern matching for C++
GPCE '13

Pattern matching is an abstraction mechanism that can greatly simplify source code. We present functional-style pattern matching for C++ implemented as a library, called Mach7¹. All the patterns are user-definable, can be stored in variables, passed ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 42, Issue 9

Proceedings of the ICFP '07 conference

September 2007

331 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1291220

Issue’s Table of Contents

ICFP '07: Proceedings of the 12th ACM SIGPLAN international conference on Functional programming
October 2007
346 pages
ISBN:9781595938152
DOI:10.1145/1291151
General Chair:
Ralf Hinze
Universität Bonn, Germany
,
Program Chair:
Norman Ramsey
Harvard University, USA

Copyright © 2007 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: 01 October 2007

Published in SIGPLAN Volume 42, Issue 9

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

58
Total Citations
View Citations
776
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chataing NDolan SScherer GYallop J(2024)Unboxed Data Constructors: Or, How cpp Decides a Halting ProblemProceedings of the ACM on Programming Languages10.1145/36328938:POPL(1509-1539)Online publication date: 5-Jan-2024
https://doi.org/10.1145/3632893
Flatt MAllred TAngle NDe Gabrielle SFindler RFirth JGopinathan KGreenman BKasivajhula SKnauth AMcCarthy JPhillips SPorncharoenwase SSøgaard JTobin-Hochstadt S(2023)Rhombus: A New Spin on Macros without All the ParenthesesProceedings of the ACM on Programming Languages10.1145/36228187:OOPSLA2(574-603)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622818
Shaikhha ASchaefer IReichenbach CStorm T(2019)Polymorphic extractors for semantic and portable pattern matching (short paper)Proceedings of the 18th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3357765.3359522(61-67)Online publication date: 21-Oct-2019
https://dl.acm.org/doi/10.1145/3357765.3359522
Egi SNishiwaki Y(2018)Non-linear Pattern Matching with Backtracking for Non-free Data TypesProgramming Languages and Systems10.1007/978-3-030-02768-1_1(3-23)Online publication date: 22-Oct-2018
https://doi.org/10.1007/978-3-030-02768-1_1
Pickering MÉrdi GPeyton Jones SEisenberg R(2016)Pattern synonymsACM SIGPLAN Notices10.1145/3241625.297601351:12(80-91)Online publication date: 8-Sep-2016
https://dl.acm.org/doi/10.1145/3241625.2976013
Pickering MÉrdi GPeyton Jones SEisenberg RMainland G(2016)Pattern synonymsProceedings of the 9th International Symposium on Haskell10.1145/2976002.2976013(80-91)Online publication date: 8-Sep-2016
https://dl.acm.org/doi/10.1145/2976002.2976013
Ferrara P(2010)Static type analysis of pattern matching by abstract interpretationProceedings of the 12th IFIP WG 6.1 international conference and 30th IFIP WG 6.1 international conference on Formal Techniques for Distributed Systems10.1007/978-3-642-13464-7_15(186-200)Online publication date: 7-Jun-2010
https://dl.acm.org/doi/10.1007/978-3-642-13464-7_15
Nakata KHasegawa M(2009)Small-step and big-step semantics for call-by-needJournal of Functional Programming10.1017/S095679680999021919:6(699-722)Online publication date: 1-Nov-2009
https://dl.acm.org/doi/10.1017/S0956796809990219
Kravchuk-Kirilyuk AFeng GIskander JZhang YAmin N(2024)Persimmon: Nested Family Polymorphism with Extensible Variant TypesProceedings of the ACM on Programming Languages10.1145/36498368:OOPSLA1(698-724)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649836
Flatt MAllred TAngle NDe Gabrielle SFindler RFirth JGopinathan KGreenman BKasivajhula SKnauth AMcCarthy JPhillips SPorncharoenwase SSøgaard JTobin-Hochstadt S(2023)Rhombus: A New Spin on Macros without All the ParenthesesProceedings of the ACM on Programming Languages10.1145/36228187:OOPSLA2(574-603)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622818
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents