Pablo's blog

A bit of this, a bit of that and a lot about computers

Erlang, the language for network programming Issue 1: pattern matching

Much is being said about the excellent capabilities of Erlang to write distributed fault-tolerant programs, but little has been said about how easy and fun it is to write servers (those programs at the other end of the line) with it. And by easy I don’t just mean that you can put up a web server in two lines of code and hope it’ll work, I mean it’ll be easy to built robust servers.

One example of this is ejabberd, a free Jabber server.

One of the Erlang features that let us write servers is its binary pattern matching. But to understand binary pattern matching first you have to understand pattern matching.

Let’s start with a classic of functional programming: factorial. This is factorial in Erlang

fac(N) ->
   if N == 0 -> 1;
      true -> N * fac(N - 1)
   end.


A bit of explanation: fac is the name of the function, N is its only parameter. What follows after the first -> is the body of the function. The if has two clauses; in them you see the predicate before the -> and the consequence after it. The last predicate, true, is like the else of other programming languages (think about “if true then N…” as the last thing is going to be checked). Don’t let recursion scare you, it is not that hard and you’ll see it in lots of places in functional programming. Something called tail-call optimization let us make it very efficient, although for clarity I haven’t done it in this case. Now fac using pattern matching:

fac(0) -> 1;
fac(N) -> N * fac(N - 1).

Half the amount of lines, simpler, easier to read and beautiful as a mathematic demonstration. You can read it as:

Define fac for zero as being 1and fac for N as being N multiplied by fac of N minus 1.

When you call fac, Erlang will try your parameter against all the patterns until it finds one that matches, and when it does, it’ll evaluate the body of that clause. Pattern matching not only tries to match, it also assigns identifiers, that’s how N comes to contain the parameter passed to the function.

Let’s see another case… one we all love, the raise salary example:

raise({Name, Salary}, N) ->
   {Name, Salary * N}.

This function, raise, gets two parameters (“hey! I see three!”, hold on, keep reading). The first, {Name, Salary}, is a tuple (an structure containing various values, in this case Name and Salary) and the second is the parameter N representing how much we are going to raise the salary by. The function returns a new tuple with the new raised salary. We could have written it in another way, like this:

raise(Person, N) ->
   {Name, Salary} = Person,   {Name, Salary * N}.

There you see the parameter Person more clearly defined, but below it, I am using the same pattern matching to take each member of the Person tuple and assign it to Name and Salary. The previous definition requires one less line, one less identifier and it is more versatile.

Thankfully, our Erlang shop doesn’t have only one employee, we are so successful that there are fifty employees and the last year gave us so much profit that we are going to raise the salary of all of them. But calling raise 50 times is tiring. Can’t we just call it once over a list ? Yes, we can. One way is to add more clauses to the first definition:

raise({Name, Salary}, N) ->
   {Name, Salary * N};
raise([], N) ->
   [];
raise([Person|Persons], N) ->
   [raise(Person, N)|raise(Persons, N)].

Now there are three clauses in the definition of the function raise. You already know the first clause, the second reads:

The result of rising the salary of an empty list (of persons) by N is an empty list (of persons).

It may be obvious to us, but the computer needs it. Not very interesting, just note that square brackets are used to define lists: [1,2,3,4]. The third clause is really cryptic, let’s interpret it:

The result of rising the salary of a list of persons, letting the identifier Person be the first person and Persons be the rest, by N is… the result of rising the salary of Person, the first person, as the first item of a list and the raise of the salary of the rest of the persons, Persons, as the rest of the list.

Long sentence. Feel free to read it again, slowly. See the piece of code and try to identify the parts. OK, it’s really cryptic. The first parameter is a pattern: [Person|Persons]. It matches a list with at least one item and identifies it as Person. The rest of the list is identified as Persons (the rest in a list containing one item is an empty list, like in Lisp and Haskell). Take a look at the whole definition:

  • The first clause matches the structure alone.
  • The second matches the empty list.
  • The third matches the list with at least one item in it.

