The Towers of Hanoi

Appearing its title, this section seems to bring nothing new. Indeed, the Towers of Hanoi it an application that is very famous in the field of computer science. It has been implemented many times featuring over a hundred different implementations (in many different languages) by a single author . However, due to its clear definition, the Towers of Hanoi can be excellently used to explain the basic idea behind the Abbey.

First, let us explain what the Towers of Hanoi is about. Given a stack of $n$ disks arranged from largest on the bottom to smallest on top placed on a rod, together with two empty rods, the towers of Hanoi puzzle asks for the minimum number of moves required to move the stack from one rod to another, where moves are allowed only if they place smaller disks on top of larger disks. It is a puzzle invented by E. Lucas in 1883. For nice illustrations of the Towers of Hanoi, we refer to http://mathworld.wolfram.com/TowerofHanoi.

A common approach is to implement the Towers of Hanoi as a simple recursive function. This function is, for instance, specified in the functional programmming language Lisp as follows.

(defun f (m)
        (+ (* 2 m) 1)

(defun moves (n)
        (if (= n 0) 0
        (f (moves (- n 1)))))

(defun hanoi (n src dst aux)
        (if (= n 0) ()
        (append
                (hanoi (- n 1) src aux dst)
                (list src dst)
                (hanoi (- n 1) aux dst src))))

(print (hanoi 10 'a 'c 'b))
Intuitively, the above functional program implements a simple strategy to solve the Towers of Hanoi puzzle. That is, to move all disks from a to c using b as auxiliary peg do the following:

People that are less familiar with Lisp, but have some knowledge of the C programming language will find the following program easier to read. The C program first reserves a buffer that is large enough to hold the complete solution and then call the hanoi function.

#include <stdio.h>

#define N       10

typedef struct {
   char src, dst;
} move_t;

void f(size_t m, size_t *result)
{
   m <<= 1;
   *result = ++m;
}

void moves(size_t n, size_t *result)
{
   if (n--) {
      moves(n,result);
      f(result,&result);
   }
   else {
      *result = 0;
   }
}

void hanoi(size_t n, char src, char dst, char aux, move_t *result)
{
   size_t size;

   if (n--) {
      moves(n, &size);
      hanoi(n, src, aux, dst, result);
      result[size].src = src; result[size].dst = dst;
      hanoi(n, aux, dst, src, result + size + 1);
   }
}

int main()
{
   size_t i, size;

   moves(N,&size);

   move_t buffer[size];

   hanoi(N,'a','c','b',buffer);

   printf("(");
   for (i=0; i<size; ++i) {
      printf("(%c %c) ", buffer[i].src, buffer[i].dst);
   }
   printf(")\n");

   return 0;
}
A standard C compiler translates the above program into so-called assembler instructions which are executed sequentially. This means that the exact order in which all instructions will be executed are known in advance. For many applications, however, it is often sufficient to specify the execution order only partially. Therefore, an Abbey compiler would not set up a fixed execution order. Instead, it creates a partial order of computational tasks where each task is identified by a function calls. Thereby, the different types of tasks are identified by function pointers in C. In the above program, for example, three types of functions are implemented; these functions are referred to by the (function) pointers: main, hanoi, moves and f. When the hanoi program is executed, the function main is called exactly once, which means that exactly one computational task of type main is assiociated with each run of the program. The hanoi function is recursively called many times; it generates many computational tasks which, in principle, can be executed concurrently.

It is up to the concurrency strategy how tasks will be executed concurrently as long as the partial order set up by the Abbey compiler will be respected. Currently, we don't use a ``real'' Abbey compiler yet, but we provide a set of easy-to-use C macros. The three most important macros are the following:

ABY_CALL This macro takes a function pointer and its arguments, and sets up a call to the function associated with this pointer. The macro returns immediately after the call has been set up, but typically before the computational task associated with the pointer has been completed.
ABY_PUT This macro assigns a value to a so-called Abbey variable which in turn can be passed to a computational tasks. This means that all arguments in a function calls are passed to the computational task using Abbey variables. Additionally, Abbey values are used as well to: (i) pass on results of a computational tasks to other computational tasks, and (ii) to temporarily store data for later use.
ABY_GET This macro reads out a value associated with an Abbey variable. The value can be the result of another computational tasks and has been set by the ABY_PUT macro.
To use the above macros, a programmer1 has to know how to rephrase a regular C program into a version that uses the macros to make function calls.

To understand the translation, lets first how have a look at Abbey-interpretable code of the very simple C function f which computes the function $f(x) = 2 x + 1$.

size_t tsk_f(
   aby_monk_t *monk, size_t argc,
   aby_var_t av_input,
   aby_var_t av_output
)
{
   size_t m;

   ABY_VERIFY(argc,2);

   ABY_GET(av_input,m);
   m <<= 1;
   ++m;
   ABY_PUT(av_output,m);

   return argc;
}
Note that the original function f has two arguments. The input data for f is passed by value in the first argument, and the second argument is a pointer to the location where the result must be written. The Abbey cannot handle f if it is written in this way, because all arguments must be passed using so-called Abbey variables. Therefore, the above Abbey implementation of f, named tsk_f, takes two arguments of type aby_var_t. The first two arguments of every computational task have a predefined purpose which is as follows: The reason to send around the number of Abbey variables using the 2nd argument is to be able to recover mismatches with the amount expected when a computational task is invoked (by another computational task).

The first argument to f contains the input, and therefore, the first Abbey variable of tsk_f is a so-called input variable. To reflect this, the variable is called av_input. The second variable is a so-called output variable and is called av_output.

Before the data in an Abbey variable can we used it must first be copied into the memory using the ABY_GET macro. In tsk_f, the value of the Abbey variable av_input is read into the variable m. The result of a computational task in written into one or more output variables using ABY_PUT. Again in tsk_f, the result of computing $2 m + 1$ is stored into the output variable av_output.

A slightly more complex task it the recursive function moves which is written as follows using the Abbey macros.

size_t tsk_moves(
   aby_monk_t *monk, size_t argc, 
   aby_var_t av_n,
   aby_var_t av_result,
   aby_var_t av_aux
)
{
   size_t n;

   ABY_VERIFY(argc,3);

   ABY_GET(av_n,n);
   if (n--) {
      ABY_PUT(av_n,n);
      ABY_CALL(monk,NULL,0,tsk_moves,2,av_n,av_aux);
      ABY_CALL(monk,NULL,0,tsk_f,2,av_aux,av_result);
   }
   else {
      n = 0;
      ABY_PUT(av_result,n);
   }

   return argc;
}
Note that the macro ABY_CALL is used in the implementation of tsk_moves. The macro ABY_CALL takes a variable number of arguments2. The arguments are as follows:
  1. name of the current monk (this must always be monk),
  2. array of to be created Abbey variables (can be NULL),
  3. length of the array of Abbey variables (0 if array is NULL),
  4. function pointer to the task's implementation,
  5. amount of variables to be passed as arguments, excluding the newly created array which is appended to the arguments,
  6. remaining arguments are all Abbey variables (there must be exactly as many variables as specified by argument 5).
If ABY_CALL is invoked with argument 2 set to NULL and argument 3 set to zero then we will speak of a static Abbey call. Otherwise, the call is called dynamic.

A static Abbey call sets up an asynchronous call to the function specified as the fourth argument and passes the amount of Abbey variables to the computational task that is specified by the fifth argument. The Abbey variables themselves are provided in argument six and higher. In the implementation of tsk_moves shown above two Abbey calls are set up:

It is interesting to note that the recursive call in tsk_moves passes only two arguments while actually three arguments are expected. The system will create the third variable on-the-fly and passed it to the newly invoked computational task. In this way, a new variable that functions as a kind of auxiliary variable is created for each recursive call. These auxiliary variables are needed for concurrency reasons. To understand this, suppose that we would have written the two asynchronous calls in the following way without using the auxiliary variable:

ABY_CALL(NULL,0,tsk_moves,2,av_n,av_result);
ABY_CALL(NULL,0,tsk_f,2,av_result,av_result);
The above code is incorrect, because it will result in a deadlock most of the time. The reason for the deadlock is that typically multiple calls to tsk_f will be created that run concurrently. These calls then all want to read from the same Abbey variable which is impossible: only one read can succeed and the others will block. The use of the auxiliary variable prevents this however. To prevent deadlock in general, we have to make sure that every input variable is used exactly once. In more complex tasks, this means that input variables must be ``split'' (this is called teeing) into multiple different variables.

This happens, for example, in the implementation of hanoi below. To split off variables dynamic Abbey calls are needed. In a dynamic Abbey call arguments 2 and 3 are used to append variables to the argument list which are created on-the-fly. The idea is as follows:

are similar, except that in the first statement av_arg2 is created on-the-fly, while in the second statement av_arg2 must have been created already.

To understand the difference between static and dynamic Abbey calls consider the translation of hanoi into Abbey-interpretable code.

size_t tsk_hanoi(
   aby_monk_t *monk, size_t argc,
   aby_var_t av_n,
   aby_var_t av_src,
   aby_var_t av_dst,
   aby_var_t av_aux,
   aby_var_t av_amount,
   ...
)
{
   char src, dst;
   size_t n, size;
   move_t move;
   aby_var_t *av_argv, av_size;
   struct {
      aby_var_t a;
      aby_var_t b;
      aby_var_t c;
   } t_src, t_dst, t_n;
   struct {
      aby_var_t a;
      aby_var_t c;
   } t_aux, t_amount;

   av_argv = &av_amount; av_argv++;

   ABY_CALL(monk,&t_n.a,3,tsk_alloc,1,av_amount);
   ABY_GET(av_amount,n);
   ABY_CALL(monk,&t_amount.a,2,tsk_alloc,1,av_amount);
   ABY_GET(av_amount,n);

   ABY_GET(av_n,n);

   if (n--) {
      ABY_PUT(t_n.b,n);
      ABY_CALL(monk,&av_size,1,tsk_moves,1,t_n.b);
      ABY_GET(av_size,size);

      struct size_st {
         aby_var_t av_argv[size];
      };

      ABY_CALL(monk,&t_src.a,3,tsk_tee,1,av_src);
      ABY_CALL(monk,&t_dst.a,3,tsk_tee,1,av_dst);
      ABY_CALL(monk,&t_aux.a,2,tsk_tee,1,av_aux);
      ABY_PUT(t_n.a,n);
      ABY_CALL(monk,NULL,0,
         tsk_hanoi,5+size,
         t_n.a,t_src.a,t_aux.a,t_dst.a,t_amount.a,
         *((struct size_st *) av_argv)
      );
      ABY_GET(t_src.b,src);
      ABY_GET(t_dst.b,dst);
      move.src = src; move.dst = dst;
      ABY_PUT(av_argv[size],move);
      ABY_PUT(t_n.c,n);
      ABY_CALL(monk,NULL,0,
         tsk_hanoi,5+size,
         t_n.c,t_aux.c,t_dst.c,t_src.c,t_amount.c,
         *((struct size_st *) (av_argv + size + 1))
      );
   }

   return argc;
}
The above implementation of tsk_hanoi contains several dynamic calls to two tasks that are so-called Abbey buildins, i.e., implementations of computational tasks that are provided in the Abbey library. These two buildin tasks are: tsk_alloc and tsk_tee.

The task tsk_alloc is used to create new variables explicitly. That is, the following call initializes a vector of n variables pointed to by av_argv.

ABY_CALL(av_argv,n,tsk_alloc,1,av_amount);
The value of n is assigned to av_amount. This means that after ABY_GET(av_amount,n) returns that variables in the array av_argv can be assumed to be initialized and ready for use.

The task tsk_tee is used to split a variable. The first argument of this computational task is an input variable and the rest are output variables. The computational tasks reads from the input variable and writes it to all output variables.

The implementation tsk_hanoi uses the two buildin function in the following way. First, it creates new variables to contain three copies of the value $n$ to be passed to subtasks later on. Next, it creates two variables for the Abbey variable av_amount, because for each recursive call this variable is required to be newly created. Finally, the input variable av_n is read and decremented, and the recursive calls are setup using sufficient calls to tsk_tee in order to avoid deadlock.

The translation of the function main is similar and looks as follows.

size_t tsk_main(
   aby_monk_t *monk, size_t argc,
   aby_var_t av_src,
   aby_var_t av_dst,
   aby_var_t av_aux,
   aby_var_t av_size,
   aby_var_t av_amount
)
{
   char x;
   size_t i, size;
   move_t move;
   struct {
      aby_var_t a;
      aby_var_t b;
   } t_n;

   ABY_VERIFY(argc,5);

   ABY_CALL(monk,&t_n.a,2,tsk_alloc,1,av_size);
   ABY_GET(av_size,i);
   i = N;
   ABY_PUT(t_n.a,i);
   ABY_PUT(t_n.b,i);

   ABY_CALL(monk,NULL,0,tsk_moves,2,t_n.a,av_size);
   ABY_GET(av_size,size);

   struct {
      aby_var_t v[size];
   } t_result;

   ABY_CALL(monk,(aby_var_t *) &t_result,size,tsk_alloc,1,av_size);
   ABY_GET(av_size,i);

   x = 'a'; ABY_PUT(av_src,x);
   x = 'c'; ABY_PUT(av_dst,x);
   x = 'b'; ABY_PUT(av_aux,x);

   ABY_CALL(monk,NULL,0,
      tsk_hanoi,5+size,
      t_n.b, av_src, av_dst, av_aux, av_amount,
      t_result
   );

   printf("("); fflush(stdout);
   for (i=0; i<size; ++i) {
      ABY_GET(t_result.v[i],move);
      printf("(%c %c) ", move.src, move.dst);
      fflush(stdout);
   }
   printf(")\n");

   return argc;
}
First, we copy the value N into two variables The first variable is used to determine the size of the solution. The second variable is used for calling tsk_hanoi. Next, to setup the call to tsk_hanoi, we create just as many variables as the size of the solution and pass them to the computational task. Finally, the output variables are read and the solution is printed.

Knoppix User 2006-03-15