More Web Proxy on the site http://driver.im/

Article

Optimizing pattern matching

Authors:

Fabrice Le Fessant,

Luc MarangetAuthors Info & Claims

ICFP '01: Proceedings of the sixth ACM SIGPLAN international conference on Functional programming

Pages 26 - 37

https://doi.org/10.1145/507635.507641

Published: 01 October 2001 Publication History

Abstract

We present improvements to the backtracking technique of pattern-matching compilation. Several optimizations are introduced, such as commutation of patterns, use of exhaustiveness information, and control flow optimization through the use of labeled static exceptions and context information. These optimizations have been integrated in the Objective-Caml compiler. They have shown good results in increasing the speed of pattern-matching intensive programs, without increasing final code size.

References

[1]

AUGUSTSSON, L. Compiling pattern matching. In Functional Programming Languages and Computer Architecture. 1985.

Digital Library

[2]

BAUDINET, M., AND MACQUEEN, D. Tree pattern matching for ML,. unpublished paper, Dec. 1985.

[3]

BERNSTEIN, R. L. Producing good code for the case statement. Software -Practice and Experience 15, 10 (Oct. 1985), 1021 1021.

Digital Library

[4]

BODIK, R., GUPTA, R., AND SOFFA, M. L. Interprocedural conditional branch elimination. In Conference on Programming Language Design and Implementation (PLDI,) (1997).

Digital Library

[5]

CARDELLI, L. Compiling a functional language. In Conference Record of the 1984 ACM Symposium on Lisp and Functional Programming (Aug. 1984), ACM. ACM, pp. 208-217.

Digital Library

[6]

FRASER, C. W. A compact, machine-independent peephole optimizer. In Symposium on Principles of Programming Languages (1979).

Digital Library

[7]

HARPER, R. W., MACQUEEN, D. B. AND MILNER, B. Standard ML, Report ECS-LFCS-86-2. Department of Computer Science, University of Edinburgh, Edinburgh. UK. 1986. Also CSR209-86.

[8]

JORGENSEN, J. Generating a pattern matching compiler by partial evaluation. In Glasgow Workshop on Functional Programming, Ullapool (1990).

[9]

KNOOP, J., RTHING, 0. AND STEFFEN, B. Partial dead code elimination. In Conference on Programming Language Design and Implementation (1994).

Digital Library

[10]

LAVILLE, A. Implementation of lazy pattern matching algorithms. In ESOP 88 (1988). I-I. Ganzinger. Ed., vol. 300. pp. 298-3 16.

[11]

LEROY, X. The objective caml system: Documentation and users manual, 2000. With Damien Doligez, Jacques Garrigue, Didier Rmy, and Jrmne Vouillon. Available from http: //caml. inria. fr.

[12]

MARANGET, L. Compiling lazy pattern matching. In Proc. of the 1992 conference on Lisp and Functional Programming (1992), ACM Press.

Digital Library

[13]

MARANGET, L. Two techniques for compiling lazy pattern matching. Research Report 2385. INRIA Rocquencourt, Oct. 1994.

[14]

PLCLUB, AND CAML'R Us. Objective-caml: Winner of the first and second prizes of the p rogramming contest. ACM SIGPLAN International Conference on Functional Programming (ICFP 2000).

[15]

PUEL, L., AND SUREZ. A. Compiling pattern matching by term decomposition. Journal of Symbolic Computation 15, 1 (Jan. 1993), 1 26.

Digital Library

[16]

SCOTT, K., AND RAMSEY, N. When do match-compilation heuristics matter? Tech. Rep. CS2000-13, Department of Computer Science. University of Virginia, May 2000.

Digital Library

[17]

SEKAR, R. C., RAMESH, R., AND RAMAKRISHNAN, I. V. Adaptive pattern matching. In Automata, Languages and Programming, 19th International Colloquium (1992), vol. LNCS 623.

Digital Library

[18]

SESTOFT, P. ML pattern match compilation and partial evaluation. Lecture Notes in Computer Science1110 (1996), 446-??

Digital Library

[19]

SPULER, D. A. Compiler code generation for ioultiwav branch statements as a static search problem. Tech. Rep. 94/3, Department of Computer Science, James Cook University, 1994.

[20]

WADLER, P. Compilation of pattern matching. In The Implementation of Functional Programming Languages, S. L. Peyton Jones, Ed. Prentice-Hall International, 1987, eh. 7.

[21]

