Erlang Programming Exercise: 5-2
Exercise 5-2 involves changing the frequency server from earlier in the chapter. Here is the task list:
- Restrict the deallocation of a frequency so that only the client that allocated it can deallocate it.
- Fix a bug: Deallocating a frequency that isn't allocated crashes the server
- Only allow shutdown of the frequency server if there are no allocated frequencies
- Limit the number of frequencies a client can allocate to 3
I worked through the tasks and then had a bit of fun with the server. I changed the shutdown sequence so that deallocations work while shutting down but allocations return an error. Once all of the outstanding frequencies have been returned it will complete the shutdown.
As you can see in the code below, I was playing around with typer and dialyzer. Please take a look and let me know if you have any suggestions.
Thanks!
Halzy
-module(frequency).
-export([start/0, stop/0, allocate/0, deallocate/1, deallocate_all/0]).
-export([init/0]).
-define(SERVER, ?MODULE).
-type frequency() :: pos_integer().
-type used_frequency() :: { frequency(), pid() }.
-record(state, {
free = [] :: [frequency()],
allocated = [] :: [used_frequency()],
shutting_down = false :: boolean(),
max_allocations = 3 :: pos_integer()
}).
%% These are the start functions used to create and
%% initialize the server.
start() ->
register(?SERVER, spawn(?MODULE, init, [])).
-spec init() -> ok.
init() ->
State = #state{
free=get_frequencies()
},
loop(State).
% Hard Coded
-spec get_frequencies() -> [frequency()].
get_frequencies() ->
[10, 11, 12, 13, 14, 15].
%% The client Functions
-spec stop() -> ok.
stop() ->
call(stop).
-spec allocate() -> {error, atom()} | pos_integer().
allocate() ->
call(allocate).
-spec deallocate(frequency()) -> ok.
deallocate(Freq) ->
call({deallocate, Freq}).
-spec deallocate_all() -> ok.
deallocate_all() ->
call(deallocate_all).
%% We hide all message passing and the message
%% protocol in a functional interface
call(Message) ->
?SERVER ! {request, self(), Message},
receive
{reply, Reply} ->
Reply
end.
%% The Main Loop
-spec loop(#state{}) -> ok.
%% [bgh] if we are shutting down, and have no outstanding frequencies, end
loop(#state{shutting_down=true, allocated=[]}) ->
ok;
loop(#state{shutting_down=ShuttingDown}=State) ->
receive
{request, Pid, allocate} when false==ShuttingDown ->
{UpdatedState, Reply} = allocate(State, Pid),
reply(Pid, Reply),
loop(UpdatedState);
{request, Pid, stop} when false==ShuttingDown ->
reply(Pid, ok),
loop(State#state{shutting_down=true});
{request, Pid, {deallocate, Freq}} ->
UpdatedState = deallocate(State, Pid, Freq),
reply(Pid, ok),
loop(UpdatedState);
{request, Pid, deallocate_all} ->
UpdatedState = deallocate_all(State, Pid),
reply(Pid, ok),
loop(UpdatedState);
{request, Pid, _} when true == ShuttingDown ->
reply(Pid, {error, shutting_down}),
loop(State)
end.
reply(Pid, Reply) ->
Pid ! {reply, Reply}.
%% The Internal Help Functions used to allocate and
%% deallocate frequencies.
-spec allocate(#state{free::[]}, pid()) ->
{#state{}, {error, no_frequency}};
(#state{free::[frequency(),...]}, pid()) ->
{#state{}, {error, max_allocations}} |
{#state{}, {ok, frequency()}}.
allocate(#state{free=[]}=State, _Pid) ->
{State, {error, no_frequency}};
allocate(#state{free=[Freq|Free], allocated=Allocated}=State, Pid) ->
case can_allocate(Allocated, Pid, State#state.max_allocations) of
false ->
{State, {error, max_allocations}};
true ->
{State#state{free=Free, allocated=[{Freq, Pid}|Allocated]}, {ok, Freq}}
end.
-spec deallocate(#state{}, pid(), frequency()) -> #state{}.
deallocate(#state{free=Free, allocated=Allocated}=State, Pid, Freq) ->
case lists:keytake(Freq, 1, Allocated) of
false ->
State;
{value, {Freq, Pid}, NewAllocated} ->
State#state{free=[Freq|Free], allocated=NewAllocated};
{value, {Freq, _WrongPid}, _NewAllocated} ->
State
end.
-spec pid_match(used_frequency(), pid()) -> boolean().
pid_match({_Freq, Pid}, Pid) -> true;
pid_match({_Freq, _OtherPid}, _Pid) -> false.
-spec deallocate_all(#state{}, pid()) -> #state{}.
deallocate_all(#state{free=Free, allocated=Allocated}=State, Pid) ->
{ToDeallocate, UpdatedAllocated} = lists:partition(fun(Elem) -> pid_match(Elem, Pid) end, Allocated),
{ReleasedFreqs, _Pids} = lists:unzip(ToDeallocate),
UpdatedFree = ReleasedFreqs ++ Free,
State#state{free=UpdatedFree, allocated=UpdatedAllocated}.
-spec can_allocate([used_frequency()], pid(), pos_integer()) -> boolean().
can_allocate(Allocated, Pid, MaxFrequencies) ->
{PidFrequencies, _Other} = lists:partition(fun(Elem) -> pid_match(Elem, Pid) end, Allocated),
length(PidFrequencies) < MaxFrequencies.
Erlang Programming Exercise: 5-1
It took a while before reading chapter 5 again. I've been off trying to cobble together an Erlang replacement for some of the proxies at work. It's almost ready, it just needs to log the health stats.
When I was reading through the "Programming Erlang" book by Joe Armstrong I ended up doing an exercise very much like Exercise 3-4, but I made a mistake and implemented it as a server, like this exercise. It's fun to compare my styles. In the last version I had a large case statement for the different actions I wanted to do, and each option called a function of the same action name. I'm understanding the behavior design patterns better now and it results in less code written.
In my implementation (below) I used the lists module as much as I could, the one exception being the match function. I couldn't find a lists function that would work. I thought about using lists:filter/2, but that would result in more code because I'd have to write the predicate function and then pull the keys out of the resulting list of tuples.
Since my last post I've also watched all of the Erlang in Practice videos by Kevin Smith. I liked his use of ?SERVER versus ?MODULE when spawning processes and sending messages. He has 5 hours worth of video in 8 screencasts. I highly recommend them to other Erlang noobs out there.
Most of the exercise was straight forward. I had to look up in the man pages the lists, spawn/3 and register/2 function calls. The part that I had the biggest problem with was the spawn call interacting with the init call. I didn't realize that if I wanted to pass an empty array to the init call I had to put it inside the arguments array like so: [[]]. My first attempt was without the inner array and it would crash at runtime. It makes sense now. It is an array of arguments. If you give it an empty array, then there are no arguments and it will look for init/0 instead of init/1.
And the implementation:
-module(my_db).
-export([start/0, stop/0, write/2, delete/1, read/1, match/1]).
-export([init/1, terminate/1]).
-define(SERVER, ?MODULE).
%% [bgh] PUBLIC INTERFACE
start() ->
register(?SERVER, spawn(my_db, init, [[]])),
ok.
stop() ->
?SERVER ! {stop, self()},
receive
{reply, Reply} ->
Reply
end.
write(Key, Element) ->
call(?SERVER, {write, Key, Element}).
delete(Key) ->
call(?SERVER, {delete, Key}).
read(Key) ->
call(?SERVER, {read, Key}).
match(Element) ->
call(?SERVER, {match, Element}).
%% [bgh] start/stop interface
init(Args) ->
loop(Args).
terminate(State) ->
State.
%% [bgh] server handler functions
handle_msg({write, Key, Element}, Db) ->
{ok, lists:keystore(Key, 1, Db, {Key, Element})};
handle_msg({delete, Key}, Db) ->
{ok, lists:keydelete(Key, 1, Db)};
handle_msg({read, Key}, Db) ->
case lists:keyfind(Key, 1, Db) of
false ->
{{error, instance}, Db};
{Key, Value} ->
{{ok, Value}, Db}
end;
handle_msg({match, Value}, Db) ->
{match(Value, Db), Db}.
match(_Element, [], Keys) ->
Keys;
match(Element, [{Key,Element}|Db], Keys) ->
match(Element, Db, [Key|Keys]);
match(Element, [_H|Db], Keys) ->
match(Element, Db, Keys).
match(Element, Db) ->
match(Element, Db, []).
%% [bgh] copy/pasted from page 135, erlang programming
call(Name, Msg) ->
Name ! {request, self(), Msg},
receive {reply, Reply} -> Reply end.
reply(To, Msg) ->
To ! {reply, Msg}.
loop(State) ->
receive
{request, From, Msg} ->
{Reply, NewState} = handle_msg(Msg, State),
reply(From, Reply),
loop(NewState);
{stop, From} ->
reply(From, terminate(State))
end.
Cheers,
Halzy
Silence
The blog has been a bit quiet. I've been rewriting some of our server software at work in Erlang and it's taken up most of my free time. I'm about done with it, so we should see the posts pick up again soon.
Cheers,
Halzy
Erlang Programming Exercise: 4-2
I've finished with the process ring. I've done this exercise once before when reading "Programming Erlang". Last time I had the processes create each other and set up the connections, this time they were created and linked by the start function. The code is much cleaner this time around.
The basic idea is that you create a number of processes and each process knows the process id of it's neighbor in the ring. When a process receives a message, it should forward it on to it's neighbor. You then send X number of messages into the ring and watch your laptop turn into a skillet.
Please review the code and let me know if you have any suggestions.
-module(four_two).
-export([start/3, test/0]).
-export([process_loop/0, process_loop/1]).
test() ->
FirstPid = start(10,4,"This is a message"),
%% [bgh] after 15 second, kill it automatically
receive
after
15000 ->
stop(FirstPid)
end.
stop(Pid) ->
Pid ! {stop, 0}.
start(M, N, Message) ->
%% [bgh] start N processes
Pids = lists:reverse(lists:foldl(
fun(_Number,PidList) ->
NewPid = spawn(?MODULE, process_loop, []),
[NewPid|PidList]
end,
[],
lists:seq(1, N)
)),
%% [bgh] Shift the one off the front, and put it on the end
NeighborPids = rotate_array(Pids),
%% [bgh] link the N processes together
link_pids(Pids, NeighborPids),
[FirstPid|_OtherPids] = Pids,
%% [bgh] start the message sending by sending M messages to PID
send_messages_to_pid(M, Message, FirstPid),
%% [bgh] start the processes sending messages
FirstPid.
rotate_array([]) ->
[];
rotate_array([First|_]=List) when length(List) =:= 1 ->
[First];
rotate_array([First|Remainder]) ->
io:format("~p ~p~n", [First,Remainder]),
lists:append(Remainder,[First]).
send_messages_to_pid(M, Message, FirstPid) when M > 0 ->
FirstPid ! {message, Message},
send_messages_to_pid(M-1, Message, FirstPid);
send_messages_to_pid(_M, _Message, _FirstPid) ->
ok.
link_pids([], []) ->
ok;
link_pids([Pid|Pids], [NPid|NeighborPids]) ->
Pid ! {link, NPid},
link_pids(Pids, NeighborPids).
process_loop() ->
receive
{link, Pid} ->
process_loop({Pid, 0});
Other ->
io:format("Ignored ~p~n", [Other]),
process_loop()
end.
process_loop({Pid, Count}) ->
receive
{message, Message} ->
Pid ! {message, Message},
process_loop({Pid, Count+1});
{stop, CountSum} ->
Pid ! {stop, Count+CountSum},
io:format("~p is shutting down, saw ~p messages~n", [self(), Count+CountSum]);
Other ->
io:format("Ignored ~p~n", [Other]),
process_loop({Pid, Count})
end.
Cheers,
Halzy
Erlang Programming Exercise: 4-1
I'm glad to be past chapter 3, and that I took the time to go through the exercises. I would highly suggest to anybody learning Erlang to do the same. They helped me learn the syntax of the language and to become much more comfortable in Erlang. I also found the erlang man pages to be very helpful. For example, to get the full documentation for the lists module you type "erl -man lists" in a shell.
Before jumping into the exercises for chapter four I went back and re-read the chapter. It's a nice reminder of how Erlang is different from the languages I use for work. I'm still having trouble trying to grok the activity vs task mentality, it's so different from what I'm used to.
Exercise 4-1 I found to be much easier than 3-10. The goal is to start up a process that prints out messages you send to it, but to have the interaction with that process through a public interface.
Here is the interface you are supposed to maintain:
echo:start() ⇒ ok echo:print(Term) ⇒ ok echo:stop() ⇒ ok
Since I've been naming my modules after the exercise chapter and number I changed 'echo' to four_one. Here is my solution:
-module(four_one).
-export([start/0,print/1,stop/0]).
-export([loop/0]).
start() ->
Pid = spawn(four_one,loop,[]),
register(four_one, Pid),
ok.
print(Term) ->
four_one ! {print, Term},
ok.
stop() ->
four_one ! stop,
ok.
loop() ->
receive
stop -> ok;
{print, Term} ->
io:format("~p~n", [Term]),
loop()
end.
Cheers,
Halzy
Erlang Programming Exercise: 3-10
Exercise 3-10 has you take unstructured text and make filled text, then later, justified text.
Now, it's trivial to justify the text, you could even do it in a single pass, but I wanted to solve both the filled text and the text justification at the same time. To make development faster, I wrote some test stubs (at the bottom of the file) that would load the text from disk, and call the interface functions.
textProcess and justifyText do basically the same thing, with justifyText trying to figure out how many extra spaces to put in each gap. They start out by creating a list of tuples of {Word, WordLength} and then passing that list into makeWordLines/4 which builds lines. At this point, passing the lines into wordLinesToString/2 will solve the filled text part of the problem. To solve the justified text part, the lines are passed into justifyWordLines/2 which will calculate how many extra spaces per gap are needed and call wordLineToString/5 to turn the line into a string.
My implementation suffers from floating point arithmetic problems. Some lines will not get the last space in the last gap because the gap value is 0.999999999999 instead of 1. 
This could be solved in a couple of ways, but I'm ready to move into chapter 4.
Looking at the code now, it's very verbose and can probably be done more succinctly.
-module(threeten).
-export([textProcess/2, justifyText/2, testProcess/1, testJustify/1]).
textProcess(Text, Width) ->
TokenText = tokenizeText(Text),
WordLines = makeWordLines(TokenText, Width, Width, []),
wordLinesToString(WordLines).
justifyText(Text, Width) ->
TokenText = tokenizeText(Text),
WordLines = makeWordLines(TokenText, Width, Width, []),
justifyWordLines(WordLines, Width).
justifyWordLines(WordLines, Width) ->
justifyWordLines(WordLines, Width, []).
justifyWordLines([], _Width, JustifiedLines) ->
lists:flatten(lists:reverse(JustifiedLines));
justifyWordLines([[]|WordLines], Width, JustifiedLines) ->
justifyWordLines(WordLines, Width, JustifiedLines);
justifyWordLines([Line|WordLines], Width, JustifiedLines) ->
SpacesPerGap = case length(WordLines) of
0 -> 0; % the last line isn't justified
_Other -> spacesPerGap(Line, Width)
end,
JustifiedString = lists:reverse(wordLineToString(Line, 0, "", SpacesPerGap, 0)),
justifyWordLines(WordLines, Width, [JustifiedString|JustifiedLines]).
spacesPerGap([], _Width) ->
0;
spacesPerGap(Line, Width) ->
Words = length(Line),
WordLength = lists:foldr(fun({_Word, Length}, Accum) -> Length + Accum end, 0, Line),
ExtraSpaces = Width - WordLength - Words + 1,
Gaps = Words-1,
if
Gaps =< 0 -> 0;
ExtraSpaces =< 0 -> 0;
ExtraSpaces > 0 -> ExtraSpaces / Gaps
end.
wordLinesToString(WordLines) ->
lists:flatten(wordLinesToString(WordLines, [])).
wordLinesToString([], Strings) ->
lists:reverse(Strings);
wordLinesToString([[]|WordLines], String) ->
wordLinesToString(WordLines, String);
wordLinesToString([Line|WordLines], String1) ->
String2 = wordLineToString(Line, 0, String1, 0, 0),
wordLinesToString(WordLines, String2).
wordLineToString([], _WordNumber, String, _SpacesPerGap, _GapLeftover) ->
NewLine = "\n",
[NewLine|String];
wordLineToString([{Word, _Length}|Line], WordNumber, String, SpacesPerGap, _GapLeftover) when WordNumber == 0 ->
wordLineToString(Line, WordNumber+1, [Word|String], SpacesPerGap, SpacesPerGap);
wordLineToString([{Word1, _Length}|Line], WordNumber1, String, SpacesPerGap, GapLeftover1) ->
WordNumber2 = WordNumber1+1, % figure out the current word number
Spaces = erlang:trunc(GapLeftover1) , % drop the decimal places
GapLeftover2 = GapLeftover1 - Spaces + SpacesPerGap, % adjust the remaining leftover
Word2 = [string:copies(" ", Spaces+1)|Word1],
wordLineToString(Line, WordNumber2, [Word2|String], SpacesPerGap, GapLeftover2).
% end case, out of words
makeWordLines([], _Width, _WidthLeft, [LastLine|Lines]) ->
ReversedLastLine = lists:reverse(LastLine),
AllLines = [ReversedLastLine|Lines],
lists:reverse(AllLines);
% if the line is currently empty, and the word length is =< than the length of the line
makeWordLines([{_Word, Length}=Token|Tokens], Width, WidthLeft, [[]|Lines]) when Length =< Width ->
makeWordLines(Tokens, Width, WidthLeft-Length, [[Token]|Lines]);
% line with words, and the word length is =< the length left
makeWordLines([{_Word, Length}=Token|Tokens], Width, WidthLeft, [LastLine|Lines]) when Length < WidthLeft ->
makeWordLines(Tokens, Width, WidthLeft-Length-1, [[Token|LastLine]|Lines]);
% if the line is empty, and the word length is > the width of the line
makeWordLines([{_Word, Length}=Token|Tokens], Width, _WidthLeft, [[]|Lines]) when Length > Width ->
makeWordLines(Tokens, Width, 0, [[Token]|Lines]);
% if there is no more space on the line, reverse the tokens on the last line and push a new one on the stack
makeWordLines(Tokens, Width, _WidthLeft, [LastLine|Lines]) ->
ReversedLastLine = lists:reverse(LastLine),
PreviousLines = [ReversedLastLine|Lines],
makeWordLines(Tokens, Width, Width, [[]|PreviousLines]);
% initial case where we have no existing lines on the stack
makeWordLines(Tokens, Width, WidthLeft, []) ->
makeWordLines(Tokens, Width, WidthLeft, [[]]).
tokenizeText(Text) ->
Tokens = string:tokens(Text, " \t\r\n"),
measureTokens([], Tokens).
measureTokens(Measured, []) ->
lists:reverse(Measured);
measureTokens(Measured, [Token|Tokens]) ->
Length = string:len(Token),
measureTokens([{Token, Length}|Measured], Tokens).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Loading Test Stubs %%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
testProcess(Width) ->
{ok, Text} = readFileText('threeten.text'),
io:format("~s~n", [textProcess(Text, Width)]).
testJustify(Width) ->
{ok, Text} = readFileText('threeten.text'),
io:format("~s~n", [justifyText(Text, Width)]).
readFileText(Filename) ->
case file:open(Filename, read) of
{ok, IoDevice} ->
Words = loadRawTextLines([], IoDevice),
file:close(IoDevice),
{ok, Words};
{error, Reason} -> {error, Reason}
end.
loadRawTextLines(Lines, IoDevice) ->
case file:read_line(IoDevice) of
{ok, Line} -> loadRawTextLines([Line|Lines], IoDevice);
eof -> lists:flatten(lists:reverse(Lines))
end.
Cheers,
Halzy
Erlang Programming Exercise: 3-9
In exercise three-nine you are to read some text into a raw document (list of lines) and then into a document (list of words). With this data you generate an index for the words to which lines they were on:
{ "Erlang", [1,1,2,4,5,6,6,98,100,102,102] }
After you have the word to line index, pretty print the index such that the example above would result in:
"Erlang 1-2,4-6,98,100,102"
I decided to start using more of the library functions in order to become more familiar with them. I used the lists/foldr function more than anything else since it lets you visit every element in a list and maintain an accumulator. It was particularly useful in situations where I didn't want to do any pattern matching on the argument, like when I broke the lines into words. It was not useful when I tried to generate the tuples needed for the pretty printed line numbers, this could have been done using a switch statement but I found the code more elegant using the recursive pattern matching.
Instead of copy/pasting a chunk of text into erl every time I wanted to test it, I made the indexer load a file from disk. I also aligned the line numbers, having them all start on the same column made a big difference visually. Here's an example run:
1> threenine:index("./threenine.erl").
0 70
1 2, 30, 32, 37, 41, 57, 80
2 64
binary 77
bs 71
case 5, 22, 37
cleannumbers 46, 51-60
close 8, 14
concat 87-88
...
updatedlinenumbers 46-47
updatedwordindex 41-42
updatewordindexlinenumbers 17, 44
when 57
Here is the code:
-module(threenine).
-export([index/1]).
index(Filename) ->
case file:open(Filename, read) of
{ok, IoDevice} ->
indexFile(IoDevice),
file:close(IoDevice);
{error, Reason} -> {error, Reason}
end.
indexFile(IoDevice) ->
RawDocument = loadRawDocument([], IoDevice),
file:close(IoDevice),
Document = loadDocument(RawDocument),
WordIndex1 = indexWords(Document),
WordIndex2 = updateWordIndexLineNumbers(WordIndex1),
prettyPrintWordIndex(WordIndex2),
ok.
loadRawDocument(Lines, IoDevice) ->
case file:read_line(IoDevice) of
{ok, Line} -> loadRawDocument([Line|Lines], IoDevice);
eof -> lists:reverse(Lines)
end.
loadDocument(RawDocument) ->
MakeDoc = fun(Line, {LineNo, Document}) ->
Tokens = string:tokens(Line, "\r\n\t {,}->:;[]().|\\=/~\"'+_"),
{LineNo+1, [{LineNo, Tokens}|Document]}
end,
{_LineNumber, Document} = lists:foldl(MakeDoc, {1, []}, RawDocument),
lists:reverse(Document).
indexWordsFun(Word, {LineNo, WordIndex}) ->
LowerWord = string:to_lower(Word),
LineNumbersList = case lists:keyfind(LowerWord, 1, WordIndex) of
{LowerWord, LineNumbers} -> LineNumbers;
false -> []
end,
UpdatedWordIndex = lists:keystore(LowerWord, 1, WordIndex, {LowerWord, [LineNo|LineNumbersList]}),
{LineNo, UpdatedWordIndex}.
updateWordIndexLineNumbers(WordIndex) ->
Update = fun({Word, LineNumbers}, NewWordIndex) ->
UpdatedLineNumbers = cleanNumbers(LineNumbers, []),
[{Word, UpdatedLineNumbers}|NewWordIndex]
end,
lists:foldr(Update, [], WordIndex).
cleanNumbers([], CleanNumbers) ->
CleanNumbers;
cleanNumbers([Number|LineNumbers], []) ->
cleanNumbers(LineNumbers, [{Number, Number}]);
cleanNumbers([Number|LineNumbers], [{_Start, Number}|_Tail]=NewNumbers) ->
cleanNumbers(LineNumbers, NewNumbers);
cleanNumbers([Number|LineNumbers], [{Start, End}|Tail]) when Number == End+1 ->
cleanNumbers(LineNumbers, [{Start, Number}|Tail]);
cleanNumbers([Number|LineNumbers], NewNumbers) ->
cleanNumbers(LineNumbers, [{Number, Number}|NewNumbers]).
indexWords(Document) ->
IndexWords = fun({LineNo, Words}, WordIndex) ->
{LineNo, WordIndex2} = lists:foldr(fun indexWordsFun/2, {LineNo, WordIndex}, Words),
WordIndex2
end,
lists:foldr(IndexWords, [], Document).
makePrintFormat(WordIndex) ->
MaxLength = lists:foldr(fun({Word,_Lines}, Max) -> erlang:max(string:len(Word), Max) end, 0, WordIndex),
io_lib:format("~~-~Bs ~~s~~n", [MaxLength]).
prettyPrintWordIndex(WordIndex) ->
PrintFormat = makePrintFormat(WordIndex),
PrintWord = fun({Word, LineNumbers}, Format) ->
PrettyLineNumbers = makePrettyLineNumbers(LineNumbers),
io:format(list_to_binary(PrintFormat), [Word, PrettyLineNumbers]),
Format
end,
lists:foldr(PrintWord, PrintFormat, lists:reverse(lists:keysort(1,WordIndex))).
getPrettyLineNumbers(Result, []) ->
Result;
getPrettyLineNumbers(Result, [{Number,Number}|LineNumbers]) ->
getPrettyLineNumbers([integer_to_list(Number)|Result], LineNumbers);
getPrettyLineNumbers(Result, [{Start,End}|LineNumbers]) ->
Range1=string:concat(integer_to_list(Start), "-"),
Range2=string:concat(Range1, integer_to_list(End)),
getPrettyLineNumbers([Range2|Result], LineNumbers).
makePrettyLineNumbers(LineNumbers) ->
RangedLineNumbers = getPrettyLineNumbers([], LineNumbers),
string:join(RangedLineNumbers, ", ").
Cheers,
-Halzy
Erlang Programming Exercise: 3-8-4 & 3-8-5
I enjoyed coding up 3-8-4 and 3-8-5. It took just a couple hours to finish the pair. In the first one you implement a compiler for a stack machine, in the second you implement the stack machine. There is a lot to think about. How does a stack machine work? What will you be generating? How do the instructions for (3+4)+5 differ from 3+(4+5)? How will the stack machine differ from the evaluator in 3-8-2?
Starting out I looked up stack machine on Wikipedia and found a link to "0-operand" instruction sets that had enough information for me to get going. I decided to keep all of my instructions one token long for simplicity. I have 'add' and 'sub' which use the first two arguments off of the stack, 'umin' (unary minus) only uses the the first item off of the stack. I don't have a need for a 'pop' instruction and decided that 'push' was the default. As an example, adding 1+2 would look like: [1, 2, add]. The numbers would get pushed onto the stack, and then add would take the first two items off of the stack, add them together and place the results back onto the stack.
I may at a later time go back and change the instruction set to have proper push and pop instructions, but for now, this worked.
-module(threeeightyfour).
-export([compile/1]).
translateInstruction(unary_minus) -> umin;
translateInstruction(minus) -> sub;
translateInstruction(plus) -> add.
compileExpression(Instructions, []) ->
Instructions;
compileExpression(Instructions, [{num, Value}|Expressions]) ->
compileExpression([Value|Instructions], Expressions);
compileExpression(Instructions, [{Operator, Value}|Expressions]) ->
Op = translateInstruction(Operator),
OpInstructions = [Op|Instructions],
ValueExp = [Value|Expressions],
compileExpression(OpInstructions, ValueExp);
compileExpression(Instructions, [{Operator, LHS, RHS}|Expressions]) ->
Op = translateInstruction(Operator),
OpInstructions = [Op|Instructions],
RightExp = [RHS|Expressions],
LeftExp = [LHS|RightExp],
compileExpression(OpInstructions, LeftExp).
compileExpression(Expression) ->
compileExpression([], [Expression]).
compile(Results, []) ->
lists:reverse(Results);
compile(Results, [CurrentExpression|Expressions]) ->
Result = compileExpression(CurrentExpression),
compile([Result|Results], Expressions).
compile(Expressions) ->
compile([], Expressions).
And the stack simulator:
-module(threeeightyfive). -export([simulate/1]). simulator([Value|_Stack], []) -> Value; simulator([Value|Stack], [umin|Instructions]) -> UminValue = -1 * Value, simulator([UminValue|Stack], Instructions); simulator([FirstValue|Stack], [sub|Instructions]) -> [SecondValue|MoreStack] = Stack, simulator([FirstValue - SecondValue|MoreStack], Instructions); simulator([FirstValue|Stack], [add|Instructions]) -> [SecondValue|MoreStack] = Stack, simulator([FirstValue + SecondValue|MoreStack], Instructions); simulator(Stack, [Number|Instructions]) -> simulator([Number|Stack], Instructions). simulator(Instructions) -> simulator([], Instructions). simulate(Results, []) -> lists:reverse(Results); simulate(Results, [Instructions|ArraysOfInstructions]) -> Result = simulator(Instructions), simulate([Result|Results], ArraysOfInstructions). simulate(ArraysOfInstructions) -> simulate([], ArraysOfInstructions).
Cheers,
-Halzy
Erlang Programming Exercise: 3-8-3
This exercise is similar to the last one. But instead of evaluating the expressions, we pretty-print them.
I had trouble trying to figure out the right way to append data to a string. I probably could have used plain old list manipulation, building the strings in reverse as I went along, and then reversing them before they returned, but I opted to try out some functions in the string module.
-module(threeeightythree).
-export([print/1]).
addParens(String) ->
A = string:concat([$(], String),
string:concat(A, [$)]).
prettyPrintDoubleOperator(Op, LHS, RHS) ->
A = string:concat(prettyPrint(LHS), [Op]),
B = string:concat(A, prettyPrint(RHS)),
addParens(B).
prettyPrintSingleOperator(Op, Expression) ->
A = string:concat([Op], prettyPrint(Expression)),
addParens(A).
prettyPrint({plus, LHS, RHS}) ->
prettyPrintDoubleOperator($+, LHS, RHS);
prettyPrint({minus, LHS, RHS}) ->
prettyPrintDoubleOperator($-, LHS, RHS);
prettyPrint({unary_minus, Expression}) ->
prettyPrintSingleOperator($~, Expression);
prettyPrint({num, Number}) ->
[Number + 48].
pretty(Results, []) ->
lists:reverse(Results);
pretty(Results, [Expression|List]) ->
Result = prettyPrint(Expression),
pretty([Result|Results], List).
print(Expressions) ->
pretty([], Expressions).
Here is an example run. This time using unary minus!
1> T83 = threeeightyone:parser("((2+3)+(4+(5+6)))~7~(8+9)").
[{plus,{plus,{num,2},{num,3}},{plus,{num,4},{plus,{num,5},{num,6}}}},
{unary_minus,{num,7}},
{unary_minus,{plus,{num,8},{num,9}}}]
2> threeeightythree:print(T83).
["((2+3)+(4+(5+6)))","(~7)","(~(8+9))"]
You'll notice some extra parenthesis. I could have been more selective with them but decided that for simplicity they would be everywhere. 
Cheers,
Ben
Erlang Programming Exercise: 3-8-2
For exercise 3-8-2 we are to create an evaluator. It should take the output (expressions) from 3-8-1 and returns its value. And to make the code a little bit easier to read, LHS and RHS are the left hand and right hand side of the expressions.
-module(threeeightytwo).
-export([evaluator/1]).
evaluate({plus, LHS, RHS}) ->
evaluate(LHS) + evaluate(RHS);
evaluate({minus, LHS, RHS}) ->
evaluate(LHS) - evaluate(RHS);
evaluate({unary_minus, Expression}) ->
-1 * evaluate(Expression);
evaluate({num, Number}) ->
Number.
eval(Results, []) ->
lists:reverse(Results);
eval(Results, [Expression|List]) ->
Result = evaluate(Expression),
eval([Result|Results], List).
evaluator(Expressions) ->
eval([], Expressions).
As you can see I return an array of results. This is because the return value from my 3-8-1 returns an array of expressions. Here is an example run:
1> T81 = threeeightyone:parser("((2+3)+(4+(5+6)))7(8+9)").
[{plus,{plus,{num,2},{num,3}},{plus,{num,4},{plus,{num,5},{num,6}}}},
{num,7},
{plus,{num,8},{num,9}}]
2> threeeightytwo:evaluator(T81).
[20,7,17]
I have three expressions as the argument to 3-8-1:
- ((2+3)+(4+(5+6)))
- 7
- (8+9)
And there are three values as the result from 3-8-2:
- 20
- 7
- 17
And we double check the results. Looks good!
Cheers,
-Halzy