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.