enlightware / enlightware/ferlium

Generalised match following Maranget 2008

Open
#13 0 comments 0 reactions 0 assignees View on GitHub
control flow hard
Dominant language
Rust
Stars
14
Forks
2
PR merge metrics
No merged PRs in 30d

Description

Ferlium currently implements a simplified and limited match operator, that can match either only values or only variants.

Having a generalized version is both very useful and and a significant piece of work (a compiler in the compiler). Some resources:
- "[Compiling pattern matching to good decision trees, from L. Maranget, 2008](http://moscova.inria.fr/~maranget/papers/ml05e-maranget.pdf)", the recognize academic paper on the question. There exists a [partial Rust implementation](https://github.com/SomewhatML/match-compile), some blog posts [here](http://compiler.club/compiling-pattern-matching/) and [here](https://alan-j-hu.github.io/writing/pattern-matching.html).
- [A comparison of various approaches in Rust](https://github.com/yorickpeterse/pattern-matching-in-rust).

The technique becomes valuable once Ferlium supports nested patterns, tuple/record/variant destructuring in match arms, better exhaustiveness checks, or useless-clause diagnostics. The main prerequisite is introducing an internal typed pattern IR that can represent nested patterns; the current PatternVar only supports named bindings and `..`.

## Implementation plan

1. Add an internal match-pattern IR capable of representing wildcards, bindings, literals, variants, tuples, and records.
2. Translate the existing parser-level Pattern AST into this IR, initially preserving current behavior and syntax.
3. Implement a simple pattern-matrix compiler:
- rows = match arms;
- columns = tested occurrences/subterms;
- specialize on constructors/literals;
- build default matrices for wildcards/bindings;
- recurse into a decision tree.
4. Lower the decision tree to existing HIR primitives:
- Case for branching;
- ExtractTag for variants;
- Project / FieldAccess for payloads;
- EnvStore / EnvLoad for bindings.
5. Start with a simple column-selection heuristic, such as first refutable column. Add Maranget-style necessity heuristics later once correctness is stable.
6. Keep exhaustiveness and useless-clause diagnostics as a separate follow-up. Maranget 2008 helps with efficient decision trees; full diagnostics need usefulness/exhaustiveness analysis on top.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.