9/21/2007

A little Erlang Tutorial

So I've been very interested in learning a little more about Erlang. Who could ignore all this hype? Well I can't so I decided to check it out for myself. I've been relearning my functional programming so it hasn't been that difficult. It's taking some time to get used to the syntax. And, I miss spell my functions all the time. I really do miss auto-completion. I'm going to go fast so it helps if you've done some of the beginner tutorials that explained tuples, lists, and atoms.

My first function was to create a shopping cart like behavior. This was something that was in the Joe Armstrong book. Although Joe was probably envisioning a web cart. I was thinking more a game inventory system. I did something like the following:


-module(shopping).
-export([total/1]).
-export([cost/1]).

cost(longbow) -> 120;
cost(sword) -> 25;
cost(bow) -> 60;
cost(shield) -> 100;
cost(longsword) -> 250.

total( [ {Item, Count} | T ] ) -> cost(Item) * Count + total(T);
total( [] ) -> 0.



So this defines a couple of functions. The total function would take a list of items and total up the amount of gold it might be worth. Here is the erl command prompt on using this function:


1> c(shopping).
{ok,shopping}
2> shopping:total( [{ sword, 1 }, { shield, 2 }, { bow, 3 }] ).
405


Ok so what's going on? Erlang is very different than most languages in that a complete function is actually a series of smaller functions. Erlang uses pattern matching to figure out which one you meant to call. This is done based on the function name, and parameters you give it. In the total() function there are actually two functions. The first accepts a non-empty list. The second function is matched only when total() is called with an empty list which is worth zero.

There's more going on with the total() function. This syntax: [ {Item, Count} | T } ] is actually doing a lot more than just defining the parameters to total(). It's create three variables (Item, Count, and T). First thing it's doing is removing the first item in the list. In this case it's a tuple, and Item and Count are set to the tuple's two values. The variable T is set to the remainder of the list. Now to calculate the total for one tuple is fairly easy. cost(Item) * Count + total( T ). Calculate the value of this item and then recursively calculate the rest.

Notice that the cost() function really is matching data like swords to values like 25. In Java, Ruby, or Python you would represent this in a map or dictionary like


costs = { 'sword' => 25, 'longbow' => 120 }


In Erlang you don't have maps or dictionaries. So how do we relate values together? Converting data to functions serves the same purpose. This really only works for fixed values, Erlang does have a map or dictionary like data structure see the comments for the docs. I'm going to use functions for the same purpose.

I want to shift gears a bit and write a new function along these same lines. Let's say our lonely hero has some gold, and he needs to purchase some supplies. Let's create a function that returns a list of items that he can afford. I'm going to write this function three different ways. Hopefully this will give you some more insight into how Erlang works. So for starters will want to iterate over the list, pull out the items we can afford, and add them to a new list. Sounds easy. Here is my first attempt:


find_possible_purchases( Gold, [{I,C} | Inventory] ) when C > 0 ->
if
Gold >= cost(I) -> [{I,C} | find_possible_purchases( Gold, Inventory )];
Gold < cost(I) -> find_possible_purchases( Gold, Inventory )
end;


You'd call this like:


