The Joy of Erlang; Or, How To Ride A Toruk

By Evan Miller

March 24, 2011

In the movie Avatar, there’s this big badass bird-brained pterodactyl thing called a Toruk that the main character must learn to ride in order to regain the trust of the blue people. As a general rule, Toruks do not like to be ridden, but if you fight one, subdue it, and then link your Blue Man ponytail to the Toruk’s ptero-tail, you get to own the thing for life. Owning a Toruk is awesome; it’s like owning a flying car you can control with your mind, which comes in handy when battling large chemical companies, impressing future colleagues, or delivering a pizza. But learning to ride a Toruk is dangerous, and very few people succeed.

I like to think of the Erlang programming language as a Toruk. Most people are frightened of Erlang. Legends of its abilities abound. In order to master it, you have to fight it, subdue it, and (finally) link your mind to it. But assuming you survive, you then get to control the world’s most advanced server platform, usually without even having to think. And let me tell you: riding a Toruk is great fun.

This guide is designed to teach you the Erlang state of mind, so that you are not afraid to go off and commandeer a Toruk of your own. I am going to introduce only a handful of Erlang language features, but we’re going to use them to solve a host of practical problems. The purpose is to give you the desire and confidence to go out and master the rest of the language yourself.

You are welcome to type the examples into your own Erlang shell and play around with them, but examples are foremost designed to be read. I recommend printing this document out and perusing it in a comfortable chair, away from email, compilers, 3-D movies, and other distractions.

Table of Contents

1. Defining Functions: A Simple Boolean Logic Library
2. Calling Functions Recursively: A Simple Arithmetic Library
3. Lists of Integers: Basic String-Processing
4. Fun With Erlang Algorithms
5. Next Steps
6. Source Code

1. Defining Functions: A Simple Boolean Logic Library

In Erlang, functions consist of one or more clauses. The last clause in a function must end with a period ("."), and all other clauses must end with a semicolon (";"). When a function is called, the first clause that matches the provided argument list is executed. You might think of functions as what would happen if C’s switch statement were exposed to toxic sludge and became a superhero.

In the simplest case, a function has one clause. Here is a function noop that simply returns its argument, the variable A (variables are always capitalized):

noop(A) -> A.

Notice that there is no "return" statement in Erlang. A function always returns the result of the last expression. Since every expression has a result, and every function clause has at least one expression, every function always has a return value.

Now suppose we wish to implement a Boolean not function that takes either true or false as its single argument. A not function would need two clauses:

not(true) -> false;
not(false) -> true.

Each time not is executed, Erlang first tests whether the argument is true (and if so, executes the first clause), then tests whether the argument is false (and if so, executes the second clause). Matching the provided arguments against the function definition is called pattern-matching. Pattern-matching makes it easy to write complicated functions without the use of internal control structures.

We can use pattern-matching to see whether the same variable appears more than once in the argument list. For example, this function implements an equality operator:

equals(A, A) -> true;
equals(A, B) -> false.

If the two provided arguments are the same, the function returns true; otherwise, the function returns false.

Note that the clause order here is important. This would be incorrect:

equals(A, B) -> false; % WRONG
equals(A, A) -> true.

Why is this incorrect? Erlang first attempts to match against the first clause. But if the two arguments are the same, a match still occurs; A and B are simply assigned identical values. The second clause is never reached. Using different variable names in the variable list does not require different values assigned to those variables.

We are now equipped to implement some more Boolean logic. Here is an implementation of and:

% AND: true if both arguments are true, false otherwise
and(true, true) -> true;
and(false, true) -> false;
and(true, false) -> false;
and(false, false) -> false.

You might think all of these truth-table clauses are tedious. They are. We can use a special anonymous variable in order to reduce the last three clauses to a single clause:

% AND: true if both arguments are true, false otherwise
and(true, true) -> true;
and(_, _) -> false.

The anonymous variable (_) matches anything, always. It is not assigned a value, so as we see in the second clause above, two or more underscore variables in the argument list do not have to match identical terms. The anonymous variable is often used to “throw away” parts of a pattern that we don’t care about.

Now that we have regular variables and the underscore variable at our disposal, the rest of our Boolean logic library is a cinch to write. Take a moment to understand why each of the following functions works as advertised.

% OR: true if either or both arguments are true, false otherwise
or(false, false) -> false;
or(_, _) -> true.

