Clementson's Blog

MapReduce Beer Song in Erlang

Sunday, May 20, 2007

In an earlier post, I created a concurrent Erlang version of the "99 Bottles of Beer" beer song. In that post, I mentioned that I was reading a beta copy of Joe Armstrong's new book Programming Erlang - Software for a Concurrent World. Well, in that book, Joe creates a simplistic version of MapReduce in Erlang. (I described MapReduce in my earlier post on "Concurrent/Parallel Programming - The Next Generation"). So, I decided to implement the beer song using Joe's Erlang version of MapReduce. (Note: Although you have to pay for a copy of Joe's book, the source code from the book is freely downloadable. If you want to try out my program below, you will need the "phofs.erl" file from that code archive.)

Basically, usage of Joe's mapreduce function is as follows:

1. The calling program calls the mapreduce(F1, F2, Acc0, L) function passing it 4 parameters:
1. F1: The name of the "map" function that will do whatever operation needs to be done on each list element that will be processed.
2. F2: The name of the "reduce" function that will take all of the output from the "map" function calls and assemble them into a list to return to the caller.
3. Acc0: The initialized value of the output list to be used by F2.
4. L: The input list that will be processed by the F1 mapping function.
2. For each element of the "L" input list, the mapreduce function spawns off a new "F1" mapping process.
3. The mapreduce function also runs the "F2" reduce process to assemble all of the output from the "F1" processes into a single list.
4. The calling program receives back the list containing all of the results from the mapreduce function and does whatever it needs to do with that list.

-module(beersong).
-export([sing/0]).

template(0)  -> "~s of beer on the wall, ~s of beer.~nGo to the store and buy some more, 99 bottles of beer on the wall.~n";
template(_N) -> "~s of beer on the wall, ~s of beer.~nTake one down and pass it around, ~s of beer on the wall.~n~n".

bottles() -> lists:seq(0,99).

phrase(0)      -> ["No more bottles", "no more bottles"];
phrase(1)      -> ["1 bottle", "1 bottle", "no more bottles"];
phrase(2)      -> ["2 bottles", "2 bottles", "1 bottle"];
phrase(Bottle) -> lists:duplicate(2, integer_to_list(Bottle) ++ " bottles") ++ [integer_to_list(Bottle-1) ++ " bottles"].

do_map(Pid, 0)      -> Pid ! {0, io_lib:format(template(0), phrase(0))};
do_map(Pid, Bottle) -> Pid ! {Bottle, io_lib:format(template(Bottle), phrase(Bottle))}.

do_reduce(Key, Verse, A) -> [{Key, Verse}|A].

sing() ->
    F1 = fun do_map/2,
    F2 = fun do_reduce/3,
    L1 = phofs:mapreduce(F1, F2, [], bottles()),
    lists:map(fun(X) -> {_, Verse} = X, io:format(Verse) end, lists:reverse(lists:sort(L1))),
    ok.