Thursday, January 10, 2008

Erlang and Tail Recursion Part II - Still Living, Still Dreaming

In a previous post, I described how I experienced tail recursion and tail call optimization first hand. I have learned to accept that the Erlang compiler can detect when recursion can be replaced with iteration, preventing stack growth and eventual overflow (which means "hard crash"). The idea is that developers can stay within the language's functional "state-less" paradigm and let the compiler do the messy work.

I spent some time dissecting a very interesting Erlang example that I found on the web at builder.au. There are a lot of interesting nuggets in this example, requiring a little time with the Erlang reference manuals.

However there was one, seemingly innocuous passage of code, that made me realize that I had a few more lessons to learn regarding Tail (or more commonly, Last) Call Optimization (LCO).

Note that while the code is from builder.au, the comments are mine.



Function searchNode

searchNode(Name, LinkDict) ->
receive
{link, ToName, ToPid} ->
% Tail recursion that will be Last Call Optimized
searchNode(Name, dict:store(ToName, ToPid, LinkDict));
{search, Path} ->
Free = notIn(Name, Path),
if
Free ->
lists:foreach(
fun(X)->
{_, Pid} = X,
Pid ! {search, Path++[Name]}
end,
dict:to_list(LinkDict));
true -> true
end,
% Tail recursion that will be Last Call Optimized
searchNode(Name, LinkDict);
{endPoint} ->
% The {endPoint} message identifies that the node
% 'embodied' by thisfunction is the 'target' of
% the search, requiring different message handling,
% and therefore a separate function 'last'.
% But this is not tail recursion?
last(Name, LinkDict)
end.


Function searchNode is the function that both represents a node in a graph and an Erlang process. Once this function is initially invoked, it awaits a message from another process. Upon receiving and handling a message, it invokes itself 'tail recursively' to continue as part of the program and graph.

Except when it receives the endPoint message. In this case another function is invoked, the last function. Message endPoint is sent during the initial phase of a search, to the node that is the target of the search. In this case the node does not propagate the search but identifies when the search has completed. Essentially the "endPoint" node/process requires different behavior, therefore control is transferred to a different function.

So what happens when the search is complete? Does last return and if so, wouldn't searchNode return - ending the process/node it represents?

Note that while the code is from builder.au, the comments are mine.



Function last

last(Name, LinkDict) ->
receive
{link, ToName, ToPid} ->
% Tail recursion that will be LCO
last(Name, dict:store(ToName, ToPid, LinkDict));
{search, Path} ->
% This is the message of interest for this
% function. This indicates that this node was
% found by the search, displays the results and -
% returns control back to searchNode!
io:format("Found path: ~w~n", [Path++[Name]]),
searchNode(Name, LinkDict);
{endPoint} ->
% Probably just handles the off-chance corner-case
% in which a node is identified as the target for a
% search while in the process of being currently
% searched. This may not work correctly.
searchNode(Name, LinkDict)
end.

Interestingly, when last has achieved its purpose it invokes function searchNode, returning control back to the process/node's primary function.

To my imperative mind this is just wrong

Think about the crazy call stack we are creating that will never unwind, eventually crashing the program. Perhaps this is handled by Last Call Optimization?

Actually the answer was right at my finger-tips, in Concurrent Programming in Erlang Part I (search on LCO).

Essentially LCO handles functions that are mutually recursive as well as the classic 'tail recursion' case.

Some final thoughts.

This example is interesting to me because it shows a situation that requires a node (or some type of entity) be assigned a special status. For example, in imperative languages we may choose to set a flag. In Erlang we wish to remain state-less, it is improper and probably very difficult to set a flag. So instead, we request a different behaviour, which is exactly what we wanted in the first place.

Tuesday, January 08, 2008

Thinking in Erlang - Coding in Everything Else

With apologies to Bruce Eckel.

Concurrent Programming in Erlang Part I uses a Binary Tree implementation to demonstrate Erlang's tuple data type.



Erlang

insert(Key, Value, nil) ->
{Key, Value, nil, nil};
insert(Key, Value, {Key,_,Smaller, Bigger}) ->
{Key, Value, Smaller, Bigger};
insert(Key, Value, {Key1,V, Smaller, Bigger}) when Key < Key1 ->
{Key1, V, insert(Key, Value, Smaller), Bigger};
insert(Key, Value, {Key1, V, Smaller, Bigger}) when Key > Key1 ->
{Key1, V, Smaller, insert(Key, Value, Bigger)}.

I was intrigued by this elegant approach to the Binary Tree.

Erlang's tuple data type collects the elements that make up a node including the node's key, value, and the references to its children nodes.

The first clause of the insert function is the "base case" that actually creates a new node. The second clause handles the case when the key is found and the value is simply replaced. Clauses three and four handle the cases that require traversal down through the tree.

Notice how the recursion is so wonderfully encoded. This is much cleaner and intuitive than the imperative solutions that I have worked with.



Python

def insert(key, value, tree):
if tree == None:
return (key, value, None, None)
(key1, v1, smaller, bigger) = tree
if key == key1:
return (key1, value, smaller, bigger)
if key1 > key:
return (key1, v1, insert(key, value, smaller), bigger)
return (key1, v1, smaller, insert(key, value, bigger))

I would guess that this elegant Binary Tree implementation is common to functional programming languages in general. Python has some functional language capability and has a tuple data type. I was able to implement the "elegant" Binary Tree using Python.



JavaScript

function insert(key, value, tree) {
if(tree == null)
return {key:key, value:value, smaller:null, bigger:null};
if(tree.key == key){
tree.value = value;
return tree;
}
else if(key < tree.key)
return {key:tree.key, value:tree.value,
smaller:insert(key, value, tree.smaller),
bigger:tree.bigger};
else
return {key:tree.key, value:tree.value,
smaller:tree.smaller,
bigger:insert(key, value, tree.bigger)};
}

I have read that JavaScript is classified as a functional programming language and its object data type looks syntactically similar to Erlang's tuple. I was able to implement the "elegant" Binary Tree using JavaScript. For more fun, I created an interactive Binary Tree web page.