Bill Clementson's Blog

Parallel Map Beer Song in Erlang

Friday, June 1, 2007

When learning a new language, it's important to learn the "idioms" that are peculiar to that language. Since I'm learning Erlang, I'm especially interested in the concurrency-related idioms. Hence, my recent exercises in translating the the "99 Bottles of Beer" beer song into both a concurrent Erlang solution (using standard Erlang spawn/send/receive code) and a MapReduce Erlang version.

Joe Armstrong commented (a year ago) on how easy it was to convert Erlang's map into a pmap (parallel map) command that would map across multiple processes. He goes into this a bit more in his new book Programming Erlang - Software for a Concurrent World and I was interested in reading more about some of the issues that he discussed. So, I did some google'ing and came across a blog post that discussed parallel-map and parallel-foreach in Erlang. That led to another interesting blog post on an implementation of a parallel map that uses job queues to make a more efficient "spread" of the map processes across multiple processors. Both articles were interesting; however, one great little tidbit came out of one of the comments to the first blog posting. Luke Gorrie posted his version of parallel map:

parmap(F, L) ->
    Parent = self(),
    [receive {Pid, Result} -> Result end || Pid <- [spawn(fun() -> Parent ! {self(), F(X)} end) || X <- L]].

-module(beersong3).
-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".

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

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"].

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

parmap(F, L) ->
    Parent = self(),
    [receive {Pid, Result} -> Result end || Pid <- [spawn(fun() -> Parent ! {self(), F(X)} end) || X <- L]].

sing() ->
    L = lists:reverse(lists:sort(parmap(fun(N) -> create_verse(N) end, bottles()))),
    lists:foreach(fun io:format/1, [Verse || {_Bottle, Verse} <- L]).