Wakatta!

Like Eureka!, only cooler

Seven Languages in Seven Weeks Erlang Day 1

New week, new language. This time is the turn of Erlang, which comes from Ericsson (the phone company), and was used internally on internal products before being unleashed on the world.

With it’s root in the telecom industry, it is not surprising that Erlang has a particular focus on availability and reliability; it comes with a strong set of tools for network applications, but little for end user interaction (the GUI is minimalist).

The most surprising aspect of Erlang’s origin, perhaps, is that the first version was an interpreter written in Prolog (actually, Erlang was meant as kind of extension to Prolog).

This is particularly obvious in Erlang’s syntax. Prolog programmers should feel mostly at home.

Erlang is functional

Erlang is also a purely functional language, with little to no updates (there are updatable stores, but you really have to look for them). Variables can be assigned a value only once, using a mechanism similar to unification (further assignments are valid only to the extend that both sides are identical, or the left hand is an unassigned variable).

Erlang: assignment
1
2
3
4
5
6
7
8
9
10
11
Eshell V5.8.5  (abort with ^G)
1> V = 3.
3
2> V = 3.
3
3> V = 4.
** exception error: no match of right hand side value 4
4> V = X.
* 1: variable 'X' is unbound
5> X = V.
3

Erlang recursion

The book introduces recursion in the module “yet_again”. Now, recursion is nothing special (few languages don’t support it), but functional languages tend to rely on it, so they often have a special optimization called tail recursion.

Typically, any function call allocate some space on the stack, which is usually a limited resource. A language that relies on recursion rather than iteration risks to run out of stack.

Tail recursion is an optimization technique that replaces a function call by a jump, reusing the stack space already allocated. It effectively turns a recursion into an iteration.

In the book, both defined functions (another_factorial and another_fib) use non tail recursion (also referred to as body recursion). It is clear that another_fib’s performance is going to be terrible (it is doubly recursive); I was surprised to find that another_factorial’s performance is actually pretty good.

I wrote tail recursive versions of both functions (simply using an accumulator):

My Yet Again module (yet_again.erl) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
-module(yet_again).
-export([another_factorial/1]).
-export([another_fib/1]).
-export([tr_fact/1]).
-export([tr_fib/1]).
-export([check_time/2]).

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

another_fib(0) -> 1;
another_fib(1) -> 1;
another_fib(N) -> another_fib(N-1) + another_fib(N-2).

tr_fact(0) -> 1;
tr_fact(N) -> tr_fact(N-1, N).
tr_fact(0, A) -> A;
tr_fact(N, A) -> tr_fact(N-1, N*A).

tr_fib(N) -> tr_fib(N, 1, 1).
tr_fib(0, A, _) -> A;
tr_fib(N, A, B) -> tr_fib(N-1, B, A+B).

check_time(F, N) -> filter(timer:tc(yet_again, F, [N])).
filter({N, _}) -> N.

I also added some code to measure the time of any of these functions.

Clearly, tr_fib is much faster than another_fib (the former is, through tail recursion optimization, iterative, while the latter is double recursive). But it turns out that another_factorial is systematically faster (although not by much) than tr_fact, at least on my machine, even for pretty large input numbers.

I could not find a definitive reason why this is so (the closest I came was suggested by this post and subsequent messages, which suggest the order of multiplication in the tail recursive version causes the accumulator to grow quickly and triggers more garbage collection than the body recursive version).

Still, it is enough to draw a few conclusions:

  • never assume anything about the performance of a piece of code without measuring it;
  • Erlang’s stack handling is awesome;
  • Erlang’s optimization is just as impressive.

Exercises

Couting words

I define a word as a sequence (at least 1) of non-space characters. I use two functions: one that looks for the beginning of words, and one that look for the end of words. That way I always know what state I’m in (between words, or in one), and can keep the count correctly.

Both functions are body-recursive, which as seen above is probably not a problem.

Counting Words (cw.erl) download
1
2
3
4
5
6
7
8
9
10
-module(cw).
-export([count_words/1]).

count_words([]) -> 0;
count_words([32|T]) -> count_words(T);
count_words(WS) -> skip_word(WS).

skip_word([]) -> 1;
skip_word([32|T]) -> 1+count_words(T);
skip_word([_|T]) -> skip_word(T).

Testing the module:

Testing Module cw
1
2
3
4
5
6
1> cw:count_words("   a  lot   of   space   ").
4
2> cw:count_words("not a lot of space").
5
3> cw:count_words("word").
1

Counting to 10

Erlang has a good support in the standard library for usual functional programming idioms, such as generating lists, and applying a function over elements of a list.

Counting to 10 (count.erl) download
1
2
3
4
5
6
7
8
9
10
11
12
13
-module(count).
-export([count_to_10/0]).
-export([count_to/1]).
-export([count_up_to/1]).

count_to_10() -> count_to(10).

count_to(N) ->
  L = count_up_to(N),
  lists:map(fun(X) -> io:fwrite("~w\n", [X]) end, L),
  L.

count_up_to(N) -> lists:seq(1,N).

The code is more generic than strictly required (which is always good):

Testing Module count
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1> count:count_to_10().
1
2
3
4
5
6
7
8
9
10
[1,2,3,4,5,6,7,8,9,10]
2> count:count_to(5).
1
2
3
4
5
[1,2,3,4,5]

Matching input

Nothing fancy here; just basic pattern matching and some calls from the standard library.

Pattern Matching (check.erl) download
1
2
3
4
5
6
7
8
-module(check).
-export([print_result/1]).
-export([check_result/1]).

print_result(M) -> io:fwrite("~s\n", [check_result(M)]).

check_result(success) -> "success";
check_result({error, Message}) -> lists:append("Error: ", Message).

The code recognizes the input as requested. Everything else will generate an error.

Testing Module check
1
2
3
4
5
6
7
8
1> c(check).
{ok,check}
2> check:print_result(success).
success
ok
3> check:print_result({error, "Something went wrong!"}).
Error: Something went wrong!
ok

And so we conclude Day 1.

Comments