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.

Metrics-Based Software Management - A Hands On Approach

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.

State Stinks! Part II

State Stinks! alright. My previous rant should have sufficed but I haven't succeeded in getting problems with state off of my chest! What could have I forgotten that would require its own posting! I had forgotten to mention the most worrisome of all forms of state - a form of state that I will refer to as uber-state.

To recap my previous post, I tried to illustrate how much of a software developer's life is spent managing and maintaining state. I also pointed out that many of our problems are self-inflicted, we trade a few gray hairs to optimize performance - some times just out of habit. All of these problems are intensified in multi-threaded applications. In short, state maintenance limits what we can accomplish with multi-threaded applications.

Uber-State - What we need is a supreme form of state that lives above normal application-maintained state. Some ancient guy said "give me a long enough pole and a fulcrum out in space and I can move the world" (or something to that effect). What we need is a fulcrum out in space. Easy enough, our application's supreme entity is the operating system. What we need is state that is managed by the OS that we can use as leverage points to assert control of our application. Right? Well this is what we current use to wrangle multi-threaded applications. Operating systems provide objects that we can use to synchronize thread operations and they work as designed.

But even Uber-State Stinks! - I am not trying to be difficult here! Let me explain. Operating System thread synchronization objects are very simple and are typically referred to as "primitives". To really harness the power of multi-threaded applications in a multi-core processor world, I need complete control of the operational state of my application. I don't just need to synchronize threads, I need to orchestrate my application. Uber-State you say (actually I said it) - horsefeathers!



I had mentioned in my previous post that naive OO designs typically ignore an application's operational state, treating state like a second-class citizen.

Using OS thread synchronization primitives has the same effect. Our applications rely on big-brother to adjucate and control access to state - leaving our application's state machine in disarray.

State doesn't have to stink - State needs to be first class citizen in our applications and work the way we would expect!

So where am I going with this? To begin with, let it be known that I do not only mean to prescribe to others with my postings, but I also wish to elicit suggestions. A former colleague, Jeff Moser, suggested that I look into Erlang. I have listened to his suggestion and my findings are fuel for my next posting to be entitled "Erlang Eureka!".

State Stinks!

Sorry, I am not referring to your favorite institution of higher learning (although they may indeed stink). I am referring to the data utilized by the software application that you are responsible for creating and/or maintaining.

Data is not necessarily state - Typically we think of application data as a raw material of sorts. This material must be processed, shifted, sorted, stored, transformed, accessed, and so on.

States of existence - Another form of data is the data used to manage the operation of the software application itself. This is typically the kind of data we associate with "state". In this case, we are talking about states of existence, the dynamic behavior of the application, the software application as a machine.

State as a second-hand citizen - I am referring to Object-Oriented design. You see it all the time, the essence of OO design is the class hierarchy. A team models the application domain into classes and begins to code. The problem - the application's engine is not considered. The code that defines the behavior of an application ends up scattered across event-handling routines, forever a breeding ground for bugs and maintenance head-aches.

State as a Sin - This is a dramatic way of saying that we use state as an optimization. Artificial state is a good term for caches and the like. This type of state is typically misused and comes with a price, we have to maintain this state to ensure that it is fresh. Once again we have stumbled across a breeding ground for problems.

Smart Pointers - Yeah right! I know what Scott Meyers says, "use smart pointers". I have used smart pointers for years. My question is why do I need to use smart pointers in a properly designed C++ application? Why not ensure that a C++ class wraps all dynamic memory concerns to begin with and let the copy constructors, assignment operators, and destructors do their jobs? The only reason I can think of is because of performance concerns. Due to a need to optimize, we now are responsible for managing a computers memory resources, and we do so in way that subverts the intent of C++ auto-scoping classes and destructor semantics. And we call it "smart".

State Maintenance is Like Pounding Sand - Did I mention concurrency?

Multi-Core Processors and Concurrency - The carrot and the stick. We humans can be stubborn. We may not always change for a carrot or a stick, but the carrot and the stick combination can be hard to refuse.
Carrot - Multi-Core processors. Think super computer.
Stick - Each core in the multi-core processor must be driven by its own thread or process.
Carrot + Stick = We must learn how to program computers for multiple concurrent processes/threads.

Stop Pounding Sand - So we need to rethink application development. We will write applications that are not optimized from the perspective of one thread of execution, but will blaze across multi-core processors. We will employ programming technologies that makes state a first class citizen and sinful state a bad memory.

This is all Good - Why? Because State Stinks! State maintenance is boring, tedious, wasteful and problematic.

Grr++ ..

Its been about two years since I've done any serious C++ however my current interests (networking) have led me back to my software development roots.

I have been working through W. Richard Steven's UNIX Network Programming book, coding up the examples on my laptop running Centos Linux. Not only am I becoming more knowledgeable in network programming, I am also stretching my skills into the Unix world - getting some work with gcc, g++, gdb, vim, make, as well as some shell scripting.

Usually when learning from a computer programming book, you have the option to download the example source code, but I think it is beneficial to type in the code. This said, I only want to type in the code once! Essentially I want to create libraries that I can reuse as I work through the book and perhaps I may wind up with stuff that I can reuse in the future.

I enjoy W. Richard Steven's classic UNIX C code, but I am compelled to wrap the C functions in C++ classes, and here I am, back in my old stomping grounds.

Now instead of diligently working through Steven's book, I am writing C++ wrapper classes.

As I remember, this was a common theme during my past self studies. I always wanted to devise some system but I usually spent my time creating libraries and tools. The work on libraries probably bore fruit in my professional life but it seemed like I never wrote that next killer app in my spare time.

Of course I discovered Java, C#, Perl, and Python, all of which featured powerful libraries. C++ began to drift off of the radar.

But now I am back. So now what?
To begin with, I like C++. Experience has shown me that GC and reference-counted memory management schemes are not a free lunch. I have seen horrendous memory leaks in GC systems due to things like circular references.

The ability to create full objects on the stack and then let nature's memory manager do its thing actually seems powerful.

So where does C++ stink?
Smell 1 - Libraries - I want XPath and XML Dom, Regular Expressions, Data Access and Concurrency libraries at my finger tips because I have been spoiled.

Smell 2 - Tight coupling with C. This is both a blessing and a curse. The blessing is that (dare I say) all system API's are written for the C programming language (my examples being Win32 and POSIX). Therefore C++ libraries are easily created to wrap these low-level API's.

I think much of the bad rap C++ got was when it was used as an abstraction layer above C. Take MFC (please take it!) for example, I wonder how many developers swore off C++ after a few years with that crappy framework. I also wonder how many developers learned how to write crappy C++ code after a few years with that framework. Java seemed like a plush, polished gem after MFC.

Also as an aside, the scripting languages did a much (I mean MUCH) better job of abstracting away the C system-level APIs.

So here I am a few years down the road and supposedly wiser, stupidly writing crappy C++ libraries around C code and feeling like I am wasting my time (which I surely am).

So C++ is not necessarily a bad language, but I need library and framework support.

Probably the only downside is that I need to assemble my own toolkit. First of all there is Boost which appears to take STL to the next level. There is ACE which provides an abstraction layer around the system APIs, particularly in the realm of networking and concurrency. And there are other sources of libraries, notably Apache which has C++ versions of its Xerces XML libary.

No worries and maybe I can find some type of library to write along the way (old habits die hard)!