jlouis' Ramblings

Musings on tech, software, and other things

Solving the Go Challenge #1 in Erlang

The first Go challenge is over. So by now, I can take my Erlang solution and write about how you would go around solving the challenge in Erlang. I’m deliberately skipping some details in Erlang, so don’t expect me to explain all the nitty-gritty parts. I do hope a reader with some programming language experience can follow along, even if you have had very little exposure to functional programming.

The goal of the challenge is to implement a parser for a binary format. The binary format encodes drum patterns for a digital drum machine, which are highly popular in many genres of music. The goal is then to produce an output which is a textual representation of the binary format:

pattern_1.splice
Saved with HW Version: 0.808-alpha
Tempo: 120
(0) kick     |x---|x---|x---|x---|
(1) snare    |----|x---|----|x---|
(2) clap     |----|x-x-|----|----|
(3) hh-open  |--x-|--x-|x-x-|--x-|
(4) hh-close |x---|x---|----|x--x|
(5) cowbell  |----|----|--x-|----|

The task requires two steps. First, once must reverse-engineer the binary patterns in the splice format. Next, the format must be parsed, and finally the parsed data must be rendered.

Erlang is built to handle binary protocols, and hence parsing the data in Erlang is going to be pretty easy. Comparing this solution to some of the Go solutions is going to be instructional and explains how different programming languages solve different problems. I’ve kept this solution under covers while the contest were running, mostly because I didn’t want to explain the format. Half the fun of the challenge is to figure out the format used, and then implement that in Go. The solution I have here is close to idiomatic Erlang. One could perhaps improve a thing or two, if one wanted to put the code into a larger project. But everything is a complete solution in about 40 lines of Erlang code, excluding test-code.

Testing

First we set up a function which returns test data:

test_table() ->
   [{"pattern_1.splice",
     "Saved with HW Version: 0.808-alpha\n"
        "Tempo: 120\n"
        "(0) kick |x---|x---|x---|x---|\n"
        "(1) snare |----|x---|----|x---|\n"
        "(2) clap |----|x-x-|----|----|\n"
        "(3) hh-open |--x-|--x-|x-x-|--x-|\n"
        "(4) hh-close |x---|x---|----|x--x|\n"
        "(5) cowbell |----|----|--x-|----|\n"},
       {"pattern_2.splice",
        "Saved with HW Version: 0.808-alpha\n"
        "Tempo: 98.4\n"
        "(0) kick |x---|----|x---|----|\n"
        "(1) snare |----|x---|----|x---|\n"
        "(3) hh-open |--x-|--x-|x-x-|--x-|\n"
        "(5) cowbell |----|----|x---|----|\n"},
        ...].

Returned is a list of pairs [{FileName, Expected}, …] where the file name is the binary file to read, and the pattern is a textual representation of the correct output. This allows us to implement a system which uses the list as a table-driven-test and verify every output is correct. It is followed by a simple function to test a single test case:

t({File, Expected}) ->
      {ok, Dat} = file:read_file("priv/fixtures/" ++ File), %1
      Output = iolist_to_binary(render(p(Dat))), %2
      Output = list_to_binary(Expected), %3
      ok.

This uses Erlangs binding rules in two ways. The reading of the binary file in (1) asserts that the output is {ok, Dat}. If the file read returns an error, this leads to a crash of the code. This is a common pattern in Erlang in which failures crashes the program. We then install other strategies for restarting failing parts of a program later. In (2) we use the p/1 function to parse the file contents, then send it to the render/1 function and finally converts its output into binary data. We stuff this into the value Output. Finally, the (3) line attempts to stuff the expected output into the same value. The binding semantics of Erlang takes this as an assertion. That is, if the expected output of (3) doesn’t match the output of (2); then the code will crash.

This is in contrast to many programming languages which would overwrite the value Output. But languages like Erlang and Prolog uses this to define an assertion. It is an often used trick in Erlang, since it avoids having to write assertion checks for a lot of code. In particular I don’t need the common

if err != nil { ... }

which is common in Go programs.

We can now write the test-driver for the system:

