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.

Answer 1

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.

Answer 2

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.