Article

Extensible pattern matching via a lightweight language extension

Authors:

Gregory Neverov,

James MargetsonAuthors Info & Claims

ICFP '07: Proceedings of the 12th ACM SIGPLAN international conference on Functional programming

Pages 29 - 40

https://doi.org/10.1145/1291151.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

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
Baudon TRadanne GGonnord L(2023)Bit-Stealing Made Legal: Compilation for Custom Memory Representations of Algebraic Data TypesProceedings of the ACM on Programming Languages10.1145/36078587:ICFP(813-846)Online publication date: 31-Aug-2023
https://dl.acm.org/doi/10.1145/3607858
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
Proceedings of the ICFP '07 conference

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 ...
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 ...
Pattern synonyms
Haskell '16

Pattern matching has proven to be a convenient, expressive way of inspecting data. Yet this language feature, in its traditional form, is limited: patterns must be data constructors of concrete data types. No computation or abstraction is allowed. The ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

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

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

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ICFP07

Sponsor:

ICFP07: ACM SIGPLAN International Conference on Functional Programming

October 1 - 3, 2007

Freiburg, Germany

Acceptance Rates

Overall Acceptance Rate 333 of 1,064 submissions, 31%

Upcoming Conference

ICFP '25

Sponsor:
sigplan

ACM SIGPLAN International Conference on Functional Programming

October 12 - 18, 2025

Singapore , Singapore

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

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
Baudon TRadanne GGonnord L(2023)Bit-Stealing Made Legal: Compilation for Custom Memory Representations of Algebraic Data TypesProceedings of the ACM on Programming Languages10.1145/36078587:ICFP(813-846)Online publication date: 31-Aug-2023
https://dl.acm.org/doi/10.1145/3607858
Kohn Tvan Rossum GBucher II GTalin Levkivskyi I(2020)Dynamic pattern matching with PythonProceedings of the 16th ACM SIGPLAN International Symposium on Dynamic Languages10.1145/3426422.3426983(85-98)Online publication date: 17-Nov-2020
https://dl.acm.org/doi/10.1145/3426422.3426983
Beasley AClarke CWatson R(2020)An OpenGL Compliant Hardware Implementation of a Graphic Processing Unit Using Field Programmable Gate Array–System on Chip TechnologyACM Transactions on Reconfigurable Technology and Systems10.1145/341035714:1(1-24)Online publication date: 2-Sep-2020
https://dl.acm.org/doi/10.1145/3410357
Paul SChatterjee NGhosal PDiguet J(2020)Adaptive Task Allocation and Scheduling on NoC-based Multicore Platforms with Multitasking ProcessorsACM Transactions on Embedded Computing Systems10.1145/340832420:1(1-26)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1145/3408324
Piovarči MKaufman DLevin DDidyk P(2020)Fabrication-in-the-loop co-optimization of surfaces and styli for drawing hapticsACM Transactions on Graphics10.1145/3386569.339246739:4(116:1-116:16)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392467
Wang BSchneider THu YAttene MPanozzo D(2020)Exact and efficient polyhedral envelope containment checkACM Transactions on Graphics10.1145/3386569.339242639:4(114:1-114:14)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392426
Li WXie BZhang YMeiss WHuang HYu L(2020)Exertion-aware path generationACM Transactions on Graphics10.1145/3386569.339239339:4(115:1-115:14)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392393
Hu YSchneider TWang BZorin DPanozzo D(2020)Fast tetrahedral meshing in the wildACM Transactions on Graphics10.1145/3386569.339238539:4(117:1-117:18)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392385
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 Table of Conten