test() ->
      lists:foreach(fun t/1, test_table()).

Testing the code amounts to call our t/1 function on every data point in the test_table list. If this code doesn’t crash, our tests passed. If the code crashes, Erlang returns a structural error with all the information we need to figure out what is wrong. Larger Erlang programs usually employ one the test systems Eunit or Common Test. But for a simple program, it is somewhat simpler just to use a simple function call to make sure things work as they should.

Parsing

Now we are ready to implement the the parser, which we do in the p/1 function. The format contains an identifying header, followed by some global information about the drum pattern and then followed by the instruments present in the drum pattern. We will have to parse these in order to handle the format and for the sake of simplicity we will parse the data and represent it internally as an abstract syntax tree. Then this tree will be fed to the rendering function later in order to render data in the textual format. In principle we are writing a compiler from the binary format to the textual format.

An atom() intermezzo is needed to explain a concept which may be helpful in the following. In Erlang, an unquoted alphanumeric identifier starting with an upper-case character, such as “Payload” is a variable. An alphanumeric starting with a lower-case character such as “instrument” is an atom. Atoms are interned by representing them as integers in the VM. That is, when the file is loaded, each atom is mapped to an integer, picking a new integer if the atom has not been seen before. If the atom already occurs in the VM, the designated number for that atom is used of course. They are used as “tags” in programs to discriminate data, and in Erlang they are also used to represent module names and function names in some situations.

The advantage of atoms are their very quick equality check, because one doesn’t have to walk through a costly string comparison. It is so-to-speak paid for in advance when the module is loaded into the system (or when foreign data enters the VM node).

And now, back to parsing…

Parsing the identifying header is the following function:

p(<<"SPLICE", Len:64/integer, Payload:Len/binary, _/binary>>) ->
    p_data(Payload).

The function defines what is called a binary pattern match where the function expects binary data and then the function proceeds by “destructuring” (picking apart) the binary data according to the specfication given. This specification says:

  • First comes 6 bytes with ascii codes“SPLICE”
  • Next comes a 64-bit Big-Endian integer which we parse as the value Len
  • Next comes the Payload, which is Len bytes and are binary data.
  • Finally comes more data, which we disregard. This is needed because pattern 5 includes errornous data in the end and we have to match it.

Any parsing error crashes the function. If we manage to parse the data, we send the Payload on to the p_data/1 function:

p_data(<<HWStr:32/binary, Tempo:32/float-little, Data/binary>>) ->
    Instruments = instruments(Data),
    #{ format => splice, hardware_string => trim_hwstring(HWStr),
     tempo => Tempo, instruments => Instruments }.

Again, we match the expected content. First comes 32 bytes of hardware string identification information. Then comes a 32 bit IEEE 754 Floating Point value in Little-Endian form. The rest is Instrument data, which we parse in a helper function called instruments/1. The return value is a map containing the data we found in the parse. The language is dynamic and we don’t have to predeclare the contents of the map, but we simply just create one and add the necessary fields. The function trim_hwstring/1 is used to get rid of the trailing 0'es which is in the end of the hardware ID string:

trim_hwstring(B) ->
    Str = binary_to_list(B),
    string:strip(Str, right, 0).

Only two functions remain. The first one is decoding each instrument line:

instruments(<<Num:8/integer, L:32/integer, Name:L/binary,
                Pattern:16/binary, Rest/binary>>) ->
    [{instrument, Num, Name, pattern(Pattern)} | instruments(Rest)];
  instruments(<<>>) ->
    [].

Here, we have two possible matches. The first match is the one that picks an instrument apart. We expect:

  • An integer in 8 bits
  • A length in a 32 bit Big-Endian integer
  • A name, whose length was just given
  • A pattern, which is 16 bytes of pattern data
  • The “rest” or remainder of the binary data.

We then create a tuple {instrument, Num, Name, Pat} where the ‘instrument’ part is an identifying atom/symbol we can use later to discriminate instruments from other data. The function recurses on the remainder of the data (the call to instruments(Rest)) and then when that call returns, it front-appends the current instrument to the list being built.

