This repository contains a collection of pattern matching algorithms implemented in Rust. The goal of these implementations it to (hopefully) make it easier to understand them, as papers related to pattern matching (and papers in general) can be difficult to read.
I ended up implementing these algorithms while investigating potential pattern matching/exhaustiveness checking algorithms for Inko. While there are plenty of papers on the subject, few of them include reference code, and almost all of them are really dense and difficult to read. I hope the code published in this repository is of use to those wishing to implement pattern matching/exhaustiveness.
| Name | Paper | Directory |
|---|---|---|
| ML pattern compilation and partial evaluation | sestoft1996 | |
| How to compile pattern matching | jacobs2021 |
Other papers I've come across (but don't necessarily want to implement):
- A generic algorithm for checking exhaustivity of pattern
matching.
- The Scala implementation is found in this PR (the
Space.scalafile). - Swift also uses this algorithm here
- Some Reddit comments about the algorithm are found here
- The Scala implementation is found in this PR (the
- Compiling pattern matching to good decision
trees.
This is about just compiling pattern matching into a decision tree, not about
exhaustiveness checking. If you don't know how to read the computer science
hieroglyphs (like me), this paper is basically impossible to understand.
- See also https://alan-j-hu.github.io/writing/pattern-matching.html and https://contificate.github.io/compiling-pattern-matching/
- There's a Rust implementation of this algorithm, though it doesn't perform exhaustiveness checking.
- Warnings for pattern matching. This is just about producing warnings/errors for e.g. non-exhaustive patterns. Similarly painful to understand as the previous paper (i.e. I gave up).
- The Implementation of Functional Programming Languages. This book has a chapter on pattern matching, but I gave up on it.
A recent-ish (as of 2022) Rust version that supports the 2021 edition (though I think the 2018 edition should also work).
Each algorithm is implemented as a library, and come with a set of unit tests
that you can run using cargo test.
The code in this repository is licensed under the Unlicense. A copy of this license can be found in the file "LICENSE".