Optimising First-Class Pattern Matching

J. Smits; Toine  Hartman; Jesper Cockx

doi:10.1145/3567512.3567519

Optimising First-Class Pattern Matching

J. Smits^*, Toine Hartman, Jesper Cockx

^*Corresponding author for this work

Programming Languages

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

86 Downloads (Pure)

Abstract

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 traditional optimisation techniques do not apply to directly.
In this paper, we investigate how to optimise programs that use first-class pattern matching. Concretely, we show how to map first-class pattern matching to a form close to traditional pattern matching, on which standard optimisations can be applied.
Through benchmarks, we demonstrate the positive effect of these optimisations on the run-time performance of Stratego programs. We conclude that the expressive power of first-class pattern matching does not hamper the optimisation potential of a language that features it.

Original language	English
Title of host publication	SLE 2022: Proceedings of the 15th ACM SIGPLAN International Conference on Software Language Engineering
Place of Publication	New York
Publisher	Association for Computing Machinery (ACM)
Pages	74-83
Number of pages	10
ISBN (Print)	978-1-4503-9919-7
DOIs	https://doi.org/10.1145/3567512.3567519
Publication status	Published - 2022
Event	The 15th ACM SIGPLAN International Conference on Software Language Engineering - Auckland , New Zealand Duration: 6 Dec 2022 → 7 Dec 2022 Conference number: 15th

Conference

Conference	The 15th ACM SIGPLAN International Conference on Software Language Engineering
Abbreviated title	SLE 2022
Country/Territory	New Zealand
City	Auckland
Period	6/12/22 → 7/12/22

Keywords

pattern matching
optimisation
strategic programming

Access to Document

10.1145/3567512.3567519Licence: CC BY

3567512.3567519Final published version, 222 KBLicence: CC BY

Cite this

@inproceedings{beed1cdb5fe74656880bede9a6f8ce6a,

title = "Optimising First-Class Pattern Matching",

abstract = "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 traditional optimisation techniques do not apply to directly.In this paper, we investigate how to optimise programs that use first-class pattern matching. Concretely, we show how to map first-class pattern matching to a form close to traditional pattern matching, on which standard optimisations can be applied.Through benchmarks, we demonstrate the positive effect of these optimisations on the run-time performance of Stratego programs. We conclude that the expressive power of first-class pattern matching does not hamper the optimisation potential of a language that features it.",

keywords = "pattern matching, optimisation, strategic programming",

author = "J. Smits and Toine Hartman and Jesper Cockx",

year = "2022",

doi = "10.1145/3567512.3567519",

language = "English",

isbn = "978-1-4503-9919-7",

pages = "74--83",

booktitle = "SLE 2022: Proceedings of the 15th ACM SIGPLAN International Conference on Software Language Engineering",

publisher = "Association for Computing Machinery (ACM)",

address = "United States",

note = "The 15th ACM SIGPLAN International Conference on Software Language Engineering, SLE 2022 ; Conference date: 06-12-2022 Through 07-12-2022",

}

Smits, J, Hartman, T & Cockx, J 2022, Optimising First-Class Pattern Matching. in SLE 2022: Proceedings of the 15th ACM SIGPLAN International Conference on Software Language Engineering. Association for Computing Machinery (ACM), New York, pp. 74-83, The 15th ACM SIGPLAN International Conference on Software Language Engineering, Auckland , New Zealand, 6/12/22. https://doi.org/10.1145/3567512.3567519

Optimising First-Class Pattern Matching. / Smits, J.; Hartman, Toine ; Cockx, Jesper.
SLE 2022: Proceedings of the 15th ACM SIGPLAN International Conference on Software Language Engineering. New York: Association for Computing Machinery (ACM), 2022. p. 74-83.

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Optimising First-Class Pattern Matching

AU - Smits, J.

AU - Hartman, Toine

AU - Cockx, Jesper

N1 - Conference code: 15th

PY - 2022

Y1 - 2022

N2 - 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 traditional optimisation techniques do not apply to directly.In this paper, we investigate how to optimise programs that use first-class pattern matching. Concretely, we show how to map first-class pattern matching to a form close to traditional pattern matching, on which standard optimisations can be applied.Through benchmarks, we demonstrate the positive effect of these optimisations on the run-time performance of Stratego programs. We conclude that the expressive power of first-class pattern matching does not hamper the optimisation potential of a language that features it.

AB - 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 traditional optimisation techniques do not apply to directly.In this paper, we investigate how to optimise programs that use first-class pattern matching. Concretely, we show how to map first-class pattern matching to a form close to traditional pattern matching, on which standard optimisations can be applied.Through benchmarks, we demonstrate the positive effect of these optimisations on the run-time performance of Stratego programs. We conclude that the expressive power of first-class pattern matching does not hamper the optimisation potential of a language that features it.

KW - pattern matching

KW - optimisation

KW - strategic programming

UR - http://www.scopus.com/inward/record.url?scp=85147028793&partnerID=8YFLogxK

U2 - 10.1145/3567512.3567519

DO - 10.1145/3567512.3567519

M3 - Conference contribution

SN - 978-1-4503-9919-7

SP - 74

EP - 83

BT - SLE 2022: Proceedings of the 15th ACM SIGPLAN International Conference on Software Language Engineering

PB - Association for Computing Machinery (ACM)

CY - New York

T2 - The 15th ACM SIGPLAN International Conference on Software Language Engineering

Y2 - 6 December 2022 through 7 December 2022

ER -

Optimising First-Class Pattern Matching

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Strategic Language Workbench Improvements

Cite this