The other variant identifies «» which is the empty binary. If there are no instruments to parse, we return [] which is the empty list. The recursion here then gradually builds up a list of instruments by recursing to the end of the instrument data and then building up the list of instruments “in reverse”.

We only need to parse patterns:

pattern(<<P1:4/binary, P2:4/binary, P3:4/binary, P4:4/binary>>) ->
      [binary_to_list(P) || P <- [P1, P2, P3, P4]].

A pattern are split into 4 groups with 4 bytes in each. We then use a list-comprehension, to convert each pattern binary into a list of bytes. Read: for each P in the list [P1, P2, P3, P4] replace P with binary_to_list(P). This returns a list(list(byte())) which will come in handy when we want to render output.

As an example, let us run this on pattern 1 and print its output. Erlang has a REPL which comes in handy for such exploratory tests:

3> {ok, Pattern1} = file:read_file("priv/fixtures/pattern_1.splice").
{ok,<<83,80,76,73,67,69,0,0,0,0,0,0,0,197,48,46,56,48,56,
      45,97,108,112,104,97,0,0,...>>}
4> decoder_dm:p(Pattern1).
#{format => splice,
  hardware_string => "0.808-alpha",
  instruments => [{instrument,0,<<"kick">>,
               [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]]},
   {instrument,1,<<"snare">>,
               [[0,0,0,0],[1,0,0,0],[0,0,0,0],[1,0,0,0]]},
   {instrument,2,<<"clap">>,
               [[0,0,0,0],[1,0,1,0],[0,0,0,0],[0,0,0,0]]},
   {instrument,3,<<"hh-open">>,
               [[0,0,1,0],[0,0,1,0],[1,0,1,0],[0,0,1,0]]},
   {instrument,4,<<"hh-close">>,
               [[1,0,0,0],[1,0,0,0],[0,0,0,0],[1,0,0,1]]},
   {instrument,5,<<"cowbell">>,
               [[0,0,0,0],[0,0,0,0],[0,0,1,0],[0,0,0,0]]}],
  tempo => 120.0}
5>

This looks about right. We now have the parser in 16 lines of code and can begin focusing on the next part, the renderer.

Rendering

For rendering, we need a couple of helper functions:

conv(Pat) -> [render_c(C) || C <- Pat].

render_c(0) -> $-;
  render_c(1) -> $x.

These two functions are helpers which are going to be used to convert a pattern such a [0,0,1,0] into [45, 45, 120, 45] which are the ASCII bytes for “ — x-”. Again, we use a list comprehension to work over the list and converting each element in the list.

We also need to handle the tempo, and in the output, a floating point value such as 120.0 is to be rendered as an integer 120 with no trailing 0. There is no such function in Erlang by default, so we test if the result is close to 0 and then convert the output into an integer if that is the case:

format_float(F) ->
      case abs(F - trunc(F)) of
          K when K < 0.0001 -> integer_to_list(trunc(F));
          _ -> float_to_list(F, [{decimals, 1}, compact])
      end.

And now, we are ready for the rendering function. Before that however, I need to have another little intermezzo about iolists in Erlang.

The iolist() datatype is a way to output data in Erlang. It is an inductively generated datatype, where the type itself is part of the type. The specification is

-type iolist() :: list(0..255 | binary() | iolist()).

which one can read as “iolists are defined as lists consisting of 3 alternate things: integers in the range 0..255, binaries, and iolists themselves”. The last part makes the definition inductive such that iolists are really trees built out of lists. They are convenient because you can avoid having to explicitly concatenate strings in many situations. Say you want to quote a string, which can be done by writing the following function:

quote(String) -> [$", String, $"].

The notation $X evaluates to the ascii code for the symbol X. And this forms a quoted string without ever copying String. Since all terms in Erlang are persistent (immutable), no risk is had by this construction.

Many typical output points in Erlang programs accepts iolists() as well as other data. Writing to a socket or file for instance. This is highly convenient as you often avoid having to manually concatenate data, but can just build up the iolist() structure and then have the system itself handle the concatenation later on. It also means the Erlang VM is free to optimize data output. For instance by pre-calculating the size needed for the concatenated target and by the use of the writev(2) system call to do “gather output” writing.

