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.

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.

Erlang and the Towers of Hanoi

My brilliant, 15 year-old son is teaching himself how to program Ruby using Chris Pine's wonderful book, Learn to Program. The book devotes an entire chapter to recursion and I spent an enjoyable evening with my son as we dissected an example program. Pine's example is reminiscent of the Towers of Hanoi, a puzzle that my son has been able to solve since he was 7. So I decided to code up this classic, first in Python and then in Erlang.

Towers of Hanoi - Erlang Style



My son could not believe that this function would solve the puzzle! I used a pencil and graph paper to illustrate an example with 4 plates and was once again amazed by the sheer beauty of this algorithm. One can only marvel as too how someone was able to discover this elegant solution.
It was my son who pointed out the "depth first" nature of the algorithm. The program recurses to a depth determined by the number of plates and then retreats back to the top of the stack of function calls, moving plates as it goes. Each retreat up the stack results in another incursion down to the depth determined by the number of plates. This continues until the original call returns and the program completes.

Essentially the process of recursion lays out a data structure of sorts that establishes a sequence of plate moves.

Notice the line in the code above: managerPid ! {self(), A,C}. This line of code is used to move a plate. The movement of the plate is handled by a separate process that represents a device or maybe even a person responsible for moving the plates.


Function manage_towers, in the code illustration above, executes within the second process and writes the tower movements to the console.

I had some philosophical concerns with the multi-process approach to the Towers of Hanoi. Recursion and distributed computing are two distinct and orthogonal solutions that are based on the same idea, the divide and conquer algorithm. However the solution does have some pragmatic appeal to me and it all begins with the immutability of Erlang's variables.
The thought is that the Towers of Hanoi program cannot actually move the plates, the plates would have to be moved by some entity apart from the program. This allows philosophical head room for both immutable variables and asynchronous calls to a process that records the plate movements.

As I watched the console display the plate movements, my mind reeled as I thought of the program descending and ascending through the call stack, briefly pausing to issue asynchronous messages of instruction to its sister process.



The Towers of Hanoi program is initiated by the code illustration shown above.

Notice that when the call to process_towers returns, the tower manager process (managerPid) is sent a message that indicates that the program has finished.

managerPid ! {self(), finished}

The main process (thread) of the program then blocks at the receive statement, awaiting acknowledgment from the tower manager process. Essentially, the main process is deferring termination until the tower manager process completes.

As you can imagine, the process_towers function computes the solution far quicker than the console can update its display. At some point, the main process waits until the tower manager handles its backlog of messages, in the order in which they arrived.

This is accomplished using Erlang's Mail Box, which probably is implemented as a thread-safe queue.

Many of the popular languages provide thread-safe queue classes but Erlang's Mail Box is built-in, readily available and seamless.

But does it work robustly? I can say yes because of my carelessness.

I tested the program with 10 plates and then decided to really test it with 20 plates. I sat there for a second before I realized what I had done. I believe Towers has an exponential growth rate, therefore 10 plates required 1000 plate movements and 20 plates requires a million plate movements.

I let the program run, all day and into the evening. My son saw the program running and asked if I had mistakenly created an infinite loop.

I ran the concept by him, "If we have 4 plates, it takes 16 moves, 5 plates takes 32 moves and 20 plates takes ...". "One million moves", he immediately replied. "But a million is not a big number for a computer", he said.

We could roughly count the number of plate moves being written to the console and determined that approximately 7 moves where displayed per second.
Therefore it would take about two days for the program to run to completion.

I went to sleep that night, thinking about the many thousands of messages queuing-up in the Tower Manager's Mail Box.

I awoke the next morning to find the program dutifully displaying plate movements. I shut the program down - satisfied that Erlang's messaging system met its challenge.

Erlang, Scalability - The Next Wave

I had a great time watching the TV series Surface on the SciFi Channel, with my son who is 10. In the final episode, Marine Biologist Dr. Laura Daugherty warns us that Tsunamis waves come in sets.

The first wave of the Erlang Tsunami was realizing Erlang's ability to harness the potential of multi-core CPU's to perform computations, by using concurrently executing threads and processes.

I had not recovered from the first wave when I was hit by the next wave in the set. The second wave is Erlang's ability to scale. Usually, scalability is used as characteristic of an architecture, system or technology. I don't recall if I have seen scalability used to characterize a programming language. Certainly, most programming languages provide features that can be used to develop scalable systems - but what would it take to make the language inherently scalable?

loop(State) ->
    receive
        {call, From, Request} ->
            {Result, State2} = handle_call(Request, State),
            From ! Result,
            loop(State2);
    end.

Function loop(State) waits at the receive statement for a message that matches tuple {call, From, Request}. When a matching message is received. it is handled by the statement that calls the aptly named function, handle_call. From is messaged with the Result returned by function handle_call.

So, the received message includes information that identifies the operation to perform, the return address, and perhaps some parameters. This operation is "stateless" because the state required to process the request is provided with the request and is not maintained by loop. This is how REST works.

A key-word used in the last couple of paragraphs is "message". Note that the only coupling between sender and receiver in this message passing approach is the "shape" of the data passed (e.g. the tuple {call, From, Request}). This results in a very dynamic, and decoupled approach.

Erlang is highly scalable because its stateless, message-passing approach is suitable for all levels of distributed computing. It matters not if the distribution is among threads in one process or among hosts arrayed around the world. Erlang programmers use the same syntax, patterns and idioms, regardless of the level of distribution.

This is true scalability.

