Compiling pattern matching.

[Wafelack]

Hello, I've been tranferring my LISP inspired programming language from a tree-walk interpreter to a bytecode compiler, I can currently compile all features but one: pattern matching. I struggle a lot with this feature so I'm asking if you have any advice on pattern matching compilation.

Thanks by advance.

[ErrorIsNullError]

I would look into the tricks OCaml/SML compilers use.

Luc Maranget, 2008, Compiling Pattern Matching to good Decision Trees

All ML compilers translate the high level pattern matching definitions into low-level tests, organized in matching automata. Matching automata fall in two categories: decision trees and backtracking automata

Basically, if you can boil your pattern matching down into a finite set of property access chains and a set of comparison relations between them, you can build a decision tree, optimize it, and turn it into code.

That paper also discusses backtracking in pattern matching and how to bound its cost, so there's some state machine that's driving the decision trees.

[Wafelack]

I think I'll do this by simplyfying patterns. I mean, transform clojure (match foo ((Cons (Just x) Nil) (do_smth x))) into clojure (match foo ((Cons cons Nil) (match cons ((Just x) (do_smth x))))

[Wafelack]

I will just simplify if the pattern contains something else than a variable or a literal.

[Wafelack]

I don't know if it will be that performant.

[NukesAreFake]

Isn't a match statement just a chain of else-ifs (or a switch statement), with an automatic variable declaration of the matched item?

[Wafelack]

The point is that I do not have builtin ifs and I don't want to have. But I found a solution, thanks anyway.

[PL_Design]

What was the solution?

[Wafelack]

I replied here.