Benjamin Halsted // [bgh] todo, add something clever here.

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