The render function of the drum machine decoder uses iolists(). It also employs another trick: each parsed element has a unique representation. Hence, we can simply analyse an element and then recurse deeper down into our abstract syntax tree. The render function always returns iolists() so we can “plug in” those into a larger iolist. The test function above then aptly uses the iolist_to_binary/1 function to convert the iolist into a binary we can use to test against the expected output.

render(#{ format := splice, tempo := Tempo,
          instruments := Instruments, hardware_string := HWS}) ->
    ["Saved with HW Version: ", HWS, $\n,
     render({tempo, Tempo}), $\n,
     render(Instruments)];
render(List) when is_list(List) ->
    [render(Elem) || Elem <- List];
render({tempo, T}) ->
    ["Tempo: ", format_float(T)];
render({instrument, N, Name, Pattern}) ->
    Prefix = io_lib:format("(~B) ~s\t", [N, Name]),
    Grid = render({pattern, Pattern}),
    [Prefix, Grid, $\n];
render({pattern, [P1, P2, P3, P4]}) ->
    [$|, conv(P1), $|, conv(P2), $|, conv(P3), $|, conv(P4), $|].

This is all of the renderer. We pattern match on different possible inputs and then handle them by outputting something which is right for that input. Two tricks are being used to make discrimination explicit. Rendering of the tempo calls recursively with {tempo, Tempo} and pattern rendering calls recursively with {pattern, Pat}. This ensures each input term is unique and thus we can employ the same rendering function for all cases.

In languages with static type systems, such a function must often be broken into several different small functions. And it is also advisable to do so in Erlang had the rendering function been larger. For a renderer this small, however, it is fine to keep functions close to each other.

We are at 39 lines and we are done. We can exploratively test our code by noting that our pattern from above was the output of shell command #4 and then use this as an input in a later command:

5> io:format("~s", [iolist_to_binary(decoder_dm:render(v(4)))]).
  Saved with HW Version: 0.808-alpha
  Tempo: 120
  (0) kick        |x---|x---|x---|x---|
  (1) snare       |----|x---|----|x---|
  (2) clap        |----|x-x-|----|----|
  (3) hh-open     |--x-|--x-|x-x-|--x-|
  (4) hh-close    |x---|x---|----|x--x|
  (5) cowbell     |----|----|--x-|----|
  ok

Notes

  • There is very little copying going on. The parsed binary is never copied, but match contexts are generated when recursing down the data. These are somewhat equivalent to a slice in Go (or Standard ML). Large parts of the output is never copied, since we are using iolists. Rather, pointers to the underlying persistent data is used by the VM.

  • Pattern matching is very efficient. A pattern match compiler analyzes the patterns and compiles alternatives into jump tables and/or if analysis with binary split. Further, both positive and negative match information is propagated such that you don’t have to “start over” for each possible match but can rely on data which has already been successfully matched or rejected in earlier patterns.

  • There is no error handling code whatsoever. This is typical of Erlang programs. An error returns a structural error which can be analyzed by Erlang programs or printed out. It is common Erlang systems have error loggers which handles crashes and writes out the structured error to disk for post-mortem analysis. The system as a whole doesn’t crash because Erlang is a truly concurrent environment where one process is (logically) isolated from other processes. Hence, the system is always able to clean up from a process crash with no trailing garbage or inconsistent state left behind.

  • It took about 30 minutes to come up with this solution in programming time. It is standard Erlang code, without magic tricks or things you would only do to act clever. In other words, the implementation is the straightforward one from an experienced Erlang programmer.

  • The implementation is reasonably speedy and clocks in at 13 microseconds on my machine for parsing pattern 1. There are some optimizations possible, but I don’t think it is necessary. Go should be roughly 5–10 times faster on this problem, but so should e.g., OCaml.

  • The tests are directly portable to Common Test, which uses the same assertion method as I used above. It is just that Common Test requires more boilerplate, as in Go’s testing package.