How does the Erlang compiler implement pattern matching?

Question

I am wondering how pattern matching is usually implemented. for example in Erlang do you think its implemented at the byte-code level( there's a byte-code for it so that its done efficiently) or is it generated as a series of instructions (series of byte-codes) by the compiler?

It is such a useful thing that I just have to put it into a toy language I am building.

score 36 · Answer 1 · edited Oct 18 '20 at 11:54

36

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.

edited Oct 18 '20 at 11:54

2240

1,547
2
12
30

answered Mar 13 '09 at 14:11

rvirding

20,848
2
37
56

2

thanks. I've had this book downloaded for a while now but never had the time to read it. how do you know that Erlang uses algorithms from it? – deepblue Mar 14 '09 at 07:23
13

Sorry for not replying earlier, much earlier. The reason I know is that I implementented compiling pattern matching for the current compiler and this is where I took the algorithm from. – rvirding Jul 23 '09 at 15:14
3

that works ;). thanks for working on erlang, its a bit odd but definitelly a breath of fresh air. made my life a better place for sure – deepblue Sep 30 '10 at 00:41
@rvirding Does that include the pattern matcher for binary data? – Martin Berger Feb 04 '15 at 00:43
2

@MartinBerger The pattern matcher for binary data was added later but is part of compiling patterns. It is a little more complex than matching other data types as the patterns can overlap much more in many different ways, for example you can match against different size integers at the start of the binary. – rvirding Feb 05 '15 at 01:25
@rvirding Thank you. There is an old paper [Efficient manipulation of binary data using pattern matching.](http://user.it.uu.se/~pergu/papers/JFP_06.pdf) that describes an Erlang pattern matcher for binary data. Is this still what's in the current compiler? – Martin Berger Feb 05 '15 at 08:21

Hynek -Pichi- Vychodil · Accepted Answer · 2009-02-25T16:35:26.347

You can see what happen if compile some code

-module(match).
-export([match/1]).
match(X) -> {a,Y} = X.

When you want see how looks like core

> c(match, to_core).

or

$ erlc +to_core match.erl

result is

module 'match' ['match'/1,
                'module_info'/0,
                'module_info'/1]
    attributes []
'match'/1 =
    %% Line 3
    fun (_cor0) ->
        case _cor0 of
          <{'a',Y}> when 'true' ->
              _cor0
          ( <_cor1> when 'true' ->
                primop 'match_fail'
                    ({'badmatch',_cor1})
            -| ['compiler_generated'] )
        end
'module_info'/0 =
    fun () ->
        call 'erlang':'get_module_info'
            ('match')
'module_info'/1 =
    fun (_cor0) ->
        call 'erlang':'get_module_info'
            ('match', _cor0)

If you want see asm code of beam you can do

> c(match, 'S').

or

$ erlc -S match.erl

and result

{module, match}.  %% version = 0

{exports, [{match,1},{module_info,0},{module_info,1}]}.

{attributes, []}.

{labels, 8}.


{function, match, 1, 2}.
  {label,1}.
    {func_info,{atom,match},{atom,match},1}.
  {label,2}.
    {test,is_tuple,{f,3},[{x,0}]}.
    {test,test_arity,{f,3},[{x,0},2]}.
    {get_tuple_element,{x,0},0,{x,1}}.
    {test,is_eq_exact,{f,3},[{x,1},{atom,a}]}.
    return.
  {label,3}.
    {badmatch,{x,0}}.


{function, module_info, 0, 5}.
  {label,4}.
    {func_info,{atom,match},{atom,module_info},0}.
  {label,5}.
    {move,{atom,match},{x,0}}.
    {call_ext_only,1,{extfunc,erlang,get_module_info,1}}.


{function, module_info, 1, 7}.
  {label,6}.
    {func_info,{atom,match},{atom,module_info},1}.
  {label,7}.
    {move,{x,0},{x,1}}.
    {move,{atom,match},{x,0}}.
    {call_ext_only,2,{extfunc,erlang,get_module_info,2}}.

As you can see {test,is_tuple,..., {test,test_arity,..., {get_tuple_element,... and {test,is_eq_exact,... are instruction how this match is performed in beam and it's transformed directly to byte-code of beam.

Erlang compiler is implemented in Erlang itself and you can look at each phase of compilation in source code of compile module and details in depend modules.

wonderful answer, lots of great info here (especially the compilation directives). thank you — deepblue, Feb 25 '09 at 21:26

score 14 · Answer 3 · answered Feb 26 '09 at 03:39

14

If you want to build your own pattern matcher there is a paper by Scott and Ramsey and a paper by Luc Maranget which both describe how to compile patterns to efficient decision trees (aka nested switch statements).

answered Feb 26 '09 at 03:39

Norman Ramsey

198,648
61
360
533

great. appreciate it, looks like lots of useful stuff – deepblue Feb 26 '09 at 14:27

score 2 · Answer 4 · answered Feb 25 '09 at 16:23

The best thing I can suggest is to compile up some test functions and have a look at the generated code.

erlc -S test.erl

generates test.S which is fairly readable.

To answer the question, pattern matches are built up in an efficient way from more primitive operations. Here's part of the code from a function clause matching {X, [H|T]}.

{test,is_tuple,{f,1},[{x,0}]}.
{test,test_arity,{f,1},[{x,0},2]}.
{get_tuple_element,{x,0},0,{x,1}}.
{get_tuple_element,{x,0},1,{x,2}}.
{test,is_nonempty_list,{f,4},[{x,2}]}.

How does the Erlang compiler implement pattern matching?

4 Answers4

Linked