On the third clause I build another list, here I use the pipe | again, but this is not a pattern matching. The pipe is for building a list. For example: [1,2,3], the list containing 1, 2 and 3, is the same as [1|[2|[3|[]]]] (read that as the list having 1 in the head of the list having 2 in the head of the list having 3 in the head of the empty list).

To make things crystal clear let’s watch an interaction:

> raise([{"Mickaël", 3000}, {"Yariv", 3000}, {"Joe", 3000}], 2).
  1. raise([{"Mickaël", 3000}|[{"Yariv", 3000}|[{"Joe", 3000}|[]]]], 2).
  2. [raise({"Mickaël", 3000}, 2)|raise([{"Yariv", 3000}|[{"Joe", 3000}|[]]], 2)].
  3. [{"Mickaël", 6000}|raise([{"Yariv", 3000}|[{"Joe", 3000}|[]]], 2)].
  4. [{"Mickaël", 6000}|[raise({"Yariv", 3000}, 2)|raise([{"Joe", 3000}|[]], 2)]].
  5. [{"Mickaël", 6000}|[{"Yariv", 6000}|raise([{"Joe", 3000}|[]], 2)]].
  6. [{"Mickaël", 6000}|[{"Yariv", 6000}|[raise({"Joe", 3000}, 2)|raise([], 2)]]].
  7. [{"Mickaël", 6000}|[{"Yariv", 6000}|[{"Joe", 6000}|raise([], 2)]]].
  8. [{"Mickaël", 6000}|[{"Yariv", 6000}|[{"Joe", 6000}|[]]]].
  9. [{"Mickaël", 6000}|[{"Yariv", 6000}|[{"Joe", 6000}]]].
  10. [{"Mickaël", 6000}|[{"Yariv", 6000},{"Joe", 6000}]].
  11. [{"Mickaël", 6000},{"Yariv", 6000},{"Joe", 6000}].

Step 1 is just the same raise call but the list is expressed in the other way, as lists are built, using the pipe |. On the second step it matched the third clause, raise([Person|Persons], N), which calls raise two times. And we can see that we have two new calls to raise. These two calls match two different clauses, the first one matches the first clause, raise({Name, Salary}, N), and the second call matches the third clause, raise([Person|Persons], N).

In the third step, we have used the first clause to raise {“Mickaël, 3000} to {“Mickaël, 6000}. Now we proceed with the rest of the list in the same way we started (using raise([Person|Persons], N)). On step 4 we separate the head of the list, {“Yariv”, 3000}, from the rest to eventually raise it to {“Yariv”, 6000} in the fifth step.

Everything continues the same up to the seventh step, where we match the yet-unused second clause, raise([], N), by passing the empty list []. From step 8 to 11 the list gets built to the point where it is the familiar comma-separated expression. Feel free to re-read all the steps and see which pattern matches and which part is assigned what. It is a daunting task when we came to functional programming for the first time because outside functional programming, recursion is hardly used at all.

If we compile fac we are going to get a warning:

raise.erl: 4: Warning: variable 'N' is unused

Oh! the identifier N of the second definition is never used, and Erlang is so kind to let us know. I hate warnings, I can’t continue to code until I get rid of them. So, what can I do ? We can define it so there can be anything in the second parameter but we don’t really care what it is:

raise({Name, Salary}, N) ->
   {Name, Salary * N};
raise([], _) ->
   [];
raise([Person|Persons], N) ->
   [raise(Person, N)|raise(Persons, N)].

And here we see how functional programming helps us make sense: if we are going to raise the salary of an empty list of persons, it doesn’t matter how much we are going to raise it by, it’ll be always an empty list of persons. Wasn’t this about network programming? keep tuned for the next issue to learn how binary pattern matching will help us build networked applications.

About these ads

Single Post Navigation

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 375 other followers

%d bloggers like this: