How pattern matching work in the background?

Hello, My question is related to pattern matching, I am new to elixir and while learning it I went through this awesome thing called pattern matching in Elixir using (=). We can do pattern matching with lists, maps, structs, tuples, literals…, Now I know how to do pattern matching and how to achieve solutions using it. But I am not able to imagine how pattern matching works in the background. Like how the compiler reacts to it. Did it first look for the data structure type and then go for the assignment or calculation… Or is there some other kind of control flow.


From Erlang docs.

In a pattern matching, a left-hand side pattern is matched against a right-hand side term. If the matching succeeds, any unbound variables in the pattern become bound. If the matching fails, a run-time error occurs.

Elixir will do the same… It will try to match left and right and if it can, all unbounds will be bounded.


If you really want to dig quite deep into how it actually works, the algorithm that the erlang implementation uses is based on the one described in the book The implementation of functional programming languages by Simon L. Peyton Jones


Also, the compiler will do some optimizations at compile time:


Thank you @dorgan for the help. I will go through this book.

Keep in mind that it’s a quite “into the weeds” book :slight_smile:
The explanations you got above are good ones. Ultimately it boils down to a lot of checks and branching in the final code, and creating bindings for any unbound variable in the pattern. Unless you want to implement it yourself, by all means those explanations are good enough :slight_smile:


It is a very good book. It’s chapter on pattern matching was a base for our implementation in the Erlang compiler, and we took the first implementations of list comprehensions from another chapter in the book.