% XOR: true if one argument is true and the other false; otherwise, false
xor(A, A) -> false;
xor(_, _) -> true.

% NAND: false if both arguments are true, true otherwise
nand(true, true) -> false;
nand(_, _) -> true.

% NOR: true if both arguments are false, false otherwise
nor(false, false) -> true;
nor(_, _) -> false.

As you can see, pattern-matching gives Erlang functions tremendous expressive power. In the next section, we will combine pattern-matching with recursion to build an arithmetic library from almost nothing. In most languages, recursion is usually a measure of last resort, and only employed to implement complex algorithms. In Erlang, recursion is often the simplest and most efficient way to do something mundane.

2. Calling Functions Recursively: A Simple Arithmetic Library

Erlang has a rich set of arithmetical operators. But in this section, we are not going to use any of them. Instead we are going to build our own complete arithmetic library, using only what we have learned so far about functions.

The task in this section is admittedly contrived, and recursion is definitely not the simplest way to solve it in the real world. However, the exercise will be a good way to practice recursive thinking in preparation for Section 3, where recursion will the best way to go about our problem.

Recall that recursive functions have at least two parts: they must first test for some kind of base case (where the algorithm terminates), and if the base case is not satisfied, the recursive function must perform some logic, and then issue a call to itself. In Erlang, recursive functions usually have at least two clauses: a “base case” clause, and an “all other cases” clause.

This will all become clear in a minute. To get things moving, I am going to provide two functions off of which the rest of the library will be built: incr and decr. Assume that incr increments the provided argument, and that decr decrements the provided argument, like this:

incr(A) -> A + 1.

decr(A) -> A - 1.

Can we use these two functions to add any two positive integers together?

Indeed we can!

% Add two positive integers
add(A, 0) -> A.
add(A, B) -> add(incr(A), decr(B)).

Sometimes it’s easiest to read recursive functions from bottom to top. So look at the second clause first: it says that adding up A and B is the same as adding up (A+1) and (B-1), which is obviously true. So the function keeps adding 1 to A, and subtracting 1 from B, until B reaches zero, in which case it terminates (first clause). By that point, add has been recursively called B times, which means that A has been incremented B times, so that the result is, indeed, A + B.

Well that was a bit of fun, now wasn’t it? Let’s implement subtraction:

% Subtract B (positive) from A
sub(A, 0) -> A.
sub(A, B) -> sub(decr(A), decr(B)).

It’s the same idea. From the second clause, we see that (A - B) is the same as ((A - 1) - (B - 1)), which is obviously true. The recursive call is made until B hits 0, in which case A has been decremented B times, giving the result A - B.

Neither of these functions work when B is negative. We can modify add to accommodate negative integers very simply:

% Add any two integers
add(A, 0) -> A;
add(A, B) when B < 0 -> add(decr(A), incr(B));
add(A, B) -> add(incr(A), decr(B)).

Notice the use of an Erlang guard in the second clause (when B < 0). We can impose conditions on the argument list with the when keyword followed by an expression. There are many types of guards allowed, but for now, we’ll just make integer comparisons.

The modified form of sub is similar:

% Subtract any B from A
sub(A, 0) -> A;
sub(A, B) when B < 0 -> sub(incr(A), incr(B));
sub(A, B) -> sub(decr(A), decr(B)).

With addition and subtraction taken care of, it’s easy to tackle multiplication. Just as we implemented addition as a series of increments, we will implement multiplication as a series of additions, again using recursion. We use the fact that A × B = A + A × (B - 1).

% Multipy A by B (positive)
multiply(A, 0) -> 0;
multiply(A, B) -> add(A, multiply(A, decr(B))).

Adding support for negative numbers is easy, because A × (B + 1) - A = A × B:

% Multipy A by any B
multiply(A, 0) -> 0;
multiply(A, B) when B < 0 -> sub(multiply(A, incr(B)), A);
multiply(A, B) -> add(A, multiply(A, decr(B))).

Division? Not a problem. With integer division, we really care about two operations: finding the quotient, and finding the remainder. In both cases, we want to subtract the divisor from the dividend until we hit zero. The remainder operation is the easier of the two:

% Find the remainder of A / B
remainder(A, B) when A < B -> A;
remainder(A, B) -> remainder(sub(A, B), B).