1> find_possible_purchases( 50, [ {longbow, 1}, { sword, 2}, {shield, 4}, {bow, 3}, {longsword, 0} ).
[ {sword, 2} ]
2>


In Erlang the period (.) is the end of the statement delimiter. Similar to semicolons in Java or C. Remember to end your statements with a period (.) in the shell.

This isn't too hard to understand. The function starts off by pulling off the head of the inventory list just as our total() function did. It takes the tuple at the head of the list and creates variables I and C for the item and the number of items in the shop. Next it uses the if statement to compare the gold to the cost of that item. If the amount of gold is greater that the cost of that item. It's added to the head of a new list, and recursively processes the rest of inventory. The same code [ {I,C} | find_possible_purchases( Gold, Inventory )] actually is also used for adding items to a list as well. So this creates a tuple with I and C and adds to to the head of the list. The other branch of the if simply recursively calls the find_possible_purchases with the rest of the inventory. This effectively filters out the item our hero can't afford.

The last thing I want to point out is that this function won't even be called if the item is out of stock. By that I mean the number of items (i.e. C) is less than 1. The clause after the function parameters ( when C > 0 ) is a guard condition, and it helps further pattern match your functions. Guard conditions can ease your burden of writing big if or case statements just to filter out certain function calls. You can even specify multiple guard conditions in the when clause. There is one limitation and that's you can' call functions! Let's compile:


1> c(shopping).
./shopping.erl:24: illegal guard expression
./shopping.erl:25: illegal guard expression



Whoa! What happened?! It looks like our if statement is wrong! Well it has to do with what I mentioned before about guards. You can't call functions in guard conditions, and our if is calling our cost() function. If and case statements are specified in a series of guard conditions as well so you cannot use functions in them. Let me show you the corrected version:


find_possible_purchases( Gold, [{I,C} | Inventory] ) when C > 0 ->
ItemCost = shopping:cost(I),
if
Gold >= ItemCost -> [{I,C} | find_possible_purchases( Gold, Inventory )];
Gold < ItemCost -> find_possible_purchases( Gold, Inventory )
end;


The solution is to call the function and store it in a variable before we use it in the guard conditions. This is a good example of a function with multiple statements. If you function is made up from multiple statements you use the comma to separate statements. I'm going to round out this function with the following:


find_possible_purchases( Gold, [{_,C} | Inventory] ) when C < 1 ->
find_possible_purchases( Gold, Inventory );
find_possible_purchases( _, [] ) -> [].


I've also added two additional functions to handle when C < 1, and when there is an empty inventory. In each of these functions we see the underscore (_) used. The underscore is a special character used to represent anything or a wildcard match on this parameter. In these function's we aren't using I so we just tell Erlang to match anything.

All in all this is very verbose. The good news is there are easier ways using Erlang's built in functions, and other features of the language. So let's see if we can simplify.

The lists:filter function is a built in function for working with lists. Let's see how our function would change.


find_possible_purchases( Gold, Inventory ) ->
Afford = fun( {I,C} ) -> Gold >= shopping:cost(I) andalso C > 0 end,
lists:filter(Afford,Inventory).


Notice this is the only function we need. Our prior version we needed three functions to handle all of the cases. Using lists:filter() we can get it done to one. Much nicer. The lists:filter() method takes two arguments. The first argument is a function that returns true or false. If this function returns true the item is included in the output, otherwise it's filtered out. The second argument is the list we want to filter. I'm using another feature of Erlang which is an inline or anonymous function. The first line of the function is creating function that takes a single tuple, compares it's cost with our gold, and sees if it's in stock. If both of these conditions are matched it returns true otherwise false. Notice the anonymous function can access variables in our surrounding function like Gold just like closures in other languages. Let's move on.

We are going to simplify this even more using Erlang's List Comprehension feature. List comprehensions allow you to do both filtering and mapping at the same time. We actually only need to filter with them, but you can performing mapping at the same time. Let's take a look at using list comprehensions:


find_possible_purchases( Gold, Inventory ) ->
[ {Item,Count} || {Item,Count} <- Inventory, Gold >= shopping:cost(Item) andalso Count > 0 ].


Now we've got a single statement. There's a lot going on here. Let's break it down. The || operator separates the mapping operations from the filtering. The stuff on the right is how we filter out items. The first statement pulls out the individual members of Inventory. It creates two variables Item and Count from the tuple. This does the same thing as our [ X | T ] notation. Those variables are used in the statements to the right to filter each member of the list (i.e. after the comma). If this item passes the filter it's passed to the left side of the || operator to map it into the resulting list. Notice we're doing something like we did in the inline function in our second attempt.

Let's compile and see our results.


40> c(shopping).
{ok,shopping}
41> shopping:find_possible_purchases( 150, [{ longbow, 3 }, { sword, 1 }, { bow, 2 }, { shield, 0 }, { longsword, 3 } ] ).
[{longbow,3},{sword,1},{bow,2}]


Alright it works. So there you have it three different ways to write the same function in Erlang. Our first implementation used only a very minimal capabilities of Erlang. It was lots of code, but hopefully it gave you the basis to understand how Erlang expresses flow control. Our next two examples built on that knowledge to simplify those raw skills into something that's easier to use. Hope you enjoyed this little lesson.

3 comments:

Isaac Gouy said...
This comment has been removed by the author.
Isaac Gouy said...

In Erlang you don't have maps or dictionaries.

That is not correct!

"Dict implements a Key - Value dictionary"

Also see ets and other standard libraries

chubbard said...

Sorry I stand corrected. :-)

Thanks Isaac.