Records in Erlang

One of the things I discovered since writing part one of my Erlang introduction is that Erlang has grown a lot over the last few years. For example, the idiom of tagged tuple as a way of creating a record-like structure has been coded into the language. There is, unfortunately, a bit of a catch. They aren't really added to the language. Instead, there's a pre-processor in Erlang, and records
are defined by translation in the pre-processor. This to me typifies one of the less attractive
attributes of Erlang: much of Erlang has a very ad-hoc flavor to it. There are important high-level features - like record data and modules - which aren't really entirely part of the language. Instead, they're just sort of spliced in however it was easiest for the implementors to cram 'em in. And there are other things that were added to later versions of the language that, while first class, are awkward - like the "fun" prefix for first-class functions.

The effect of that kind of thing is mainly syntactic. The implementation is good enough that
even though things like records are really pre-processor constructs, they feel almost as
if they're built-ins.

Anyway - let's take a look at records.

As I mentioned in the first Erlang post, the basic data type idiom of Erlang is
based on tuples. Typically, to represent a data type, you create a tuple whose first element
is an atom which identifies the type of the tuple.

That's exactly what the record facility does. You define a record type, and it's built using
a tuple whose first element is the atom which names the record type. The rest of the entries of a record tuples are the fields of the record, which are represented by alternating field names (as atoms) and field values. So, for example, if we
wanted to define a binary tree like the following Haskell:

data Tree a = Node (Tree a) (Tree a) | Leaf a

sample = Node (Node (Leaf 1) Leaf 2) (Leaf 3)

Would be implemented as something like the following in tuples in Erlang:

Sample = {node, 
           left, {node, 
                   left, {leaf, value, 1},
                   right, {leaf, value, 2}},
           right, {leaf, value, 3}}

That's obviously pretty ugly, and pretty laborious to code. The record-feature in the meta-language makes it much more convenient:

-record(node, {left,right})
-record(leaf, {value})

Sample = #node{left=#node{left=#leaf{value=1},
                          right=#leaf{value=2}},
               right=#leaf{value=3}}

A record is declared with a pre-processor form "-record". The first parameter to the form is
the atom naming the record type; the second parameter is a tuple of the record field names. Once a record type is defined, you can create an instance of it with "#" followed by the record type name, and a set of field assignments inside of curly braces.

Like everything in Erlang, the way to manipulate records is by pattern matching:

#node{left=L,right=R} = Sample

will assign "L" to "#node{left=#leaf{value=1},right=#leaf{value=2}}", and "R" to "#leaf{value=3}".

Aside from the weirdness of the meta-language division, the sequential part of Erlang is very
straightforward. It's a classic eager functional language. Programs in Erlang are quite similar to
programs in a language like Scheme, except for syntax, and the syntax is OK; sort-of a bastard offspring
of Lisp and Prolog, which isn't an awful thing.

To give you a bit of flavor, here's a simple bit of binary search tree code in
Erlang:

-module(bt).
-export([insert/2]).

-record(node,{value,left,right}).

insert(#node{value=N,left=L,right=R}, V)  when N > V ->
   #node{value=N, left=insert(L,V), right=R};
insert(#node{value=N,left=L,right=R}, V) ->
   #node{value=N, left=L, right=insert(R,V)};
insert(none, V) ->
   #node{value=V, left=none, right=none}.

fetch(#node{key=K, value=V, left=L, right=R}, K) ->
V;
fetch(#node{key=K, value=V, left=L, right=R}, Target) when K > Target ->
fetch(L, Target);
fetch(#node{key=K, value=V, left=L, right=R}, Target) ->
fetch(R, Target);
fetch(none, Target) -> none.

It's very straightforward functional code. It's almost exactly the same way that it would be written
in ML (my favorite eager functional languages), and very close to how it would be written in Haskell. It is a bit verbose - but that's because I'm not using Erlang to its full advantage. The code can be
simplified a bit by using record field access and update syntax.

If you only want to access one field of a record, there's a shorthand syntax that's more convenient
then writing out a full pattern match to get at one field: if Sample is a variable
containing a record, then Sample#node.left gets the value of the field named "left" of the
record type "node". (If you use this syntax with the wrong record type, you'll get a run-time error.)

Similarly, there's a syntax for updating a record - that is, creating a new record that's the same
as an old record except for a couple of modified fields: Sample#node{right=#leaf{4}} will
create a new tuple of type "node", with the same left value as Sample, but with a different right
value.

So, using that, we can modify "insert", so that we don't need to write the full record
construction syntax. Instead, we could write insert the following way (called "sinsert" for "simpler insert"):

sinsert(none, Newkey, Newval) -> 
   #node{key=Newkey, value=Newval, left=none, right=none};
sinsert(Node, Newkey, Newval) when Node#node.key > Newkey ->
Node#node{left=sinsert(Node#node.left, Newkey, Newval)};
sinsert(Node,Newkey, Newval) -> 
Node#node{right=sinsert(Node#node.right, Newkey, Newval)}.

For this kind of straightforward data structure programming, Erlang is a really pleasant language.
The record system is very nice, flexible, and easy to work with. The strong pattern matching facility of the language is flexible enough that for an impressively large number of functions, you don't need to write any control structure code beyond patterns and "when" guards. I just wish it wasn't in the
meta-syntax - when I get around to explaining the way that a large Erlang program is broken into multiple files, you'll see a bit of why I'm unhappy that it's meta.

In general, my impression thus far playing with Erlang (which I've used for a bit more complicated
stuff than I've included in this post) is that it's very easy to read and write, and it behaves in a
very intuitive fashion. I definitely find it easier to pick up as a beginner than I did Haskell, but I think that's mainly because I find eager evaluation to be easier to predict than lazy. For this kind of basic data structure programming, I think it's a toss-up with Haskell: I prefer Haskell's
strong types, but Erlang's eager semantics make it a whole lot easier to understand the efficiency
tradeoffs between different implementation strategies.

Before moving on, I'll toss in some information on the bit of Erlang that I really hate.
Aside from using a preprocessor for implementing meta-language features like records, Erlang's
preprocessor also has a macro facility that's modeled on the macro system from the C preprocessor.
Like cpp, it's ugly as all get-out, and it's bloody dangerous to use. It's a ghastly
thing, but it's there, and a fair bit of Erlang code uses it. (Gag.) One minor redeeming feature of the
macro system is that at least uses of macros are clearly marked - unlike C or C++, you can clearly tell a macro invocation from a function invocation.

To define a preprocessor macro, you use:

-define(name, replacement)

Or, for a macro with parameters:

-define(name(p1, p2, p3), replacement)

For example:

-define(TIMEOUT, 2500)
-define(Double(X),2*X)

Then you can use the macros by prefixing the name with a "?": ?Double(10).

Naturally, if you've got a hideous preprocessor, you can't escape using it for conditional compilation. So the Erlang preprocessor includes "-undef", "-ifdef", "-ifndef", "-else", "-endif", each
of which means pretty much the same thing as the corresponding C preprocessor directive.

Once again, gag.

Anyway - next post, I'll go into more depth about control structures in Erlang, and introduce one of the more unusual features of Erlang, called bit syntax. Bit syntax is an amazingly powerful and flexible pattern-matching syntax for data encoded in bit streams. Given Erlang's origins, it's fairly obvious why this is part of the language - and it's one of the things that make it so suitable for high performance distributed systems: it's got deep support for the kind of bit-tweaking that's necessary for
many communication protocols, and it's done in a way that allows the compiler to optimize the living daylights out of it. But that's the next post.