For the quotient function, we will use a common pattern in Erlang, which is to have an internal recursive function that is distinct from the main interface. The internal function takes an extra argument, which keeps track of the number of times we have subtracted the divisor.

% Find the quotient of A / B
quotient(A, B) -> quotient(A, B, 0).

% Internal function includes an accumulator
quotient(A, B, Answer) when A < B -> Answer;
quotient(A, B, Answer) -> quotient(sub(A, B), B, incr(Answer)).

With divide and multiply in our toolchest, the world is our problem set. Let’s implement a power function, for instance. We use the exact same idea as before, recognizing that raising a number to an exponent is really just a series of calls to multiply. In other words, A^B = A × A^B-1.

% Raise A to the B power (positive)
pow(A, 0) -> 1;
pow(A, B) -> multiply(A, pow(A, decr(B))).

In practice, all of these functions are terribly inefficient, since they reduce everything to a series of increments or decrements. But this recursive frame of mind is absolutely essential to getting the most out of Erlang, as we’ll see in the string-processing library we are about to build.

3. Lists of Integers: Basic String-Processing

In Erlang, strings are represented as lists of integers. These integers are either ASCII character codes or Unicode code points. For example, the ASCII string "dog" is represented as the list of the integers 100 ("d"), 111 ("o"), 103 ("g"). The literal representation of an Erlang list is surrounded by square brackets, so "dog" can be written [100, 111, 103] if you so desire. To represent the integer for a particular character, simply precede it with a dollar sign ("$"). So [$d, $o, $g] is the same as [100, 111, 103] is the same as "dog".

Every list is divided into two parts: a head and a tail. The head is the first item, and the tail is everything else. Lists are recursive data structures. The tail of a list is a list; it has its own head and its own tail. And so on.

The empty list is represented as "[]". It has no head and no tail.

In Erlang, to push an item to the head of the list, use the "|" operator (a pipe character):

NewList = [NewItem | OldList]

The | operator can also be used in pattern-matching to pull an item from the head of a list:

some_function([FirstItem | RestOfList]) ->
   ... do something with FirstItem ...

To reverse a list, use the function lists:reverse(). Reversing a list may seem like an obscure operation, but as we’ll see, it is used all the time in implementing list algorithms in Erlang.

We now know enough about strings to get started with an example. Let’s write a function that capitalizes the first letter of the input.

The basic idea of this function will be simple. We examine the first character (head) of the input to see whether it’s a lowercase ASCII character. If so, we convert it to uppercase (by adding the difference between uppercase ASCII characters and their lowercase equivalents), and push it back on to the tail. If not, we simply return the unadulterated input:

capfirst([Head | Tail]) when Head >= $a, Head =< $z ->
    [Head + ($A - $a) | Tail];
capfirst(Other) ->
    Other.

Here we have used a few new mathematical operators, the meaning of which you can probably figure out. Also note that a comma is used to separate multiple guards on the same clause.

If you thought that was fun, just wait until you try converting an entire string to uppercase. In a world without for-loops, how does one process every element of a string? It’s time to revisit our old friend, recursion:

% public
uppercase(String) ->
   uppercase(String, []).

% internal
uppercase([], Output) ->
    lists:reverse(Output);
uppercase([Char | Rest], Output) when Char >= $a, Char =< $z ->
    uppercase(Rest, [Char + ($A - $a) | Output]);
uppercase([Char | Rest], Output) ->
    uppercase(Rest, [Char | Output]).

As with the quotient function we wrote in Section 2, this function has a public interface and an internal recursive function that includes an extra argument. The extra argument is known as the accumulator, which starts out as an empty list. The general strategy is to pop an item from the head of the input, convert it, and push it onto the head of the accumulator. When we run out of input, the answer we want will be stored in the accumulator — but in reversed form. We therefore call lists:reverse and return the result to the public function.

Let’s examine the internal function clause-by-clause to see how this strategy is implemented.

In the base case, there is no more input. We therefore reverse the accumulator:

uppercase([], Output) ->
    lists:reverse(Output);

If there is still input, and the next character is a lowercase ASCII letter between "a" and "z", we convert it to an uppercase ASCII letter, push it onto the accumulator, then recursively call uppercase on the remaining input:

uppercase([Char | Rest], Output) when Char >= $a, Char =< $z ->
    uppercase(Rest, [Char + ($A - $a) | Output]);

