Friday, October 27, 2006

Visualizing problems in Erlang

Ever since I started learning Erlang almost 10 months ago, I have always just had this deep down unexplainable gut feeling that Erlang is neat. Erlang just feels so right. The flow from idea to implementation in Erlang is so smooth, sometimes I second guess myself, "can it really be this easy?!"

Last night I couldn't sleep, so naturally I stayed in bed thinking about Erlang, and I think I might have figured out why Erlang is so nice: visualization.

Let's just take an example. Let's say I tell you to write Quick Sort in C.

The first thing you would probably do is look up the algorithm which is:

function quicksort(q)
var list less, pivotList, greater
if length(q) = 1
return q
select a pivot value pivot from q
for each x in q except the pivot element
if x < pivot then add x to less
if x = pivot then add x to greater
add pivot to pivotList
return concatenate(quicksort(less), pivotList, quicksort(greater))

To code the algorithm, you need to start thinking about the implementation details, such as how you will manage the pivot list, what type of values will your quick sort support, etc. It is very difficult to go from the algorithm directly to C, there are too many C things to worry about first.

void quickSort(int numbers[], int array_size)
q_sort(numbers, 0, array_size - 1);
void q_sort(int numbers[], int left, int right)
int pivot, l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = numbers[left];
while (left < right)
while ((numbers[right] >= pivot) && (left < right))
if (left != right)
numbers[left] = numbers[right];
while ((numbers[left] <= pivot) && (left < right))
if (left != right)
numbers[right] = numbers[left];
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(numbers, left, pivot-1);
if (right > pivot)
q_sort(numbers, pivot+1, right);

Now let's say I tell you to think about writing a Merge Sort in Erlang. You instantly realize this problem is dead easy using a list a few recursion calls and Erlang's powerful list operators. There are no memory issues to think about, no type checking to worry about, no extra temporary values to handle, no having to "translate" your programs calls to fit the algorithm. With Erlang you can actually imagine in your head, having a long list of things, doing a few list operations, then using recursion and being done.

sort([Pivot|T]) ->
sort([ X || X <- T, X < Pivot]) ++
[Pivot] ++
sort([ X || X <- T, X >= Pivot]);
sort([]) -> [].

While I admit it takes a functional mindset to get used to seeing things this way, once you do have it, it is an almost instantaneous process of going from algorithm to code. Being able to visualize both the algorithm and the Erlang code together at the same time without much difficulty and implementing them immediately makes programming a lot more enjoyable and fulfilling. Gone are the days of tedious details and mindless translations.


No comments: