The Algebra of Patterns (Extended Version)
David Binder, Lean Ermantraut · 2025
Read The Algebra of Patterns (Extended Version) by David Binder, Lean Ermantraut (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-18920.txt.
Introduction
Pattern matching lets a program pick a branch by the shape of its data, a feature shared by many language families. David Binder and Lean Ermantraut argue in 2025 that the usual rule, try each clause in order until one fits, makes programs depend on clause order. Their fix gives patterns a logic of their own, in which the opposite of a pattern can also be written.
With that algebra, a match no longer needs its clauses in a set order. A new default clause covers the leftover cases without breaking that freedom. The authors show the design in a formal way, as an extended version of their work. They aim it at language designers who want matching that reads as facts, not as a queue.
Catalog record
| CREATOR | David Binder, Lean Ermantraut |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 150 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-18920
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Algebra of Patterns (Extended Version) David Binder, Lean Ermantraut Abstract Pattern matching is a popular feature in functional, imperative and object-oriented programming languages. Language designers should therefore invest effort in a good design for pattern matching. Most languages choose a first-match semantics for pattern matching; that is, clauses are tried in the order in which they appear in the program until the first one matches. As a consequence, the order in which the clauses appear cannot be arbitrarily changed, which results in a less declarative programming model. The declarative alternative to this is an order-independent semantics for pattern matching, which is not implemented in most programming languages since it requires more verbose patterns. The reason for this verbosity is that the syntax of patterns is usually not expressive enough to express the complement of a pattern. In this paper, we show a principled way to make order-independent pattern matching practical. Our solution consists of two parts: First, we introduce a boolean algebra of patterns which can express the complement of a pattern. Second, we introduce default clauses to pattern matches. These default clauses capture the essential idea of a fallthrough case without sacrificing the property of order-independence. University of Kent, United [email protected] by ARIA programme for Safeguarded AI (grant MSAI-PR01-P11). Radboud University Nijmegen, [email protected] {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10003752.10003753.10003754.10003733¡/concept_id¿ ¡concept_desc¿Theory of computation Lambda calculus¡/concept_desc¿ ¡concept_significance¿300¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003790.10011740¡/concept_id¿ ¡concept_desc¿Theory of computation Type theory¡/concept_desc¿ ¡concept_significance¿300¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ keywords functional programming, pattern matching, algebraic data types, equational reasoning ccs Theory of computation Lambda calculus ccs Theory of computation Type theory † † editors: Jonathan Aldrich and Alexandra Silva † † event-title: 39th European Conference on Object-Oriented Programming (ECOOP 2025) † † event-shorttitle: ECOOP 2025 † † event-acronym: ECOOP † † year: 2025 † † event-date: June 30–July 2, 2025 † † event-location: Bergen, Norway † † series-volume: 333 † † articleno: 19 † † runningauthor: David Binder and Lean Ermantraut † † copyright: David Binder and Lean Ermantraut 1 Introduction Pattern matching is a programming language feature that combines two operations: Testing whether a value matches a given pattern and, if the test is successful, extracting subexpressions of the value and binding them to variables. A pattern matching expression consists of the scrutinee which is analyzed by the pattern match and a list of clauses . Each clause consists of a pattern , hence the name, and an expression called the right-hand side . These elements can all be seen in the following example of the length function, which computes the length of a list: \text{length}(\mathit{xs})\coloneqq\mathbf{case}\ \underbracket{\quad\mathit{xs}\quad}_{\text{scrutinee}}\ \mathbf{of}\ \{\ \underbracket{\,\mathtt{Nil}\Rightarrow 0\,}_{\text{clause}},\underbracket{\,\mathtt{Cons}(\_,\mathit{zs})\,}_{\text{pattern}}\Rightarrow\underbracket{1+\text{length}(\mathit{zs})}_{\text{right-hand side}}\ \ \} Programming with pattern matching is popular. For a long time, only programmers who use functional languages could enjoy this feature, but today pattern matching has arrived in the mainstream of object-oriented and imperative programming languages. For example, Python, Java, Dart, and C# added pattern matching as an extension to the language, and some newer languages such as Rust and Swift, which are not primarily functional languages, supported pattern matching from the beginning. Pattern matching has become one of the central constructs that is used to structure the control and data flow of a program. How pattern matches are checked and evaluated therefore fundamentally determines how we reason about the meaning of our programs; both informally when we read and write code in our daily lives, and formally in proof assistants, static analyzers and other verification tools. It is therefore important to choose a semantics for pattern matching which makes reasoning as simple as possible. One choice that language designers have to make is whether the clauses are tried in the order in which they appear in the program, or whether the order of the clauses does not matter. The following definition captures this difference: Definition 1 (First-Match and Order-Independent Semantics) . A language uses first-match semantics if the clauses of a pattern match are tried in the order in which they occur until the first pattern matches the scrutinee. A language uses order-independent semantics if any of the matching clauses in a pattern match can be used to non-deterministically reduce a pattern matching expression. Overlapping clauses, i.e. two clauses with patterns that can match the same scrutinee, are a problem for order-independent semantics since a pattern-matching expression with overlapping clauses can non-deterministically reduce to two different results. The obvious solution is to enforce that two clauses must never overlap. But if we adopt this solution, then programmers usually have to write much more verbose patterns. For example, instead of the following function which checks whether the argument is the color \mathtt{Red} \text{isRed}(c)\coloneqq\mathbf{case}\ c\ \mathbf{of}\ \{\ \mathtt{Red}\Rightarrow\mathtt{True},\ \_\Rightarrow\mathtt{False}\ \}, the programmer has to write the following more verbose expression \text{isRed}(c)\coloneqq\mathbf{case}\ c\ \mathbf{of}\ \{\ \mathtt{Red}\Rightarrow\mathtt{True},\ \mathtt{Green}\Rightarrow\mathtt{False},\ \mathtt{Blue}\Rightarrow\mathtt{False}\ \}. The source of this verbosity is the poor expressiveness of patterns, which usually do not allow to express the complement of a pattern without exhaustively enumerating all the alternatives. In this example, we had to explicitly mention both \mathtt{Blue} and \mathtt{Green} to express the complement of the pattern \mathtt{Red} . In languages that support or-patterns we can combine the last two clauses in the single clause (\mathtt{Green}\mathbin{\parallel}\mathtt{Blue})\Rightarrow\mathtt{False} , but we still have to mention all constructors explicitly. It is unreasonable to ask programmers to always list all constructors of a data type, and they would rightfully reject a programming language which enforces this. Every proposal to use order-independent pattern matching in a realistic programming language therefore has to address this verbosity problem. We propose two complementary solutions to the verbosity problem. In our system, the function can be written in the following ways: \displaystyle\text{isRed}(c) \displaystyle\coloneqq\mathbf{case}\ c\ \mathbf{of}\ \{\ \mathtt{Red}\Rightarrow\mathtt{True},\ \neg\mathtt{Red}\Rightarrow\mathtt{False}\ \} (Negation Pattern) \displaystyle\text{isRed}(c) \displaystyle\coloneqq\mathbf{case}\ c\ \mathbf{of}\ \{\ \mathtt{Red}\Rightarrow\mathtt{True},\ \mathbf{default}\Rightarrow\mathtt{False}\ \} (Default Clause) To write the first variant we enrich the syntax of patterns with negation patterns which match whenever the negated pattern does not match. The two patterns are no longer overlapping, and at the same time, the pattern matching expression is not more verbose than our first version. Such negation patterns were already proposed under the name of “anti-patterns” [ 15 , 16 , 5 ] and are also mentioned by some other authors [ 18 , 10 ] ; the core contribution of this paper, however, is to consider them in the context of a complete boolean algebra of patterns which allows us to apply algebraic reasoning to patterns. To write the second variant we enrich the syntax of pattern-matching expressions with default clauses 1 1 1 Some programming languages support default clauses with similar semantics to what we propose. Ada, for example, enforces that clauses in a case statement are not overlapping, but allows an optional “other” clause with the same semantics as our default clause. The clauses that Ada allows are however much more restricted, since they only work for enums instead of algebraic data types. . A pattern matching expression can contain at most one such default clause (where \mathbf{default} is a keyword instead of a pattern) which matches whenever none of the normal clauses matches the scrutinee. At first glance, the meaning of a default clause looks identical to the meaning of a clause with a wildcard pattern, but this is only the case for