The Tsunami metaphor might have seemed like an over-statement, hopefully I have proved otherwise, but let us consider one final point. The Erlang programmer's skill scales. If a programmer can develop programs using concurrency and Erlang, it matters little if the program runs stand-alone on one box, or is widely distributed across the internet.
Do you feel the wave?

Erlang, Tail Recursion, and Living the Dream

Erlang Eureka! describes a moment of discovery as the narrator walks through a Erlang code example. Function loop is an example of a function that runs within its own thread, awaits messages from other threads, and then acts on received messages. Note that function loop is a loop only in the sense that loop repeats by calling itself.

loop(Module, State) ->
receive
{call, From, Request} ->
 {Result, State2} = Module:handle_call(Request, State),
 From ! {Module, Result},
 loop(Module, State2);
{cast, Request} ->
 State2 = Module:handle_cast(Request, State),
 loop(Module, State2)
end.

Loops, such as for and while loops, are a considered to be iterative. Function loop is a different beast in that it uses recursion to mimic the iterative loop mechanism. Function loop uses a type of recursion that is called "tail recursion". Essentially if a function returns the return value of a recursive call, it is tail recursive.

In languages such as Java, C, C++, C# and Ada (imperative languages), tail recursion is frowned upon because it risks overflowing the stack Tail recursion can be easily replaced with an iterative approach, a process called tail call optimization.

On the other hand, functional languages such as Erlang, Lisp, Scheme, and F# make use of tail recursion as we can see from the code example.

Why?

1. Iteration by recursion is required because variables may be assigned only once in most functional languages, including Erlang. This "assign once" feature is one of the key reasons that Erlang can manage state well in the face of concurrency. Notice how State is updated within loop and stored in State2 which is passed by parameter to the tail recursive call to loop.

2. Functional programming language compilers, such as Erlang, perform tail call optimization. Functional language programmers will actually structure code to achieve tail recursion (pretty different). See A Deeper Look at Tail Recursion.

I also would like to credit Jomo Fisher's Adventures in F# -- Tail Recursion in Three Languages blog .

Its funny how I set off to research this topic. After experimenting with Erlang over a weekend and blogging about it, I went to work on Monday and actually thought about implementing a loop using recursion, for about a microsecond. My fingers stopped so fast that they left skid marks on the keyboard. Could you imagine implementing an application's main loop using recursion and several seconds into operation the stack overflows, the application crashes, and there you sit feeling very dumb?

With a bolt of lightening, a clear perspective of the differences between imperative and functional programming languages lay before me.

It is great when your work is interesting and your work-place is your laboratory - that is why I am Living the Dream.

Erlang Eureka!

State Stinks! Part II discusses that managing the operational control of an application is problematic when the application is multi-threaded. Multi-threaded applications consist of concurrently operating execution paths that share common state and data.

Jeff Moser suggested that I look into the Erlang programming language. One of his blog postings led me to an excellent interview with Joe Armstrong, the principal inventor of Erlang. Joe is an engaging individual and has many interesting things to say. Joe prefers "concurrent orientation" over "object orientation" and he makes a compelling point. Some of my past posts reflect my opinion that strongly favors object orientation. I also ruminated on threads and the odd pairing of concurrency and object orientation. Basically this is the kind of stuff that peaks my interest so I proceeded to download Erlang.

First of all, everything went well, the Erlang web site is well organized and full of resources. Erlang has been around since 1991 and is a very well documented, mature programming language.

I started working my way through the tutorials, looking forward to that "eureka" moment when I would see Erlang's secret sauce. To begin with, Erlang's functional approach with (immutable) variables that can only be bound once, is well chronicled. Other features of the language such as dynamic-typing combined with assignment by pattern-matching makes for a feature-rich, expressive language that you just have to try for yourself.

My eureka moment?

init(Module) ->
   register(Module, self(),
   State = Module:init(),
    loop(Module, State).

loop(Module, State) ->
receive
 {call, From, Request} ->
     {Result, State2} = Module:handle_call(Request, State),
     From ! {Module, Result},
     loop(Module, State2);
 {cast, Request} ->
     State2 = Module:handle_cast(Request, State),
     loop(Module, State2)
end.

Note the function loop(Module, State). Erlang variables are capitalized. loop has two parameters Module and State. I won't discuss Module, think of it as a file containing a group of helper functions.

State is an immutable value containing our application's operational state.
First, the receive statement blocks the thread that loop is executing and awaits a message (from another thread) that contains data that matches one of the two tuples (variables enclosed in curly braces) either {call, From, Request}, or {cast, Request}.

If the message matches {call, From, Request}, the next three lines in the code will execute. First, the Request is delegated to one of the handle_call helper function in Module. Note that the immutable State is passed along. The updated state is returned to variable State2.

Next, the calling thread identified by From is messaged (!) with data {Module, Result}.

Finally, loop is called for its next iteration with the updated state present in the State2 variable.

It is important to note that the above code fragment is not pseudo-code. The code demonstrates sending and receiving messages between threads and how messages are used to share state.

At the top of this post I mentioned that an application's threads share common state. Erlang threads do not directly share common state but must share state as immutable variables passed using messages. Erlang calls threads "processes" because they do not share state.

Eureka! - Erlang's secret sauce isn't very secret, just saucy. State is maintained via very simple and explicit operations that are designed to scale up into large, robust systems. The code fragment did not show any detail about State/State2 and how State was updated (e.g. inside the Module:handle_call function).

Note that Erlang doesn't remove the need to manage state, in fact, state within a Erlang application may be very complex if it uses multiple "processes" to handle computations.

Erlang allows us to use its full toolkit to simply, safely and explicitly work with the data used to maintain the operational state of a software application.