A Reasonable Solution to Hamming's Problem

/**************************************************************************
 *
 *          A Nearly Complete Solution to Hamming's Problem.
 *
 *   input:  A list of prime numbers in increasing order entered in the
 *           command tail.
 *
 *  output:  A stream of integers, each having at least one of the given
 *           prime numbers as a factor and only prime numbers from the
 *           given list of primes as factors.  The integers are placed in
 *           the output stream in increasing order.
 * 
 *  limits:  Since the stream is infinite and computer resources are bounded,
 *           not all of the stream can be constructed.  However, the code
 *           below makes no attempt at determining when a resource bound is
 *           reached.
 *
 *
 *                 Conceptual Description of the Code.
 *     
 *    Let ham(p) be the stream of integers representing the solution to the
 *    instance of Hamming's problem given by the list of primes p.  Let
 *    hamming(p,T) be the stream ham(p) multiplied by the positive integer T.
 *    Let car(p) be the first element of the list of primes p.  Let cdr(p) be
 *    the list of primes equal to p with car(p) removed. Let + denote stream
 *    concatenation.  Then
 *
 *       hamming(p,T) = 
 *            if (p == NULL) return(NULL);
 *            else
 *            return(car(p)*T + merge(hamming(p,car(p)*T),hamming(cdr(p),T)))
 *
 *
 *                         Implementation Notes
 *
 *    The recursive solution specified above cannot be implemented directly in
 *    C.  One must first build an abstraction and then compose a solution 
 *    based on that abstraction.  The abstract "machine" which we call queue 
 *    simulates the suspension of the computation of stream tails.  This is
 *    accomplished by storing enough state to uniquely define the future of
 *    the computation of the stream from the point of suspension.  The current
 *    implementation of queue is based on maintaining a linear list and is,
 *    therefore, not optimally efficient.
 *
 **********************************************************************/


#include < stdio.h >

#define ADD 1
#define POP 2

long a[1000][4],head = 1,tail = 0;


/**********************************************************************
 *
 *  queue:   X  -> suspends process & stores state-array
 *           X  -> resume process of least "value"
 *                                   (state-array is output)
 *
 **********************************************************************/


long queue(int func, unsigned long q[])
{
   long tptr, i, val_arg, ptr_arg, t_arg;

   val_arg = q[1];
   ptr_arg = q[2];
   t_arg   = q[3];

   if (func == ADD) 
   {
      tptr = ++tail;  
      while (a[tptr-1][1] > val_arg && tptr > head)
      {
         for (i=1; i<=3; i++) a[tptr][i] = a[tptr-1][i];
         tptr -= 1;
      }
      a[tptr][3] = t_arg;
      a[tptr][2] = ptr_arg;
      a[tptr][1] = val_arg;
   }
   else
   if (func == POP)
   {
      q[1] = a[head][1];
      q[2] = a[head][2];
      q[3] = a[head][3];
      head++; 
   }
}

unsigned long ham(unsigned long p[])
{
   unsigned long right[4], left[4], q[4], i;
   int fbreak();

   right[1]=0; right[2]=0; right[3]=0;
   left[1]=0;  left[2]=0;  left[3]=0;

   q[1] = p[1]; q[2] = 1; q[3] = 1;
   queue(ADD,q);

   while (1)
   { 
      queue(POP,q);
      printf("%ld ",q[1]);  if (getchar()==27) exit(0);

      left[1]=q[3]*p[q[2]+1];     right[1]=q[3]*p[q[2]]*p[q[2]];    
      left[2]=q[2]+1;             right[2]=q[2];
      left[3]=q[3];               right[3]=q[3]*p[q[2]];

      queue(ADD ,right);
      if (left[1]>0) queue(ADD ,left);
   }
}

main(int argc, char **argv)
{
   long p[11],i;

   printf("\nprime list:");
   p[argc]=0;
   for (i=1; i < argc; i++)
   {
      p[i] = atoi(argv[i]);
      printf(" %d",p[i]);
   }
   printf("\n\n");

   ham(p); 
}