Home > Coding > Erlang

Erlang

A little while ago I bought Seven Languages in Seven Weeks because I’m a language geek. Being pressed for time lately, I’ve not really had chance to more than dabble with it.

I dipped my toe into Prolog a bit, and finally got my head around it – and realized it’s of no practical use to me.

I’ve struggled with the book, though, because the author comes across as one of those most annoying types of Java programmers, a believer: even as he notes that Erlang is about robustness, reliability and fault tolerance, he notes that it is “not […] on the [Java Virtual Machine]” (page 207, Integration) and that “the JVM does come with baggage, such as a process and threading model that’s inadequate for Erlang’s needs. But being on the JVM has a set of advantages , too, including the wealth of Java libraries and the hundreds of thousands of potential deployment servers.” (page 207, Integration)

Taken on it’s own, he could just be looking for cons to list in his pro/cons wrap up for Erlang. But, the Java refrain lasts throughout the book. It just seems inappropriate for a book that otherwise appeals to me as a well thought out exploration of some of the more interesting current languages.

The investigations of each language are fairly short, but where this book pays off is in the sort of shared exploration of those languages. If you can take the languages in order, there’s also a plan to the madness. The venture into Prolog turns out not to be worthless; rather it helps provide a foundation for the ventures into Erlang and Haskell etc.

I’ve previously looked at Erlang and found it troublesome – I’m an C/C++ programmer, an OOP guy, and functional programming challenges me.

At the end of the first day, the author tasks the reader to write a program that counts words in a string. Erlang treats strings as arrays of numbers, and it also uses Prolog style pattern matching.

I was stumped. After skimming thru the Day 1 Erlang stuff, I really felt totally out of my depth – precisely because I was bringing my procedural/OOP concepts of strings as objects with me.

So, I tried to cheat, and use Google. Fortunately, the first several I found were cries for help. Looking at their solutions made me realize the flaws in my own thinking, and made the Prolog penny drop.

Functional languages are basically programming by use-case, also called pattern matching.

In a procedural language, you specify parameters to a function:

// (Edited version that would actually work ;-P)
int factorial(const int n)
{
  if ( n <= 1 ) return 1 ;
  return n + factorial(n, -1) ;
}

// Tail recursion version.
static int _factorial_using_tr(const int n, const int accumulator)
{
  if ( n == 1 ) return accumulator ;
  else return _factorial_using_tr(n - 1, n * accumulator) ;
}
int factorial_with_tr(const int n)
{
  if ( n < 1 ) return 0 ;
  return _factorial_using_tr(n, 1) ;
} 

In a procedural language such as this, there is a lot of declaration going on. We declare that factorial can take an argument, n, and that it returns an integer. Then we have to write code to specifically test for the case where n is 1, before finally – but not very clearly – stating that in the general case, <factorial of N> is <value of N plus factorial of <N – 1>>.

In a functional language, such as Erlang, we state these two cases directly:

factorial(1) -> 1;   % specific use case.
factorial(N) -> N + factorial(1).

The “->” is read as “in this case” or “results in” or “causes”.

It’s a bit like C++ overloaded functions, except that instead of being limited to flavors by parameter type, we are exacting about each use case.

Two of the examples I found, predictably, just tried to count spaces in string. Erlang treats strings as arrays of numbers, which is honestly a bit weird, but the examples were like this:

words([]) -> 0 ;
 words([32|Rest]) -> 1 + words(Rest) ;
 words([_|Rest]) -> words(Rest).

The first line says: words with an empty string/array gives a result of 0. The second line says: words with an array containing a space and some other stuff returns one plus the result of words on the other stuff. Finally, the last rule says: words with an array containing something followed by some more stuff … returns the result of words on the more stuff.

Note: This is the WRONG way to do it. However, it’s a good start because if you can understand the last two rules you can get your head around erlang.

Because Erlang is a pattern matching rule, the second rule, [32|Rest], eliminates the case where words is called with a space and some more stuff. Therefore, it’s implied in the 3rd rule that we’re NOT looking at a space…

In Python, this might be something like:

def words(N):
  if len(N) == 0: return 0
  if N[0] == " ": return 1 + words(N[1:])
  return words(N[1:])

Again – the second rule (if N[0] == ‘ ‘) eliminates the use case where we are currently looking at a space followed by zero or more things.

With this understanding, I was able to put together my version. Factor in that this code is deliberately recursive, so even though you may start with an array representing “Hello World”, you will ultimately end up considering an empty array.

% Count the words in an array.
% ASSUMPTION: Array contains only letters and spaces.

-module(test).
-export([word_count/1]).

% Empty array or the end of the array; no words.
word_count([]) -> 0;

% An array consisting just a space has no words.
% This also handles the case of trailing spaces.
word_count([32]) -> 0;

