DigitalJoel

2011/03/31

Erlang Concurrency Demo Application

Filed under: development — Tags: , — digitaljoel @ 9:37 pm

As I said in my last post I was responsible for a demo in Erlang today. Before starting this application, I had about 2 hours of experience programming in Erlang. Day 3 in Bruce Tate’s book, Seven Languages in Seven Weeks focused on the concurrency aspects of Erlang. I was looking for an example program I could write that would demonstrate this, and didn’t want to just copy the example from the book. I asked on StackOverflow.com and didn’t really get anything I wanted to tackle.

Finally, last night while on my way to Kenpo I was able to think up this cool application. One process would be the air traffic control tower. Then, other processes would be all of the airplanes. Here’s the whole program

-module(aircontrol).
-export([run/0, fastrun/0, tower/0, createPlane/5, removePlane/2, addPlane/3]).

% method to run the program, creating a tower and some planes.
% in this run, 4 of the 5 planes crash
run() ->
  Tower = tower(),
  createPlane(Tower, 1, 5, 5, 2000),
  createPlane(Tower, 2, 1, 1, 4000),
  createPlane(Tower, 3, 1, 5, 6000),
  createPlane(Tower, 4, 5, 3, 10000),
  createPlane(Tower, 5, 5, 1, 5000).

% all planes survive here
fastrun() ->
  Tower = tower(),
  createPlane(Tower, 1, 5, 5, 30),
  createPlane(Tower, 2, 1, 1, 10),
  createPlane(Tower, 3, 1, 5, 30),
  createPlane(Tower, 4, 5, 3, 10),
  createPlane(Tower, 5, 5, 1, 10).

 

%%%%%%%%%%%%% Tower methods %%%%%%%%%%%%
tower() -> 
  io:format( "Tower ready for duty~n" ),
  spawn( fun() -> tower(lists:duplicate(25, null ))end).

tower(Occupied) ->
  receive
    {arrive, {Plane, Id, 3, 3 }} ->
      io:format("Tower: Flight ~p, welcome home.~n", [Id] ),
      tower(removePlane(Plane, Occupied));

    {arrive, {Plane, Id, X, Y }} ->
      {NewX, NewY} = getBearing( X, Y),
      io:format( "Tower: Flight ~p, please head to bearing (~p, ~p)~n", [Id, NewX, NewY]),
      Plane ! {bearing, getBearing( X, Y )},
      tower( addPlane( Plane, ((Y-1)*5)+X, removePlane( Plane, Occupied )));

    _ -> io:format( "Tower: I don't understand. ~n" )
end.

removePlane(Plane, List) -> lists:map(
  fun(X) -> 
    if 
      X == Plane -> null; 
      true -> X
    end
  end
, List).

addPlane(Plane, Index, List) -> 
  Occupant = lists:nth( Index, List ),
  if
    Occupant /= null ->
      Occupant ! crash,
      Plane ! crash,
      removePlane(Occupant, List );
    true ->
      lists:append([lists:sublist(List, Index-1), [Plane], lists:sublist(List, Index+1, 25)])
  end.

% get the next bearing as an X,Y tuple
getBearing(X, Y) ->
  if
    Y /= 3 -> {X, getBearing(Y)};
    true -> {getBearing(X), Y}
  end.

% Get a component of the next bearing
getBearing(Num) ->
  case Num of
    1 -> 2;
    2 -> 3;
    3 -> 3;
    4 -> 3;
    5 -> 4
  end.


%%%%%%%% Plane methods %%%%%%%%

createPlane(Tower, Id, X, Y, Speed) ->
  Plane = spawn(fun() -> plane(Tower, Id, Speed) end ),
  Plane ! {new, {X, Y}}.

plane(Tower, Id, Speed) ->
  receive
    {new, {X, Y}} ->
      io:format("Flight ~p created at (~p, ~p)~n", [Id, X, Y]),
      Tower ! {arrive, {self(), Id, X, Y }},
      plane(Tower, Id, Speed);
  
    {bearing, {X, Y}} ->
      io:format("Roger that tower, Flight ~p heading to bearing (~p, ~p)~n", [Id, X, Y]),
      timer:sleep(Speed),
      Tower ! {arrive, {self(), Id, X, Y}},
      plane(Tower, Id, Speed);

    crash ->
      io:format("MAYDAY! MAYDAY!, Flight ~p is going down!~n", [Id])