WEGMAN, M., AND ZADECK, F. K. Constant propagation with conditional branches. In Symposium on Principles of Programming Languages (1985).

Digital Library

Cited By

Cheng LParreaux L(2024)The Ultimate Conditional SyntaxProceedings of the ACM on Programming Languages10.1145/36897468:OOPSLA2(988-1017)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689746
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
Taft SBaird SDross C(2022)Defining a Pattern Matching Language Feature for AdaACM SIGAda Ada Letters10.1145/3577949.357796342:1(79-79)Online publication date: 19-Dec-2022
https://dl.acm.org/doi/10.1145/3577949.3577963
Show More Cited By

Index Terms

Optimizing pattern matching
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language types
        Functional languages

Recommendations

Optimizing pattern matching

We present improvements to the backtracking technique of pattern-matching compilation. Several optimizations are introduced, such as commutation of patterns, use of exhaustiveness information, and control flow optimization through the use of labeled ...
Optimising First-Class Pattern Matching
SLE 2022: Proceedings of the 15th ACM SIGPLAN International Conference on Software Language Engineering

Pattern matching is a high-level notation for programs to analyse the shape of data, and can be optimised to efficient low-level instructions. The Stratego language uses first-class pattern matching, a powerful form of pattern matching that ...
Extensible pattern matching in SNOBOL4
ACM '75: Proceedings of the 1975 annual conference

Although the string pattern-matching facilities of SNOBOL4 are the most powerful of those of any widely used programming language, they suffer both from complexity and lack of a mechanism for defining new scanning procedures. This paper describes a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICFP '01: Proceedings of the sixth ACM SIGPLAN international conference on Functional programming

October 2001

277 pages

ISBN:1581134150

DOI:10.1145/507635

General Chair:
Benjamin Pierce
Univ. of Pennsylvania

ACM SIGPLAN Notices Volume 36, Issue 10
October 2001
276 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/507669
Issue’s Table of Contents

Copyright © 2001 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

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICFP01

Sponsor:

SIGPLAN

ICFP01: International Conference on Functional Programming

September 3 - 5, 2001

Florence, Italy

Acceptance Rates

ICFP '01 Paper Acceptance Rate 23 of 66 submissions, 35%;

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

49
Total Citations
View Citations
1,241
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)5

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cheng LParreaux L(2024)The Ultimate Conditional SyntaxProceedings of the ACM on Programming Languages10.1145/36897468:OOPSLA2(988-1017)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689746
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
Taft SBaird SDross C(2022)Defining a Pattern Matching Language Feature for AdaACM SIGAda Ada Letters10.1145/3577949.357796342:1(79-79)Online publication date: 19-Dec-2022
https://dl.acm.org/doi/10.1145/3577949.3577963
Smits JHartman TCockx JFischer BBurgueño LCazzola W(2022)Optimising First-Class Pattern MatchingProceedings of the 15th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3567512.3567519(74-83)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3567512.3567519
Quiring BReppy JShivers O(2022)Analyzing binding extent in 3CPSProceedings of the ACM on Programming Languages10.1145/35476456:ICFP(650-678)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3547645
Ballantyne MKing AFelleisen M(2020)Macros for domain-specific languagesProceedings of the ACM on Programming Languages10.1145/34282974:OOPSLA(1-29)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428297
Garrigue JLe Normand J(2017)GADTs and Exhaustiveness: Looking for the ImpossibleElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.241.2241(23-35)Online publication date: 7-Feb-2017
https://doi.org/10.4204/EPTCS.241.2
Karachalias GSchrijvers TVytiniotis DJones S(2015)GADTs meet their match: pattern-matching warnings that account for GADTs, guards, and lazinessACM SIGPLAN Notices10.1145/2858949.278474850:9(424-436)Online publication date: 29-Aug-2015
https://dl.acm.org/doi/10.1145/2858949.2784748
Karachalias GSchrijvers TVytiniotis DJones SFisher KReppy J(2015)GADTs meet their match: pattern-matching warnings that account for GADTs, guards, and lazinessProceedings of the 20th ACM SIGPLAN International Conference on Functional Programming10.1145/2784731.2784748(424-436)Online publication date: 29-Aug-2015
https://dl.acm.org/doi/10.1145/2784731.2784748
Solodkyy YDos Reis GStroustrup B(2013)Open pattern matching for C++ACM SIGPLAN Notices10.1145/2637365.251722249:3(33-42)Online publication date: 27-Oct-2013
https://dl.acm.org/doi/10.1145/2637365.2517222
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