skip to main content
article

Extensible pattern matching via a lightweight language extension

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.
[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.
[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.
[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.
[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.
[9]
Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy. Composable memory transactions. In Principles and Practice of Parallel Programming. ACM, 2005.
[10]
Haruo Hosoya and Benjamin Pierce. Regular expression pattern matching for XML. ACM SIGPLAN Notices, 36(3):67--80, 2001.
[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.
[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.
[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.
[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.
[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.
[28]
Mark Tullsen. First class patterns. In Practical Aspects of Declarative Languages. Springer, 2000.
[29]
Philip Wadler. Views: A way for pattern matching to cohabit with data abstraction. In Principles of Programming Languages. ACM, 1987.
[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.

Cited By

View all
  • (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
  • (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
  • (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
  • Show More Cited By

Index Terms

  1. Extensible pattern matching via a lightweight language extension

    Recommendations

    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
    • 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
    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

    1. F#
    2. ML
    3. functional programming
    4. pattern matching

    Qualifiers

    • Article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)14
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 18 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (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
    • (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
    • (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
    • (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
    • (2016)Pattern synonymsACM SIGPLAN Notices10.1145/3241625.297601351:12(80-91)Online publication date: 8-Sep-2016
    • (2016)Pattern synonymsProceedings of the 9th International Symposium on Haskell10.1145/2976002.2976013(80-91)Online publication date: 8-Sep-2016
    • (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
    • (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
    • (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
    • (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
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media