Learn Me Some Erlang

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

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

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

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;

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});

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

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:

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

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

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)

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

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.

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}) ->

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

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

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