Learn Me Some Erlang

[learnesomeerlang]

Designing a Concurrent Application - The Event Server (part VIII)

Implementing the Status Messages

shutdown -> exit(shutdown); {'DOWN', Ref, process, _Pid, _Reason} -> loop(S#state{clients=orddict:erase(Ref, S#state.clients)}); code_change -> ?MODULE:loop(S); Unknown -> io:format("Unknown message: ~p~n",[Unknown]), loop(S)

The first case (shutdown) is pretty explicit. You get the kill message, let the process die. If you wanted to save state to disk, that could be a possible place to do it. If you wanted safer save/exit semantics, this could be done on every add, cancel or done message. Loading events from disk could then be done in the init function, spawning them as they come.--book

The 'DOWN' message's actions are also simple enough. It means a client died, so we remove it from the client list in the state.--book

Unknown messages will just be shown with io:format/2 for debugging purposes, although a real production application would likely use a dedicated logging module--book

And here comes the code change message. This one is interesting enough for me to give it its own section.--book

[learnesomeerlang]

Designing a Concurrent Application - The Event Server (part VII)

Implementing the Event Timing Out Message - reminder fire away

the events timing out. That message is simply {done, Name}:--book

{done, Name} -> case orddict:find(Name, S#state.events) of {ok, E} -> send_to_clients({done, E#event.name, E#event.description}, S#state.clients), NewEvents = orddict:erase(Name, S#state.events), loop(S#state{events=NewEvents}); error -> %% This may happen if we cancel an event and %% it fires at the same time loop(S) end;

And the function send_to_clients/2 does as its name says and is defined as follows:--book

send_to_clients(Msg, ClientDict) -> orddict:map(fun(_Ref, Pid) -> Pid ! Msg end, ClientDict).

[learnesomeerlang]

Designing a Concurrent Application - The Event Server (part VI)

Implementing the Client Message - cancel (cancel a reminder)

The next message defined in our protocol is the one where we cancel an event. Canceling an event never fails on the client side, so the code is simpler there. Just check whether the event is in the process' state record. If it is, use the event:cancel/1 function we defined to kill it and send ok. If it's not found, just tell the user everything went right anyway -- the event is not running and that's what the user wanted.--book

{Pid, MsgRef, {cancel, Name}} -> Events = case orddict:find(Name, S#state.events) of {ok, E} -> event:cancel(E#event.pid), orddict:erase(Name, S#state.events); error -> S#state.events end, Pid ! {MsgRef, ok}, loop(S#state{events=Events});

[learnesomeerlang]

Designing a Concurrent Application - The Event Server (part V)

Implementing the Client Message - add (adding a reminder)

{Pid, MsgRef, {add, Name, Description, TimeOut}}

The next message to care about is the one where we add events. Now, it is possible to return an error status. The only validation we'll do is check the timestamps we accept. While it's easy to subscribe to the {{Year,Month,Day}, {Hour,Minute,seconds}} layout, we have to make sure we don't do things like accept events on February 29 when we're not in a leap year, or any other date that doesn't exist. Moreover, we don't want to accept impossible date values such as "5 hours, minus 1 minute and 75 seconds". A single function can take care of validating all of that.--book

The first building block we'll use is the function calendar:valid_date/1. This one, as the name says, checks if the date is valid or not. Sadly, the weirdness of the calendar module doesn't stop at funky names: there is actually no function to confirm that {H,M,S} has valid values. We'll have to implement that one too, following the funky naming scheme:--book

valid_datetime({Date,Time}) -> try calendar:valid_date(Date) andalso valid_time(Time) catch error:function_clause -> %% not in {{Y,M,D},{H,Min,S}} format false end; valid_datetime(_) -> false. valid_time({H,M,S}) -> valid_time(H,M,S). valid_time(H,M,S) when H >= 0, H < 24, M >= 0, M < 60, S >= 0, S < 60 -> true; valid_time(_,_,_) -> false.

Now on to implementing the add message with datetime valid function:

{Pid, MsgRef, {add, Name, Description, TimeOut}} -> case valid_datetime(TimeOut) of true -> EventPid = event:start_link(Name, TimeOut), NewEvents = orddict:store(Name, #event{name=Name, description=Description, pid=EventPid, timeout=TimeOut}, S#state.events), Pid ! {MsgRef, ok}, loop(S#state{events=NewEvents}); false -> Pid ! {MsgRef, {error, bad_timeout}}, loop(S) end;

If the time is valid, we spawn a new event process, then store its data in the event server's state before sending a confirmation to the caller. If the timeout is wrong, we notify the client rather than having the error pass silently or crashing the server. Additional checks could be added for name clashes or other restrictions (just remember to update the protocol documentation!)--book

[learnesomeerlang]

Designing a Concurrent Application - The Event Server (part IV)

Implementing the Client Message - Subscribe

Remember the skeleton code:

-module(evserv). -compile(export_all). loop(State) -> receive {Pid, MsgRef, {subscribe, Client}} -> ... {Pid, MsgRef, {add, Name, Description, TimeOut}} -> ... {Pid, MsgRef, {cancel, Name}} -> ... {done, Name} -> ... shutdown -> ... {'DOWN', Ref, process, _Pid, _Reason} -> ... code_change -> ... Unknown -> io:format("Unknown message: ~p~n",[Unknown]), loop(State) end.

We're going to implement each message one by one:

{Pid, MsgRef, {subscribe, Client}} -> Ref = erlang:monitor(process, Client), NewClients = orddict:store(Ref, Client, S#state.clients), Pid ! {MsgRef, ok}, loop(S#state{clients=NewClients});

So what this section of loop/1 does is start a monitor, and store the client info in the orddict under the key Ref. The reason for this is simple: the only other time we'll need to fetch the client ID will be if we receive a monitor's EXIT message, which will contain the reference (which will let us get rid of the orddict's entry).--book

[learnesomeerlang]

Designing a Concurrent Application - The Event Server (part III)

Convert events and clients to orddicts

It would be nice if both events and clients were orddicts. We're unlikely to have many hundreds of them at once. If you recall the chapter on data structures, orddicts fit that need very well. We'll write an init function to handle this:--book

init() -> %% Loading events from a static file could be done here. %% You would need to pass an argument to init telling where the %% resource to find the events is. Then load it from here. %% Another option is to just pass the events straight to the server %% through this function. loop(#state{events=orddict:new(), clients=orddict:new()}).

[learnesomeerlang]

Designing a Concurrent Application - The Event Server (part II)

Adding State to The Event Server

Now, the server will need to keep two things in its state:--book

a list of subscribing clients

and a list of all the event processes it spawned.

If you have noticed, the protocol says that when an event is done, the event server should receive {done, Name}, but send {done, Name, Description}. The idea here is to have as little traffic as necessary and only have the event processes care about what is strictly necessary. So yeah, list of clients and list of events:--book

-record(state, {events, %% list of #event{} records clients}). %% list of Pids -record(event, {name="", description="", pid, timeout={{1970,1,1},{0,0,0}}}).

So the two things in state is events and clients.

And the loop now has the record definition in its head:

loop(S = #state{}) -> receive ... end.

[learnesomeerlang]

Designing a Concurrent Application - The Event Server (part I)

The Event Server (layout and stuff)

According to the protocol, the skeleton for that one should look a bit like this:--book

-module(evserv). -compile(export_all). loop(State) -> receive {Pid, MsgRef, {subscribe, Client}} -> ... {Pid, MsgRef, {add, Name, Description, TimeOut}} -> ... {Pid, MsgRef, {cancel, Name}} -> ... {done, Name} -> ... shutdown -> ... {'DOWN', Ref, process, _Pid, _Reason} -> ... code_change -> ... Unknown -> io:format("Unknown message: ~p~n",[Unknown]), loop(State) end.

You'll notice I have wrapped calls that require replies with the same {Pid, Ref, Message} format as earlier.--book

{Pid, MsgRef, {subscribe, Client}} -> ... {Pid, MsgRef, {add, Name, Description, TimeOut}} -> ... {Pid, MsgRef, {cancel, Name}} ->

[learnesomeerlang]

Designing a Concurrent Application - An Event Module (part V)

Better Time Style instead of Milliseconds

The last thing annoying with the event module is that we have to input the time left in seconds. It would be much better if we could use a standard format such as Erlang's datetime ({{Year, Month, Day}, {Hour, Minute, Second}}). Just add the following function that will calculate the difference between the current time on your computer and the delay you inserted:--book

time_to_go(TimeOut={{_,_,_}, {_,_,_}}) -> Now = calendar:local_time(), ToGo = calendar:datetime_to_gregorian_seconds(TimeOut) - calendar:datetime_to_gregorian_seconds(Now), Secs = if ToGo > 0 -> ToGo; ToGo =< 0 -> 0 end, normalize(Secs).

Now fix the init function to call this one instead of normalize/1. You can also rename Delay variables to say DateTime if you want the names to be more descriptive:--book

init(Server, EventName, DateTime) -> loop(#state{server=Server, name=EventName, to_go=time_to_go(DateTime)}).

[learnesomeerlang]

Designing a Concurrent Application - An Event Module (part IV)

Abstracting the cancel msg

So instead of having the user knowing how the message cancel is structured we're going to abstract it. Reminder of the cancel message structure: {Server, Ref, cancel}

Here's a reminder how loop is implemented to recieve the cancel message.

% ... receive {Server, Ref, cancel} -> Server ! {Ref, ok} % ...

So here's the abstraction or an interface to the cancel message:

cancel(Pid) -> %% Monitor in case the process is already dead Ref = erlang:monitor(process, Pid), Pid ! {self(), Ref, cancel}, receive {Ref, ok} -> erlang:demonitor(Ref, [flush]), ok; {'DOWN', Ref, process, Pid, _Reason} -> ok end.

So what do we have here?

It looks normal except for these new functions:

erlang:monitor(process, Pid)

erlang:demonitor(Ref, [flush])

"Oh! A new trick! Here I'm using a monitor to see if the process is there or not. If the process is already dead, I avoid useless waiting time and return ok as specified in the protocol. If the process replies with the reference, then I know it will soon die: I remove the reference to avoid receiving them when I no longer care about them. Note that I also supply the flush option, which will purge the DOWN message if it was sent before we had the time to demonitor."--book

A wut? ("drank")

"Oh! A new trick! Here I'm using a monitor to see if the process is there or not."

%% Monitor in case the process is already dead Ref = erlang:monitor(process, Pid),

"If the process is already dead, I avoid useless waiting time and return ok as specified in the protocol."

{'DOWN', Ref, process, Pid, _Reason} -> ok

"If the process replies with the reference, then I know it will soon die: I remove the reference to avoid receiving them when I no longer care about them. Note that I also supply the flush option, which will purge the DOWN message if it was sent before we had the time to demonitor."

{'DOWN', Ref, process, Pid, _Reason} -> ok

Test (Let's test these)

17> c(event). {ok,event} 18> f(). ok 19> event:start("Event", 0). <0.103.0> 20> flush(). Shell got {done,"Event"} ok 21> Pid = event:start("Event", 500). <0.106.0> 22> event:cancel(Pid). ok

[learnesomeerlang]

Designing a Concurrent Application - An Event Module (part III)

Abstracting Timeout Problem

"It would be very annoying to have to manually call something like event:normalize(N) every time an event process is started, especially since our workaround shouldn't be of concern to programmers using our code. The standard way to do this is to instead have an init function handling all initialization of data required for the loop function to work well."--book

start(EventName, Delay) -> spawn(?MODULE, init, [self(), EventName, Delay]). start_link(EventName, Delay) -> spawn_link(?MODULE, init, [self(), EventName, Delay]). %%% Event's innards init(Server, EventName, Delay) -> loop(#state{server=Server, name=EventName, to_go=normalize(Delay)}).

So is going on with the code?

Let's start with this piece of code:

%%% Event's innards init(Server, EventName, Delay) -> loop(#state{server=Server, name=EventName, to_go=normalize(Delay)}).

We're abstracting the workaround to an interface init(Server, EventName, Delay).

start(EventName, Delay) -> spawn(?MODULE, init, [self(), EventName, Delay]).

We're basically abstracting the spawn process. So instead of havin the user calling the spawn/3 function, we automated ourself.

start_link(EventName, Delay) -> spawn_link(?MODULE, init, [self(), EventName, Delay]).

We're basically abstracting the spawn_link process. So instead of havin the user calling the spawn_link/3 function, we automated ourself.

[learnesomeerlang]

Designing a Concurrent Application - An Event Module (part II)

Timeout Problem

"It turns out Erlang's timeout value is limited to about 50 days in milliseconds."

See for yourself:

15> spawn(event, loop, [#state{server=self(), name="test", to_go=365*24*60*60}]). <0.69.0> 16> =ERROR REPORT==== DD-MM-YYYY::HH:mm:SS === Error in process <0.69.0> with exit value: {timeout_value,[{event,loop,1}]}

Workaround

%% Because Erlang is limited to about 49 days (49*24*60*60*1000) in %% milliseconds, the following function is used normalize(N) -> Limit = 49*24*60*60, [N rem Limit | lists:duplicate(N div Limit, Limit)].

Basically divided by chunks for 49 days and put it in a list, with the remainder in the list too.

Wut?

Let's concentrate on this line:

[N rem Limit | lists:duplicate(N div Limit, Limit)].

Let's say we're doing 2*49 days + 4 remainders (4 milliseconds).

The lists:duplicate(N div Limit, Limit) will devide N by Limit, so basically you'll get 2 because the max days we can have per list is 49 days. So the code lists:duplicate(N div Limit, Limit) will created a list [49,49]

The N rem Limit gets the remainder which is 4 ms.

Then we concatenate the remainders with the 49 days list [N rem Limit | lists:duplicate(N div Limit, Limit)]. Basically [4 | [49,49]] which is [4,49,49].

Modify Loop to use Workaround

%% Loop uses a list for times in order to go around the ~49 days limit %% on timeouts. loop(S = #state{server=Server, to_go=[T|Next]}) -> receive {Server, Ref, cancel} -> Server ! {Ref, ok} after T*1000 -> if Next =:= [] -> Server ! {done, S#state.name}; Next =/= [] -> loop(S#state{to_go=Next}) end end.

We now take a list,[T|Next], in the to_go property of the state record.

In the after we a value from the to_go list and continue to take each one until none or left before sending a message ({done, S#state.name}) to the Server.

[learnesomeerlang]

Designing a Concurrent Application - An Event Module (part I)

An Event Module

-module(event). -compile(export_all). -record(state, {server, name="", to_go=0}). loop(S = #state{server=Server}) -> receive {Server, Ref, cancel} -> Server ! {Ref, ok} after S#state.to_go*1000 -> Server ! {done, S#state.name} end.

The reason why I bind the variable 'Server' in the function head is because it's used in pattern matching in the receive section. Remember, records are hacks! The expression S#state.server is secretly expanded to element(2, S), which isn't a valid pattern to match on.--book

Wtf does this mean? This mean that:

loop(S = #state{server=Server}) ->

becomes:

element(2, S)

So

receive {Server, Ref, cancel} ->

the Server cannot pattern match with element(2, S), it's not valid.

Therefore we needed to do this:

loop(S = #state{server=Server}) ->

This still works fine for S#state.to_go after the after part, because that one can be an expression left to be evaluated later.--book

[learnesomeerlang]

It was getting slow so I skim through the other chapters

So it was getting slow so I skim through the chapters to get to where I can build a concurrent application...

[learnesomeerlang]

Picture: The Clash - London Calling

Heathrow to London - PART II

Reading/Parsing Files

1> {ok, Binary} = file:read_file("road.txt"). {ok,<<"50\r\n10\r\n30\r\n5\r\n90\r\n20\r\n40\r\n2\r\n25\r\n10\r\n8\r\n0\r\n">>} 2> S = string:tokens(binary_to_list(Binary), "\r\n\t "). ["50","10","30","5","90","20","40","2","25","10","8","0"]

3> [list_to_integer(X) || X <- S]. [50,10,30,5,90,20,40,2,25,10,8,0]

-module(road). -compile(export_all). main() -> File = "road.txt", {ok, Bin} = file:read_file(File), parse_map(Bin). parse_map(Bin) when is_binary(Bin) -> parse_map(binary_to_list(Bin)); parse_map(Str) when is_list(Str) -> [list_to_integer(X) || X <- string:tokens(Str,"\r\n\t ")].

group_vals([], Acc) -> lists:reverse(Acc); group_vals([A,B,X|Rest], Acc) -> group_vals(Rest, [{A,B,X} | Acc]).

parse_map(Bin) when is_binary(Bin) -> parse_map(binary_to_list(Bin)); parse_map(Str) when is_list(Str) -> Values = [list_to_integer(X) || X <- string:tokens(Str,"\r\n\t ")], group_vals(Values, []).

1> c(road). {ok,road} 2> road:main(). [{50,10,30},{5,90,20},{40,2,25},{10,8,0}]

the book chapter

[learnesomeerlang]

Heathrow to London

the book chapter

You're on a plane due to land at Heathrow airport in the next hours. You have to get to London as fast as possible; your rich uncle is dying and you want to be the first there to claim dibs on his estate.--book

There are two roads going from Heathrow to London and a bunch of smaller streets linking them together. Because of speed limits and usual traffic, some parts of the roads and smaller streets take longer to drive on than others. Before you land, you decide to maximize your chances by finding the optimal path to his house. Here's the map you've found on your laptop--book

road.txt:

50 10 30 5 90 20 40 2 25 10 8 0

The road is laid in the pattern: A1, B1, X1, A2, B2, X2, ..., An, Bn, Xn, where X is one of the roads joining the A side to the B side of the map. We insert a 0 as the last X segment, because no matter what we do we're at our destination already. Data can probably be organized in tuples of 3 elements (triples) of the form {A,B,X}.--book

Writing a Recursive Function

Base case

When writing a recursive function, the first thing to do is to find our base case. For our problem at hand, this would be if we had only one tuple to analyze, that is, if we only had to choose between A, B (and crossing X, which in this case is useless because we're at destination)--book

A ---10 min-- | Destination | B ---23 min---

In base case scenario you got two options, or rather two roads that leads to your destination. Either you pick road A which will take you 10 minutes to get to your destination or road B which takes 23 minutes.

Then the choice is only between picking which of path A or path B is the shortest. If you've learned your recursion right, you know that we ought to try and converge towards the base case. This means that on each step we'll take, we'll want to reduce the problem to choosing between A and B for the next step.--book

Let's extend our map and start over:

Ah! It gets interesting! How can we reduce the triple {5,1,3} to a strict choice between A and B?--book

For Point A (*)

A1 Pt A A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 B2

Let's see how many options are possible for A [(*)]. To get to the intersection of A1 and A2 (I'll call this the point A1), I can either take road A1 directly (5), ...

A1 A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 B2

or come from B1 (1) and then cross over X1 (3).

A1 A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 B2

In this case, The first option (5) is longer than the second one (4). For the option A, the shortest path is [B, X].

So what are the options for B?

A1 A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 Pt B B2

You can either proceed from A1 (5) then cross over X1 (3),

A1 A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 Pt B B2

or strictly take the path B1 (1).--book

A1 A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 Pt B B2

Alright! What we've got is a length 4 with the path [B, X] towards the first intersection A and a length 1 with the path [B] towards the intersection of B1 and B2. We then have to decide what to pick between going to the second point A (the intersection of A2 and the endpoint or X2) and the second point B (intersection of B2 and X2). To make a decision, I suggest we do the same as before. Now you don't have much choice but to obey, given I'm the guy writing this text. Here we go!--book

A1 A2 Pt A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 B2 Pt B2

All possible paths to take in this case can be found in the same way as the previous one. We can get to the next point A [Pt A2] by either taking the path A2 from [B, X], which gives us a length of 14 (14 = 4 + 10),

A1 A2 Pt A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 B2

or by taking B2 then X2 from [B], which gives us a length of 16 (16 = 1 + 15 + 0).

A1 A2 Pt A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 B2

In this case, the path [B, X, A] is better than [B, B, X].--book

We can also get to the next point B by either taking the path A2 from [B, X] and then crossing over X2 for a length of 14 (14 = 4 + 10 + 0),

A1 A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 B2 Pt B2

or by taking the road B2 from [B] for a length of 16 (16 = 1 + 15). Here, the best path is to pick the first option, [B, X, A, X].--book

A1 A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 B2 Pt B2

So when this whole process is done, we're left with two paths, A [[B, X, A]] or B [[B, X, A, X]], both of length 14.

[learnesomeerlang]

more of these pictures @ xkcd

Reverse Polish Notation Calculator - PART III

Well an alternative implementation to fun erlang:'*'/2 is:

lists:foldl(fun(X, Prod) -> X * Prod end, 1, [1,2,3,4,5]).

Original book's version

lists:foldl(fun erlang:'*'/2, 1, [0.5, 20, 10, 10]).

Code Review - "breaking it down"

foldl(Fun, Acc0, List) -> Acc1

Calls Fun(Elem, AccIn) on successive elements A of List, starting with AccIn == Acc0. Fun/2 must return a new accumulator which is passed to the next call. The function returns the final value of the accumulator. Acc0 is returned if the list is empty.

The code (that we're analyzing):

lists:foldl(fun(X, Prod) -> X * Prod end, 1, [1,2,3,4,5]).

Fun is fun(X, Prod) -> X * Prod end

Acc0 is 1

List is [1,2,3,4,5]

Elem is X

AccIn is Prod