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.

About these ads

1 Comment »

  1. Excellent example. I’m going to try this for starters :D

    Comment by Herman A. Junge — 2011/07/14 @ 11:08 pm


RSS feed for comments on this post. TrackBack URI

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

The Silver is the New Black Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 224 other followers