Together with my coauthor Lean Ermantraut we have a new paper accepted at ECOOP '25: The Algebra of Patterns https://arxiv.org/abs/2504.18920
We answer the question why most PLs implement first-match semantics for pattern matching instead of the more declarative order-independent semantics. We think that the poor expressiveness of patterns, especially their inability to express complements, requires much more verbose patterns if we have to ensure that patterns don't overlap.
We also propose a solution which makes order-independent pattern matching practical: A boolean algebra of patterns and default clauses.
Algebraic patterns are much more expressive since they can talk about conjunction, disjunction and complements of patterns. (We prove that the patterns satisfy all the expected boolean laws formally in Rocq.)
An efficient compilation strategy for algebraic patterns is very important for us, so we also show how to compile them first to a disjunctive normal form, and then use compilation to decision trees to obtain good code.