% The above rule eliminated spaces, so this must be
% a letter. If there's a letter, there's a word.
% ("_" is the default variable, and sort of means
% 'anything we didn't already match').
word_count([_]) -> 1;

% If the first element of our current array slice
% is a space, ignore the space. This handles the
% case of an array that starts with excess space.
% The '32 | Rest' means a 32 (i.e. a space)
% followed by "stuff we'll % call Rest";
% don't read is as "or".
word_count([32 | Rest]) -> word_count(Rest);

% We dealt with <space><...> in the previous rule,
% so we know that our first element is NOT a space.
% However if the NEXT element is a space, then we
% are looking at a word followed by a space, so we
% know we have a word.
% '_, 32 | Rest' means 'something and a space followed
% by stuff we'll call Rest'. Again, don't read the '|'
% as "or".
word_count([_, 32 | Rest]) -> 1 + word_count(Rest);

% If we get this far, we're looking at a non-space
% followed by one-or-more non-space, so we are
% probably in the middle of a word.
word_count([_ | Rest]) ->; word_count(Rest).

This handles all cases: “”, ” “, “a”, ” a”, “a “, ” a “, “aa”, ” aa”, “aa “, ” aa “, “a a”, “a a “, ” a a”, ” a a “, “aaa”, “a aa aaa”, ” a aa aaa ” etc…

I’m fairly sure it’s not perhaps the best or the most efficient Erlang code, but hey – this is day 1 :)

Categories: Coding Tags: , , ,
  1. August 25, 2011 at 3:56 am

    here is my version, quickly hacked up in 10-15 minutes:

     -module(word_count).
     -compile([export_all]).
     
     -define(SPACE, $\ ).
     
     count_words_in_string(Str) ->
         count_words(0, ?SPACE, Str).
     
     count_words(Count, _, []) ->            % all input is processed
         Count;
     
     count_words(Count, Delim, [Ch]) when Ch =/= Delim ->
         Count + 1;
     
     %% Ch1==DELIM,Ch2==NON-DELIM
     count_words(Count, Delim, [Ch1, Ch2|Rest]) when Ch1 =:= Delim, Ch2 =/= Delim ->
         count_words(Count+1, Delim, [Ch2|Rest]);
     
     count_words(Count, Delim, [_| Rest]) ->         % eat till end-of-word
         count_words(Count, Delim, Rest).
    
  2. August 25, 2011 at 10:27 am

    Like the use of when; but curious why you would want to pass the count as a parameter rather than as a return? Seems like that would hurt tail recursion?

  3. August 25, 2011 at 10:33 am

    Also, I get the following error:

    Erlang R13B03 (erts-5.7.4) [/source] [smp:4:4] [rq:4] [async-threads:0] [hipe] [kernel-poll:false]

    Eshell V5.7.4 (abort with ^G)
    1> c(test.erl).
    ./test.erl:7: variable ‘SPACE’ is unbound
    error

    Pretty sure that anything starting with a capital letter is a Variable, atoms have to be lowercase. Changing it to lower case allowed it to compile, but it doesn’t handle all cases:

    1> c(word_count.erl).
    {ok,word_count}
    2> word_count:count_words_in_string(” a b”).
    3

  4. August 25, 2011 at 5:44 pm

    Ahh – because Anumpam’s count-passing takes advantage of tail recursion :).

  5. August 25, 2011 at 9:33 pm

    whoopsie !!! a slight change in the “when clause” makes it work just fine:

    ,—-
    | %% Ch1==DELIM,Ch2==NON-DELIM
    | count_words(Count, Delim, [Ch1, Ch2|Rest]) when Ch1 =/= Delim, Ch2 =:= Delim ->
    | count_words(Count+1, Delim, [Ch2|Rest]);
    `—-

    sorry for the late correction to this thing, i accidentally forgot to “check” the ‘notify me of followup…’ thingie.

  6. Neil
    August 27, 2011 at 11:12 am

    Interesting factorial function! One bug that would blow up your stack and another in that it doesn’t compute the factorial. If you can’t get the C version right……. ;)

  7. Neil
    August 27, 2011 at 11:13 am

    Forgot to say- my copy of that book arrived a couple of days ago. Strange. Oh and now do it all in FORTH!

  8. August 28, 2011 at 9:07 pm

    Whatcha talking about – that example of imperative code is completely non-functional ;-P

  9. August 29, 2011 at 6:04 am

    kfsone :
    Whatcha talking about – that example of imperative code is completely non-functional ;-P

    hmmm, i am not sure if you are replying to me. but wordpress was eating up the formatting on the code and all. anyways, here it is git://gist.github.com/1178180.git, and it does work :)

  10. drave
    August 29, 2011 at 10:44 am

    If you don’t know Erlang, you should definitly invest some time into it. I once had a course at the university (Introduction to 10 programming languages) where we had a look at Erlang. I then invested some additional time outside of the course. It is a really nice language, especially its threading model and things like hot code swap.

    Have fun!

  11. August 30, 2011 at 2:21 pm

    @anupam Oh – I was replying to “Neil” :)

  1. No trackbacks yet.

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 218 other followers

%d bloggers like this: