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).
1 2 3 4 5 6 7 8 9 10 11
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_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):
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
I also added some code to measure the time of any of these functions.
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.
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.
1 2 3 4 5 6 7 8 9 10
Testing the module:
1 2 3 4 5 6
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.
1 2 3 4 5 6 7 8 9 10 11 12 13
The code is more generic than strictly required (which is always good):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Nothing fancy here; just basic pattern matching and some calls from the standard library.
1 2 3 4 5 6 7 8
The code recognizes the input as requested. Everything else will generate an error.
1 2 3 4 5 6 7 8
And so we conclude Day 1.