The last clause matches when the next character is not a lowercase ASCII character. In that case, we simply move the character from the input to the accumulator untouched:

uppercase([Char | Rest], Output) ->
    uppercase(Rest, [Char | Output]).

And that’s the end of our algorithm. Writing a lowercase function is left as an exercise for the reader.

Now it’s time to get fancy. Getting fancy, of course, entails Capitalizing The First Letter Of Every Word rather than EVERY SINGLE CHARACTER. We’ll call this function titlecase.

titlecase(String) ->
    titlecase(String, []).

titlecase([], Output) ->
    lists:reverse(Output);
titlecase([Char | Rest], [] = Output) when Char >= $a, Char =< $z ->
    titlecase(Rest, [Char + ($A - $a) | Output]);
titlecase([Char | Rest], [$\  |_] = Output) when Char >= $a, Char =< $z ->
    titlecase(Rest, [Char + ($A - $a) | Output]);
titlecase([Char | Rest], Output) ->
    titlecase(Rest, [Char | Output]).

The only difference between titlecase and uppercase is that we use pattern-matching to peek at the accumulator before deciding what to do. If the accumulator is empty (second clause), that means we are at the beginning of the input and want to capitalize the next character. If the accumulator has a space character at its head (third clause), that means we are at the beginning of a word and want to capitalize the next character. Note that the integer representation of a space character is dollar-slash-space ("$\ "). Here we have also used the match operator ("="), which lets combine pattern-matching with variable assignment right in the argument list.

As you can see, recursion, accumulators, and pattern-matching are a powerful combination. We can write context-dependent algorithms without state variables or regular expressions. More importantly, we can express the solutions to problems clearly, and have confidence in the correctness of our algorithms. The joy of Erlang is to write code without fear of forgetting something.

4. Fun With Erlang Algorithms

So now we’re ready to have some fun. Since you know the basics of Erlang now, I won’t spend too much time explaining the following algorithms. They’re just meant for you to ponder and enjoy.

A classic interview question is converting a string to an integer (atoi in C). Here’s how to do that in Erlang:

% public
atoi([$- | String]) -> % negative
    -1 * atoi(String, 0);
atoi(String) -> % non-negative
    atoi(String, 0).

% internal
atoi([], Acc) ->
    Acc;
atoi([C | Rest], Acc) when C >= $0, C =< $9 ->
    atoi(Rest, 10 * Acc + (C - $0)).

Note that the accumulator here is an integer, rather than a string like we’ve been using so far. In principle, of course, an accumulator can be anything.

Now suppose we want to do the opposite: convert an integer to a string. Here’s how:

% public
to_string(0) ->
    [$0];
to_string(Integer) when Integer < 0 -> % negative
    [$-|to_string(-1 * Integer, [])];
to_string(Integer) -> % positive
    to_string(Integer, []).

% internal
to_string(0, Acc) ->
    Acc;
to_string(Integer, Acc) ->
    to_string(Integer div 10, [(Integer rem 10) + $0 | Acc]).

Note that here I’ve used two integer operators: div is integer divison, and rem is integer modulo (usually represented as % in C-style languages).

Let’s pretend we’re writing a productivity suite in Erlang and need to convert positive integer column numbers to the string representation used by most spreadsheets ("A" through "Z", followed by "AA" through "ZZ", etc.). Here’s how:

% public
num2excel(Number) ->
    num2excel((Number-1) div 26, (Number-1) rem 26, []).

% internal
num2excel(0, Remainder, Acc) ->
    [(Remainder + $A)|Acc];
num2excel(Quotient, Remainder, Acc) ->
    num2excel((Quotient-1) div 26, (Quotient-1) rem 26, [(Remainder + $A)|Acc]).

Or maybe the word-processor in our productivity suite needs a word-count function. Piece of cake:

% public
wordcount(Input) ->
    wordcount(Input, 0).

% internal
wordcount([], Count) ->
    Count;
% End of the input. Count the last word, if we didn't already
wordcount([C1], Count) when C1 =/= $\  ->
    Count+1;
% End of a word. Count it.
wordcount([C1, C2|Rest], Count) when C1 =/= $\ , C2 =:= $\  ->
    wordcount([C2|Rest], Count + 1);
% Not the end of a word. Don't count it.
wordcount([_|Rest], Count) ->
    wordcount(Rest, Count).

