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

Erlang Programming Exercise: 3-8-1

When I made it to exercise 3-8 my jaw hit the floor. How did we go from using the lists module to writing a parser for arithmetical expressions? This first part of this exercise took me weeks. I worked my way through it after many revisions and scrapping the whole thing two times. Since the instructions are long, I've summed it up:

Write a parser turning expressions like ((2+3)-4) into Erlang representation {minus, {plus, {num, 2}, {num,3}}, {num, 4}}

My first version didn't have a stack and could only parse expressions where it didn't have to remember anything. ((2+3)+4) it could handle, but not (4+(3+2)) because it would have to remember that it was in the middle of parsing the 4+X expression when it had to parse the (3+2) part.

My second version had a stack and could handle parsing expressions like (4+(3+2)) and ((2+3)+4), but it could not handle parsing ((2+3)+(4+(5+6))). It would parse the (2+3) just fine and start into the second half, and could parse it, but I wasn't keeping track of what was left to be parsed, so it became confused at that point and would crash.

Here is my third revision. Note that it doesn't implement the unary minus (~) from the instructions. So far it only supports well formed expressions that use ()+- and single digit numbers.

-module(threeeightyone).
-export([parser/1]).

getNextExpressionUntil(Stack, [Until|String], Until) ->
	{Stack, String};
getNextExpressionUntil(Stack, String, Until) ->
	{Expression, ModifiedStack, StringLeft} = getNextExpression(Stack, String),
	getNextExpressionUntil([Expression|ModifiedStack], StringLeft, Until).

getNextOperator(Op, [PreviousExpression|RemainingStack], String) ->
	{NextExpression, ModifiedStack, RemainingString} = getNextExpression(RemainingStack, String),
	{{Op, PreviousExpression, NextExpression}, ModifiedStack, RemainingString}.

getNextExpression(Stack, [$(|String]) ->
	{Expression, [], RemainingString1} = getNextExpression([], String),
	{[NextExpression|_T], RemainingString2} = getNextExpressionUntil([Expression], RemainingString1, $)),
	{NextExpression, Stack, RemainingString2};

getNextExpression(Stack, [$+|String]) ->
	getNextOperator(plus, Stack, String);
getNextExpression(Stack, [$-|String]) ->
	getNextOperator(minus, Stack, String);

% 0=48 9=57
getNextExpression(Stack, [H|String]) when H >= 48 , H =< 57->
	{{num, H-48}, Stack, String};

getNextExpression(Stack, [H|String]) ->
	{H, Stack, String}.

parseString(Stack, []=_String) ->
	lists:reverse(Stack);
parseString(Stack, String) ->
	{Expression, ModifiedStack, StringLeft} = getNextExpression(Stack, String),
	parseString([Expression|ModifiedStack], StringLeft).

parseString(String) ->
	parseString([], String).

parser(String) ->
	parseString(String).

Something new for me was the use of the dollar sign. It lets you specify a literal character. If you want to look for the letter A, you would write $A. If you wanted a dollar sign, you would write $$.

Cheers,
-Halzy

Erlang Programming Exercise: 3-5 (refactor)

I wasn't happy with how the flatten and concatenate functions turned out. They weren't taking advantage of tail call optimizations, so I rewrote the flatten function for fun. During my rewrite I also wanted to avoid using BIFs to work on my pattern matching. I wasn't sure if I would be able to match the head of a list, that was the head of a list. It worked out, here is the result:

flattenHelper(Dst, []) ->
        Dst;
flattenHelper(Dst, [[[]|HeadTail]|T]) ->
        flattenHelper(Dst, [HeadTail|T]);
flattenHelper(Dst, [[HeadTop|HeadTail]|T]) ->
        NewList1 = [HeadTail|T],
        NewList2 = [HeadTop|NewList1],
        flattenHelper(Dst, NewList2);
flattenHelper(Dst, [[]|T]) ->
        flattenHelper(Dst, T);
flattenHelper(Dst, [H|T]) ->
        flattenHelper([H|Dst], T);
flattenHelper(Dst, Item) ->
        [Item|Dst].

flatten(Lists) ->
        reverse(flattenHelper([], Lists)).

Cheers,
-Halzy

Erlang Programming Exercise: 3-4

In this exercise you are to make a database using this interface:

db:new() ⇒ Db.
db:destroy(Db) ⇒ ok.
db:write(Key, Element, Db) ⇒ NewDb.
db:delete(Key, Db) ⇒ NewDb.
db:read(Key, Db) ⇒{ok, Element} | {error, instance}.
db:match(Element, Db) ⇒ [Key1, ..., KeyN].

This one took a while to get right. In other languages I can look at some code and quickly figure out what it does. When I look at erlang recursive list code, it takes a while to parse it and figure out what it does.

In the read/2 and match/2 functions below, I end up discarding the head item from the list if it doesn't match what I'm looking for. It took a while for me to get used to throwing away data like this. In other languages I would iterated over the list until I found what I was looking for, saving allocation and deallocation cycles. Getting access to the head item in Erlang is very fast so this is a common pattern. This makes me wonder what sort of optimizations the Erlang VM (beam) guys have done to minimize the data copy costs. Anyhow, here is my solution:

-module(threefour_db).
-export([new/0, destroy/1, write/3, delete/2, read/2, match/2]).

new() ->
	[].

destroy(_Db) ->
	ok.

delete(_Key, NewDb, []) ->
	NewDb;
delete(Key, NewDb, [{Key, _Element}|T]) ->
	delete(Key, NewDb, T);
delete(Key, NewDb, [H|T]) ->
	delete(Key, [H|NewDb], T).

delete(Key, Db) ->
	delete(Key, [], Db).

write(Key, Element, Db) ->
	NewDb = delete(Key, Db),
	[{Key, Element}|NewDb].