end.

Alright, what is going on here. You have a playing field that is a 5×5 grid. Each plane will be in one section of the grid at a time, so a plane that is at location (1,1) is in the top left corner, and a plane at (5,5) is in the bottom right corner. The airport (and the control tower) is at (3,3) and if a plane gets to the airport then it lands and is not tracked anymore.

Each plane has a flight number, coordinates, and a speed. The speed may be counter intuitive because the lower the number, the faster the plane flies. A plane with a speed of 2000 means that it takes 2000 milliseconds (or 2 seconds) to go from one square to the next. If two planes are in the same square in the playing field, then they collide and crash. Obviously we don’t want this to happen, but whoever is running the tower isn’t very good at their job.

When a plane arrives at a new square it checks in with the tower. The tower then tells it which square to go to next. The plane travels at its speed to the next square, checking in with the tower when it arrives, and getting new coordinates from the tower, and so on, until the plane arrives at the airport.

So, let’s step through and see where in the code this is all happening.

run() ->
  Tower = tower(),
  createPlane(Tower, 1, 5, 5, 2000),
  % create more planes here.

The run method takes care of creating the tower, and the planes, which sets everything in motion. When we call tower(), here’s what happens


tower() -> 
  % print a method to the user telling them that the tower is starting up.
  io:format( "Tower ready for duty~n" ),

  % spawn the tower process.  This is a little different than the spawn code in the book.  In the book none of the functions
  % used to spawn a process took any parameters.  Here we need to pass a list that says which places on the grid are 
  % currently occupied by planes.  I seed that list with 25 null values.  25 for the 5x5 grid, using an offset scheme within
  % the list to represent the different rows in the grid.
  spawn( fun() -> tower(lists:duplicate(25, null ))end).

After spawning the tower, it goes into its receive loop. The receive loop accepts one type of message which contains the atom
receive and a tuple containing the Plane process, the flight number, and the (X,Y) coordinates that the plane arrived at. There are two cases I handle here, the first being when the plane has arrived at the airport safely, and the second being where the tower needs to tell the plane where to go to next.

tower(Occupied) ->
  receive
    {arrive, {Plane, Id, 3, 3 }} ->
      % in this case, the plane has arrived at the airport
      io:format("Tower: Flight ~p, welcome home.~n", [Id] ),

      % since the plane has landed, remove it from the list of planes that are in the air.
      % and recursively call ourselves with the new list so we can receive messages from more planes.
      tower(removePlane(Plane, Occupied));

    {arrive, {Plane, Id, X, Y }} ->
      % in this case the plane has arrived at some square and needs directions on where to go next.

      % Here we get the new bearings for the flight
      {NewX, NewY} = getBearing( X, Y),
      io:format( "Tower: Flight ~p, please head to bearing (~p, ~p)~n", [Id, NewX, NewY]),

      % and here we send the bearings to the plane.
      Plane ! {bearing, getBearing( X, Y )},

      % next we change the location of the plane in the grid.
      tower( addPlane( Plane, ((Y-1)*5)+X, removePlane( Plane, Occupied )));

    _ -> io:format( "Tower: I don't understand. ~n" )
end.

I’m not going to go into the guts of how we figure out where the plane should go. The tower will always move a plane on the Y axis until it gets to 3, then it moves it along the X axis toward the airport. This isn’t the greatest algorithm in order to avoid a collision, but it is what it is.

The code where we figure out if we have a crash is in the addPlane method, which is as follows:

addPlane(Plane, Index, List) -> 
  % get the current occupant of the target space
  Occupant = lists:nth( Index, List ),

  if
    Occupant /= null ->
      % if the occupant isn't null, then we have a collision.
      % send a message to each of the planes in the space letting them know there's a problem.
      Occupant ! crash,
      Plane ! crash,

      % because Plane is not in the list, we only need to remove the Occupant.
      removePlane(Occupant, List );

    true ->
      % otherwise, Occupant is null, so we can just add this plane to the list.
      lists:append([lists:sublist(List, Index-1), [Plane], lists:sublist(List, Index+1, 25)])
  end.

