CODEWITHSUNDEEP
compiler-constructionerlangpattern-matching
deepblue
deepblue

Reputation: 8596

How does the Erlang compiler implement pattern matching?

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.

Upvotes: 35

Views: 6920

Answers (4)

rvirding
rvirding

Reputation: 20916

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.

Upvotes: 36

Norman Ramsey
Norman Ramsey

Reputation: 202505

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).

Upvotes: 14

Hynek -Pichi- Vychodil
Hynek -Pichi- Vychodil

Reputation: 26121

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.

Upvotes: 21

cthulahoops
cthulahoops

Reputation: 3835

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}]}.

Upvotes: 2

Related Questions