Here we’ve used a couple of new operators: =:= is the equality operator in Erlang, and =/= is the not-equality operator. Now you know.

Of course, if we plan to build a competitor to Microsoft FrontPage, we’ll need a way to escape HTML special characters. No sweat:

% public
escape(String) ->
    escape(String, []).

% internal
escape([], Acc) ->
    lists:reverse(Acc);
escape([$< | Rest], Acc) ->
    escape(Rest, lists:reverse("&lt;", Acc));
escape([$> | Rest], Acc) ->
    escape(Rest, lists:reverse("&gt;", Acc));
escape([$& | Rest], Acc) ->
    escape(Rest, lists:reverse("&amp;", Acc));
escape([C | Rest], Acc) ->
    escape(Rest, [C | Acc]).

There’s something new in the above code: the two-argument form of lists:reverse(). It reverses the first argument, and then appends the second argument. It’s handy for code like this where we are building up an accumulator in reverse (which is often the case in string-processing).

Outlook Express had better watch out, because we now have the tools to write a killer email client. Let’s wrap words at 80 characters for outgoing email. As we scan input, we’ll have a word accumulator and an output accumulator, and decide when to push the accumulated word onto the output, and when to insert newlines. There’s a new operator for you in here: ++ concatenates two lists.

% public
wordwrap(Input) ->
    wordwrap(Input, [], [], 0, 80).

% internal
% No more input, we're done
wordwrap([], Acc, WordAcc, LineLength, WrapAt) ->
    lists:reverse(WordAcc ++ Acc);

% Premature newline
wordwrap([$\n | Rest], Acc, WordAcc, LineLength, WrapAt) ->
    wordwrap(Rest, [$\n | WordAcc ++ Acc], [], 0, WrapAt);

% Hit the wrap length at a space character. Add a newline
wordwrap([$\  | Rest], Acc, WordAcc, WrapAt, WrapAt) ->
    wordwrap(Rest, [$\n | WordAcc ++ Acc], [], 0, WrapAt);

% Hit a space character before the wrap length. Keep going
wordwrap([$\  | Rest], Acc, WordAcc, LineLength, WrapAt) ->
    wordwrap(Rest, [$\  | WordAcc ++ Acc], [], LineLength + 1 + length(WordAcc), WrapAt);

% Overflowed the current line while building a word
wordwrap([C | Rest], Acc, WordAcc, 0, WrapAt) when erlang:length(WordAcc) > WrapAt ->
    wordwrap(Rest, Acc, [C | WordAcc], 0, WrapAt);
wordwrap([C | Rest], Acc, WordAcc, LineLength, WrapAt) 
                        when erlang:length(WordAcc) + LineLength > WrapAt ->
    wordwrap(Rest, [$\n | Acc], [C | WordAcc], 0, WrapAt);

% Just building a word...
wordwrap([C | Rest], Acc, WordAcc, LineLength, WrapAt) ->
    wordwrap(Rest, Acc, [C | WordAcc], LineLength, WrapAt).

And that’s a wrap!

5. Next Steps

Erlang is a rich language that you come to appreciate more as you dig deeper into it. In order to get straight to the algorithms in this guide, I have deliberately avoided covering Erlang’s major data structures, its libraries, and its built-in functions. But if you’ve enjoyed thinking about problems with an Erlang frame of mind, I encourage you to go out, learn the rest of the language, and start putting Erlang to work. Erlang has an active, growing, and friendly developer community, exciting potential applications, and many interesting and useful open-source projects.

Admittedly, learning to ride a bird-brained pterodactyl can be tough business, but once you master it, you’ll wonder how you ever got along before.

6. Source Code

Download the source code that appears in this guide

---

You’re reading evanmiller.org, a random collection of math, tech, and musings. If you liked this you might also enjoy:

• Elixir RAM and the Template of Doom
• Why I Program in Erlang
• Write A Template Compiler For Erlang

---

Get new articles as they’re published, via LinkedIn, Twitter, or RSS.

---

Want to look for statistical patterns in your MySQL, PostgreSQL, or SQLite database? My desktop statistics software Wizard can help you analyze more data in less time and communicate discoveries visually without spending days struggling with pointless command syntax. Check it out!

---

Back to Evan Miller’s home page – Subscribe to RSS – LinkedIn – Twitter

---