Now, on to the code for the airplanes. First, the code to create a new plane. This is a convenience method since we could obviously spawn them and send the message ourselves


createPlane(Tower, Id, X, Y, Speed) ->
  % spawn the process, passing in the tower, flight id, and speed
  Plane = spawn(fun() -> plane(Tower, Id, Speed) end ),

  % then we send a message to the process, letting it know its starting location
  Plane ! {new, {X, Y}}.

Next, we need a receive loop for the plane so it can get the messages back from the tower. Receive accepts three messages, either the atom new with coordinates, the atom bearing with coordinates, or the atom crash. Perhaps the first two could be combined into a single match, but I implemented them separate. Here is the implementation.

plane(Tower, Id, Speed) ->
  receive
    {new, {X, Y}} ->
      io:format("Flight ~p created at (~p, ~p)~n", [Id, X, Y]),

      % we need to get on the radar with the tower, so tell them where we are so they can tell us where to go next
      Tower ! {arrive, {self(), Id, X, Y }},

      % now recurse into our receive loop again
      plane(Tower, Id, Speed);
  
    {bearing, {X, Y}} ->
      io:format("Roger that tower, Flight ~p heading to bearing (~p, ~p)~n", [Id, X, Y]),

      % the second receive pattern sleeps for Speed ms to simulate the time it takes to fly from
      % one square to the next
      timer:sleep(Speed),

      % once we arrive, we need to tell the tower where we are, then recurse into the loop again to accept more messages.
      Tower ! {arrive, {self(), Id, X, Y}},
      plane(Tower, Id, Speed);

    crash ->
      % if we crash, we don't recurse back into the receive loop because our process is done.
      io:format("MAYDAY! MAYDAY!, Flight ~p is going down!~n", [Id])
end.

So, there you go. A sample concurrency implementation written in erlang made up completely in my head. I was very happy with how this turned out, and it only took me a couple hours to program it. Yeah, the meat of the implementation (without the run methods) is only about 80 lines, but it does a lot in those lines, and I think it’s something coming from an entrenched OO programmer.

Project Euler problem 22 in Erlang

Filed under: development — Tags: , — digitaljoel @ 7:24 pm

At work I’m in a reading group covering Bruce Tate’s Seven Languages in Seven Weeks. Each week we get together for an hour to discuss the current language. One person or duo is responsible for giving a presentation on the current language. This week was Erlang, and I was partly responsible for the presentation. After reading the chapter, I was trying to find a small program I could write in order to demonstrate some of the concepts discussed. I settled on problem 22 of Project Euler.

The problem is as follows:

Using names.txt (right click and ‘Save Link/Target As…’), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 53 = 49714.

What is the total of all the name scores in the file?

This is the very first problem I tried to solve with Erlang. Fortunately, the documentation on the language is pretty good, and the standard libraries are nice too. When I started programming in 1993 in college, my first language was Pascal, but I haven’t done much in a functional language since then, and working in Java exclusively for my occupation since 2000 hasn’t really kept me in the functional frame of mind. Anyway, to the code.

-module(euler).
-export([prob22/0]).

% http://projecteuler.net/index.php?section=problems&id=22
% problem 22 in project euler.
% Load the names in names.txt, then sort them alphabetically
% Then working out the alphabetical value for each name, multiply this value 
% by its alphabetical position in the list to obtain a name score.
% Then find the total of all name scores in the file.
%
% I massaged input by putting all names on their own line and remove quote characters
% before running this program.

prob22() -> 
    UnsortedNameList = readlines("names.txt"),
    SortedNameList = lists:sort(UnsortedNameList),
    % convert the Names to the integers representing the characters.
    % but don't accept the \n at the end of each name.
    NumberNameList = lists:map(fun(Name) -> [X-64 || X <- Name, X>64] end, SortedNameList),
    % NumberNameList contains all the names adjusted so A=1, B=2, etc.
    addNameValues( NumberNameList, 1).

