How Erjang compiles pattern matching

krestenkrab edited this page Sep 13, 2010 · 13 revisions

Well, that’s easy. The Erlang compiler does most of the work of optimizing matching, emitting specialized instructions to do pattern matching. All Erjang has to do is just provide implementation of those as part of the translation to Java bytecode.

Let me show an example.

The Erlang code

ins_opts([Opt | Opts], Opts2) ->
    ins_opts(Opts, ins_opt(Opt, Opts2));
ins_opts([], Opts2) -> Opts2.

Which in turn becomes this beam code (slightly edited to make it more readable). You can see clearly how erlc has done all the work for me. Hint: {x,0} and {x,1} are “registers” that contain the arguments on entry.

{function, ins_opts, {nargs,2}}.
  {label,264}.
    {test,is_nonempty_list,{fail_label,265},[{x,0}]}.
    {get_list,{x,0},{x,0},{y,0}}.
    {call,2,ins_opt}.
    {move,{x,0},{x,1}}.
    {move,{y,0},{x,0}}.
    {call_last,2,ins_opts,1}.
  {label,265}.
    {test,is_nil,{fail_label,263},[{x,0}]}.
    {move,{x,1},{x,0}}.
    return.
  {label,263}.
    {func_info,{atom,appmon_info},{atom,ins_opts},2}.

compiles to this in Java as shown below. All terms are instances of classes like EInt32, ETuple, ECons and so on, which all implement a set of virtual methods such as test_is_nonempty_list(). Only if it is a cons cell will it return non-null.

public static EObject ins_opts___2(EProc eproc, EObject arg1, EObject arg2)
{
   tail: while(true) {
    ECons cons;
    if((cons = arg1.as_nonempty_list_or_null()) != null) {
        // extract list
        EObject hd = cons.head();
        EObject tl = cons.tail();
        // call ins_opt/2
        EObject tmp = ins_opt___2(eproc, hd, arg2);
        // self-tail recursion
        arg1 = tl;
        arg2 = tmp;
        continue tail;
    } else if ((arg1.as_nil_or_null()) != null) {
        return arg2;
    }
    throw ERT.func_info(atom_appmon_info, atom_ins_opts, 2);
  }
}