read(_Key, []) ->
	{error, instance};
read(Key, [{Key,Element}|_T]) ->
	{ok, Element};
read(Key, [_H|T]) ->
	read(Key, T).

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

Cheers,
-Halzy

Erlang Programming Exercise: 3-3

Side Effects is the title of exercise 3-3. Is printing to stdout a side effect? It must be since it makes a permanent change to the system. I just hadn't considered that before.

After the first couple of exercises, this one is a bit easier and gives you a little pat on the back. Enjoy feeling smart for a couple minutes, exercise 3-8 is around the corner.

Here are the two parts for this exercise:

Write a function that prints out the integers between 1 and N.
Write a function that prints out the even integers between 1 and N.

-module(threethree).
-export([print_count/1, print_even_count/1]).

print_number(Number) ->
	io:format("Number:~p~n", [Number]).

print_count(End, End) ->
	print_number(End);
print_count(Current, End) ->
	print_number(Current),
	print_count(Current+1, End).

print_count(Num) when Num > 0 ->
	print_count(1, Num).

print_even_number(Number) when Number rem 2 == 0 ->
	print_number(Number);
print_even_number(_Number) ->
	ok.

print_even_count(End, End) ->
	print_even_number(Current);
print_even_count(Current, End) ->
	print_even_number(Current),
	print_even_count(Current+1, End).

print_even_count(Num) when Num > 0 ->
	print_even_count(1, Num).

I didn't refactor this code until I went to post it. My guards are on the print function, so I re-use the incrementing loop and pass in which print function I want to use:

-module(threethree_ref).
-export([print_count/1, print_even_count/1]).

print_number(Number) ->
	io:format("Number:~p~n", [Number]).

print_even_number(Number) when Number rem 2 == 0 ->
	print_number(Number);
print_even_number(_Number) ->
	ok.

print_count_loop(Print, End, End) ->
	Print(End);
print_count_loop(Print, Current, End) ->
	Print(Current),
	print_count_loop(Print, Current+1, End).

print_count(Num) when Num > 0 ->
	print_count_loop(fun print_number/1, 1, Num).

print_even_count(Num) when Num > 0 ->
	print_count_loop(fun print_even_number/1, 1, Num).

Here it is in action:

2> threethree:print_count(5).
Number:1
Number:2
Number:3
Number:4
Number:5
ok
3> threethree:print_even_count(5).
Number:2
Number:4
ok

Cheers,
-Halzy

Erlang Programming Exercise: 3-2

Exercise 3-2 is also 2 questions:

Write a function that returns a list of the format [1,2,..,N-1,N].

Write a function that returns a list of the format [N, N-1,..,2,1]

I've created 4 functions, create/1, create/2, reverse_create/1, and reverse_create/2. The /1 functions set up the arguments for the /2 worker functions to loop on.

-module(threetwo).
-export([create/1, reverse_create/1]).

create(1, [1|_T]=List) ->
	List;
create(Num, List) ->
	Next = Num-1,
	create(Next, [Next|List]).

create(Num) when Num > 0 ->
	create(Num, [Num]).

reverse_create_list(Num, [Num|_T]=List) ->
	List;
reverse_create_list(Num, [H|_T]=List) ->
	reverse_create_list(Num, [H+1|List]).

reverse_create(Num) when Num > 0 ->
	reverse_create_list(Num, [1]).

An example run:

4> threetwo:create(10).
[1,2,3,4,5,6,7,8,9,10]
5> threetwo:reverse_create(10).
[10,9,8,7,6,5,4,3,2,1]

The key in is to pass your target number along and to build the list from right to left. In each iteration we peak at the head of the list, modify that value and then prepend the result to the head of the full list.

[H|_T]=List

H is the first item in the list.
List is the full List.

Cheers,
Ben

Erlang Programming Exercise: 3-1

I'm posting the exercises starting with chapter 3. The previous chapters have you work in the shell and don't require much file work. Exercise 3-1 is:

Write a function sum/1 which, given a positive integer N, will return the sum of all the integers between 1 and N.

And the second part:

Write a function sum/2 which, given two integers N and M, where N =< M, will return the sum of the interval between N and M. If N > M, you want your process to terminate abnormally.

Here is my solution: threeone.erl

-module(threeone).
-export([sum/1, sum/2]).

sum(1) ->
	1;
sum(Number) ->
	Number + sum(Number - 1).

sum(Lower, Lower) ->
	Lower;
sum(Lower, Upper) when Lower =< Upper ->
	Upper + sum(Lower, Upper-1).

If you give sum/1 a number less than 1, you'll infinite loop.

The above solution doesn't use Erlang's tail call optimizations. If you give them a very large set of numbers to add up, they keep eating up memory. I wanted to see what would happen when it ran out of memory or stack space, so I told it to sum up a billion. After my system started swapping and started to crawl I killed the process. Maybe next time.

Here is the reworked version that takes advantage of tail call optimization and can sum up numbers from 1 to a billion without making my system swap. The beam.smp process stays around 10mb of memory.

-module(threeone_tco).
-export([sum/1, sum/2]).

sum_range(Sum, Lower, Lower) ->
	Sum + Lower;
sum_range(Sum, Lower, Upper) ->
	sum_range(Sum + Upper, Lower, Upper-1).

sum(Number) when Number > 0 ->
	sum_range(0, 1, Number).

sum(Lower, Upper) when Lower =< Upper ->
	sum_range(0, Lower, Upper).

The big change comes from passing the Sum as an argument to the next function call. To use TCO (Tail Call Optimization) you want to leave no work to be done in your function, and the last thing your function does, should be calling itself. Previously, the function would still have to add two numbers after it's recursion finished.

Cheers,
-Halzy