% add the name values in the list, as specified in the requirements of problem 22.
addNameValues( [], _ ) -> 0;
addNameValues( [Head|Tail], Index ) -> 
    HeadValue = lists:foldl(fun(X, Sum) -> X + Sum end, 0, Head),
    HeadValue*Index + addNameValues(Tail, Index+1).
    

% file reading blatantly borrowed from http://www.trapexit.org/Read_File_to_List
readlines(FileName) ->
    {ok, Device} = file:open(FileName, [read]),
    get_all_lines(Device, []).

get_all_lines(Device, Accum) ->
    case io:get_line(Device, "") of
        eof  -> file:close(Device), lists:reverse(Accum);
        Line -> get_all_lines(Device, [Line|Accum])
    end.

Not any big rocket science. Note that I modified the source file by putting each name on its own line and removing the quotes around each name, so maybe that’s cheating, but I only had a little while to work on this, so I didn’t want to spend the time really looking into getting around that.

In the book, each of the functions were quite terse with their variable names and most were a single line. I didn’t feel like that did the reader any favors, but just for fun I thought I would try to condense it a bit. Here’s what I came up with

-module(eulerSmall).
-export([prob22/0]).

prob22() -> add( lists:map(fun(N) -> [X-64 || X <- N, X>64] end, lists:sort(readlines("names.txt"))), 1).

% add the name values in the list, as specified in the requirements of problem 22.
add( [], _ ) -> 0;
add( [H|T], I ) -> I * lists:foldl(fun(X, Sum) -> X + Sum end, 0, H) + add(T, I+1).

% file reading blatantly borrowed from http://www.trapexit.org/Read_File_to_List
readlines(FileName) ->
    {ok, Device} = file:open(FileName, [read]),
    get_all_lines(Device, []).

get_all_lines(Device, Accum) ->
    case io:get_line(Device, "") of
        eof  -> file:close(Device), lists:reverse(Accum);
        Line -> get_all_lines(Device, [Line|Accum])
    end.

Notice that by combining all of the list manipulation together, the prob22() function now takes a single line. That’s kind of fun.

2010/05/16

Pair Programming Without The Bad Breath

Filed under: general — Tags: , , — digitaljoel @ 11:05 pm

Let’s say you are working from home, but you need to do a code review or want to do pair programming or something. I was in this situation last week with a good friend. He lives about 45 minutes from me and neither of us were really in the mood to do any driving. We are both working on macbooks. I was planning on driving the programming session, so he put together the following instructions for setting up SSH access to my computer

Steps for setup:

  1. Open TCP port of your choice on the router and forward that to port 22 of the IP for your Mac (ifconfig @ command prompt, or use the network control panel to get your IP).
  2. Create a user/pwd that I can use to connect with in the Accounts Preferences Panel*
  3. Turn on Remote Login in the Sharing Preferences Panel (System Preferences).
  4. Turn on Screen Sharing.
  5. Add that user to the list of who can connect in the Allow access list box.
  6. Go to the Firewall preference panel and click on Advanced… Ensure that ssh is allowed through.

Finally, I gave him my IP address and his account information and he logged in through SSH, started screen sharing and was then viewing EVERYTHING I was viewing on the screen.  We also started up iChat and started a voice chat through our AIM connection.  The sound was actually very good and the screen sharing performance was also very good.  My friend said he could see the change on the screen as soon as he heard the key press through the microphone.

In order to connect, he issued the following command line.

ssh -p <yourport> -f -L 1200:localhost:5900 <iphere> sleep 10 ; open vnc://localhost:1200

where <iphere> is replaced by the ip address I sent to him, and <yourport> is the port specified in step one.  Note that the username I setup on my machine was the same as the username he uses on his machine so he didn’t have to specify a username at login time.

We worked for about 3 hours this way, talking and programming without any issues.  Will it 100% replace in-person pair programming or code reviews, certainly not, but I plan to use it a lot with my buddy.

*You probably shouldn’t be sending the username/password combination to your friend through email or something like that.  I called mine to give him that sensitive information.

Create a free website or blog at WordPress.com.