Extensible Pattern Matching in an Extensible Language
đź“ś Abstract
Pattern matching is a widely used technique in functional languages, especially those in the ML and Haskell traditions, where it is at the core of the semantics. In languages in the Lisp tradition, in contrast, pattern matching is typically provided by libraries built with macros. We present match, a sophisticated pattern matcher for Racket, implemented as language extension using macros. The system supports novel and widely-useful pattern-matching forms, and is itself extensible. The extensibility of match is implemented via a general technique for creating extensible language extensions.
✨ Summary
The paper presents Racket’s match as a macro-based language extension rather than a fixed core-language feature. Its central contribution is match expanders: hygienic compile-time transformers that allow users to define new pattern forms by translating them into existing patterns. The implementation combines this extensibility mechanism with compiled pattern matching, sequence patterns, predicate patterns, application/view patterns, and support for user-defined structures.
The paper’s ideas influenced subsequent Scheme standardization work. SRFI 262, “Extensible pattern matcher,” explicitly describes its design as closely inspired by Racket’s matcher and adopts an analogous transformer-based mechanism for defining new pattern syntax. (srfi.schemers.org) The GNU Emacs pcase implementation also cites this paper as a presentation of ideas that significantly influenced its later design. (github.com) The paper additionally documents applications of match expanders in Racket, including domain-specific rewrite-rule languages and abstraction libraries for views. (ccs.neu.edu)