What data structure is used to implement pattern match?

Question

In the book "Programming Elixir", the author states that "Even if you have thousands of clauses, pattern matching used in this way is fast. Matching a map or struct is O(log n).".

I wonder what data structure is used to implement pattern match in Elixir such that the time complexity if O(log n).

Is it some kind of tree structure?

I suppose it is the Kernel https://hexdocs.pm/elixir/Kernel.html#content — GavinBrelstaff, Jun 24 '20 at 05:55
Does this answer your question? [pattern matching - implementation](https://stackoverflow.com/questions/586362/pattern-matching-implementation) — Adam Millerchip, Jun 28 '20 at 03:33
@AdamMillerchip Thanks for finding a related question. But I think they are not identical, Erlang and Elixir are not the same language. — satoru, Jun 28 '20 at 04:20
Elixir delegates to Erlang for pattern matching. Added an answer. — Adam Millerchip, Jun 28 '20 at 04:58

score 2 · Answer 1 · answered Jun 24 '20 at 07:58

2

The implementation of pattern matching differs across functional languages but in most of the cases it boils down to decision trees.

Luc Maranget paper "Compiling Pattern Matching to Good Decision Trees" gives a pretty good in depth description of how pattern matching can be implemented into decision trees.

Another very good resource in merit is the book "The Implementation of Functional Programming Languages" by Simon Peyton Jones.

answered Jun 24 '20 at 07:58

noxdafox

14,439
4
33
45

Joe said a lot in his talks that the pattern matching is implemented based on the one in prolog. – Daniel Jun 24 '20 at 17:16
Robert Virding, who wrote Erlang's pattern matching, which Elixir uses, [states](https://stackoverflow.com/questions/586362/pattern-matching-implementation#comment992425_642896) that Erlang uses the algorithms from the SPJ book. – Adam Millerchip Jun 28 '20 at 03:40

score 1 · Accepted Answer · answered Jun 28 '20 at 04:58

Elixir delegates to Erlang's pattern matching.

Looking through Elixir's source code, written in Erlang, here is the code that seems to be handling matching:

elixir_clauses.erl:

match(Fun, Expr, #{current_vars := Current, unused_vars := {_, Counter} = Unused} = AfterE, BeforeE) ->
  #{
    context := Context,
    prematch_vars := Prematch,
    current_vars := {Read, _}
  } = BeforeE,

  CallE = BeforeE#{
    context := match,
    prematch_vars := {Read, Counter},
    current_vars := Current,
    unused_vars := Unused
  },

  {EExpr, #{current_vars := NewCurrent, unused_vars := NewUnused}} = Fun(Expr, CallE),

  EndE = AfterE#{
    context := Context,
    prematch_vars := Prematch,
    current_vars := NewCurrent,
    unused_vars := NewUnused
  },

  {EExpr, EndE}.

This is Erlang code, so here Elixir is delegating to Erlang's = operator. As this is the case, Robert Virding (the author of Erlang's pattern matching code)'s answer to this related Erlang question is useful:

A very good description of compiling pattern matching is given in "The implementation of functional programming languages" by Simon Peyton Jones. It is a bit old but a very good book. It also contains, amongst other things, a description of compiling list comprehensions.

The Erlang compiler uses both of these algorithms from the book.

What data structure is used to implement pattern match?

2 Answers2