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.